RSA算法实验C++.doc

1、 实验目的通过编程实现RSA的加密和解密过程，加深对公钥（非对称）密码算法的认识。 2、 实验环境软件工具：Visual C+ 6.0操作系统:windows xp3、 实验思想公钥密码算法是指一个加密系统的加密密钥和解密密钥是不同的，或者说不能用其中一个推导出另一个。在公钥密码算法的两个密钥中，一个是用于加密的密钥，它是可以公开的，称为公钥；另一个是用于解密的密钥，是保密的，称为私钥。公钥密码算法解决了对称密码体制中密钥管理的难题，并提供了对信息发送人的身份进行验证的手段，是现代密码学最重要的发明。 RSA密码体制是目前为止最成功的公钥密码算法，虽然它的安全性还未能得到理论证明，但经过20多年的密码分析和攻击，迄今仍然被实践证明是安全的。 RSA算法描述如下： 1公钥 选择两个互异的大素数p和q, n是二者的乘积，即n二pq使D(n)=(p-1)(q-1), D(n)为欧拉函数。随机选取正整数e,使其满足gcd(e, (D(n)=1，即e和D (n)互质，则将(n,e)作为公钥。 2.私钥 求出正数d,使其满足e d=1 mod D (n),则将(p,q,d)作为私钥。 3.加密算法 对于明文M,由C=Me mod n，得到密文C。 4.解密算法 对于密文C,由M=Cd mod n,得到明文M如果窃密者获得了n, e和密文C,为了破解密文必须计算出私钥d，为此需要先分解n为了提高破解难度，达到更高的安全性，一般商业应用要求n的长度不小于1024位，更重要的场合不小于2048位。4、 实验数据（源程序）#define MAX 100 /数组的最大长度#define MARK (0-1)char* Addition(char a,char b);/实现加法char* Substraction(char a,char b);/实现减法，若abchar* Mode(char a,char b,char c);/实现取余运算(ab) mod cvoid djs(char s);/生成大奇数sint Rabin_Miller_Test(char s);/素数检验算法生成100位的奇数void djs(char s)/生成大奇数sint i,j;srand(time(NULL); /修改随机数种子j=rand()%10;while(j=0)j=rand()%10;s0=j+0; /最高位不为0保证产生的随机数有MAX位while(fmod(j,2)=0)j=rand()%10;sMAX-1=j+0; /最低位为奇数保证产生的随机数为奇数for(i=1;i=0)djs(a);j=0;strcpy(c,Mode(a,b,s);if(Compare(c,1)=0 | Compare(c,e)=0)return 1;loop:if(j0 & Compare(c,1)=0)return 0;j+;if(ji & Compare(c,e)!=0)strcpy(c,Mode(c,2,s);goto loop;if(Compare(c,e)=0)return 1;if(j=i & Compare(c,e)!=0)return 0;ab mod c的快速算法char* Mode(char a,char b,char c)/实现取余运算(ab) mod cchar a1MAX,b1MAX,c1MAX,d2*MAX,e2*MAX;int i;strcpy(a1,a);strcpy(b1,b);strcpy(c1,1);while(Compare(b1,0)!=0)if(fmod(b1strlen(b1)-1-0,2)=0)/b能够被2整除strcpy(b1,Division(b1,2);strcpy(d,Multiplication(a1,a1);if(Compare(d,c)0)strcpy(a1,d);else strcpy(e,Division(d,c); strcpy(e,Multiplication(e,c);strcpy(d,Substraction1(d,e); for(i=0;istrlen(d);i+) a1i=di; a1i=0;else/b不能够被2整除strcpy(b1,Substraction(b1,1);strcpy(d,Multiplication(c1,a1);if(Compare(d,c)0)strcpy(c1,d);else strcpy(e,Division(d,c); strcpy(e,Multiplication(e,c); strcpy(d,Substraction1(d,e); for(i=0;istrlen(d);i+) c1i=di; c1i=0;re