RSA算法实验报告

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。（n，e1）,(n，e2）就是密钥对。

2、其中(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来说分配公钥的过程是非常重要的。分配公钥的过程必须能够抵挡一个从中取代的攻击。假设Eve交给Bob一个公钥，并

3、使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作为他的公开密钥，保密p、q和d。加密时，对每一明文m计算密文 cm（modn）解密时，对每一密文c计算明文 mc（modn）算法流程图 开始

4、输入两个素数p和q N调用Prime（）Y 找出N=(p-1)*(q-1)的所有公约数输入不等于N公约数的e输入明文长度len及明文i=0调用ExtendEuclid（e，N，&d）Ni len开始加密调用Encryption（）Y调用multiplication(m1i,e,n)i+输出密文i=0Ni len开始解密调用Decipher()Y调用multiplication(m1i,e,n)i+输出明文，结束实验结果截图实验源代码#include#include#includetypedef int Elemtype;Elemtype p,q,e;Elemtype fn;Elemtype m

5、,c;int flag=0;typedef void(*Msghandler)(void);struct MsgMapchar ch;Msghandler handler;/*公钥*/struct PUElemtype e;Elemtype n;pu;/*私钥*/struct PRElemtype d;Elemtype n;pr;/*判定一个数是否为素数*/bool test_prime(Elemtype m)if(m=1)return false;else if(m=2)return true;elsefor(int i=2;i0)binn=b%2;n+;b/=2;/*初始化主界面*/voi

6、d 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;coutpress a key:in2?in1:in2);Elemtype b=(in1in2?in1:in2);in1=a;in2=b;/*求最大公约数*/Elemtype gcd(Elemtype a,Elemtype b)order(a,b);int r;if(b=0)return a;elsewhile(true

7、)r=a%b;a=b;b=r;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)%n;

8、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=1;cout公钥(e,n）:pu.e,pu.nendl;cou

9、t私钥d:pr.dendl;cout请输入下一步操作序号:endl;/*加密*/void encrypt()if(flag=0)coutsetkey first:endl;produce_key();coutm;c=modular_multiplication(m,pu.e,pu.n);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