RSA算法实验报告(共8页).doc
精选优质文档-倾情为你奉上 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）就是密钥对。其中(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一个公钥，并使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（0<e<(n)）,满足（e,(n)=1 (即e与欧拉函数互素（n）)。（4） B使用欧几里得算法计算e的模余（n）的乘法逆元素d。（5） B在目录中公开n和e作为他的公开密钥，保密p、q和d。加密时，对每一明文m计算密文 cm（modn）解密时，对每一密文c计算明文 mc（modn）算法流程图 开始输入两个素数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<iostream.h>#include<math.h>#include<stdio.h>typedef int Elemtype;Elemtype p,q,e;Elemtype fn;Elemtype m,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;i<=sqrt(m);i+)if(m%i)=0)return false;break;return true;/*将十进制数据转化为二进制数组*/void switch_to_bit(Elemtype b,Elemtype bin32)int n=0;while(b>0)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;cout<<"press a key:"<<endl;/*将两个数排序，大的在前面*/void order(Elemtype &in1,Elemtype &in2)Elemtype a=(in1>in2?in1:in2);Elemtype b=(in1<in2?in1:in2);in1=a;in2=b;/*求最大公约数*/Elemtype gcd(Elemtype a,Elemtype b)order(a,b);int r;if(b=0)return a;elsewhile(true)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<3;i+)ti=ai-q*bi;ai=bi;bi=ti;/*快速模幂算法*/Elemtype modular_multiplication(Elemtype a,Elemtype b,Elemtype n)Elemtype f=1;Elemtype bin32;switch_to_bit(b,bin);for(int i=31;i>=0;i-)f=(f*f)%n;if(bini=1)f=(f*a)%n;return f;/*产生密钥*/void produce_key()cout<<"输入素数 p 和 q:"cin>>p>>q;while(!(test_prime(p)&&test_prime(q)cout<<"输入错误，请重新输入!"<<endl;cout<<"输入素数 p 和 q:"cin>>p>>q;pr.n=p*q;pu.n=p*q;fn=(p-1)*(q-1);cout<<"fn为："<<fn<<endl;cout<<"输入随机数e:"cin>>e;while(gcd(fn,e)!=1)cout<<"e输入错误，请重新输入!"<<endl;cout<<"输入随机数e:"cin>>e;pr.d=(extend_euclid(fn,e)+fn)%fn;pu.e=e;flag=1;cout<<"公钥(e,n）:"<<pu.e<<","<<pu.n<<endl;cout<<"私钥d:"<<pr.d<<endl;cout<<"请输入下一步操作序号:"<<endl;/*加密*/void encrypt()if(flag=0)cout<<"setkey first:"<<endl;produce_key();cout<<"输入明文 m:"cin>>m;c=modular_multiplication(m,pu.e,pu.n);cout<<"密文c 为:"<<c<<endl;cout<<"请输入下一步操作序号:"<<endl;/*解密*/void decrypt()if(flag=0)cout<<"setkey first:"<<endl;produce_key();cout<<"输入密文 c:"cin>>c;m=modular_multiplication(c,pr.d,pr.n);cout<<"明文m 为:"<<m<<endl;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+;专心-专注-专业
