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

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

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

3、和原理 4.2.1.1 RSA 算法介绍 4.2.1.2 RSA 算法的实现原理 4.2.2 RSA 数字签名基本概念和 RSA 数字签名算法的实现原理 5.2.2.1 RSA 数字签名基本概念 5.2.2.2 RSA 数字签名算法的实现原理 6.3 RSA 数字签名的逻辑设计与实现 7.3.1 RSA 数字签名的总体设计 7.3.1.1 RSA 数字签名所需实现的功能 7.3.1.2 总体要求和设计 7.3.2 各部分的设计实现 8.3.2.1 密钥产生的实现 8.3.2.2 产生消息摘要的设计实现 1.13.2.3 数字签名的设计实现 1.33.2.4 验证数字签名的设计与实现 1.63.

4、2.5 RSA 数字签名的运行结果 1.84 软件的整体测试和分析改进 1.94.1 软件的整体测试 1.94.2 性能分析与改进设想 2.0开发体会 2.0.参考文献 2.1.1 引言1.1 课题的研究背景随着电子信息技术的迅速发展， 人类已步入信息社会。 但是由于整个社会形 成了一个巨大的计算机网络， 任何一个计算机网络出现的安全问题， 都会影响整 个国家的网络安全， 所以信息安全、 计算机网络安全问题已引起了人类的高度重 视。网络的安全措施应是能全方位地针对各种不同的威胁和脆弱性， 这样才能确 保网络信息的保密性、完整性和可用性。现代密码学已成为信息安全技术的核心， 密码学是以研究通信安

5、全保密的学 科，即研究对传输信息采用何种秘密的变换以防止第三者对信息的窃取。RSA公钥加密算法是第一个既能用于数据加密也能用于数字签名的算法。 它 易于理解和操作，也十分流行。随着越来越多的商业应用和标准化工作， RSA已 经成为最具代表性的公钥加密技术。 现今，网上交易加密连接、 网上银行身份验 证、各种信用卡使用的数字证书、 智能移动电话和存储卡的验证功能芯片等， 大 多数使用RSA技术。1.2 课题的研究意义随着电子商务的发展， 网络上资金的电子交换日益频繁， 如何防止信息的伪 造和欺骗成为非常重要的问题。 目前关于数字签名的研究主要集中点是基于公钥 密码体制的数字签名。 手写签名的每一

6、项业务都是数字签名的潜在用场。 数字签 名可以提供数据完整性、 真实性和不可否认性。 数字签名技术在身份识别和认证、 数据完整性、 抵赖等方面具有其它技术无法替代的作用， 它在军事、电子商务和 电子政务等领域有着极广泛的应用。 而在公钥体制中，RSA是一个较为完善的公 钥密码算法， 不仅能够同时用于加密和数字签名， 而且易于理解和操作， 是被广 泛研究的公钥密码算法。因此，基于RSA的数字签名具有较强的研究性和实际应 用意义。2 RSA 算法和 RSA 数字签名算法的概念设计2.1 RSA 算法的概念和原理2.1.1 RSA 算法介绍RSA算法是一种公钥密码算法，实现RSA算法包括生成RSA密

7、钥，加密和解密 数据。RSA算法是第一个能同时用于加密和数字签名的算法， 也易于理解和操作。 RSA是被研究得最广泛的公钥算法。RSA的缺点主要有：A）产生密钥很麻烦，受到素数产生技术的限制，因而难 以做到一次一密。B）分组长度太大，为保证安全性，n至少也要600 bits。2.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 O（n）中求出解密密钥d。5）得公钥（ e

8、， n ） , 私钥 （d , n） 。6）公开公钥，但不公开私钥。7）将明文P （假设P是一个小于n的整数）加密为密文C,计算方法为：C = PAe mod n;8）将密文C解密为明文P,计算方法为：P=CAd mod n;然而只根据n和e （不是p和q）要计算出d是不可能的。因此，任何人都可对 明文进行加密，但只有授权用户（知道 d）才可对密文解密。2.2 RSA 数字签名基本概念和 RSA 数字签名算法的实现原理2.2.1 RSA 数字签名基本概念RSA数字签名体制使用了 RSA公开密钥密码算法进行数字签名， 鉴于RSA算 法在实践中已经被证明了的安全性，RSA数字签名体制在许多安全标准

9、中得以广 泛应用。ISO/IEC 9796和ANSI X9.30-199X 以及美国联邦信息处理标准 FIPS 186-2已经将RSA作为推荐的数字签名标准算法之一。RSA数字签名算法，包括签名算法和验证签名算法。 它是利用的RSA算法的 加密和解密算法的原理进行的一种数字签名， 实际上是通过一个哈希函数来实现 的（本设计是通过的 MD5 算法）产生消息摘要 MD 来实现的所需加密的对象。数字签名的特点是它代表了消息的特征， 消息如果发生改变， 数字签名的值 也将发生改变， 不同的消息将得到不同的数字签名。 安全的数字签名使接收方可 以得到保证： 消息确实来自发送方。 因为签名的私钥只有发送方

10、自己保存， 他人 无法做一样的数字签名， 如果第三方冒充发送方发出一个消息， 而接收方在对数 字签名进行解密时使用的是发送方的公开密钥， 只要第三方不知道发送方的私有 密钥，加密出来的数字签名和经过计算的数字签名必然是不相同的， 这就提供了 一个安全的确认发送方身份的方法，即数字签名的真实性得到了保证。数字签名类似手书签名，它具有以下的性质：1 ）能够验证签名产生者的身份，以及产生签名的日期和时间；2）能用于证实被签消息内容；3）数字签名可由第三方验证，从而能够解决通信双方的争议。 为了满足数字签名的这些要求， 例如，通信双方在发送消息时， 既要防止接收方或其他第三方伪造， 又要防止发送方因对

11、自己的不利而否认， 也就是说， 为 了保证数字签名的真实性。数字签名的原理是：（发送方和接收方根据要求各自产生自己的一对公钥和 私钥）1）被发送文件采用某种算法对原始消息进行运算，得到一个固定长度的数 字串，称为消息摘要（MD ），不同的消息得到的消息摘要各异，但是对相同的 消息它的消息摘要却是唯一的；2）发送方生成消息的消息摘要，用自己的私钥对摘要进行加密来形成发送 方的数字签名；3 ）这个数字签名将作为消息的附件和消息一同用接收方的公钥进行加密， 将加密后的密文一起发送给接收方；4）接收方首先把接收到的密文用自己的私钥解密，得到原始消息和数字签 名，再用发送方的公钥解密数字签名，随后用同样

12、的算法计算出消息摘要；5）如果计算出来的消息摘要和发送方发送给他的消息摘要（通过解密数字 签名得到的）是相同的，这样接收方就能确认数字签名确实是发送方的， 否则就 认为收到的消息是伪造的或是中途被篡改的。数字签名的原理图如2-1所示AB用A的私钥加密用B的公钥用B的私钥用A的公钥解密数字签名加密解密核实签名图2-1数字签名的原理222 RSA数字签名算法的实现原理RSA数字签名算法分为以下两个步骤：1）签名算法（包括两步：消息摘要计算， RSA加密）消息摘要MD的计算：消息在签名前首先通过MD5计算，生成128位的消息摘要；MD5函数是一种单向散列函数，它将任意长度的消息压缩成128位的消息摘

13、要。应用MD5的单向性（即给定散列值，计算消息很难）和抗碰撞性（即 给定消息M，要找到另一消息M 并满足两者的散列值很难），可以实现信息的 完整性检验。另外该函数的设计不基于任何假设和密码体制而直接构造，执行的速度快，是一种被广泛认可的单向散列算法。（2）对MD作RSA加密算法：采用签名者的私钥加密消息摘要，得到加密后的 字符串即数字签名；2）验证签名算法 （RSA解密、对消息摘要计算和比较）验证签名算法包括两步：RSA解密得签名者的消息摘要，验证者对原消息计 算摘要，比较两个消息摘要。 验证签名的过程输入为消息， 签名者的公钥， 签名； 输出为验证的结果，即是否是正确的签名。RSA解密： 签

14、名实际是加密的消息摘要，用以上所述的 RSA解密方法 采用签名者的公钥对这个加密的消息摘要解密， 解密的结果应为 128位的消息摘 要。（2）消息摘要计算和比较： 验证者对消息用 MD5 算法重新计算， 得到验证者 自己的消息摘要。 验证者比较解密得到的消息摘要和自己的消息摘要， 如果两者 相同，则验证成功，可以确认消息的完整性及签名确实为签名者的；否则，验证 失败，确认签名被冒充或是被篡改。3 RSA 数字签名的逻辑设计与实现3.1 RSA 数字签名的总体设计3.1.1 RSA 数字签名所需实现的功能在本软件中需要实现的功能有以下几个：（1）生成 RSA密钥：公钥 ke= （ e,n），私钥

15、 kd=（d,n）；（2）利用 MD5 算法计算出消息摘要 MD ；（3）数字签名的实现：用私钥d对消息摘要进行加密计算（RSA算法中的 加密方法）；（4）验证数字签名：用公钥e对数字签名进行解密计算（RSA算法中的解密 方法），得到的解密结果与 （2）步计算出的消息摘要比较，如果两个消息摘要一 样则签名成功。3.1.2 总体要求和设计本软件的总体要求有：1 ）按要求生成非对称密钥公钥和私钥；2）按任意写入的的消息字符串 （明文信息 ）生成所需要的消息摘要 MD ；3）在本设计中用产生的私钥d根据RSA算法的加密原理对所生成的消息摘 要进行加密运算，得到数字签名；4）在本设计中用产生的公钥e根

16、据RSA算法的解密原理对所加密的消息摘要 即数字签名进行解密运算， 得到对应的消息摘要（在本设计中标示的为解密信息） 比较两个消息摘要，验证数字签名者的身份的真实与否；5）提示信息完整、操作舒适、图形界面雅观。本软件的总体设计都是基于 C+ 的开发环境，采用的是 Microsoft Visual c+ 6.0 的运行环境。3.2各部分的设计实现3.2.1密钥产生的实现在密钥的产生部分中起决定性作用的是素数的选择，对随机数作素性检测，若通过则为素数；否则增加一个步长后再做素性检测，直到找出素数。素性检测 采用Fermat测试。这个算法的理论依据是费尔马小定理：如果m是一个素数，且a不是m的倍数，

17、那么根据费尔马小定理有：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密钥产生密钥产生的部分代码实现：CStri ng str;/第一步产生任意素数Gen eratePrimeNumbers();/第二步计算n=p*qm_n = m_Prime1 * m_Prime

18、2;/ 第三步 O=(p-1)(q-1)m_U ndef = (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_private_key.SetWindowText(str);/ 选择一个 e 使 e 与 m_Undef 互素/选择e的函数的实现SelectE(

19、) CString str;for(float i=2;i100000;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,Y);X=Y;Y=R;if(X != 1)return false;elsereturn true;/ 互素/计算D的函数的

20、实现CalculateD()float d;long d_dash;CString str;for(float k=1;k100000;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);/通过以下两个函数可获得两个大素数，但增加了计算复杂性，为了方便, 直接给定素数/m_Prime1 = Fi ndPrime(1);/m_Prime2 = Fin dPr

21、ime(m_Prime1);m_Prime1=47;m_Prime2=71;3.2.2产生消息摘要的设计实现计算消息摘要的理论实现流程图如图3-2所示:初始化MD5所需的常量1!计算所需的追加长度1T对原始信息进行补位1T将输入分成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个子块，

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

23、.length();/ 对原始信息进行补位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=WriteM

24、essagei;if(Index=63)Index=-1;/ 将64 字节位转换为 16个字节Transform(x);/将寄存器ABCD的最终值转换为16进制返回给用户return T oHex（UpperCase）;323数字签名的设计实现数字签名的理论实现流程图如图3-3所示，数字签名，就是通过在数据单元 上附加数据，或对数据单元进行加密变换，从而使接收者可以确认数据来源和完 整性。数字签名是防止他人对传输的文件进行破坏，以及确定发信人的身份的手 段。数字签名中的加密算法就是应用的RSA加密原理，而它的验证算法则是应用 的RSA解密原理。得到消息摘要MD1F用私钥d加密MD1f得到数字签

25、名图3-3数字签名的实现流程RSA的加密、解密过程都为求一个整数的整数次幕，再取模。如果按其含义直接计算，则中间结果非常大，有可能超出计算机所允许的整数取值范围。为了减小中间结果和提高加、解密运算中指数运算的有效性，本设计采用了快速指 数算法。它的运算过程为（假如要算 aAm 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 ) 若 二 进 制

26、 数 是 1, 则 在 上 面 的 运 算 后 继 续 以 下 运 算 ： c=c+1;d=fmod(d*a,n); 得到的结果 d 才为该步的最终结果。数字签名主要实现过程的代码如下：/ 消息摘要， 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;d

27、ouble data;/19;long i,k=NO_BITS;int sizeof_d=sizeof(double);/ 将十进制数私钥 d 转换为二进制D_to_B(m_d,32,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;/ 把字符串变为十六进制数后连接字符串 st

28、rcat(showstr,longtohex(d);/ 结束循环/ 显示结果 m_result.SetWindowText(showstr);/ 字符串变为 16 进制数的函数的实现 longtohex(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

29、; break;case 5 : stri=5; break;case 6 : stri=6; break;case 7 : stri=7; break;case 8 : 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); r

30、eturn str;3.2.4 验证数字签名的设计与实现开始图3-4验证数字签名流程验证数字签名的正确与成功性，主要是比较得到的两次消息摘要是否一样， 如果验证方用签名方的公钥解密得到消息摘要（即是本设计中得到的解密信息） 和他自己计算得到的消息摘要（在本系统中为第一次计算得到的消息摘要）是一 样的，则证明签名是正确的，没有被篡改或是冒充，验证签名的原理则是根据 RSA的解密算法，具体的理论流程图如图 3-4所示：（在本设计中签名和验证签 名都在同一界面实现，不进行文件的双方传输）验证数字签名的过程时应用的解密算法是 RSA的解密原理，而RSA的解密过 程也应用了求一个整数的整数次幕，再取模的

31、运算。在此也采用了快速指数算法， 具体的算法过程同RSA的加密过程中应用的快速指数算法是一样的。验证数字签名主要实现过程的代码如下：int NO_BITS;double 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(

32、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);/ 结束循环/从d中读取字符放入 message中 messagej=d;/ 显示结果m_mingwen.SetWindowText(message);3.2.5 RSA 数字签名的运行结果图3-5RSA数字签名的运行结果在本软件中得到二个消息摘要：根据写入的消息（明文信息）计算出来的消 息摘要、解密数字签名得到的消息摘要（即是本设计中的解密信息）。如果两个 消息摘要是一样的则证明RSA数字签名者的身份的真实性，从而实现了 RSA数字 签

33、名。该系统的运行结果如图3-5所示。产生的消息摘要和解密得到的消息摘要 （在此处是解密信息）是完全一样的，则证明了数字签名的真实性。4软件的整体测试和分析改进4.1软件的整体测试（1 ）测试密钥的生成：产生密钥的前提是要有两个素数的生成，密钥的产 生依赖于素数的生成，素数生成不一样则密钥也会不相同，在本设计中素数是 47和71，则相对应的的密钥是公钥（3，3337 ）和私钥（2147，3337）；（2）测试消息摘要MD的生成：写入的消息（明文信息）不一样得到消息摘要就有所区别，但是在产生消息摘要时所使用的计算方法是一样的即MD5算法，该算法的核心是其中的四轮循环，如果四轮循环中的一个细节出了问

34、题则所 产生的MD便是相差极远，如若明文信息是dfgfhfhgjk贝U得到的消息摘要A4127B4881D24B01A85696477A07C17C，若明文信息是 cvnjj 则得到的消息摘要是 A1E2C15FF4C9F4D407EF33D1AC56C632;（3） 测试数字签名的生成：根据 RSA算法的加密原理对不同的消息摘要 MD进行加密运算，得到的便是不同的数字签名DS;若消息摘要 MD 是 A1E2C15FF4C9F4D407EF33D1AC56C632则得到的 DS 是DD6865036D64198985366C98523593F286980023D6D36411F361F050 ，若消息摘要 MD 是 66F753A8408C91EC0B16D91A1100902A则得到的 DS 是 1F1F98F2410D1F5931F366CD686369371D61F236CD6DD6D693936C935 0D；（4）测试数字签名的真实与否（验证数字签名）：根据 RSA 算法的解密原 理对