非对称加密-解密算法RSA的C--实现

信息安全技术实验报告———非对称加密、解密算法RSA的C++实现计算机学院2008级12班学号：53081224姓名：胡守峰Page2of8非对称加密、解密算法RSA的C++实现【我的目的】根据课上老师所讲“非对称加密、解密算法RSA”的有关知识，编写其的C++语言实现。【我的加密思想】第一步，用户首先输入两个素数p和q，并求出n=p*q，然后再求出n的欧拉函数值phi。第二步，在[e，phi]中选出一个与phi互素的整数e，并根据e*d≡1（modphi），求出e的乘法逆元。至此我们已经得到了公开密钥{e，n}和秘密密钥{d，n}。第三步，让用户输入要进行加密的小于n一组正整数（个数不超过MAXLENGTH=500），输入以-1为结束标志，实际个数存入size中，正整数以clear[MAXLENGTH]保存。第四步，对第三步所得的明文clear[MAXLENGTH]进行加密。遍历clear[size]，对每一个整数用以下算法进行加密,并将加密后的密文保存在Ciphertext[MAXLENGTH]中。注意：此处不能用m2[j]=clear[j]^e整数的幂，因为当e和clear[j]较大时，会发生溢出，至使出现无法预料的结果。第五步，输出加密后的密文。【我的解密思想】第一步，根据在以上算法中求出的解密密钥[d,phi],对加密后的密文Ciphertext[MAXLENGTH]进行解密，结果保存在DecryptionText[MAXLENGTH]中，算法如下：第二步，输出对加密前的明文和加密并解密后的密文进行比较，判断两个数组是否一致，从而得知算法是否正确。【我的实验】1、RSA加密、解密算法的C++实现(可以在VC6.0上运行)：Page3of8#includeiostream#includecmathusingnamespacestd;#defineMAXLENGTH500//明文最大长度，即所允许最大整数个数intsize=0;//保存要进行加密的正整数的个数intp,q;//两个大素数intn,phi;//n=p*q，phi=(p-1)*(q-1)是n的欧拉函数值inte;//{e,n}为公开密钥intd;//{d,n}为秘密密钥intclear[MAXLENGTH],Ciphertext[MAXLENGTH];//分别用于存放加//密前的明//文和加密后的密文intDecryptionText[MAXLENGTH];//存放解密后的明文//////////////////////////////////////////////////////////////以下为加密算法voidEncryption(){//加密算法cout请输入两个较大的素数：;cinpq;coutp=p,q=qendl;n=p*q;//求解n，phi=(p-1)*(q-1);//求解n的欧拉函数值coutn=n,phi=phiendl;cout请从[0，phi-1]中选择一个与phi互素的数e：;cine;floatd0;for(inti=1;;i++){///求解乘法逆元e*d≡1(modphi)d0=(float)(phi*i+1)/e;if(d0-(int)d0==0)break;}d=(int)d0;coutendl;coute=e,d=dendl;cout公开密钥Pk={e,n}={e,n}endl;cout秘密密钥Sk={d,n}={d,n}endl;coutendl;cout请输入要加密的小于n正整数（以-1结束）：endl;cout加密前的明文为：;for(i=0;iMAXLENGTH;i++)Ciphertext[i]=1;intcount;for(intj=0;jMAXLENGTH;j++){Page4of8cinclear[j];if(clear[j]==-1)break;count=e;while(count0){//对明文进行加密Ciphertext=（clear）^emodnCiphertext[j]=(Ciphertext[j]*clear[j])%n;//加密算法count--;}}cout密文为：;size=j;//实际密文长度for(intk=0;kj;k++)coutCiphertext[k];coutendl;}////////////////////////////////////////////////////////////////以下为解密算法voidDecryption(){//解密算法for(inti=0;iMAXLENGTH;i++)DecryptionText[i]=1;intcount;for(intj=0;jsize;j++){count=d;while(count0){//对密文进行解密DecryptionText=（Ciphertext）^d(modn)DecryptionText[j]=((DecryptionText[j]*Ciphertext[j])%n);count--;}}cout解密后的明文为：;for(intk=0;ksize;k++)coutDecryptionText[k];coutendl;cout加密前的明文为：;for(k=0;ksize;k++)coutclear[k];coutendl;}voidmain(){Encryption();charc;coutendl;cout是否要解密（YorN）:;cinc;if(c=='y'||c=='Y')Decryption();Page5of8elsereturn;}2、运行结果：①②③Page6of83、实验分析：1输入两个大素数p和q时，没有进行判断所输入的是不是素数2对phi求解e的乘法逆元时，必须保证e和phi互素，在这里我们也没有进行判断。3由于以上原因，当我们所用数据较大时，会出现错误，例如运行结果③。4当我们输入要进行加密的明文时，必须保证每个正整数小于n，我们没有做防范措施，也会出现错误结果。【参考资料】1、Page7of82、百度文库：算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即SA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人Page8of8士倾向于因子分解不是NPC问题。RSA的缺点主要有：A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B)分组长度太大，为保证安全性，n至少也要600bits以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET(SecureElectronicTransaction)协议中要求CA采用2048bits长的密钥，其他实体使用1024比特的密钥。C)RSA密钥长度随着保密级别提高，增加很快。下表列出了对同一安全级别所对应的密钥长度。保密级别对称密钥长度（bit）RSA密钥长度（bit）ECC密钥长度（bit）保密年限808010241602010112112204822420301281283072256204019219276803842080256256153605122120这种算法1978年就出现了，它是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也很流行。算法的名字以发明者的名字命名：RonRivest,AdiShamir和LeonardAdleman。早在1973年，英国国家通信总局的数学家CliffordCocks就发现了类似的算法。但是他的发现被列为绝密，直到1998年才公诸于世。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)就是密钥对。RSA加解密的算法完全相同,设A为明文，B为密文，则：A=B^e1modn；B=A^e2modn；e1和e2可以互换使用，即：A=B^e2modn；B=A^e1modn;