RSA算法.doc

成都信息工程学院课程设计报告RSA加密解密的实现课程名称：应用密码算法程序设计 学生姓名： 黄富致 学生学号： 2004033043 专业班级： 信息安全1班 任课教师： 张金全 2007年 6 月 29 日目录总页数：20页1.引言1.1背景1.2 目的1.3 本设计的主要任务1.4开发环境2.总体设计2.1需求规定2.2运行环境2.3 基本设计的处理流程及结构2.4工程方案选择2.5系统设计2.5.1设计概述2.5.2算法的功能3. RSA加密解密器主要功能介绍3.1概述3.2 RSA的构成3.3 RSA思想的证明3.4 RSA中素数的选取3.5 RSA安全性分析3.3主要功能3.3.1界面设计3.3.2具体功能函数及函数功能的实现4.RSA加密解密软件的测试报告5.总结参考文献：21.引言1.1背景RSA公钥加密算法是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也十分流行。算法的名字以发明者的姓氏首字母命名：Ron Rivest, Adi Shamir 和Leonard Adleman。虽然自1978年提出以来，RSA的安全性一直未能得到理论上的证明，但它经历了各种攻击，至今（2006年）未被完全攻破。随着越来越多的商业应用和标准化工作，RSA已经成为最具代表性的公钥加密技术。VISA、MasterCard、IBM、Microsoft等公司协力制定的安全电子交易标准（Secure Electronic Transactions，SET）就采用了标准RSA算法，这使得RSA在我们的生活中几乎无处不在。网上交易加密连接、网上银行身份验证、各种信用卡使用的数字证书、智能移动电话和存储卡的验证功能芯片等，大多数使用RSA技术。当今公钥加密更广泛应用于互联网身份认证，本课题将公钥加密算法RSA应用于小型文件加密。将任意文件加密成文本的解决方案，使其使用更加灵活。整个工程的分层设计，给引用移植和后续开发带来便利。1.2 目的随着大型企业管理软件的发展，其应用越来越广泛，企业数据平台涉及局域网、广域网、Internet等，在各类系统中保存的企业关键数据量也越来越大，许多数据需要保存数十年以上，甚至是永久性保存。于是关键业务数据成了企业生存的命脉和宝贵的资源，数据安全性问题越来越突出。如何增强企业软件系统的安全性、保密性、真实性、完整性，成为每一位软件开发人员关注的焦点。加密算法在现实生活中也越来越重要。在一些特殊场合，达到保密传递信息的目的。1.3 本设计的主要任务根据RSA加密算法实现任意长度的文本加密解密.任意大小任意格式的文件加密解密.向用户提供良好的界面.良好的操作性。1.4开发环境C+是既适合于作为系统描述语言，也适合于编写应用软件的既面向对象又面向过程的一种混合型程序设计语言，它是在c语言的基础之上发展起来的。最初的c语言知识为描述和显示UNIX操作系统而提供的 一种程序设计语言。1973年，贝尔实验室的K。Thompson和D。M。Ritchie两人合作把UNIX的百分之九十以上的代码用c语言改写。后来c语言有作了多次的改进，1978年以后，c语言已先后移植到大。中。小及微型计算机上。到了20世纪80年代美国的贝尔实验室的Bjarne Stroustrup在c语言的基础之上推出了c +程序设计语言。由于c+提出了把数据和在数据之上的操作封装在一起的类，对象和方法的机制，并通过派生，继承，重载和多态性等特征，实现了人们期待依旧的软件重用和程序自动生成。这使得软件，特别是大型复杂软件的构造和维护变得更加有效和容易，并使软件开发能更自然地反映事物的本质，从而大大提高了软件的开发效率和质量。C+越来越受到重视并得到广泛的应用，许多软件公司都为c+设计编译系统。如ATT，Apple,Sun等，其中国内最为流行的应当是Microsoft公司的VISUAL C+。与此同时，许多大学和公司也在为C+ 编写各种不同的库类，Microsoft公司的MFC就比较优秀的代表，在国内外得到广泛的应用。2.总体设计2.1需求规定输入：加密：任意长度的明文 输出：解密：正常的明文2.2运行环境WINDOWS 9x,XP,NT,200X.2.3 基本设计的处理流程及结构 图1 用户模型 图2 生成密钥 图3 载入密钥和保存密钥根据以上分析，一般来说，需要进行编码的程序有 1.RSA密钥生成 2.RSA加密解密 3.各环节必要的数据编码转换 4.图形操作界面2.4工程方案选择整个工程使用Windows本地化程序实现，在不应用Windows或第三方现成组件的情况下，需从RSA算法出发编码实现。其他各功能的设计开发，如文件操作、数据编码转换和图形界面等，可以使用ATL、MFC或Windows API实现。这种工程几乎是为Windows量身订做，执行效率最好。但是对于非PC设备，只能方便的移植到运行Windows嵌入式操作系统的设备，向其他操作系统移植困难，需要重新编写大量代码。通常解决本地化代码的移植问题，都是使用C+标准库，即功能尽量多的由C+标准库完成，这样在移植的时候，只需要重新编写操作系统相关的代码即可。这种开发方式比起前两种，缺点就是设计开发模式陈旧，代码烦琐，不方便维护；流行的.Net上的语言引用各种功能比较麻烦。2.5系统设计 2.5.1设计概述本此设计在深入理解RSA 加密/解密算法理论的基础上，设计一个RSA加密/解密软件，可以对数字和字母,汉字加密，也可以进行解密，而且还可以提供良好的用户界面。 2.5.2算法的功能1能够生成随机产生公钥和私钥，和模数R2能够对明文(包括汉字，数字，字母)进行加密3能够对明文(包括汉字，数字，字母)进行解密4能够直接退出界面3. RSA加密解密器主要功能介绍3.1概述当前最著名、应用最广泛的公钥系统RSA是在1978年，由美国麻省理工学院(MIT)的Rivest、Shamir和Adleman在题为获得数字签名和公开钥密码系统的方法的论文中提出的。它是一个基于数论的非对称(公开钥)密码体制，是一种分组密码体制。其名称来自于三个发明者的姓名首字母。 它的安全性是基于大整数素因子分解的困难性，而大整数因子分解问题是数学上的著名难题，至今没有有效的方法予以解决，因此可以确保RSA算法的安全性。RSA系统是公钥系统的最具有典型意义的方法，大多数使用公钥密码进行加密和数字签名的产品和标准使用的都是RSA算法。 RSA算法是第一个既能用于数据加密也能用于数字签名的算法，因此它为公用网络上信息的加密和鉴别提供了一种基本的方法。它通常是先生成一对RSA 密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册，人们用公钥加密文件发送给个人，个人就可以用私钥解密接受。为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。 该算法基于下面的两个事实,这些事实保证了RSA算法的安全有效性： 1) 已有确定一个数是不是质数的快速算法； 2) 尚未找到确定一个合数的质因子的快速算法。 RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因子分解不是NPC问题。 RSA的缺点主要有：A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B)分组长度太大，为保证安全性，n 至少也要 600 bits 以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET( Secure Electronic Transaction )协议中要求CA采用比特长的密钥，其他实体使用比特的密钥。3.2 RSA的构成 RSA系统由以下几部分组成： (1) 随机选取的在素数P和Q，还有N，其中N=P*Q，P和Q保密，N公开。 (2) 任取 (n)=（P-1）*(Q-1)，其中 (n)表示比n小的素数的个数，任取2=eDvoid IntRandom(byteint RandomA,int num); /随机产生一个大数void LoadInt(byteint A,mtype B); /将质数类型转换为大数类型void TransBi(byteint B,signed char flag400); /将大数B转换为二进制形式void Mdata(); /产生用于生成质数中进行比较的数int Prime(byteint Prm); /产生一个长度为MLENGTH的质数int ComputingPK(byteint Rvalue,byteint SK,byteint PK); /计算公钥PKvoid ComputingR(byteint p,byteint q,byteint R); /计算模值Rvoid ComputingRvalue(byteint p,byteint q,byteint Rvalue); /计算$(r)void IntCpy(byteint A1,byteint B1); /将大数B1的值拷贝到大数A1中void SetZero(byteint A); /将大数A清零CString PrtInt(byteint A); /将一个大数类型转换为一个CString类型int Getinput(byteint result,CString input); /将字符串转换为对应的大数形式int Getinput1(byteint result,unsigned long input); /将长整形数转换为对应的大数形式void RsaDo(byteint source,byteint R,byteint key,byteint desti); /实现加解密void GenKeys(CString& pk,CString& sk,CString& R);/提供给服务器使用的秘钥产生函数int RsaEncrypt(CString& source,const char* key,const char* R,CStringArray& result);/加密CString RsaDecrypt(CStringArray& source,const char* sk,const char* R);/解密void GenKeysTable(); /生成秘钥对文主要函数功能的实现：1.功能：进行相关大数的初始化void CRsaA:InitInt(void)SetZero(ZEROVALUE);/对大数变量zerovalue清零memset(mZEROVALUE,0,MLENGTH);SetZero(ONEVALUE); /对大数变量ONEVALUE进行清零ONEVALUEDATALENGTH-1=1;/ONEVALUE的最后一位为1SetZero(TWOVALUE);/将TOWVALUE进行清零 TWOVALUEDATALENGTH-1=2;/TOWVALUE的最后一位为2SetZero(EIGHTVALUE);/对EIGHTVALUE进行清零 EIGHTVALUEDATALENGTH-1=8;/最后一位为8return ;2.功能：该函数用来进行模幂算法，A为底数，模为c，二进制的指数B存放在数组flag中入口参数：底数A，模C，结果D，二进制质数flag400返回值：AB=1(mod C),返回1；AB=p-1(mod C),返回2；否则返回0int CRsaA:PowerMode(byteint A,byteint C,byteint D,signed char flag400)byteint buf;byteint result;byteint temp,P;register i;SetZero(D); SetZero(buf); SetZero(result); SetZero(temp); SetZero(P); /将D清零IntCpy(temp,A); /将A的值拷贝到temp中if(flag399=1)/最低位为1，拷贝本身，flagi只有1或者0两种情况IntCpy(result,A);else /最低位为0，则幂为1IntCpy(result,ONEVALUE);i=398;while(flagi!=-1) /判断是否已经到达指数尽头Multiply(temp,temp,buf); /temp*temp-buf SetMode(buf,C,temp,P); /buf%c余数-temp,商-pif(flagi!=0) /如果该位不是0，则将其和前一步低一位的结果进行乘法运算 /否则，将其作为该位的模，在高一位的运算中，只要进行一次Multiply(temp,result,buf); /平方运算，就可以得到高一位的模SetMode(buf,C,result,P);i-; /result中存放的是最终结果IntCpy(buf,C);IntCpy(D,result);Substract(buf,ONEVALUE,temp);if(IntCmp(result,ONEVALUE)=0) /p mod n=1，判断是否有AB=1(mod C)return 1;if(IntCmp(result,temp)=0) /p mod n=-1p-1=-1(mod p)，判断是否有AB=p-1(mod C)return 2;return 0;3.功能：计算公钥PK入口参数：$(r)的值在Rvalue中，私钥SK，公钥PK返回值：成功找到，返回1int CRsaA:ComputingPK(byteint Rvalue,byteint SK,byteint PK)register i;byteint PA,PB,PC,buf1,temp,buf2;SetZero(PK); SetZero(PA); SetZero(PB); SetZero(PC); SetZero(buf1); /清零初始化SetZero(temp); SetZero(buf2);while(1)IntRandom(SK,SKLENGTH); /随机产生一个大数奇数作为Generated secret keyIntCpy(PB,SK);IntCpy(PA,Rvalue);while(1)SetMode(PA,PB,PC,PK); /PA=PB*PK+PCi=IntCmp(PC,ONEVALUE);if(i=0) /PC=1, i=0break; /满足条件，是互质的i=IntCmp(PC,ZEROVALUE);if(i=0)i=-1; /PC=0,i=-1break; /不满足互质条件，跳出循环，从新生成一个随机数IntCpy(PA,PB); /按照欧几里的定理继续判断IntCpy(PB,PC);if(i=0) /满足，跳出查找循环break;IntCpy(temp,ONEVALUE);IntCpy(PA,Rvalue);IntCpy(PB,SK);while(1)Multiply(PA,temp,buf1); /buf1=PA*tempPlus(buf1,ONEVALUE,buf2);/buf2=(PA*temp)+1SetMode(buf2,PB,buf1,PK);/buf=(PA*temp)+1)%PBif(IntCmp(buf1,ZEROVALUE)=0)break;Plus(temp,ONEVALUE,buf1);IntCpy(temp,buf1);return 1; /SK and PK found4.功能：计算模R入口参数：产生的质数p，q，模R返回值：无void CRsaA:ComputingR(byteint p,byteint q,byteint R)Multiply(p,q,R); / R=p*q, public mode number5.功能：实现加密，解密运算功能入口参数：明文(大数类型source)，模R，秘钥key，结果desti返回值：无void CRsaA:RsaDo(byteint source,byteint R,byteint key,byteint desti)TransBi(key,flag);PowerMode(source,R,desti,flag);6.功能：生成一个秘钥存贮文件 (入口参数：无返回值：无)void CRsaA:GenKeysTable()CStringArray RArray,SKArray,PKArray;CString r,pk,sk;int j=1,i; /参数j表示产生的秘钥对的个数unsigned char strlength;/设置数组的元素个数RArray.SetSize(j,1);SKArray.SetSize(j,1);PKArray.SetSize(j,1);文件格式为：长度 秘钥 长度 秘钥.- - - -1byte nbyte 1byte nbyte (中间无空格,R,SK,PK)*/CFile file;for(i=0;ij;i+)GenKeys(pk,sk,r); /循环产生秘钥RArray.SetAt(i,r); SKArray.SetAt(i,sk); PKArray.SetAt(i,pk);/if(file.Open(c:key.txt,CFile:modeCreate|CFile:modeReadWrite)=0)if(file.Open(key.txt,CFile:modeCreate|CFile:modeReadWrite)=0)AfxMessageBox(open file error!); /打开文件失败return;for(i=0;ij;i+) /循环写入结果strlength = (unsigned char)(RArray.GetAt(i).GetLength();file.Write(&strlength,1);file.Write(RArray.GetAt(i),(RArray.GetAt(i).GetLength();strlength = (unsigned char)(SKArray.GetAt(i).GetLength();file.Write(&strlength,1);file.Write(SKArray.GetAt(i),(SKArray.GetAt(i).GetLength();strlength = (unsigned char)(PKArray.GetAt(i).GetLength();file.Write(&strlength,1);file.Write(PKArray.GetAt(i),(PKArray.GetAt(i).GetLength();file.Close();void CRsaA:LoadKeysFromFile(CString& r,CString& sk,CString& pk) int j=10,len;char *pbuffer;unsigned char strlen1;CFile file;CFileException e;CString strFileName;if(file.Open(c:key.txt,CFile:modeRead)=0)AfxMessageBox(File(key.txt)could not be opened );file.Read(&strlen1,1); /读出R长度len = (int)strlen1;pbuffer = new charlen+1;pbufferlen=0;file.Read(pbuffer,len); /读出Rr=pbuffer;delete pbuffer;file.Read(&strlen1,1); /读出SK长度len = (int)strlen1;pbuffer = new charlen+1;pbufferlen=0;file.Read(pbuffer,len); /读出SKsk=pbuffer;delete pbuffer;file.Read(&strlen1,1); /读出PK长度len = (int)strlen1;pbuffer = new charlen+1;pbufferlen=0;file.Read(pbuffer,len); /读出PKpk=pbuffer;delete pbuffer;file.Close();4.RSA加密解密软件的测试报告1点击 2弹出对话