浅谈如何利用RSA算法进行数字签名

来源 :电脑知识与技术·学术交流 | 被引量 : 0次 | 上传用户:ycy111
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
  摘要:文章介绍了RSA算法的基本原理,提出了RSA算法中数据分块的基本方法,分析了RSA数字签名算法的基本理念,给出了运用RSA算法进行数字签名的步骤以及进行验证的步骤。
  关键词:RSA;数字签名
  中图分类号:TP309文献标识码:A文章编号:1009-3044(2008)15-21048-02
  
  Discussed Shallowly how to Carry on Digital Signature Using the RSA Algorithm
  LI Chun-mei
  (Anhui Xinhua University,Hefei 230088,China)
  Abstract:The article introduced the RSA algorithm’s basic principle, proposed in the RSA algorithm the data piecemeal’s essential method, has analyzed the RSA digital signature algorithm basic idea, gave has carried on digital signature using the RSA algorithm the step as well as carries on confirmation the step.
  Key words:RSA;Digital signature
  
  1 引言
  
  数字签名是目前电子商务、电子政务中应用最普遍、技术最成熟的、可操作性最强的一种电子签名方法。它采用了规范化的程序和科学化的方法,用于鉴定签名人的身份以及对一项电子数据内容的认可。它通过将原始信息进行散列函数(哈希函数,Hash Function)运算,并将得到的结果使用密钥进行加密,从而得到数字签名值。其依据是在使用安全的哈希函数(单向哈希函数)的情形下,要想从已知的哈希函数结果中推导出原信息来,实际上是不可能的,因此,数字签名可以在更少且可预见的数据量上进行运算,生成数字签名,却保持与原信息内容之间的高度相关,有效的保证了其完整性、真实性和不可抵赖性的特点。
  基于公钥密码体制和私钥密码体制都可以获得数字签名,目前主要是基于公钥密码体制的数字签名,包括普通数字签名和特殊数字签名。普通数字签名算法有RSA、ElGamal、Fiat-Shamir、Guillou-Quisquarter、Schnorr、Ong-Schnorr-Shamir数字签名算法、Des/DSA,椭圆曲线数字签名算法和有限自动机数字签名算法等。特殊数字签名有盲签名、代理签名、群签名、不可否认签名、公平盲签名、门限签名、具有消息恢复功能的签名等,它与具体应用环境密切相关。其中RSA算法是一种公认十分安全的算法,而且是目前网络上进行保密通信和数字签名的最有效的安全算法。
  
  2 RSA签名算法的确定
  
  RSA算法所根据的原理是:根据数论,寻求两个大素数比较简单,而将它们的乘积分解开则及其困难。在这一体制中,密钥分为两种:加密密钥PK={e,n}和解密密钥SK={d,n}。
  其中的加密密钥PK是公开的,使得其他人可以使用,而对解密密钥中的d则保密。这里,n为两个大素数p和q的乘积(素数p和q一般为100位以上的十进制数),e和d满足一定的关系,在已知e和n的情况下不能求出d。
  下面是密钥产生的过程:
  (1)计算n。秘密选择两个大素数p和q,计算出n=p*q。n成为RSA算法的模。
  (2)计算Φ(n)。再计算出n的欧拉函数Φ(n)=(p-1)(q-1),Φ(n)定义为不超过n并于n互素的数的个数。
  (3)选择e。从[0,Φ(n)-1]中选择一个与Φ(n)互素的数e作为公开的加密指数。
  (4)计算d。计算出满足下式的d:e*d=1 mod Φ(n),d作为解密指数。
  (5)得出所需要的公开密钥和秘密密钥:
  公开密钥(即加密密钥)PK={e,n}
  秘密密钥(即解密密钥)SK={d,n}
  RSA的加解密算法是一样的,公式如下:Y=Xa mod n (公式一)
  当进行加密操作时,令a=e,则Y是X加密后的密文。当进行解密操作时,令a=d,则Y是将X解密后的原文。则该算法也可标识为:
   Y=PowerMod(X,a,n) (公式二)
  其中:X待操作的对象,a为运算指数,n为模,Y为操作结果,PowerMod则为Xa mod n。
  由此,可得到RSA加密和解密的算法如下:
  加密算法 EPK(X)=PowerMod(X,e,n) PK={e,n} (公式三)
  解密算法 DSK(X)=PowerMod(X,d,n) SK={d,n} (公式四)
  其中: DSK(EPK(X))=X (公式五)
  这里的X只是表示不大于n的整数。当X大于n时,就要将X分块,使得每块的长度一致且其值均不大于n,对于整数,显然是无法分块的,这就需要先对X进行编码。编码的基本要求是将X分块,每块是一个8位字节串EB,由块标记BT,填充块PS和数据D组成。
   EB = 00 || BT || PS || 00 || D(等式一)
  块标记BT是一个标记字节,表示加密块的结构。它有00,01,或02值。私钥操作为00,或01;公钥操作为02。填充串PS为k-3-||D||(D的字节长度)长的8位字节字符串。对于00型,填充串为00;对于01型,填充串为ff;对于02型,填充串为假散列生成的非0值。这使得加密块EB的长度为k(模n的长度)。其中开始的00值字节保证了转化成整数后的分块小于模数n。
  其中需要注意的地方如下:
  对于00型(BT=00)来说,数据D必须以一个非0字节开始,或是必须知道长度,以便块能被清楚的解析(EB中粗体部分)。对于01和02型来说,块能被清楚的解析,这是因为填充块PS不包含00值字节,它可以被一个00值字节从数据D分开。
  01型被推荐为私钥操作标志。
  对于02类型来说,建议为每一个加密过程都独立生成假散列字节,特别是如果相同的数据被输入多于一个的加密过程。
  对于01和02类型来说,填充串至少是8个字节长,为了防止攻击者通过测试所有可能的加密块来恢复数据。
  上面的加密和解密算法适用的环境是他人通过PK将信息进行加密传送给拥有SK者,拥有SK者在用SK进行解密,得到原始信息,这样可防止其他人窃取信息。但是在数字签名中却不适用,因为数字签名的过程正好相反,要求是拥有SK者先将信息进行加密,其他人在通过PK进行签名验证,那么该如何处理呢?
  考虑这样一个公式: EPK(DSK(X))=X(公式六)
  这个公式看起来和上面的加密公式(公式五)很相似,只不过把加密和解密的过程换了个顺序,但是满足了数字签名的要求,为什么呢?从公式二、公式三和公式四可知,E(加密)和D(解密)算法没什么区别,只是参数不同而已,如果把参数互换一下,则可得到下面的公式:
  加密算法 ESK(X) =PowerMod(X,d,n) SK={d,n}(公式七)
  解密算法 DPK(X)=PowerMod(X,e,n) PK={e,n} (公式八)
  其中: DPK(ESK(X))=X(公式九)
  很显然,公式九就是需要的数字签名的算法。
  
  3 数字签名的流程
  
  对于给定的原始数据,有时有可能比较大,而且RSA处理又是很慢,如果直接加密的话很是浪费时间,所以为了节省处理时间,在数字签名时一般不通过直接加密原始数据而得到签名值,而是先对原始数据进行散列化(单向散列),然后对散列的结果进行加密。这样便得到了数字签名的4个基本步骤:
  3.1 第一步:消息散列
  对于有效的散列算法,一般选择MD2,MD4,MD5,SHA(SHA1)等算法,其中MD系列散列算法产生32字节的摘要信息,SHA系列算法产生40字节的摘要信息(散列的结果越长,越不容易被伪造)。可以任意选择一种算法对消息M进行处理,进而得到M的散列信息MD,即消息散列。
  3.2 第二步:数据编码
  如果直接对第一步得到的MD进行加密不就生成数字签名信息了吗?为什么还要有数据编码的步骤呢?这个问题在第一步中就可以得到答案。
  在第一步中提到有很多种散列算法都可以生成有效的摘要信息,这些算法生成的摘要信息均不包含散列算法信息,这就给接收者进行数字签名验证带来了很大的麻烦,会因为无法得知发送方的散列方法而无法对接收到的数字签名信息进行验证,这时,就要求发送方在生成数据摘要时提供所使用的散列算法,以满足接收者进行签名验证的需要。所以把散列算法和散列结果组合在一起,作为一个数据摘要完整的整体,这就是数据编码过程所要完成的工作。
  一般情况下,把消息散列MD和消息散列算法标识符组成下面所描述的ASN.1类型DigestInfo的值,此类型将通过BER编码来生成一个8位字节串D,即原始数据。
  DigestInfo ::= SEQUENCE {
  digestAlgorithm DigestAlgorithmIdentifier,/* 散列函数标识编码 */
  digest Digest/*消息散列MD */
  }
  DigestAlgorithmIdentifier ::= AlgorithmIdentifier
  Digest ::= OCTET STRING
  类型DigestInfo的域有下列含义:
  digestAlgorithm表示用于散列的算法(以及相关参数)。它标识了所选的散列算法:MD2、MD4、MD5或SHA等。作为参考,以下是部分相关的对象标识符:
  md2 OBJECT IDENTIFIER ::={ iso(1) member-body(2) US(840) rsadsi(113549)digestAlgorithm(2) 2 }
  md4 OBJECT IDENTIFIER ::={ iso(1) member-body(2) US(840) rsadsi(113549)digestAlgorithm(2) 4 }
  md5 OBJECT IDENTIFIER ::={ iso(1) member-body(2) US(840) rsadsi(113549)digestAlgorithm(2) 5 }
  sha-1 OBJECT IDENTIFIER ::= {iso(1) identified-organization(3) oiw(14) secsig(3) algorithm(2) 26}
  对这些对象标识符来说,散列算法的参数域是空(散列函数除消息M外无其他参数)。
  digest是消息散列过程的结果,例如消息散列MD。
  具体编码方法可参考ASN.1相关标准。
  3.3 第三步:RSA私钥加密
  为了安全起见,数字签名所使用的RSA的密钥长度(n的长度)最少选择1024位(转换成二进制为128个字节),长度远远大于MD编码后的字符串D。D被签名者采用公式七进行加密,生成一个8位字节串ED,其块标记为01(见1节)。
  3.4 第四步:字节串到位串的转换
  第三步中加密的结果ED是一个8位字节串,而签名值是个位串,签名验证时是一位一位进行验证的,所以要将ED转换成一个位串S,即签名值 。具体来说,ED的第一个字节的第一位成为S的第一个数据位,以此类推,直到ED的最后一个字节的最后一位,它将变成S的最后一个数据位。实际上就是取ED的二进制编码。
  注意:签名S的位长度是8的倍数(是字节串的二进制表示)。
  
  4 数字签名的验证
  
  验证过程同样包括四个步骤:位串到字节串的转换,RSA公钥解密,BER数据解码得到解密后的散列值,最后与原始数据散列值进行比较,若每一位都相同则验证通过,否则验证失败。
  4.1 位串到字节串的转换
  签名S被转换成字节串ED,即被加密的数据。具体来说,假设S的位长度是8的倍数,S的第一位将变成字节串的第一个字节的第一位,以此类推,直到签名的最后一位变成字节串的最后一个字节的最后一位。如果签名的位长度不是8的倍数,则是错误。
  4.2 RSA解密
  采用公式八使用签名者的公钥对被加密数据ED进行解密,得到字节串EB,然后根据等式一进行解析,得出块标记BT,填充块PS和原始数据D。如果有下列情况发生,则为错误:
  BT标记不是01(私钥加密,BT应该为01)。
  填充块PS少于8字节,或是和块标记BT不匹配。
  4.3 数据解码
  将原始数据D是DigestInfo 类型的ASN.1编码结构,将D进行BER解码,得到分成消息散列MD和消息散列算法标识符。消息散列算法标识符决定了下一步所选的消息散列算法。如果消息散列算法标识符不是MD2,MD4,MD5或SHA(SHA1)消息散列算法,则为错误。
  4.4 消息散列和比较
  使用所选的消息散列算法对收到的消息M进行散列,得到字节串MD’。如果MD`和MD完全相同,则表示验证成功,否则为失败。
  
  5 结束语
  
  在实际应用中,进行数字签名的RSA中的模n一般都要求1024位或2048位,这在常用的编程软件中都是很难处理的。因为在常用的编程软件中整数最大只支持到64位,也就是说n≤2^64,远远满足不了要。但是,如果把大数换算成其他x进制的数(比如2^16进制、2^30进制等),用长度为x的无符号长整型数组来存储每一“位”x进制的数,这样每一“位”x进制的数就可以表示0~2^x之间的整数,保证2个x进制的数进行任何运算都不会出现溢出,处理好这个x进制数的相关运算(加、减、乘、除、幂等)后就可以自己编写满足数字签名要求的RSA算法了。
  
  参考文献:
  [1] 谢希仁.计算机网络教程[M].北京:人民邮电出版社,2004.
  [2] RFC2313-1998 PKCS #1:RSA Encryption Version 1.5[S].
  [3] GBT 16262.1-2006 抽象语法记法(ASN.1)基本记法规范[S].
  [4] GBT 16263.2-2006 ASN.1编码规则第1部分,基本编码规则(BER)、正则编码规则(CER)和非典型编码规则(DER)规范[S].
其他文献
摘 要:由于近年来公安民警伤亡严重,对徒手搏击技能越来越重视,随之而来的就是在搏击技能运动中出现的运动损伤问题,该文就是针对在搏击技能训练中出现的运动损伤进行调查研究,分析在搏击技能运动中损伤的发生及其预防的工作,为的是在今后的警务搏击技能运动训练中能减少运动损伤的发生,从而让学生能够更好地进行训练。  关键词:搏击训练 运动损伤 预防  中图分类号:G8 文献标识码:A 文章编号:2095-28
摘 要:警式体育在司法警官职业类院校所开设课程结构当中起到了核心支撑性作用,既然是体育课程必然会涉及学生的体能、技能的练习。从当前各地区司法警官职业学院警式体育的开设现状来看还有很多欠缺的地方,尤其在专项性的练习方面以及训练设施保障方面的完善,能够为之后学生警务技能的掌握和熟练打下坚实的根基。该次研究通过有针对性地对司法警官职业学院当前现状提出合理的意见和方案,为司法警官类院校的体育教学发展提供理
关键词:高校财务 流程再造 信息化  随着高等教育事业的迅速发展,高校外部环境和内部管理体制都发生了很大变化,传统的高校财务管理模式及运行流程正面临着严峻的考验,财务部门的业务量成倍增加,财务工作人员又面临高校机关精简的压力。为适应形势发展的要求,高校财务部门一方面需要加快推进体制机制改革、加强专业团队建设,通过提升服务质量、精简工作程序、完善内控制度来更好地满足学校教学、科研和各项事业发展的需要
摘要:EDA技术综合了现代电子技术和计算机技术的最新研究成果,其设计采用自顶向下的设计方法,通常采用硬件描述语言进行电子电路设计;VHDL语言以其强大的建模和逻辑综合功能成为EDA技术中应用最广泛的硬件描述语言之一。基于VHDL设计了交通信号灯。  关键词:EDA;自顶向下;VHDL;交通信号灯  中图分类号:TP311文献标识码:A 文章编号:1009-3044(2008)15-21050-04
摘要:本文介绍了P2P的工作原理及几个典型,着重分析比较了基于超级节点的和基于区域划分结构的两种P2P模型的特性,最后提出自己的观点。  关键词:P2P网络模型;发现机制;区域划分;身份认证   中图分类号:TP393文献标识码:A文章编号:1009-3044(2008)15-2pppp-0c    Comparison and Research of two P2P Network Models
摘要:交叉表的设计一直是程序开发的难点,充分利用C#2005数据集和数据表的离线功能,我们可以把一张表的数据行变成另一个内存表的数据列,这样我们就可以非常容易地进行数据汇总统计,统计要求符合中国报表特色。  关键词:离线模式;数据集;数据表;交叉表  中图法分类号:TP31 文献标识码:B 文章编号:1009-3044(2008)15-20ppp-0c    Implement CrossTabl
摘要:介绍了在CVI中通过DLL的方式来使用C 语言的编程方法,给出了实现例子,并验证了其有效性。实现了在CVI中使用C 语言的程序设计。  关键词:C语言;C 语言;CVI  中图分类号:TP312文献标识码:A文章编号:1009-3044(2008)15-20ppp-0c    How to Use C Language in CVI  ZHANG Fu-song  (Unit 92
摘要:文章分析了CSSCI管理类29家刊物网站建设运营情况,约有27.5%的学术期刊有自己的网站,但是大多数网站后期运营状况不好。文章指出学术期刊应该建立符合自身特点的有特色的网站,接着应当设法提高网站利用效率,从而提高所刊登文章引用率、总被引频次、影响因子,提高期刊的学术影响力;通过BBS或QQ在线交谈,增强互动性,及时查看、回复作者读者的问题,了解作者读者的需求、动态,作好读者服务;同时可通过
摘要:基于J2EE架构的教学辅助系统的研究与设计首先简介了J2EE平台,分析了其在教学辅助系统开发中的优势,然后简述了教学辅助系统要实现的主要功能,介绍了系统多层体系结构的设计原理,最后对基于struts的MVC开发模式进行了阐述。实践证明,采用J2EE架构开发教学辅助系统,技术上完全可行,而且投入小,便于后期的维护、扩充和升级。  关键词:教学辅助系统;J2EE;MVC模式  中图分类号:TP3
摘要:数控机床是典型的机电一体化系统。随着数控技术的迅速发展,数控机床的普及渐渐成为机械行业的潮流。本文详细分析了可编程控制器(PLC)在数控机床中的应用方式及其特点,以及PLC的设计方法。  关键词:可编程控制器; 数控机床; PLC;控制逻辑    CNC Machine Tool Design and Application of PLC  ZHANG Yao-qi  (siemens, B