公钥密码学,RSA算法
2021/5/6 14:55:29
本文主要是介绍公钥密码学,RSA算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
公钥密码学
1976年Diffie和Hellman针对上面的问题提出了单向函数加密方法,这种方法和之前数千年来密码学中的所有方法有根本的区别,即公钥密码体制。
非对称加密算法使用完全不同但又是完全匹配的一对钥匙: 公钥和私钥 公钥:公开的,任何人都知道
私钥:只有自己知道
算法:一对密钥中用公钥加密的结果可以用私钥解密,反过来用私钥加密的结果也可以用公钥解密。
公钥加密的使用方式
Alice和Bob互发(公布)各自的公钥,私钥只有自己知道
Alice用对称密钥加密信件,再用Bob的公钥加密对称密
Bob用自己的私钥解密对称密钥,再用对称密钥解密信
公钥密码学与对称密码学比较
对称密码学基于替换和置换(混淆和扩散),运算速度快
公钥密码学基于数学理论(单向函数),运算速度慢
对称密码学使用单密钥,需要额外秘密信道协商密钥
公钥密码学使用两个独立的密钥,不需要秘密信道协商密钥
RSA算法
RSA算法1977年由MIT三位密码学家Rivest - Shamirh和Adleman发明,是迄今为止最为成熟完善的公钥密码体制。
RSA算法能够抵抗到目前为止已知的绝大多数密码攻击,已被ISo推荐为公钥数据加密标准。
RSA原理
公钥和私钥的产生
任意选择两个大的质数(素数)p和q,p不等于q,计算N=pq
根据欧拉函数,不大于N且与N互质的整数个数为(p-1)(q-1)
选择一个整数e 与(p-1)(q-1)互质,并且e小于(p-1)(q-1)
用以下这个公式计算d: dxe = 1(mod(p-1)(q-1))
将p和q销毁后,(N,e)是公钥, (N,d)是私钥
加密消息
假设Bob想给Alice送一个消息,他知道Alice产生的公钥N和e
将原始信息分为多段,每一段(假定为n)分别用以下公式计算出c : n^e= c (mod N)
将多个n计算出的多个c串在一起,就是密文,发送即可。
解密消息
Alice得到Bob的消息c后就可以利用她的密钥( N,d)来解码。她可以用以下这个公式来将c转换为n : c=n (mod N)
得到n后,她可以将原来的信息m重新复原。
RSA应用
加密少量数据
比起DES和其它对称算法来说, RSA的运算速度要慢得多。
实际使用时,RSA算法不用来加密消息,而是用来加密传输密钥,加密消息用对称算法,如 DES 。
实现数字签名
将RSA 算法反向使用(私钥加密公钥解密),对消息摘要加密,可以实现数字签名的功能。
数字签名可以防止数据篡改﹑数据抵赖和数据伪造发生。
RSA算法源码
#include<stdio.h> #include<string.h> #include<math.h> #include<stdlib.h> #include<algorithm> using namespace std; int prime[1305];//存放素数 int p[10005];//用筛选法求素数 void PRIME(){ int i,i2,k; for(i=0;i<=10000;i+=2) p[i]=0; for(i=1;i<=10000;i+=2) p[i]=1; p[2]=1;p[1]=0; for(i=3;i<=100;i+=2){ if(p[i]==1){ i2=i+i; k=i2+i; while(k<=10000){ p[k]=0; k+=i2; } } } prime[0]=1; prime[1]=2; for(i=3;i<=10000;i+=2) if(p[i]) prime[++prime[0]]=i; } // 计算逆元素 __int64 mod(__int64 a,__int64 n){ return (a%n+n)%n; } void gcd(__int64 a,__int64 b,__int64 &d,__int64 &x,__int64 &y){ if(b==0) { d=a; x=1; y=0; return; } gcd(b,a%b,d,y,x); y-=x*(a/b); } //a-1 mod n __int64 Inv(__int64 a,__int64 n){ // 计算逆元素 __int64 d,x,y; gcd(a,n,d,x,y); if(d==1) return mod(x,n); else return -1; } //求两个数的最大公约数 __int64 GCD(__int64 n,__int64 m){ __int64 t,r; if(n<m){ t=n; n=m; m=t; } while((r=n%m)!=0){ n=m; m=r; } return m; } //x=a^b(mod n) __int64 ModPow(__int64 a,__int64 b,__int64 n){ __int64 d=1,i=0; while(b>=(1<<i)) i++; for(--i;i>=0;--i){ d=d*d%n; if(b&(1<<i)) d=d*a%n; } return d; } int main(){ __int64 i,e,d,n,st,ed,eula; __int64 m,c,ans; PRIME(); printf("素数的个数:%d\n",prime[0]); printf("选择两个不同的素数(输入编号,空格隔开):\n");//47和71分别是第15个和20个 while(scanf("%I64d%I64d",&st,&ed)!=EOF){ printf("你选择的两个素数分别是:%d和%d\n",prime[st],prime[ed]); n=prime[st]*prime[ed]; printf("计算得到N是%I64d\n",n); //N的Eula数 eula=(prime[st]-1)*(prime[ed]-1); //找一个与eula互质的数 for(i=2;i<eula;i++) if(GCD(eula,i)==1){ e=i; break; } //e=79; //上面找到了公开密钥n--e d=Inv(e,eula); //上面找到了私密钥n--d printf("生成公钥:(%I64d %I64d)\n",e,n); //输出密钥 printf("生成私钥:(%I64d %I64d)\n",d,n); //切忌加密的数要比n小 printf("请输入要加密的数(<N)\n"); scanf("%I64d",&m); c=ModPow(m,e,n); printf("通过计算%I64d^%I64d(mod %I64d)得到密文=%I64d\n",m,e,n,c); ans=ModPow(c,d,n); printf("通过计算%I64d^%I64d(mod %I64d)得到明文=%I64d\n",c,d,n,ans); printf("素数的个数:%d\n",prime[0]); printf("选择两个不同的素数(输入编号,空格隔开):\n");//47和71分别是第15个和20个 } return 0; }
这篇关于公钥密码学,RSA算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性
- 2024-05-29哪些无用敏捷指标正在破坏敏捷转型?
- 2024-05-29鸿蒙原生应用再新丁!新华社 入局鸿蒙
- 2024-05-29设计模式 之 迭代器模式(Iterator)