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

1、课程实践报告书课程名称： 密码学与网络安全课程实践 题 目：实现数字签名的RSA算法的设计与实现学生姓名： 专 业：班 别： 学 号： 指导老师： 日 期： 2016 年 6 月 18 日实现数字签名的RSA算法的设计与实现摘 要随着计算机网络和信息技术的发展，信息安全在各领域发挥着越来越重要的作用，其中密码学已成为信息安全技术的核心，本文主要介绍了信息加密技术的应用。 RSA算法是目前公认的在理论和实际应用中最为成熟和完善的一种公钥密码体制，它是第一个既能用于数据加密也能用于数字签名的算法，是公钥密码体制的代表。数字签名是起到身份认证、核准数据完整性的一种信息安全技术。它通过认证技术来辨认真

2、伪。RSA数字签名体制使用的是RSA公开密钥密码算法进行数字签名。本文主要内容包括：第一,对RSA算法进行系统的介绍；第二,介绍RSA数字签名的一些基本概念和数字签名的理论实现过程；第三详述RSA数字签名的设计与实现，主要实现的模块包括RSA密钥的产生（一对公钥和私钥），RSA加密算法和解密算法的实现，；第四,对该系统进行了整体的测试和分析改进。关键字：RSA算法；加密； 解密；RSA数字签名 目 录 1 引言31.1 课题的研究背景31.2 课题的研究意义32 RSA算法和RSA数字签名算法的概念设计32.1 RSA算法的概念和原理32.1.1 RSA算法介绍32.1.2 RSA算法的实现原

3、理32.2 RSA数字签名基本概念和RSA数字签名算法的实现原理42.2.1 RSA数字签名基本概念42.2.2 RSA数字签名算法的实现原理53 RSA数字签名的逻辑设计与实现63.1 RSA数字签名的总体设计63.1.1 RSA数字签名所需实现的功能63.1.2 总体要求和设计63.2 各部分的设计实现73.2.1 密钥产生的实现73.2.2 产生消息摘要的设计实现103.2.3 数字签名的设计实现123.2.4 验证数字签名的设计与实现153.2.5 RSA数字签名的运行结果184 软件的整体测试和分析改进184.1软件的整体测试184.2 性能分析与改进设想19开发体会19参考文献20

4、1 引言1.1 课题的研究背景随着电子信息技术的迅速发展，人类已步入信息社会。但是由于整个社会形成了一个巨大的计算机网络，任何一个计算机网络出现的安全问题，都会影响整个国家的网络安全，所以信息安全、计算机网络安全问题已引起了人类的高度重视。网络的安全措施应是能全方位地针对各种不同的威胁和脆弱性，这样才能确保网络信息的保密性、完整性和可用性。现代密码学已成为信息安全技术的核心，密码学是以研究通信安全保密的学科，即研究对传输信息采用何种秘密的变换以防止第三者对信息的窃取。RSA公钥加密算法是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也十分流行。随着越来越多的商业应用和标准化工

5、作，RSA已经成为最具代表性的公钥加密技术。现今，网上交易加密连接、网上银行身份验证、各种信用卡使用的数字证书、智能移动电话和存储卡的验证功能芯片等，大多数使用RSA技术。1.2 课题的研究意义随着电子商务的发展，网络上资金的电子交换日益频繁，如何防止信息的伪造和欺骗成为非常重要的问题。目前关于数字签名的研究主要集中点是基于公钥密码体制的数字签名。手写签名的每一项业务都是数字签名的潜在用场。数字签名可以提供数据完整性、真实性和不可否认性。数字签名技术在身份识别和认证、数据完整性、抵赖等方面具有其它技术无法替代的作用，它在军事、电子商务和电子政务等领域有着极广泛的应用。而在公钥体制中，RSA是一

6、个较为完善的公钥密码算法，不仅能够同时用于加密和数字签名，而且易于理解和操作，是被广泛研究的公钥密码算法。因此，基于RSA的数字签名具有较强的研究性和实际应用意义。2 RSA算法和RSA数字签名算法的概念设计2.1 RSA算法的概念和原理2.1.1 RSA算法介绍RSA算法是一种公钥密码算法,实现RSA算法包括生成RSA密钥，加密和解密数据。RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法。RSA的缺点主要有：A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B)分组长度太大，为保证安全性，n 至少也要 600 bits。2.

7、1.2 RSA算法的实现原理1) 随机选择两个不同的素数p和q，它们的宽度是密钥宽度的二分之一。2) 计算出p和q的乘积n 。3) 在2和(n)之间随机选择一个数e , e 必须和(n)互素，整数e用做加密密钥（其中(n)=(p-1)*(q-1)）。4) 从公式ed 1 mod (n)中求出解密密钥d 。5) 得公钥（e ，n ）, 私钥 (d , n) 。6) 公开公钥，但不公开私钥。7) 将明文P (假设P是一个小于n的整数)加密为密文C，计算方法为：C = Pe mod n;8) 将密文C解密为明文P，计算方法为：P=Cd mod n;然而只根据n和e（不是p和q）要计算出d是不可能的。

8、因此，任何人都可对明文进行加密，但只有授权用户（知道d）才可对密文解密。2.2 RSA数字签名基本概念和RSA数字签名算法的实现原理2.2.1 RSA数字签名基本概念RSA数字签名体制使用了RSA公开密钥密码算法进行数字签名，鉴于RSA算法在实践中已经被证明了的安全性，RSA数字签名体制在许多安全标准中得以广泛应用。ISO/IEC 9796和ANSI X9.30-199X 以及美国联邦信息处理标准FIPS 186-2已经将RSA作为推荐的数字签名标准算法之一。RSA数字签名算法，包括签名算法和验证签名算法。它是利用的RSA算法的加密和解密算法的原理进行的一种数字签名，实际上是通过一个哈希函数来

9、实现的（本设计是通过的MD5算法）产生消息摘要MD来实现的所需加密的对象。数字签名的特点是它代表了消息的特征，消息如果发生改变，数字签名的值也将发生改变，不同的消息将得到不同的数字签名。安全的数字签名使接收方可以得到保证：消息确实来自发送方。因为签名的私钥只有发送方自己保存，他人无法做一样的数字签名，如果第三方冒充发送方发出一个消息，而接收方在对数字签名进行解密时使用的是发送方的公开密钥，只要第三方不知道发送方的私有密钥，加密出来的数字签名和经过计算的数字签名必然是不相同的，这就提供了一个安全的确认发送方身份的方法，即数字签名的真实性得到了保证。数字签名类似手书签名，它具有以下的性质：1）能够

10、验证签名产生者的身份，以及产生签名的日期和时间；2）能用于证实被签消息内容；3）数字签名可由第三方验证，从而能够解决通信双方的争议。为了满足数字签名的这些要求，例如，通信双方在发送消息时，既要防止接收方或其他第三方伪造，又要防止发送方因对自己的不利而否认，也就是说，为了保证数字签名的真实性。数字签名的原理是：（发送方和接收方根据要求各自产生自己的一对公钥和私钥）1）被发送文件采用某种算法对原始消息进行运算，得到一个固定长度的数字串，称为消息摘要（MD），不同的消息得到的消息摘要各异，但是对相同的消息它的消息摘要却是唯一的；2）发送方生成消息的消息摘要，用自己的私钥对摘要进行加密来形成发送方的数

11、字签名；3）这个数字签名将作为消息的附件和消息一同用接收方的公钥进行加密，将加密后的密文一起发送给接收方；4）接收方首先把接收到的密文用自己的私钥解密，得到原始消息和数字签名，再用发送方的公钥解密数字签名，随后用同样的算法计算出消息摘要；5）如果计算出来的消息摘要和发送方发送给他的消息摘要（通过解密数字签名得到的）是相同的，这样接收方就能确认数字签名确实是发送方的，否则就认为收到的消息是伪造的或是中途被篡改的。数字签名的原理图如2-1所示 A BEDED 用A的私钥加密 用B的公钥 用B的私钥 用A的公钥解密 数字签名 加密 解密 核实签名图2-1 数字签名的原理2.2.2 RSA数字签名算法

12、的实现原理RSA数字签名算法分为以下两个步骤： 1） 签名算法（包括两步：消息摘要计算，RSA加密）(1)消息摘要MD的计算： 消息在签名前首先通过MD5计算，生成128位的消息摘要 ；MD5函数是一种单向散列函数，它将任意长度的消息压缩成128位的消息摘要。应用MD5的单向性（即给定散列值,计算消息很难）和抗碰撞性(即给定消息M，要找到另一消息M并满足两者的散列值很难)，可以实现信息的完整性检验。另外该函数的设计不基于任何假设和密码体制而直接构造，执行的速度快，是一种被广泛认可的单向散列算法。(2)对MD作RSA加密算法：采用签名者的私钥加密消息摘要，得到加密后的字符串即数字签名；2）验证签

13、名算法 （RSA解密、对消息摘要计算和比较）验证签名算法包括两步：RSA解密得签名者的消息摘要，验证者对原消息计算摘要，比较两个消息摘要。验证签名的过程输入为消息，签名者的公钥，签名；输出为验证的结果，即是否是正确的签名。(1)RSA解密： 签名实际是加密的消息摘要，用以上所述的RSA解密方法采用签名者的公钥对这个加密的消息摘要解密，解密的结果应为128位的消息摘要。(2)消息摘要计算和比较： 验证者对消息用MD5算法重新计算，得到验证者自己的消息摘要。验证者比较解密得到的消息摘要和自己的消息摘要，如果两者相同，则验证成功，可以确认消息的完整性及签名确实为签名者的；否则，验证失败，确认签名被冒

14、充或是被篡改。3 RSA数字签名的逻辑设计与实现3.1 RSA数字签名的总体设计3.1.1 RSA数字签名所需实现的功能在本软件中需要实现的功能有以下几个：（1）生成RSA密钥：公钥ke=（e,n），私钥kd=(d,n)；（2）利用MD5算法计算出消息摘要MD；（3）数字签名的实现：用私钥d对消息摘要进行加密计算（RSA算法中的加密方法）；（4）验证数字签名：用公钥e对数字签名进行解密计算（RSA算法中的解密方法），得到的解密结果与(2)步计算出的消息摘要比较，如果两个消息摘要一样则签名成功。3.1.2 总体要求和设计本软件的总体要求有：1）按要求生成非对称密钥公钥和私钥；2）按任意写入的的消

15、息字符串(明文信息)生成所需要的消息摘要MD；3）在本设计中用产生的私钥d根据RSA算法的加密原理对所生成的消息摘要进行加密运算，得到数字签名；4）在本设计中用产生的公钥e根据RSA算法的解密原理对所加密的消息摘要即数字签名进行解密运算，得到对应的消息摘要（在本设计中标示的为解密信息），比较两个消息摘要，验证数字签名者的身份的真实与否；5）提示信息完整、操作舒适、图形界面雅观。本软件的总体设计都是基于C+的开发环境，采用的是Microsoft Visual c+ 6.0的运行环境。3.2 各部分的设计实现3.2.1 密钥产生的实现在密钥的产生部分中起决定性作用的是素数的选择，对随机数作素性检测

16、，若通过则为素数；否则增加一个步长后再做素性检测，直到找出素数。素性检测采用Fermat测试。这个算法的理论依据是费尔马小定理：如果m是一个素数，且a不是m的倍数，那么根据费尔马小定理有：a m-1=1 ( mod m)。 实际应用时：a m-1 = 1 ( mod m) a m = a ( mod m) a= a m ( mod m)， 因此对于整数m，只需计算a m ( mod m)，再将结果与a比较，如果两者相同，则m为素数。选取a=2，则a一定不会是任何素数的倍数。根据所选的素数的不同产生不同的密钥。密钥的理论产生模块流程图如图3-1所示：图3-1 密钥产生密钥产生的部分代码实现：CS

17、tring str;/第一步 产生任意素数GeneratePrimeNumbers();/第二步 计算 n=p*qm_n = m_Prime1 * m_Prime2;/第三步 0=(p-1)(q-1)m_Undef = (m_Prime1-1) * (m_Prime2-1);/第四步 选择eSelectE();/第五步 计算DCalculateD();/显示公钥和私钥/(1) 公钥 KU=e,nstr.Format(%d, %d,m_e,m_n);m_public_key.SetWindowText(str);/(2) 私钥KU=d,nstr.Format(%d, %d,m_d,m_n);m_

18、private_key.SetWindowText(str);/ 选择一个 e 使 e与 m_Undef互素/选择e的函数的实现SelectE() CString str;for(float i=2;i;i+)if(IsRelativePrime(float)m_Undef,(float)i)m_e=(long)i;return;/互为素数的函数的实现IsRelativePrime(float X,float Y) float R;/输入: X,Yif(XY)/如果X较小则交换两个值X=X+Y;Y=X-Y;X=X-Y;/在这时X总是比Y大for(;)if(Y=0) break;R=fmod(X

19、,Y);X=Y;Y=R;if(X != 1) return false;else return true;/互素/ 计算D的函数的实现CalculateD()float d;long d_dash;CString str;for(float k=1;k;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()CString str;UpdateData(TRUE);/通过以下两个函数可获得两个大素数，但增加了计算复杂性

20、，为了方便，直接给定素数/m_Prime1 = FindPrime(1);/m_Prime2 = FindPrime(m_Prime1);m_Prime1=47;m_Prime2=71;3.2.2 产生消息摘要的设计实现计算消息摘要的理论实现流程图如图3-2所示：得到消息摘要图3-2 消息摘要计算流程在以上流程图中其中循环处理块是最重要的一步，也是MD5的核心算法，在这一步中包括了：（1）把四个连接变量复制到了四个变量a,b,c,d中，使a=A，b =B，c =C，d=D；其中a,b,c,d组合成128位的寄存器，且在实际算法运算中保存中间结果和最终结果；（2）将当前的512位块分解为16个子

21、块，每个子块为32位；（3）要循环四轮，每一轮处理一个块中的16个子块，四轮的第一步进行不同的处理，其他的相同：每一轮有16个输入子块M0，M1，.M15，或表示为Mi，其中i为0-15；t是常量数组，包含64个元素，每个元素为32位，数组t表示为t1，t2，t64，或tk，k为1-64；MD5的循环四轮操作过程用下式表示： a=b+(a+proccessP(b,c,d)+Mi+Tk)s) (s表示循环左移s位)产生消息摘要的主要代码如下：int i;int Index;/初始化MD5所需常量Init(); /计算追加长度Append(WriteMessage.length();/对原始信息进

22、行补位for( i=0;im_AppendByte;i+)if(i=0) WriteMessage+=(unsigned char)0x80;else WriteMessage+=(unsigned char)0x0; /将原始信息长度附加在补位后 的数据后面for( i=0;i8;i+) WriteMessage+=m_MsgLeni;/位块数组unsigned char x64=0;/循环，将原始信息以64字节为一组拆分进行处理for( i=0,Index=-1;iWriteMessage.length();i+)x+Index=WriteMessagei;if(Index=63)Inde

23、x=-1;/将64字节位转换为16个字节Transform(x);/将寄存器ABCD的最终值转换为16进制返回给用户return ToHex(UpperCase);3.2.3 数字签名的设计实现 数字签名的理论实现流程图如图3-3所示，数字签名，就是通过在数据单元上附加数据，或对数据单元进行加密变换，从而使接收者可以确认数据来源和完整性。数字签名是防止他人对传输的文件进行破坏，以及确定发信人的身份的手段。数字签名中的加密算法就是应用的RSA加密原理，而它的验证算法则是应用的RSA解密原理。 结束图3-3 数字签名的实现流程RSA的加密、解密过程都为求一个整数的整数次幂，再取模。如果按其含义直接

24、计算，则中间结果非常大，有可能超出计算机所允许的整数取值范围。为了减小中间结果和提高加、解密运算中指数运算的有效性，本设计采用了快速指数算法。它的运算过程为（假如要算am mod n）：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才为该步的最终结果。数字签名主要实现过程的

25、代码如下： /消息摘要，8位为一组 一个字符一组char message200; /从文本框中得到消息摘要 m_message.GetWindowText(message,200);len=strlen(message); char showstr1000=;int NO_BITS=32;double c=0,d=1;char bits100;double n=(double)m_n;unsigned char ch;double data;/19;long i,k=NO_BITS;int sizeof_d=sizeof(double); /将十进制数私钥d转换为二进制D_to_B(m_d,3

26、2,bits);/得到合适的字节GetOnlyProperBits(bits);k=NO_BITS = strlen(bits)-1;for(int ii=0;ii=0;i-)c=2*c;d=fmod(d*d,n);if(bitsNO_BITS-i = 1)c=c+1;d=fmod(data*d,n);/ 从d中读取字符放入result中 resultii=d; /把字符串变为十六进制数后连接字符串 strcat(showstr,longtohex(d);/结束循环 /显示结果m_result.SetWindowText(showstr); /字符串变为16进制数的函数的实现longtohex

27、(long x) char str8; int i=0; /商 int a; /余数 int b; long tt=x; while(tt=16) a=tt/16; b=tt%16; switch(b) case 0 : stri=0; break; case 1 : stri=1; break; case 2 : stri=2; break; case 3 : stri=3; break; case 4 : stri=4; break; case 5 : stri=5; break; case 6 : stri=6; break; case 7 : stri=7; break; case 8

28、 : stri=8; break; case 9 : stri=9; break; case 10 : stri=A; break; case 11 : stri=B; break; case 12 : stri=C; break; case 13 : stri=D; break; case 14 : stri=E; break; case 15 : stri=F; break; ; i+; tt=a; stri=0; strrev(str); return str;3.2.4 验证数字签名的设计与实现图3-4 验证数字签名流程 验证数字签名的正确与成功性，主要是比较得到的两次消息摘要是否一样

29、，如果验证方用签名方的公钥解密得到消息摘要（即是本设计中得到的解密信息）和他自己计算得到的消息摘要（在本系统中为第一次计算得到的消息摘要）是一样的，则证明签名是正确的，没有被篡改或是冒充，验证签名的原理则是根据RSA的解密算法，具体的理论流程图如图3-4所示：（在本设计中签名和验证签名都在同一界面实现，不进行文件的双方传输）验证数字签名的过程时应用的解密算法是RSA的解密原理，而RSA的解密过程也应用了求一个整数的整数次幂，再取模的运算。在此也采用了快速指数算法，具体的算法过程同RSA的加密过程中应用的快速指数算法是一样的。验证数字签名主要实现过程的代码如下：int NO_BITS;doubl

30、e c=0,d=1;char bits100;double n=(double)m_n;double data;/19;long i,k; int sizeof_d=sizeof(double); /用于存储解密信息char message200; /将十进制数公钥e转换为二进制D_to_B(m_e,32,bits); GetOnlyProperBits(bits); k=NO_BITS = strlen(bits)-1;for(int j=0;j=0;i-)c=2*c;d=fmod(d*d,n);if(bitsNO_BITS-i = 1)c=c+1;d=fmod(data*d,n);/结束循

31、环/从d中读取字符放入message中 messagej=d; /显示结果m_mingwen.SetWindowText(message);3.2.5 RSA数字签名的运行结果图3-5 RSA数字签名的运行结果在本软件中得到二个消息摘要：根据写入的消息（明文信息）计算出来的消息摘要、解密数字签名得到的消息摘要（即是本设计中的解密信息）。如果两个消息摘要是一样的则证明RSA数字签名者的身份的真实性，从而实现了RSA数字签名。该系统的运行结果如图3-5所示。产生的消息摘要和解密得到的消息摘要（在此处是解密信息）是完全一样的，则证明了数字签名的真实性。4 软件的整体测试和分析改进4.1软件的整体测试

32、（1）测试密钥的生成：产生密钥的前提是要有两个素数的生成，密钥的产生依赖于素数的生成，素数生成不一样则密钥也会不相同，在本设计中素数是47和71，则相对应的的密钥是公钥（3，3337）和私钥（2147，3337）；（2）测试消息摘要MD的生成：写入的消息（明文信息）不一样得到消息摘要就有所区别，但是在产生消息摘要时所使用的计算方法是一样的即MD5算法，该算法的核心是其中的四轮循环，如果四轮循环中的一个细节出了问题则所产生的MD便是相差极远，如若明文信息是dfgfhfhgjk则得到的消息摘要A4127B4881D24B01AA07C17C ，若明文信息是cvnjj 则得到的消息摘要是A1E2C15FF4C9F4D407EF33D1AC56C632；（3）测试数字签名的生成：根据RSA算法的加密原理对不同的消息摘要MD进行加密运算，得到的便是不同的数字签名DS；若消息摘要MD是A1E2C15FF4C9F4D407EF33D1AC56C632 则得到的DS是DDDCFD6D36411F361F050，若消息摘要MD是66F753A8408C91EC0B16D91AA则得到的DS是1F1F98F2410D1F5931F366CDD61F236CD6DD6DC9350D；（4）测试数字签名的真实与否（验证数字签名）