实现数字签名的RSA算法的设计与实现样本

课程实践报告书课程名称：密码学与网络安全课程实践题目：实现数字签名RSA算法设计与实现学生姓名：专业：班别：学号：指引教师：日期：年6月18日实现数字签名RSA算法设计与实现摘要随着计算机网络和信息技术发展，信息安全在各领域发挥着越来越重要作用，其中密码学已成为信息安全技术核心，本文重要简介了信息加密技术应用。RSA算法是当前公认在理论和实际应用中最为成熟和完善一种公钥密码体制，它是第一种既能用于数据加密也能用于数字签名算法，是公钥密码体制代表。数字签名是起到身份认证、核准数据完整性一种信息安全技术。它通过认证技术来辨认真伪。RSA数字签名体制使用是RSA公开密钥密码算法进行数字签名。本文重要内容涉及：第一,对RSA算法进行系统简介；第二,简介RSA数字签名某些基本概念和数字签名理论实现过程；第三详述RSA数字签名设计与实现，重要实现模块涉及RSA密钥产生（一对公钥和私钥），RSA加密算法和解密算法实现，；第四,对该系统进行了整体测试和分析改进。核心字：RSA算法；加密；解密；RSA数字签名目录284451引言 3151161.1课题研究背景 342541.2课题研究意义 3241882RSA算法和RSA数字签名算法概念设计 3228082.1RSA算法概念和原理 332812.1.1RSA算法简介 3221252.1.2RSA算法实现原理 374062.2RSA数字签名基本概念和RSA数字签名算法实现原理 4108432.2.1RSA数字签名基本概念 4159942.2.2RSA数字签名算法实现原理 5285063RSA数字签名逻辑设计与实现 6280793.1RSA数字签名总体设计 6301463.1.1RSA数字签名所需实现功能 6293173.1.2总体规定和设计 688913.2各某些设计实现 7118493.2.1密钥产生实现 7184333.2.2产生消息摘要设计实现 10212193.2.3数字签名设计实现 12170353.2.4验证数字签名设计与实现 15146823.2.5RSA数字签名运营成果 18244594软件整体测试和分析改进 18310544.1软件整体测试 18170044.2性能分析与改进设想 1912684开发体会 197091参照文献 201引言1.1课题研究背景随着电子信息技术迅速发展，人类已步入信息社会。但是由于整个社会形成了一种巨大计算机网络，任何一种计算机网络浮现安全问题，都会影响整个国家网络安全，因此信息安全、计算机网络安全问题已引起了人类高度注重。网络安全办法应是能全方位地针对各种不同威胁和脆弱性，这样才干保证网络信息保密性、完整性和可用性。当代密码学已成为信息安全技术核心，密码学是以研究通信安全保密学科，即研究对传播信息采用何种秘密变换以防止第三者对信息窃取。RSA公钥加密算法是第一种既能用于数据加密也能用于数字签名算法。它易于理解和操作，也十分流行。随着越来越多商业应用和原则化工作，RSA已经成为最具代表性公钥加密技术。现今，网上交易加密连接、网上银行身份验证、各种信用卡使用数字证书、智能移动电话和存储卡验证功能芯片等，大多数使用RSA技术。1.2课题研究意义随着电子商务发展，网络上资金电子互换日益频繁，如何防止信息伪造和欺骗成为非常重要问题。当前关于数字签名研究重要集中点是基于公钥密码体制数字签名。手写签名每一项业务都是数字签名潜在用场。数字签名可以提供数据完整性、真实性和不可否认性。数字签名技术在身份辨认和认证、数据完整性、抵赖等方面具备其他技术无法代替作用，它在军事、电子商务和电子政务等领域有着极广泛应用。而在公钥体制中，RSA是一种较为完善公钥密码算法，不但可以同步用于加密和数字签名，并且易于理解和操作，是被广泛研究公钥密码算法。因而，基于RSA数字签名具备较强研究性和实际应用意义。2RSA算法和RSA数字签名算法概念设计2.1RSA算法概念和原理2.1.1RSA算法简介RSA算法是一种公钥密码算法,实现RSA算法涉及生成RSA密钥，加密和解密数据。RSA算法是第一种能同步用于加密和数字签名算法，也易于理解和操作。RSA是被研究得最广泛公钥算法。RSA缺陷重要有：A)产生密钥很麻烦，受到素数产生技术限制，因而难以做到一次一密。B)分组长度太大，为保证安全性，n至少也要600bits。2.1.2RSA算法实现原理1)随机选取两个不同素数p和q，它们宽度是密钥宽度一半。2)计算出p和q乘积n。3)在2和Φ(n)之间随机选取一种数e，e必要和Φ(n)互素，整数e用做加密密钥（其中Φ(n)=(p-1)*(q-1)）。4)从公式ed≡1modΦ(n)中求出解密密钥d。5)得公钥（e，n），私钥(d，n)。6)公开公钥，但不公开私钥。7)将明文P(假设P是一种不大于n整数)加密为密文C，计算办法为：C=P^emodn;8)将密文C解密为明文P，计算办法为：P=C^dmodn;然而只依照n和e（不是p和q）要计算出d是不也许。因而，任何人都可对明文进行加密，但只有授权顾客（懂得d）才可对密文解密。2.2RSA数字签名基本概念和RSA数字签名算法实现原理2.2.1RSA数字签名基本概念RSA数字签名体制使用了RSA公开密钥密码算法进行数字签名，鉴于RSA算法在实践中已经被证明了安全性，RSA数字签名体制在许多安全原则中得以广泛应用。ISO/IEC9796和ANSIX9.30-199X以及美国联邦信息解决原则FIPS186-2已经将RSA作为推荐数字签名原则算法之一。RSA数字签名算法，涉及签名算法和验证签名算法。它是运用RSA算法加密和解密算法原理进行一种数字签名，事实上是通过一种哈希函数来实现（本设计是通过MD5算法）产生消息摘要MD来实现所需加密对象。数字签名特点是它代表了消息特性，消息如果发生变化，数字签名值也将发生变化，不同消息将得到不同数字签名。安全数字签名使接受方可以得到保证：消息的确来自发送方。由于签名私钥只有发送方自己保存，她人无法做同样数字签名，如果第三方冒充发送方发出一种消息，而接受方在对数字签名进行解密时使用是发送方公开密钥，只要第三方不懂得发送方私有密钥，加密出来数字签名和通过计算数字签名必然是不相似，这就提供了一种安全确认发送方身份办法，即数字签名真实性得到了保证。数字签名类似手书签名，它具备如下性质：1）可以验证签名产生者身份，以及产生签名日期和时间；2）能用于证明被签消息内容；3）数字签名可由第三方验证，从而可以解决通信双方争议。为了满足数字签名这些规定，例如，通信双方在发送消息时，既要防止接受方或其她第三方伪造，又要防止发送方因对自己不利而否认，也就是说，为了保证数字签名真实性。数字签名原理是：（发送方和接受方依照规定各自产生自己一对公钥和私钥）1）被发送文献采用某种算法对原始消息进行运算，得到一种固定长度数字串，称为消息摘要（MD），不同消息得到消息摘要各异，但是对相似消息它消息摘要却是唯一；2）发送方生成消息消息摘要，用自己私钥对摘要进行加密来形成发送方数字签名；3）这个数字签名将作为消息附件和消息一同用接受方公钥进行加密，将加密后密文一起发送给接受方；4）接受方一方面把接受到密文用自己私钥解密，得到原始消息和数字签名，再用发送方公钥解密数字签名，随后用同样算法计算出消息摘要；5）如果计算出来消息摘要和发送方发送给她消息摘要（通过解密数字签名得到）是相似，这样接受方就能确认数字签名的确是发送方，否则就以为收到消息是伪造或是半途被篡改。数字签名原理图如2-1所示ABEDEDEDED用A私钥加密用B公钥用B私钥用A公钥解密数字签名加密解密核算签名图2-1数字签名原理2.2.2RSA数字签名算法实现原理RSA数字签名算法分为如下两个环节：1）签名算法（涉及两步：消息摘要计算，RSA加密）(1)消息摘要MD计算：消息在签名前一方面通过MD5计算，生成128位消息摘要；MD5函数是一种单向散列函数，它将任意长度消息压缩成128位消息摘要。应用MD5单向性（即给定散列值,计算消息很难）和抗碰撞性(即给定消息M，要找到另一消息M’并满足两者散列值很难)，可以实现信息完整性检查。此外该函数设计不基于任何假设和密码体制而直接构造，执行速度快，是一种被广泛承认单向散列算法。(2)对MD作RSA加密算法：采用签名者私钥加密消息摘要，得到加密后字符串即数字签名；2）验证签名算法（RSA解密、对消息摘要计算和比较）验证签名算法涉及两步：RSA解密得签名者消息摘要，验证者对原消息计算摘要，比较两个消息摘要。验证签名过程输入为消息，签名者公钥，签名；输出为验证成果，即与否是对的签名。(1)RSA解密：签名实际是加密消息摘要，用以上所述RSA解密办法采用签名者公钥对这个加密消息摘要解密，解密成果应为128位消息摘要。(2)消息摘要计算和比较：验证者对消息用MD5算法重新计算，得到验证者自己消息摘要。验证者比较解密得到消息摘要和自己消息摘要，如果两者相似，则验证成功，可以确认消息完整性及签名的确为签名者；否则，验证失败，确认签名被冒充或是被篡改。3RSA数字签名逻辑设计与实现3.1RSA数字签名总体设计3.1.1RSA数字签名所需实现功能在本软件中需要实现功能有如下几种：（1）生成RSA密钥：公钥ke=（e,n），私钥kd=(d,n)；（2）运用MD5算法计算出消息摘要MD；（3）数字签名实现：用私钥d对消息摘要进行加密计算（RSA算法中加密办法）；（4）验证数字签名：用公钥e对数字签名进行解密计算（RSA算法中解密办法），得到解密成果与(2)步计算出消息摘要比较，如果两个消息摘要同样则签名成功。3.1.2总体规定和设计本软件总体规定有：1）按规定生成非对称密钥——公钥和私钥；2）按任意写入消息字符串(明文信息)生成所需要消息摘要MD；3）在本设计中用产生私钥d依照RSA算法加密原理对所生成消息摘要进行加密运算，得到数字签名；4）在本设计中用产生公钥e依照RSA算法解密原理对所加密消息摘要即数字签名进行解密运算，得到相应消息摘要（在本设计中标示为解密信息），比较两个消息摘要，验证数字签名者身份真实与否；5）提示信息完整、操作舒服、图形界面雅观。本软件总体设计都是基于C++开发环境，采用是MicrosoftVisualc++6.0运营环境。3.2各某些设计实现3.2.1密钥产生实现在密钥产生某些中起决定性作用是素数选取，

对随机数作素性检测，若通过则为素数；否则增长一种步长后再做素性检测，直到找出素数。素性检测采用Fermat测试。这个算法理论根据是费尔马小定理：如果m是一种素数，且a不是m倍数，那么依照费尔马小定理有：am-1=1(modm)。实际应用时：am-1=1(modm)am=a(modm)a=am(modm)，因而对于整数m，只需计算am(modm)，再将成果与a比较，如果两者相似，则m为素数。选用a=2，则a一定不会是任何素数倍数。依照所选素数不同产生不同密钥。密钥理论产生模块流程图如图3-1所示：产生任意素数产生任意素数p和q计算n=p*q计算ou_la=(p-1)(q-1)选取e作为公钥计算d作为私钥图3-1密钥产生密钥产生某些代码实现： CStringstr; //第一步产生任意素数 GeneratePrimeNumbers(); //第二步计算n=p*q m_n=m_Prime1*m_Prime2; //第三步0=(p-1)(q-1) m_Undef=(m_Prime1-1)*(m_Prime2-1); //第四步选取'e' SelectE(); //第五步计算D CalculateD(); //显示公钥和私钥 //(1)公钥KU={e,n} str.Format("{%d，%d}",m_e,m_n); m_public_key.SetWindowText(str); //(2)私钥KU={d,n} str.Format("{%d，%d}",m_d,m_n); m_private_key.SetWindowText(str); //选取一种'e'使'e'与m_Undef互素//选取e函数实现SelectE(){CStringstr;for(floati=2;i<100000;i++) { if(IsRelativePrime((float)m_Undef,(float)i)) { m_e=(long)i; return; } }}//互为素数函数实现IsRelativePrime(floatX,floatY){floatR;//输入：X,Y if(X<Y)//如果X较小则互换两个值 { X=X+Y; Y=X-Y; X=X-Y; } //在这时X总是比Y大 for(;;) { if(Y==0) break; R=fmod(X,Y); X=Y; Y=R; }if(X!=1) returnfalse; else returntrue;//互素}//计算D函数实现CalculateD(){ floatd; longd_dash; CStringstr; for(floatk=1;k<100000;k++) { d=(m_Undef*k+1)/m_e; d_dash=(long)((m_Undef*k+1)/m_e); if(d==d_dash) { m_d=d; return; } }}//产生素数函数实现GeneratePrimeNumbers(){ CStringstr; UpdateData(TRUE);//通过如下两个函数可获得两个大素数，但增长了计算复杂性，为了以便，直接给定素数// m_Prime1=FindPrime(1);// m_Prime2=FindPrime(m_Prime1); m_Prime1=47; m_Prime2=71;}3.2.2产生消息摘要设计实现计算消息摘要理论实现流程图如图3-2所示：初始化MD5初始化MD5所需常量计算所需追加长度对原始信息进行补位将输入提成512位块循环解决块得到消息摘要得到消息摘要图3-2消息摘要计算流程在以上流程图中其中循环解决块是最重要一步，也是MD5核心算法，在这一步中涉及了：（1）把四个连接变量复制到了四个变量a,b,c,d中，使a=A，b=B，c=C，d=D；其中a,b,c,d组合成128位寄存器，且在实际算法运算中保存中间成果和最后成果；（2）将当前512位块分解为16个子块，每个子块为32位；（3）要循环四轮，每一轮解决一种块中16个子块，四轮第一步进行不同解决，其她相似：每一轮有16个输入子块M[0]，M[1]，…………..M[15]，或表达为M[i]，其中i为0-15；t是常量数组，包括64个元素，每个元素为32位，数组t表达为t[1]，t[2]，………t[64]，或t[k]，k为1-64；MD5循环四轮操作过程用下式表达：a=b+((a+proccessP(b,c,d)+M[i]+T[k])<<<s)(<<<s表达循环左移s位)产生消息摘要重要代码如下： inti;intIndex; //初始化MD5所需常量Init()； //计算追加长度Append(WriteMessage.length());//对原始信息进行补位 for(i=0;i<m_AppendByte;i++) { if(i==0)WriteMessage+=(unsignedchar)0x80; elseWriteMessage+=(unsignedchar)0x0; }//将原始信息长度附加在补位后数据背面for(i=0;i<8;i++)WriteMessage+=m_MsgLen[i]; //位块数组unsignedcharx[64]={0};//循环，将原始信息以64字节为一组拆分进行解决 for(i=0,Index=-1;i<WriteMessage.length();i++) { x[++Index]=WriteMessage[i]; if(Index==63) { Index=-1;//将64字节位转换为16个字节 Transform(x); } }//将寄存器ABCD最后值转换为16进制返回给顾客 returnToHex(UpperCase);3.2.3数字签名设计实现数字签名理论实现流程图如图3-3所示，数字签名，就是通过在数据单元上附加数据，或对数据单元进行加密变换，从而使接受者可以确认数据来源和完整性。数字签名是防止她人对传播文献进行破坏，以及拟定发信人身份手段。数字签名中加密算法就是应用RSA加密原理，而它验证算法则是应用RSA解密原理。开始得到数字签名开始得到数字签名得到消息摘要MD用私钥d加密MD结束图3-3数字签名实现流程RSA加密、解密过程都为求一种整数整多次幂，再取模。如果按其含义直接计算，则中间成果非常大，有也许超过计算机所容许整数取值范畴。为了减小中间成果和提高加、解密运算中指数运算有效性，本设计采用了迅速指数算法。它运算过程为（如果要算a^mmodn）：1）将m表达为二进制形式；2）初始化c=0，d=1，c在这里表达指数某些成果，它终值即为指数m，d是中间成果，它终值即为所求成果；3）从二进制数最高位到最低位开始对每一位都用公式1进行运算，得到d为该步成果，公式1：c=2*c;d=fmod(d*d,n);4）若二进制数是1,则在上面运算后继续如下运算：c=c+1;d=fmod(d*a,n);得到成果d才为该步最后成果。数字签名重要实现过程代码如下：//消息摘要，8位为一组一种字符一组 charmessage[200]；//从文本框中得到消息摘要m_message.GetWindowText(message,200); len=strlen(message); charshowstr[1000]=""; intNO_BITS=32; doublec=0,d=1; charbits[100]; doublen=(double)m_n; unsignedcharch; doubledata;//19; longi,k=NO_BITS; intsizeof_d=sizeof(double);//将十进制数私钥d转换为二进制D_to_B(m_d,32,bits);//得到适当字节 GetOnlyProperBits(bits); k=NO_BITS=strlen(bits)-1; for(intii=0;ii<len;ii++) { //从message中读取字符放入'data'中 ch=message[ii]; data=(double)ch; //计算((data)^dmodn)迅速指数算法实现 c=0;d=1; for(i=k;i>=0;i--) { c=2*c; d=fmod(d*d,n); if(bits[NO_BITS-i]=='1') { c=c+1; d=fmod(data*d,n); } } //从'd'中读取字符放入result中 result[ii]=d;//把字符串变为十六进制数后连接字符串 strcat(showstr,longtohex(d)); }//结束循环//显示成果 m_result.SetWindowText(showstr); }//字符串变为16进制数函数实现longtohex(longx){charstr[8]; inti=0;//商 inta；//余数 intb; longtt=x; while(tt>=16) { a=tt/16; b=tt%16; switch(b) { case0：str[i]='0'；break; case1：str[i]='1'；break; case2：str[i]='2'；break; case3：str[i]='3'；break; case4：str[i]='4'；break; case5：str[i]='5'；break; case6：str[i]='6'；break; case7：str[i]='7'；break; case8：str[i]='8'；break; case9：str[i]='9'；break; case10：str[i]='A'；break; case11：str[i]='B'；break; case12：str[i]='C'；break; case13：str[i]='D'；break; case14：str[i]='E'；break; case15：str[i]='F'；break; }; i++;tt=a; } str[i]='\0'; strrev(str); returnstr;}3.2.4验证数字签名设计与实现得到数字签名得到数字签名用公钥e解密数字签名得到消息摘要（解密信息）开始结束图3-4验证数字签名流程验证数字签名对的与成功性，重要是比较得到两次消息摘要与否同样，如果验证方用签名方公钥解密得到消息摘要（即是本设计中得到解密信息）和她自己计算得到消息摘要（在本系统中为第一次计算得到消息摘要）是同样，则证明签名是对的，没有被篡改或是冒充，验证签名原理则是依照RSA解密算法，详细理论流程图如图3-4所示：（在本设计中签名和验证签名都在同一界面实现，不进行文献双方传播）验证数字签名过程时应用解密算法是RSA解密原理，而RSA解密过程也应用了求一种整数整多次幂，再取模运算。在此也采用了迅速指数算法，详细算法过程同RSA加密过程中应用迅速指数算法是同样。验证数字签名重要实现过程代码如下：intNO_BITS; doublec=0,d=1; charbits[100]; doublen=(double)m_n; doubledata;//19; longi,k;intsizeof_d=sizeof(double);//用于存储解密信息 charmessage[200];//将十进制数公钥e转换为二进制 D_to_B(m_e,32,bits); GetOnlyProperBits(bits); k=NO_BITS=strlen(bits)-1; for(intj=0;j<len;j++) { //从result中读取字符放入'data'中 data=result[j]; //计算((data)^emodn)迅速指数算法实现 c=0;d=1; for(i=k;i>=0;i--) { c=2*c; d=fmod(d*d,n); if(bits[NO_BITS-i]=='1') { c=c+1; d=fmod(data*d,n); } }//结束循环 //从'd'中读取字符放入message中 message[j]=d; }//显示成果 m_mingwen.SetWindowText(message); }3.2.5RSA数字签名运营成果图3-5RSA数字签名运营成果在本软件中得到二个消息摘要：依照写入消息（明文信息）计算出来消息摘要、解密数字签名得到消息摘要（即是本设计中解密信息）。如果两个消息摘要是同样则证明RSA数字签名者身份真实性，从而实现了RSA数字签名。该系统运营成果如图3-5所示。产生消息摘要和解密得到消息摘要（在此处是解密信息）是完全同样，则证明了数字签名真实性。4软件整体测试和分析改进4.1软件整体测试（1）测试密钥生成：产生密钥前提是要有两个素数生成，密钥产生依赖于素数生成，素数生成不同样则密钥也会不相似，在本设计中素数是47和71，则相相应密钥是公钥（3，3337）和私钥（2147，3337）；（2）测试消息摘要MD生成：写入消息（明文信息）不同样得到消息摘要就有所区别，但是在产生消息摘要时所使用计算办法是同样即MD5算法，该算法核心是其中四轮循环，如果四轮循环中一种细节出了问题则所产生MD便是相差极远，如若明文信息是dfgfhfhgjk则得到消息摘要A4127B4881D24B01A85696477A07C17C，若明文信息是cvnjj则得到消息摘要是A1E2C15FF4C9F4D407EF33D1AC56C632；（3）测试数字签名生成：依照RSA算法加密原理对不同消息摘要MD进行加密运算，得到便是不同数字签名DS；若消息摘要MD是A1E2C15FF4C9F4D407EF33D1AC56C63