《密码学报告讲解.doc》由会员分享，可在线阅读，更多相关《密码学报告讲解.doc（16页珍藏版）》请在三一办公上搜索。
1、基于RSA的数字签名的设计与实现摘 要随着计算机网络和信息技术的发展，信息安全在各领域发挥着越来越重要的作用，其中密码学已成为信息安全技术的核心，本文主要介绍了信息加密技术的应用。 RSA算法是目前公认的在理论和实际应用中最为成熟和完善的一种公钥密码体制，它是第一个既能用于数据加密也能用于数字签名的算法，是公钥密码体制的代表。数字签名是起到身份认证、核准数据完整性的一种信息安全技术。它通过认证技术来辨认真伪。RSA数字签名体制使用的是RSA公开密钥密码算法进行数字签名。本文主要研究的内容包括：第一,对RSA算法进行了全面系统的介绍，包括RSA算法的应用现状和原理大素数的产生、密钥对的产生、对明
2、文的加密运算和密文的解密运算，为具体实现打下了理论基础；第二,介绍了RSA数字签名的一些基本概念和数字签名的理论实现过程；第三，详述了RSA数字签名的设计与实现，主要实现的模块包括RSA密钥的产生（一对公钥和私钥），RSA加密算法和解密算法的实现，消息摘要MD的生成以及利用RSA算法实现数字签名和签名的验证；第四,对该系统进行了整体的测试和分析改进；第五，分析了RSA数字签名的安全性，指出了RSA数字签名的发展方向。关键字：RSA算法 加密 解密 RSA数字签名一、课程设计目的1.1 研究背景随着电子信息技术的迅速发展，人类已步入信息社会。但是由于整个社会形成了一个巨大的计算机网络，任何一个计
3、算机网络出现的安全问题，都会影响整个国家的网络安全，所以信息安全、计算机网络安全问题已引起了人类的高度重视。无论是在局域网还是在广域网中，都存在着自然和人为等诸多因素的脆弱性和潜在威胁。故此，网络的安全措施应是能全方位地针对各种不同的威胁和脆弱性，这样才能确保网络信息的保密性、完整性和可用性。针对网络安全的威胁主要有三方面：（1）人为的无意失误；（2）人为的恶意攻击；（3）网络软件的漏洞和“后门”。现代密码学已成为信息安全技术的核心，密码学是以研究通信安全保密的学科，即研究对传输信息采用何种秘密的变换以防止第三者对信息的窃取。密码学包括两个分支：密码编码学和密码分析学。密码编码学主要研究对信息
4、进行交换，以保护信息在信道的传递过程中不被他人窃取、解密和利用的方法，而密码分析学则与密码编码学相反，它主要研究如何分析和破译密码。两者之间既相互对立又相互促进。密码体制的分类有很多，其中一种是根据加密算法和解密算法所使用的密钥是否相同，可以将密码体制分为对称密钥密码体制（单钥密码体制）和非对称密钥密码体制（公钥密码体制），这两种密码体制各有自己的长处和短处，因此现在采用了两种的混合体，如PGP。 公钥密码体制的特点是：接收方B产生一对密钥（PK和）；公开，保密；从推出是很困难的；、双方通信时，通过任何途径取得的公钥，用的公钥加密信息，加密后的信息可通过任何不安全信道发送。收到密文信息后，用自
5、己私钥解密恢复出明文。公钥密码体制已成为确保信息的安全性的关键技术。RSA公钥密码体制到目前为止还是一种被认可为安全的体制。RSA公钥加密算法是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也十分流行。算法的名字以发明者的姓氏首字母命名：Ron Rivest, Adi Shamir 和Leonard Adleman。虽然自1978年提出以来，RSA的安全性一直未能得到理论上的证明，但它经历了各种攻击，至今（2006年）未被完全攻破。随着越来越多的商业应用和标准化工作，RSA已经成为最具代表性的公钥加密技术。VISA、MasterCard、IBM、Microsoft等公司协力制
6、定的安全电子交易标准（Secure Electronic Transactions，SET）就采用了标准RSA算法，这使得RSA在我们的生活中几乎无处不在。网上交易加密连接、网上银行身份验证、各种信用卡使用的数字证书、智能移动电话和存储卡的验证功能芯片等，大多数使用RSA技术。1.2 研究意义随着电子商务的发展，网络上资金的电子交换日益频繁，如何防止信息的伪造和欺骗成为非常重要的问题。在计算机通信系统中，维护电子文档的安全也成为至关重要和非常敏感的问题。为保护信息的安全，数字签名应运而生，它是现代密码学主要研究的内容之一。目前关于数字签名的研究主要集中点是基于公钥密码体制的数字签名。在公钥密码
7、体制中，解密和加密密钥不同，解密和加密可分离，通信双方无须事先交换密钥就可建立起保密通信，因此它较好地解决了传统密码体制在网络通信中出现的问题。手写签名的每一项业务都是数字签名的潜在用场。数字签名可以提供数据完整性、真实性和不可否认性。因而当需要对某一实体进行认证、传输具有有效性的密钥以及进行密钥分配时，便可以借助数字签名来完成任务。数字签名技术在身份识别和认证、数据完整性、抵赖等方面具有其它技术无法替代的作用，它在军事、电子商务和电子政务等领域有着极广泛的应用。而在公钥体制中，RSA是一个较为完善的公钥密码算法，不仅能够同时用于加密和数字签名，而且易于理解和操作，是被广泛研究的公钥密码算法。
8、因此，基于RSA的数字签名具有较强的研究性和实际应用意义。二、 RSA算法和RSA数字签名算法的基本概念和原理2.1 RSA算法的基本概念和原理2.1.1 RSA算法介绍与应用现状RSA算法是一种公钥密码算法,实现RSA算法包括生成RSA密钥，加密和解密数据。RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能
9、如何，而且密码学界多数人士倾向于因子分解不是NP-C问题。RSA的缺点主要有：A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B)分组长度太大，为保证安全性，n 至少也要 600 bits。RSA算法的时间复杂性取决于它所设计的几个基本运算的时间复杂性。密钥生成过程时间主要是生成随机素数的时间及计算公钥和私钥的模乘法的时间。生成随机素数的时间在于完成对随机大数的Fermat测试的时间，Fermat测试的时间复杂度为O(log2n)3)，n所测试的整数。模乘法的计算方法采取先计算两个数的乘积，再取模n，时间复杂性为O(log2n)2)。 RSA加密解密计算的时间主要是模幂运算的
10、时间，即形式为xc mod n的函数的运算时间。模幂算法采取平方乘算法，设l是c的长度，则计算xc mod n至多需要2l次模乘法，因为 1log2n+1,所以模幂运算能在时间O(log2n)3)内完成。因此，RSA的加密和解密均可在多项式时间内完成。RSA公开密钥加密算法自20世纪70年代提出以来，已经得到了广泛认可和应用。发展至今，电子安全领域的各方面已经形成了较为完备的国际规范。RSA作为最重要的公开密钥算法，在各领域的应用数不胜数。RSA在硬件方面，以技术成熟的IC应用于各种消费类电子产品。RSA在软件方面的应用，主要集中在Internet上、加密连接、数字签名和数字证书的核心算法广泛
11、使用RSA。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 (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）要计算
12、出d是不可能的。因此，任何人都可对明文进行加密，但只有授权用户（知道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算法的加密和解密算法的原理进行的一种数字签名，实际上是通
13、过一个哈希函数来实现的（本设计是通过的MD5算法）产生消息摘要MD来实现的所需加密的对象。数字签名的特点是它代表了消息的特征，消息如果发生改变，数字签名的值也将发生改变，不同的消息将得到不同的数字签名。安全的数字签名使接收方可以得到保证：消息确实来自发送方。因为签名的私钥只有发送方自己保存，他人无法做一样的数字签名，如果第三方冒充发送方发出一个消息，而接收方在对数字签名进行解密时使用的是发送方的公开密钥，只要第三方不知道发送方的私有密钥，加密出来的数字签名和经过计算的数字签名必然是不相同的，这就提供了一个安全的确认发送方身份的方法，即数字签名的真实性得到了保证。数字签名通过认证技术来辨认真伪。
14、认证技术主要包括数字签名认证、身份认证以及公开密钥证明等。数字签名认证机制提供了一种对数字签名进行鉴别的方法；身份认证机制提供了辨别和确认通信双方真实身份的方法；公开密钥证明机制则对密钥进行验证。网络时代中，人们验证数字签名来确定你正在和谁打交道，验证你的文件是否已被黑客篡改。数据的安全性和真实性已成为网络安全中至关重要的一部分。数字签名类似手书签名，它具有以下的性质：1）能够验证签名产生者的身份，以及产生签名的日期和时间；2）能用于证实被签消息内容；3）数字签名可由第三方验证，从而能够解决通信双方的争议。为了实现数字签名的以上性质，它就应满足下列要求：1）签名是可信的：任何人都可以验证签名的
15、有效性；2）签名是不可伪造的：除了合法的签名者外，任何人伪造其签名是困难的；3）签名是不可复制的：对一个消息的签名不能通过复制变为另一个消息的签名。如果一个消息的签名是从别处复制得到的，则任何人都可以发现消息与签名之间的不一致性，从而可以拒绝签名的消息；4）签名的消息是不可改变的：经签名的消息不能篡改，一旦签名的消息被篡改，任何人都可以发现消息与签名之间的不一致性；5）签名是不可抵赖的：签名者事后不能否认自己的签名。可以由第三方或仲裁方来确认双方的信息，以做出仲裁。为了满足数字签名的这些要求，例如，通信双方在发送消息时，既要防止接收方或其他第三方伪造，又要防止发送方因对自己的不利而否认，也就是
16、说，为了保证数字签名的真实性。数字签名的原理是：（发送方和接收方根据要求各自产生自己的一对公钥和私钥）1）被发送文件采用某种算法对原始消息进行运算，得到一个固定长度的数字串，称为消息摘要（MD），不同的消息得到的消息摘要各异，但是对相同的消息它的消息摘要却是唯一的；2）发送方生成消息的消息摘要，用自己的私钥对摘要进行加密来形成发送方的数字签名；3）这个数字签名将作为消息的附件和消息一同用接收方的公钥进行加密，将加密后的密文一起发送给接收方；4）接收方首先把接收到的密文用自己的私钥解密，得到原始消息和数字签名，再用发送方的公钥解密数字签名，随后用同样的算法计算出消息摘要；5）如果计算出来的消息摘
17、要和发送方发送给他的消息摘要（通过解密数字签名得到的）是相同的，这样接收方就能确认数字签名确实是发送方的，否则就认为收到的消息是伪造的或是中途被篡改的。数字签名的原理图如2-1所示图2-1 数字签名的原理简图2.2.2 RSA数字签名算法的实现原理一个数字签名由两部分组成：签名算法和验证算法。签名算法是产生数字签名的某种算法，而验证算法是检验一个数字签名是否有效（即是否由指定实体生成）的某种算法。例如A能够使用一个签名算法sign来为消息m签名，签名结果sign（m）随后能够使用一个公开的验证算法ver得到验证，验证算法根据签名是否有效而返回“真”或“假”。数字签名的形式化定义：（1）系统初始
18、化系统初始化产生签名方案的基本参数（M，S，K，Sign，Ver），其中，M为消息空间，S为签名空间，K为密钥空间，包含私钥和公钥，Sign为签名算法的集合，Ver为签名验证算法集合。（2）签名产生过程对每一个k =（k1，k2）K，其中k1是公钥，k2是私钥，有签名算法signk2Sign，signk2：MS。对任意的消息mM，有s =signk2（m），且sS，那么s为消息的签名，将签名消息组（m，s）发送给签名验证者。（3）签名验证过程对于上述的k1K，有相应的签名验证算法：verk1：MSTRUE，FALSE，verk1Ver。签名验证者受到（m,s）后，计算verk1（m，s），若v
19、erk1（m，s）=TRUE，则签名有效；否则签名无效。对于每一个kK，签名signk2和签名验证函数verk1是容易计算的。一般情况下，signk2可以公开也可以不公开，并且在签名算法中要求保证私钥的安全性；而验证函数verk1是公开的，同时还要求对任意的消息m，从集合S中计算s使得verk1（m，s）=True是非常困难的，也就是说，攻击者对消息m产生有效的签名s是不可能的。三、 RSA数字签名的设计与实现3.1 RSA数字签名的总体设计3.1.1 RSA数字签名所需实现的功能在本软件中需要实现的功能有以下几个：（1）生成RSA密钥：公钥ke=（e,n），私钥kd=(d,n)；（2）利用H
20、ash函数算法计算出消息摘要MD；（3）数字签名的实现：用私钥d对消息摘要进行加密计算（RSA算法中的加密方法）；（4）验证数字签名：用公钥e对数字签名进行解密计算（RSA算法中的解密方法），得到的解密结果与(2)步计算出的消息摘要比较，如果两个消息摘要一样则签名成功。3.2 各部分的设计实现3.2.1 密钥产生的实现在密钥的产生部分中起决定性作用的是素数的选择，对随机数作素性检测，若通过则为素数；否则增加一个步长后再做素性检测，直到找出素数。素性检测采用Fermat测试。这个算法的理论依据是费尔马小定理：如果m是一个素数，且a不是m的倍数，那么根据费尔马小定理有：a m-1=1 ( mod
21、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所示：产生任意素数p和q计算n=p*q计算t=(p-1)(q-1)选择e作为公钥计算d作为私钥图3-1 密钥产生3.2.2数字签名的设计实现 数字签名的理论实现流程图如图3-2所示，数字签名，就是通过在数据单元上附加数据，或对数据单元进行加密变换，从而使接收者可以确认
22、数据来源和完整性。数字签名是防止他人对传输的文件进行破坏，以及确定发信人的身份的手段。数字签名中的加密算法就是应用的RSA加密原理，而它的验证算法则是应用的RSA解密原理。结束开始得到数字签名S得到消息摘要M用私钥d 加密M验证数字签名S图3-2 数字签名的实现流程四、 课程设计分析4.1 RSA数字签名的安全性分析对于一个完整的数字签名系统而言，安全性是其要求的第一位，RSA体制的安全性决定于RSA公开密钥密码算法的安全性，在设计RSA数字签名系统时为了保证其安全性，应注意以下几个问题：1）根据被加密文件的重要程度和加密时间的要求来选择n的长度。因为RSA的安全性则是依赖于分解大素数的难度。
23、随机选择足够大且相互之间差别比较大的素数p和q来提高系统的安全性（目前应在512位以上），解密密钥d相对模 n 不应过小。因为若d达到n的1/4大小，且 e比n 小，则有方法可以恢复d；2）在使用RSA的通信网络协议中，不应该使用公共模 n ，这是因为已经知道了对于一个加密/解密密钥指数对，攻击者就能分解这个模，也就可以不分解n 来计算出别的加密/解密对；3）不要让攻击者得到原始的解密结果；4）相关的消息不要用相同的密钥加密；5）在实际运用中不要对一个陌生人提交的随机消息解密，不对自己一无所知的信息签名，要先利用一个单向散列函数对消息进行散列hash（MD5）处理，尽管Hash（MD5） 算法
24、是公开的，但是根据hash（MD5）值计算出明文在统计学上是不可能的。因此仅重视RSA的实现是不够的，实现细节也很重要。总之，对一个数字签名系统而言，重要的是从整体上研究，而不应局限于系统的一部分。仅有一个安全的算法是不够的，整个密码系统必须是安全的。4.2 RSA数字签名的前景展望基于RSA算法的数字签名在2000年的第六届国际密码学会议上被推荐为公钥密码系统的加密算法中的一种，则RSA数字签名有较好的发展空间。对于未来的加密、生成和验证数字签名的工具还需完善，只有用SSL（安全套接层）建立安全连接的Web浏览器，才会频繁使用数字签名，公司要对其员工在网络上的行为进行规范，就要建立广泛协作机
25、制来支持数字签名，支持数字签名是Web发展的目标，确保数据保密性、数据完整性和不可否认性才能保证在线商业的安全交易。和数字签名有关的复杂认证能力就像现在操作、应用环境中的口令保护一样直接做进操作系统环境、应用、远程访问产品、信息系统等中，像Microsoft支持X.509的Internet Explorer4.0客户机软件及支持对象签名检查的JAVA虚拟机等。数字签名作为一项信息加密和安全传送技术，越来越得到人们的重视，其中它涉及到的关键技术也很多，并且很多新的协议，如网上交易安全协议SSL、SET协议都会涉及到数字签名，因此数字签名将得到广泛的应用和人们的首选。但是运用越来越广泛的网络安全技
26、术数字签名，今后也很可能导致毫无私密可言。五、 程序清单及注释#includeint mod(int a,int b,int c) /进行模运算 int s=1; b=b+1; while(b!=1) s=s*a; s=s%c; b-; return s;int gcd(int x,int y) /判断两个数是否为素数 int t; while(y) t=x; x=y; y=t%y; if(x=1) return 0; else return 1;int main() int p,q,e,d,n,t,m,i,h,s,c,y,x; printf(基于RSA的数字签名方案n); printf(1.
27、初始化n); printf(请输入两个素数p,q:); scanf(%d%d,&p,&q); n=p*q; /计算得到n printf(计算得n为%3dn,n); t=(p-1)*(q-1); /欧拉函数t printf(计算得t为%3dn,t); printf(请输入公钥e:); scanf(%d,&e); if(et|gcd(e,t) /判断输入的随机数e是否合格 printf(e不合要求，请重新输入:); scanf(%d,&e); d=1; while(e*d)%t)!=1) d+; /得到私钥d printf(经计算d为%dn,d); printf(=); printf(=n); p
28、rintf(初始化完成!n); printf(公钥为(n=%d,e=%d)n,n,e); printf(私钥为%dn,d); printf(=); printf(=n); printf(2.签名过程n); printf(请输入带签名的消息m:); scanf(%d,&m); h=m; /哈希函数得消息的值 s=mod(h,d,n); /模运算得到数字签名s c=mod(m,e,n); /模运算得到密文c printf(经计算s为%dn,s); printf(经计算c为%dn,c); printf(=); printf(=n); printf(签名过程完成!n); printf(加密后密文为:%
29、dn,c); printf(数字签名为:%dn,s); printf(=); printf(=n); printf(3.验证过程); printf(请输入密文c:); scanf(%d,&c); m=mod(c,d,n); printf(请输入数字签名s:); scanf(%d,&s); y=mod(s,e,n); /计算se mod n x=mod(h,1,n); /计算h(m) mod n printf(经计算m为%dn,m); printf(经计算x为%dn,x); printf(经计算y为%dn,y); printf(=); printf(=n); printf(3.验证过程完成!n)
30、; printf(解密后原文为:%dn,m); if(x=y) /验证过程， printf(由于x与y相等!n); printf(验证成功，签名有效!n); else printf(由于x与y不相等!n); printf(验证失败，签名无效!n); 六、 运行结果及分析七、 心得体会随着互联网的迅猛发展，当前信息技术的快速发展和信息交换的大量增加，尤其是在电子商务的出现，网络信息安全越来越受到人们的关注。网络信息安全包括两个方面：一是信息的完整性，数据不能被任何第三方破坏和修改。二是要保证信息的统一性，接受方要确认信息的来源。而在电子商务中，合同或者文件都是以电子形式在网络上传输，就会有一些不
31、法分子通过网络篡改合同或文件内容以获得非法利益。这时，就可以依靠数字签名技术，保证交易的完整性、真实性和不可抵赖性。数字签名是目前电子商务、电子政务中应用最成熟、可操作性最强的一种电子签名的方法。本文是基于对公钥密码体制中的广泛流行的RSA算法进行了研究学习并利用C语言实现基于RSA算法的数字签名方法。RSA密码体制的安全性主要依赖于整数因子分解问题，试图分解模数n的素数因子是攻击RSA最直接方法。RSA数字签名算法,包括签名算法和验证签名算法.首先用MD5算法对信息作散列计算.签名的过程需用户的私钥,验证过程需用户的公钥.A用签名算法将字符串形式的消息处理成签名;B用验证签名算法验证签名是否
32、是A对消息的签名,确认是A发送的消息;消息没有被攥改过;A一定发送过消息。但是，RSA算法的安全性只是一种计算安全性，绝不是无条件的安全性，这是由它的理论基础决定的。参 考 文 献1 谭浩强.C程序设计M.北京：清华大学出版社，2010。2 谷利泽，郑世慧等著.现代密码学教程M.北京：北京邮电大学出版社，2009。3 王 勇.RSA公开密钥密码体制的密钥生成研究J .计算机应用研究，1998。4 冯登国,裴定一.密码学导引M. 北京：科学出版社，1999。5 卢开澄.计算机密码学M.北京：清华大学出版社，1998。6 蔡庆华.公钥密码体制RSA算法J.安庆师范学院学报(自然科学版)，2003。7 蔡乐才，张仕斌.应用密码学M. 北京：中国电力出版社，2005。8 Atreya M等著，贺军等译.数字签名M.北京：清华大学出版社，2003。9 宋震.密码学M.北京：中国水利水电出版社，2002。10 张 周.我国企业开始重视网络安全J.计算机世界A9版,2000。 11 张仕斌，谭三.网络安全技术M. 北京：清华大学出版社，2004。12 赖溪松.计算机密码学及其应用M.北京:国防工业出版社，2001。13 Mao W著，王继林等译.现代密码学理论与实践M.北京：电子工业出版社。
