2022年RSA算法实验报告 .pdf

《2022年RSA算法实验报告 .pdf》由会员分享，可在线阅读，更多相关《2022年RSA算法实验报告 .pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、RSA 算法的实现实验原理算法原理RSA 公开密钥密码体制。所谓的公开密钥密码体制就是使用不同的加密密钥与解密密钥，是一种“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制。RSA 算法是一种非对称密码算法，所谓非对称，就是指该算法需要一对密钥，使用其中一个加密，则需要用另一个才能解密。RSA 的算法涉及三个参数，n、e1、e2。其中， n 是两个大质数p、q 的积， n 的二进制表示时所占用的位数，就是所谓的密钥长度。e1 和 e2 是一对相关的值，e1 可以任意取，但要求 e1 与(p-1）*(q-1 ）互质； 再选择 e2，要求（e2*e1）mod(p-1）*(q-1 ） ）=1

2、。 （n，e1）,(n，e2）就是密钥对。其中(n，e1）为公钥， (n，e2）为私钥。RSA 加解密的算法完全相同，设 A 为明文， B 为密文，则： A=Be2 mod n ；B=Ae1 mod n ；（公钥加密体制中，一般用公钥加密，私钥解密）e1 和 e2 可以互换使用，即：A=Be1 mod n ；B=Ae2 mod n; 密钥生成首先要使用概率算法来验证随机产生的大的整数是否质数，这样的算法比较快而且可以消除掉大多数非质数。 假如有一个数通过了这个测试的话，那么要使用一个精确的测试来保证它的确是一个质数。密钥分配和其它加密过程一样，对RSA 来说分配公钥的过程是非常重要的。分配公钥

3、的过程必须能够抵挡一个从中取代的攻击。假设Eve 交给 Bob 一个公钥，并使Bob 相信这是Alice 的公钥，并且她可以截下Alice 和 Bob 之间的信息传递，那么她可以将她自己的公钥传给Bob，Bob 以为这是 Alice 的公钥。步骤如下（这里设B 为是实现着）（1）B 寻找出两个大素数p 和 q。（2）B 计算出 n=p*q 和（n） =） （p-1）*（q-1） 。（3）B 选择一个随机数e（ 0e(n)） ,满足（ e,(n)=1 (即 e与欧拉函数互素（n）)。（4）B 使用欧几里得算法计算e 的模余（n）的乘法逆元素d。（5）B 在目录中公开n和 e 作为他的公开密钥，保

4、密p、q 和 d。加密时，对每一明文m 计算密文c me（modn ）解密时，对每一密文c 计算明文m cd（modn ）算法流程图开始输入两个素数p 和 q 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - - - 实验结果截图调用 Prime（）找出 N=(p-1)*(q-1) 的所有公约数输入不等于N 公约数的 e 调用 ExtendEuclid （e，N，&d）开始加密调用Encryption （）输入明文长度len 及明文i l

5、en 调用 multiplication(m1i,e,n)i+ 输出密文开始解密调用Decipher()i=0 i len i+ 调用 multiplication(m1i,e,n)输出明文，结束Y N Y N Y N i=0 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 7 页 - - - - - - - - - 实验源代码#include #include #include typedef int Elemtype; Elemtype p,q,e; Elemtype

6、 fn; Elemtype m,c; int flag=0; typedef void(*Msghandler)(void); struct MsgMap char ch; Msghandler handler; ; /*公钥 */ struct PU Elemtype e; Elemtype n; pu; /*私钥 */ struct PR Elemtype d; Elemtype n; pr; /*判定一个数是否为素数*/ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，

7、共 7 页 - - - - - - - - - bool test_prime(Elemtype m) if(m=1) return false; else if(m=2) return true; else for(int i=2;i0) binn=b%2; n+; b/=2; /*初始化主界面 */ void Init() cout*endl; cout* Welcome to use RSA encoder *endl; cout* 1.setkey *endl; cout* 2.加密*endl; cout* 3.解密*endl; cout* 4.退出*endl; cout*endl;

8、coutpress a key:in2?in1:in2); Elemtype b=(in1in2?in1:in2); in1=a; in2=b; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - /*求最大公约数 */ Elemtype gcd(Elemtype a,Elemtype b) order(a,b); int r; if(b=0) return a; else while(true) r=a%b; a=b; b=r;

9、if(b=0) return a; break; /*用扩展的欧几里得算法求乘法逆元*/ Elemtype extend_euclid(Elemtype m,Elemtype bin) order(m,bin); Elemtype a3,b3,t3; a0=1,a1=0,a2=m; b0=0,b1=1,b2=bin; if(b2=0) return a2=gcd(m,bin); if(b2=1) return b2=gcd(m,bin); while(true) if(b2=1) return b1; break; int q=a2/b2; for(int i=0;i=0;i-) f=(f*f

10、)%n; if(bini=1) f=(f*a)%n; return f; /*产生密钥 */ void produce_key() coutpq; while(!(test_prime(p)&test_prime(q) cout 输入错误，请重新输入!endl; coutpq; ; pr.n=p*q; pu.n=p*q; fn=(p-1)*(q-1); coutfn 为： fnendl; coute; while(gcd(fn,e)!=1) coute 输入错误，请重新输入!endl; coute; pr.d=(extend_euclid(fn,e)+fn)%fn; pu.e=e; flag=

11、1; cout 公钥 (e,n）:pu.e,pu.nendl; cout 私钥 d:pr.dendl; cout 请输入下一步操作序号:endl; /*加密 */ void encrypt() if(flag=0) coutsetkey first:endl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - produce_key(); coutm; c=modular_multiplication(m,pu.e,pu.n);

12、cout 密文 c 为:cendl; cout 请输入下一步操作序号:endl; /*解密 */ void decrypt() if(flag=0) coutsetkey first:endl; produce_key(); coutc; m=modular_multiplication(c,pr.d,pr.n); cout 明文 m 为:mendl; cout 请输入下一步操作序号:endl; /*消息映射 */ MsgMap Messagemap= 1,produce_key, 3,decrypt, 2,encrypt, 4,NULL ; /*主函数，提供循环*/ void main() Init(); char d; while(d=getchar()!=4) int i=0; while(Messagemapi.ch) if(Messagemapi.ch=d) Messagemapi.handler(); break; i+ ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -