RSA加密解密的设计与实现

上海电力学院《应用密码学》课程设计题目：RSA加密解密的设计与实现院系：计算机科学与技术学院专业年级：2010级学生姓名：李正熹学号：20103273指导教师：田秀霞2013年1月8日目录目录1.设计要求2.开发环境与工具3.设计原理（算法工作原理）4.系统功能描述与软件模块划分5.设计核心代码6.参考文献7.设计结果及验证8.软件使用说明9.设计体会附录1.设计要求1随机搜索大素数，随机生成公钥和私钥2用公钥对任意长度的明文加密3用私钥对密文解密4界面简洁、交互操作性强2.开发环境与工具WindowsXP操作系统MicrosoftVisualC++6.01.创建rsa工程2.在rsa工程中创建20103273李正熹cpp文件3.设计原理RSA算法简介公开密码算法与其他密码学完全不同，它是基于数学函数而不是基于替换或置换。与使用一个密钥的对称算法不同，公开密钥算法是非对称的，并且它使用的是两个密钥，包括用于加密的公钥和用于解密的私钥。公开密钥算法有RSA、Elgamal等。RSA公钥密码算法是由美国麻省理工学院(MIT)的Rivest，Shamir和Adleman在1978年提出来的，并以他们的名字的有字母命名的。RSA是第一个安全、实用的公钥密码算法，已经成为公钥密码的国际标准，是目前应用广泛的公钥密码体制。RSA的基础是数论的Euler定理，其安全性基于二大整数因子分解问题的困难性，公私钥是一对大素数的函数。并且该算法已经经受住了多年深入的密码分析，虽然密码分析者既不能证明也不能否定RSA的安全性，但这不恰恰说明该算法有其一定的可信度。4.系统功能描述与软件模块划分功能：1.进行加密加密第一步，随机两个素数p和q，并求出n=p*q，然后再求出n的欧拉函数值phi。第二步，在[e，phi]中选出一个与phi互素的整数e，并根据e*d≡1（modphi），求出e的乘法逆元。至此我们已经得到了公开密钥{e，n}和秘密密钥{d，n}。第三步，让用户输入要进行加密的小于n一组正整数（个数不超过MAXLENGTH），输入以-1为结束标志，实际个数存入size中，正整数以clear[MAXLENGTH]保存。第四步，对第三步所得的明文clear[MAXLENGTH]进行加密。遍历clear[size]，对每一个整数用以下算法进行加密,并将加密后的密文保存在Ciphertext[MAXLENGTH]中。第五步，输出密文Ciphertext[MAXLENGTH]2.进行解密第一步，输入加密后的密文Ciphertext1[MAXLENGTH]，输入以-1为结束标志第二步，输入解密密钥[d,phi],对密文进行解密，结果保存在DecryptionText[MAXLENGTH]中。第三步，输出解密后明文DecryptionText[MAXLENGTH]生成随机素数：先生成一个随机数然后判断它是否为素数从而输出unsignedlongfoo()//生成随机数intpanduan(unsignedlongb)//判断是否为素数unsignedlongtiqu(unsignedlong&p,unsignedlong&q)//从随机素数中选取两个为p和q求e时需要用到e与phi的互逆所以在随机产生e的同时需要作互逆判断若互逆则输出随机e否则重新生成eintgcd(intx,inty)//判断两数是否为互素在p、q、e都准备就绪的时候就可以进行加解密的运算因为考虑到溢出所以3个一组进行加解密voidEncryption()//加密算法voidDecryption()//解密算法5.设计核心代码unsignedlongfoo(){unsignedlongrandom=0;srand((int)time(0));random=rand()%300;returnrandom;}srand函数是随机数发生器的初始化函数需要提供一个种子这里使用time来获取系统当前时间rand()%300是随机0-299的整数//以下为加密算法voidEncryption(){//加密算法cout随机生成两个较大的素数：endl;tiqu(p,q);n=p*q;//求解n，phi=(p-1)*(q-1);//求解n的欧拉函数值coutn=n,phi=phiendl;cout请从[0，phi-1]中选择一个与phi随机生成互素的数e：;while(1){e=foo();if(gcd(e,phi)==1&&e=100&&e=300&&e!=q&&e!=p)break;}couteendl;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请3位一组输入要加密的正整数（以-1结束）：endl;cout加密前的明文为：;for(i=0;iMAXLENGTH;i++)Ciphertext[i]=1;intcount;for(intj=0;jMAXLENGTH;j++){cinclear[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(){//解密算法intpp,kk;for(inti=0;iMAXLENGTH;i++)DecryptionText[i]=1;intcount;cout请输入要解密的密文（以-1结束）：endl;for(intu=0;uMAXLENGTH;u++){cinCiphertext1[u];if(Ciphertext1[u]==-1)break;}cout输入密钥解密(d,n)endl;cinppkk;for(intj=0;jsize;j++){count=pp;while(count0){//对密文进行解密DecryptionText=（Ciphertext）^d(modn)DecryptionText[j]=((DecryptionText[j]*Ciphertext1[j])%kk);count--;}}cout解密后的明文为：;for(intk=0;ksize;k++)coutDecryptionText[k];coutendl;}6.参考文献[1]赛迪网．RSA2010:云安全需急迫解决的安全隐患.旧金山：赛迪网，2010.[2]赛迪网．RSA主席认为云安全成2010安全领域趋势.旧金山：赛迪网，2010.[3]魏晨.安全风向标：品味RSA2012信息安全大会.旧金山：赛迪网，2012.[4]四夕．新的安全威胁而前需要新的安全架构.旧金山：赛迪网，2012.[5]王茜．倪建伟，一种基于RSA的加密算法.重庆大学学报，2005,28(1)：68-72.[6]周升力．RSA密码算法的研究与改进实现．现代计算机，2008：51-53．[7]管占明.邓亚娟．RSA加密算法的研究及应用.科技广场，2009：98-99.[8]胡向东，魏琴芳等．应用密码学．北京市：电子工业出版社，2008:114-119．[9]卢开澄．计算机密码学.北京市：清华大学出版社，2002:73-77[10]史予荣．软件加密技术从入门到精通，北京市：清华大学出版社．2007:74-77.7.设计结果及验证进行加密得到公钥（113，11021）和私钥（2105，11021）加密明文12358711456189得到密文14533857882632948732744输入密文解密得到先前加密的明文123587114561898.软件使用说明1.选择RSA加解密系统功能1为加密2为解密0为退出输入其他错误重新输入2.输入1进行加密过程输入需要加密的明文3个一组空格空开-1结束生成密文并且返回主界面2.输入2进行解密输入加密好的密文-1结束输入密钥dn解密得到加密前明文解密成功返回主界面9.设计体会RSA课程设计中，包含了加解密的过程，刚开始对做设计的时候，觉得对于RSA的加解密只要套用公式就可以很方便地进行，实现并不是非常困难。但是在真正实现的时候还是碰到了不少的问题，在随机产生素数的时候，不同的实现方法会具有不同的复杂度，从而使得时间效率也有所不同，若直接生成素数，系统需要很长一段时间来生成，而随机生成一个数后再判断是否为素数可以减少很多时间，效率也就提高了。在加解密的时候，起初使用的是int型的整形变量，但是发现int型只有4位长度8字节，所以在计算时，数字一大就会产生溢出，所以使用了数组进行了加解密。而在大素数生成时，可以生成非常大的素数，但是在加密时，因为程序效率过于低以至于一天都没有算出结果，所以在实现时使用了可进行运算和实现较大的素数而并不是大素数。随机大素数进行RSA加解密的程序还需要时间进行进一步改进。需要进一步调用大整数的加减乘除算法，素数明文密文密钥公钥都要使用数组才能加以实现，在此暂时保留这个程序，将用更充分的时间来实现。总结这次课程设计，不可否定又是一次对于自己编程能力的提升以及团队合作的加深，自己动手编程真的是一种成就感，然而在这以外，我还发现了自己会有一些突发奇想的思路，会发现和挖掘实现实验时某些过程的优化，而这些思路又可以帮助自己来完成程序。这次课程设计的不足是还没有完全完成课程设计所需要的任务要求，写的程序还是略微有点简单化了，可能自己能力还是有限，在静候的时间里还需要更加的磨练才行。附录#includeiostream#includectime#includecstdlib#includecmathusingnamespacestd;#defineMAXLENGTH500//明文最大长度，即所允许最大整数个数intsize=0;//保存要进行加密的正整数的个数unsignedlongp,q;//两个大素数intn,phi;//n=p*q，phi=(p-1)*(q-1)是n的欧拉函数值inte;//{e,n}为公开密钥intd;//{d,n}为秘密密钥longclear[MAXLENGTH],Ciphertext[MAXLENGTH],Ciphertext1[MAXLENGTH];//分别用于存放加//密前的明//文和加密后的密文longDecryptionText[MAXLENGTH];//存放解密后的明文////////////////////////////////////////////////////////////unsignedlongfoo(){unsignedlongrandom=0;srand((int)time(0));random=rand()%300;returnrandom;}intpanduan(unsignedlongb){intflag=1;if(flag){for(unsignedlongj=2;j=sqrt(b);j++){if(b%j==0){flag=0;//coutbbu是素数!endl;}}}if(flag){return1;}elsereturn0;}unsignedlongtiqu(unsignedl