基于RSA的数字签名的设计与实现论文Word文件下载.docx
《基于RSA的数字签名的设计与实现论文Word文件下载.docx》由会员分享,可在线阅读,更多相关《基于RSA的数字签名的设计与实现论文Word文件下载.docx(31页珍藏版)》请在冰点文库上搜索。
RSAalgorithmisconsideredasapublic-keycryptosystemofthemostfullydevelopedandcompleteintheoryandpracticeapplicationatpresent.Itisthefirstalgorithmforbothdataencryptionanddigitalsignature.Digitalsignatureisaninformationsecuritytechnologyusedtocheckauthenticationanddataintegrity.Itidentifiestrueorfalsebytheauthenticationtechnology.RSAdigitalsignaturesystemcarriesondigitalsignaturebyusingRSApublic-keycipheralgorithm.
Themaincontentofthisthesisincludessixparts.Firstofall,itisacomprehensivesystematicintroductionaboutRSAalgorithmincludingthepresentapplicationsituationandprincipleofRSAalgorithm----producingbigprimenumbersandsecretkeys,theencryptionarithmeticforinformationandthedecryptionforsecretinformation,whichestablishthetheoryfoundationforachievingconcrete;
secondly,itintroducessomebasicconceptionofRSAdigitalsignatureandtheoryofdigitalsignaturerealizingprocess;
thirdly,itintroducesthebasicprincipleofMD5algorithm;
fourthly,itstatesdesignandrealizationofRSAdigitalsignatureindetail.ThemainmodulesincludesproducingRSAsecretkeys(apublickeyandprivatekey),implementationofRSAencryptionalgorithmanddecryptionalgorithm,producingmessagedigestandrealizingdigitalsignatureandverificationbyRSA;
thefifth,itcarriesontestingentirely,analyzingandimprovingforthissystem;
Thesixth,itanalysesthesecurityofRSAdigitalsignatureandpointsoutthedevelopmentdirectionofRSAdigitalsignature.
Keywords:
RSAalgorithm;
encryption;
decryption;
MD5algorithm;
RSAdigitalsignature
论文总页数:
23页
1引言
1.1研究背景
随着电子信息技术的迅速发展,人类已步入信息社会。
但是由于整个社会形成了一个巨大的计算机网络,任何一个计算机网络出现的安全问题,都会影响整个国家的网络安全,所以信息安全、计算机网络安全问题已引起了人类的高度重视。
无论是在局域网还是在广域网中,都存在着自然和人为等诸多因素的脆弱性和潜在威胁。
故此,网络的安全措施应是能全方位地针对各种不同的威胁和脆弱性,这样才能确保网络信息的保密性、完整性和可用性。
针对网络安全的威胁主要有三方面:
(1)人为的无意失误;
(2)人为的恶意攻击;
(3)网络软件的漏洞和“后门”。
现代密码学已成为信息安全技术的核心,密码学是以研究通信安全保密的学科,即研究对传输信息采用何种秘密的变换以防止第三者对信息的窃取。
密码学包括两个分支:
密码编码学和密码分析学。
密码编码学主要研究对信息进行交换,以保护信息在信道的传递过程中不被他人窃取、解密和利用的方法,而密码分析学则与密码编码学相反,它主要研究如何分析和破译密码。
两者之间既相互对立又相互促进。
密码体制的分类有很多,其中一种是根据加密算法和解密算法所使用的密钥是否相同,可以将密码体制分为对称密钥密码体制(单钥密码体制)和非对称密钥密码体制(公钥密码体制),这两种密码体制各有自己的长处和短处,因此现在采用了两种的混合体,如PGP。
公钥密码体制的特点是:
接收方B产生一对密钥(PK和SK);
PK公开,SK保密;
从PK推出SK是很困难的;
A、B双方通信时,A通过任何途径取得B的公钥,用B的公钥加密信息,加密后的信息可通过任何不安全信道发送。
B收到密文信息后,用自己私钥解密恢复出明文。
公钥密码体制已成为确保信息的安全性的关键技术。
RSA公钥密码体制到目前为止还是一种被认可为安全的体制。
RSA公钥加密算法是第一个既能用于数据加密也能用于数字签名的算法。
它易于理解和操作,也十分流行。
算法的名字以发明者的姓氏首字母命名:
RonRivest,AdiShamir和LeonardAdleman。
虽然自1978年提出以来,RSA的安全性一直未能得到理论上的证明,但它经历了各种攻击,至今(2006年)未被完全攻破。
随着越来越多的商业应用和标准化工作,RSA已经成为最具代表性的公钥加密技术。
VISA、MasterCard、IBM、Microsoft等公司协力制定的安全电子交易标准(SecureElectronicTransactions,SET)就采用了标准RSA算法,这使得RSA在我们的生活中几乎无处不在。
网上交易加密连接、网上银行身份验证、各种信用卡使用的数字证书、智能移动电话和存储卡的验证功能芯片等,大多数使用RSA技术。
1.2本课题的研究意义
随着电子商务的发展,网络上资金的电子交换日益频繁,如何防止信息的伪造和欺骗成为非常重要的问题。
在计算机通信系统中,维护电子文档的安全也成为至关重要和非常敏感的问题。
为保护信息的安全,数字签名应运而生,它是现代密码学主要研究的内容之一。
目前关于数字签名的研究主要集中点是基于公钥密码体制的数字签名。
在公钥密码体制中,解密和加密密钥不同,解密和加密可分离,通信双方无须事先交换密钥就可建立起保密通信,因此它较好地解决了传统密码体制在网络通信中出现的问题。
手写签名的每一项业务都是数字签名的潜在用场。
数字签名可以提供数据完整性、真实性和不可否认性。
因而当需要对某一实体进行认证、传输具有有效性的密钥以及进行密钥分配时,便可以借助数字签名来完成任务。
数字签名技术在身份识别和认证、数据完整性、抵赖等方面具有其它技术无法替代的作用,它在军事、电子商务和电子政务等领域有着极广泛的应用。
而在公钥体制中,RSA是一个较为完善的公钥密码算法,不仅能够同时用于加密和数字签名,而且易于理解和操作,是被广泛研究的公钥密码算法。
因此,基于RSA的数字签名具有较强的研究性和实际应用意义。
2RSA算法和RSA数字签名算法的基本概念和原理
2.1RSA算法的基本概念和原理
2.1.1RSA算法介绍与应用现状
RSA算法是一种公钥密码算法,实现RSA算法包括生成RSA密钥,加密和解密数据。
RSA算法是第一个能同时用于加密和数字签名的算法,也易于理解和操作。
RSA是被研究得最广泛的公钥算法,从提出到现在已近二十年,经历了各种攻击的考验,逐渐为人们接受,普遍认为是目前最优秀的公钥方案之一。
RSA的安全性依赖于大数的因子分解,但并没有从理论上证明破译RSA的难度与大数分解难度等价。
即RSA的重大缺陷是无法从理论上把握它的保密性能如何,而且密码学界多数人士倾向于因子分解不是NP-C问题。
RSA的缺点主要有:
A)产生密钥很麻烦,受到素数产生技术的限制,因而难以做到一次一密。
B)分组长度太大,为保证安全性,n至少也要600bits。
RSA算法的时间复杂性取决于它所设计的几个基本运算的时间复杂性。
密钥生成过程时间主要是生成随机素数的时间及计算公钥和私钥的模乘法的时间。
生成随机素数的时间在于完成对随机大数的Fermat测试的时间,Fermat测试的时间复杂度为O((log2n)3),n所测试的整数。
模乘法的计算方法采取先计算两个数的乘积,再取模n,时间复杂性为O((log2n)2)。
RSA加密解密计算的时间主要是模幂运算的时间,即形式为xcmodn的函数的运算时间。
模幂算法采取平方乘算法,设l是c的长度,则计算xcmodn至多需要2l次模乘法,因为1£
[log2n]+1,所以模幂运算能在时间O((log2n)3)内完成。
因此,RSA的加密和解密均可在多项式时间内完成。
RSA公开密钥加密算法自20世纪70年代提出以来,已经得到了广泛认可和应用。
发展至今,电子安全领域的各方面已经形成了较为完备的国际规范。
RSA作为最重要的公开密钥算法,在各领域的应用数不胜数。
RSA在硬件方面,以技术成熟的IC应用于各种消费类电子产品。
RSA在软件方面的应用,主要集中在Internet上、加密连接、数字签名和数字证书的核心算法广泛使用RSA。
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)签名是可信的:
任何人都可以验证签名的有效性;
2)签名是不可伪造的:
除了合法的签名者外,任何人伪造其签名是困难的;
3)签名是不可复制的:
对一个消息的签名不能通过复制变为另一个消息的签名。
如果一个消息的签名是从别处复制得到的,则任何人都可以发现消息与签名之间的不一致性,从而可以拒绝签名的消息;
4)签名的消息是不可改变的:
经签名的消息不能篡改,一旦签名的消息被篡改,任何人都可以发现消息与签名之间的不一致性;
5)签名是不可抵赖的:
签名者事后不能否认自己的签名。
可以由第三方或仲裁方来确认双方的信息,以做出仲裁。
为了满足数字签名的这些要求,例如,通信双方在发送消息时,既要防止接收方或其他第三方伪造,又要防止发送方因对自己的不利而否认,也就是说,为了保证数字签名的真实性。
数字签名的原理是:
(发送方和接收方根据要求各自产生自己的一对公钥和私钥)
1)被发送文件采用某种算法对原始消息进行运算,得到一个固定长度的数字串,称为消息摘要(MD),不同的消息得到的消息摘要各异,但是对相同的消息它的消息摘要却是唯一的;
2)发送方生成消息的消息摘要,用自己的私钥对摘要进行加密来形成发送方的数字签名;
3)这个数字签名将作为消息的附件和消息一同用接收方的公钥进行加密,将加密后的密文一起发送给接收方;
4)接收方首先把接收到的密文用自己的私钥解密,得到原始消息和数字签名,再用发送方的公钥解密数字签名,随后用同样的算法计算出消息摘要;
5)如果计算出来的消息摘要和发送方发送给他的消息摘要(通过解密数字签名得到的)是相同的,这样接收方就能确认数字签名确实是发送方的,否则就认为收到的消息是伪造的或是中途被篡改的。
数字签名的原理图如2-1所示
AB
用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算法重新计算,得到验证者自己的消息摘要。
验证者比较解密得到的消息摘要和自己的消息摘要,如果两者相同,则验证成功,可以确认消息的完整性及签名确实为签名者的;
否则,验证失败,确认签名被冒充或是被篡改。
2.3MD5算法的介绍
MD5消息摘要算法(RFC1321)是由Rivest(公开密钥密码RSA算法的设计者之一)所设计的单向散列函数,MD5不基于任何假设和密码体制,它采用了直接构造的办法,速度很快,非常实用。
MD5算法的典型应用是对一段信息(message)产生信息摘要(MD),以防止被篡改。
比如,在unix下有很多软件在下载的时候都有一个文件名相同,文件扩展名为.md5的文件,在这个文件中通常只有一行文本,大致结构如:
md5(tanajiya.tar.gz)=0ca175b9c0f726a831d895e269332461
这就是tanajiya.tar.gz文件的数字签名。
md5将整个文件当作一个大文本信息,通过其不可逆的字符串变换算法,产生了这个唯一的md5信息摘要。
如果在以后传播这个文件的过程中,无论文件的内容发生了任何形式的改变(包括人为修改或者下载过程中线路不稳定引起的传输错误等),只要你对这个文件重新计算md5时就会发现信息摘要不相同,由此可以确定你得到的只是一个不正确的文件。
如果再有一个第三方的认证机构,用md5还可以防止文件作者的"
抵赖"
,这就是所谓的数字签名应用。
md5还广泛用于加密和解密技术上。
比如在unix系统中用户的密码就是以md5(或其它类似的算法)经加密后存储在文件系统中。
当用户登录的时候,系统把用户输入的密码计算成md5值,然后再去和保存在文件系统中的md5值进行比较,进而确定输入的密码是否正确。
通过这样的步骤,系统在并不知道用户密码的明码的情况下就可以确定用户登录系统的合法性。
这不但可以避免用户的密码被具有系统管理员权限的用户知道,而且还在一定程度上增加了密码被破解的难度。
MD5算法以任意长度的消息作为输入,产生一个128比特消息散列值(或称消息摘要)作为输出。
具体的算法步骤如下:
步骤1:
附加填充比特,对消息进行填充,使消息的长度(比特数)与448模512同余,即恰好为一个比512比特的倍数仅小64位的数。
步骤2:
附加消息长度值,将用64比特表示的初始消息(填充前)的长度(比特数)附加在步骤1的结果后。
步骤3:
初始化MD缓存,MD5算法使用了一个4个字(128比特,MD4中每个字32比特)的缓存来计算消息摘要,它们主要用来存放MD5的中间及最终结果。
缓存可以看成是4个32比特的寄存器(A,B,C,D)。
步骤4:
以512比特(16个字)分组处理消息,这一步是MD5算法的主循环,以512比特作为分组,在后面有详细的介绍。
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所示:
图3-1密钥产生
密钥产生的部分代码实现:
CStringstr;
//第一步产生任意素数
GeneratePrimeNumbers();
//第二步计算n=p*q
m_n=m_Prime1*m_Prime2;
//第三步0=(p-1