（计算机应用技术专业论文）门限数字签名方案的研究.pdf

沈阳航空工业学院硕士学位论文 摘要 数字签名是现代密码学主要研究内容之一，数字签名技术在身份识别和认 证、数据完整性、抗抵赖等方面具有其它技术所无法替代的作用，在军事、电子 商务和电子政务等领域都有着极广泛的应用。 门限签名、证实签名等特殊的数字签名适应了一些应用环境的特殊需要。本 文在详细研究了数字签名、门限秘密共享体制和门限数字签名体制的基础上，提 出了一个具有证实功能的双重门限证实数字签名方案；方案不但签名秘密钥是由 签名参与者以门限秘密共享方式产生，而且证实秘密钥也是由证实参与者以门限 秘密共享方式产生，在方案中使用了两次门限方式来产生用于签名与证实的秘密 钥，因而在一定程度上提高了系统的安全性，并更大范围地实现了权利的制约与 平衡。 方案在分发签名和证实秘密钥的同时，公布了验证信息，防止了秘密分发人 对秘密分享成员及成员与成员之间的欺诈：另外，方案中证实与否认协议的设计 满足了零知识的要求；方案主要基于已证明是正确的s h a m i r 门限秘密共享协议， 最后可以证明在假设离散对数和大整数难题安全的假设下，方案是安全的。 关键词数字签名秘密共享门限数字签名方案证实签名 沈阳航空工业学院硕士学位论文 a b s t r a e t d i g i t a ls i g n a t u r ei so n eo ft h em a i nr e s e a r c hp a r t si nm o d e r nc r y p t o l o g y d i g i t a l s i g n a t u r et e c h n o l o g yh a sp l a y e da ni r r e p l a c e a b l er o l ei ni d e n t i t y - a u t h e n t i c a t i o n ，d a t a i n t e g r i t y , a n du n d e n i a b l es i g n a t u r e ；a l s oh a sg r e a ta p p l i c a t i o ni nt h ef i e l d ss u c ha s m i l i t a r ya f f a i r s ，e l e c t r o n i cb u s i n e s sa f f a i r s ，e l e c t r o n i cg o v e r n m e n ta f f a i r s ，e r e s p e c i f i cd i g i t a ls i g n a t u r es u c ha st h r e s h o l ds i g n a t u r e ，c o n f i r m e rs i g n a t u r ea r ea p p l i e d t om e e tt h en e e d so fs p e c i f i cn e c e s s i t i e so fg i v e na p p l i e de n v i r o n m e n t i nt h i sp a p e r , a d o u b l e - t h r e s h o l dc o n f i r m e rd i g i t a ls i g n a t u r es c h e m ew i t hc o n f i n n i n gf u n c t i o nw a s p r o p o s e d i nt h ep a p e rn o to n l yt h eo r d i n a r ys i g n a t u r ew a sp r o d u c e db yt h et h r e s h o l d s e c r e ts h a r i n gm e a n s ，b u ta l s ot h ec o n f i r m e rs i g n a t u r ew a sp r o d u c e db yt h es a m e m e a n s ，a n dt h r e s h o l dm e a n sw e r eu s e dt op r o d u c et h es e c r e tk e yo fs i g n e ra n d c o n f i r m e rt w i c ei nt h i ss c h e m e t h e r e f o r e ，t h es e c u r i t yl e v e lo ft h es y s t e mw a s s t r e n g t h e n e dt os o m ee x t e n d ，a n di nag r e a t e rs c o p e ，t h er e s t r i c t i o n sa n db a l a n c e so f r i g h tw e r er e a l i z e d t h et e s t i f y i n gi n f o r m a t i o nw a sp u b l i c i z e dw h e nt h es i g n e ra n de o n f i r m e rs e c r e tk e y w e r ed i s t r i b u t e d ，a n dp r e v e n tt h ec h e a t i n gf r o mt h es e c r e td i s t r i b u t o rt os e c r e ts h a r i n g p a r t i c i p a n t sa n da m o n g t h ep a r t i c i p a n t s f u r t h e r m o r e ，t h ed e s i g no fc o n _ f i r m e ra n d d e n yp r o t o c o lm e tt h en e e do fz e r o - k n o w l e d g e ，a n dt h es c h e m ew a sm a i n l yb a s e do n t h ep r o v e d - t o b e c o r r e c ts h a m i rt h r e s h o l ds e c r e ts h a r i n gp r o t o c o l ，a tl a s ti tw a s p r o v e dt h a tt h en e ws c h e m ew a ss a f e ，w h i l eu n d e rt h eh y p o t h e s i st h a tt h ed i s c r e t e l o g a r i t h mp r o b l e m a n dl a r g ei n t e g e rp r o b l e mw e r es a f e k e y w o r d s d i g i t a ls i g n a t u r e ，s e c r e ts h a r i n g ，t h r e s h o l dd i g i t a ls i g n a t u r es c h e m e ， c o n f i r m e rs i g n a t u r e i i 原创性声明 本人郑重声明：所呈交的学位论文是本人在导师的指导下独立完 成的。除文中已经注明引用的内容外，本论文不包含其他个人或集体 已经发表或撰写过的作品或成果，也不包含本人为获得其他学位雨使 用过的成果。对本文研究做出重要贡献的个人或集体均已在论文中进 行了说明并表示谢意。本声明的法律后果由本人承担。 论文作者签名： 狄蜷 训f 年，月目 版权授权说明 本人授权学校“有权保留送交学位论文的原件，允许学位论文被 查阅和借阅，学校可以公布学位论文的全部或部分内容，可以影印、 缩印或其他复制手段保存学位论文”；愿意将本人学位论文电子版提交 给研究生部指定授权单位收录和使用。学校必须严格按照授权对论文 进行处理，不得超越授权对毕业论文进行任意处置。 授权人：蜀0 港 例绛，月fe t 沈阳航空工业学院硕士学位论文 第一章绪论 1 1 研究背景 近年来，随着因特网的日益普及，我国己经进入了信息化时代，信息产业飞 速发展，电子商务作为信息化社会的重要组成部分，已经成为今天商业活动不可 或缺的手段。越来越多的商业活动通过 n t e m e t 进行交易，据中国互联网数据中 心估计，2 0 0 3 年中国电子商务交易额约为6 0 0 亿美元，2 0 0 4 年约为3 7 0 0 亿美元， 到2 0 0 7 年，将达到1 7 3 7 3 亿美元。 电子商务的进行完全依赖于数据在网上的传输，但日益严重的网络犯罪正在 对虚拟世界里的用户造成巨大的危害，用户越来越能感受到其背后潜伏着的脆弱 性、不安全性和危险性，因而如何保证合法用户的安全性和权利不受到危害或侵 犯，以及保障数据的安全和交易双方的身份确认已成为电子商务应用的关键问 题。电子商务系统和电子商务的安全管理体系应该实现系统对用户身份的有效确 认、对私有密钥和口令的有效保护、对非法攻击的有效防范等，以实现合法用户 相关信息的安全性。可见，电子商务的安全将直接关系到这一蓬勃发展的新生事 物的生死存亡。 2 0 0 5 年4 月1 日，第一部中华人民共和国电子签名法的颁布实施，意 味着我国电予商务已经进入了高速发展的阶段，需要立法来规范商业行为和保护 交易人权利。据统计，中国目前有4 0 0 0 多个电子商务网站和7 0 多家认证机构， 逐年递增的国内国际电子商务交易额意味着对数字签名技术发展的更高要求。 数字签名技术已成为保证电子商务安全进行的技术手段之一【l 】，在电子商务 中，系统对信息安全的要求主要包括信息的保密性、数据的完整性、用户身份的 鉴别、信息发送者的不可抵赖性等。 1 2 数字签名技术及应用 数字签名( d 塘i t a ls i g n a t u r e ) 撕：，又称为电子签名技术，己经广泛地应用到 电子商务、数据库安全、身份认证、计算机病毒检测、软件保护等各个方面，主 要用于对数字消息进行签名，以防止消息的冒名伪造或篡改，亦可以用于通信双 方的身份鉴别。 在人们的同常生活中以及工作中，书信、文件、商业合同都需要当事者的签 沈阳航空工业学院硕士学位论文 名。在传统的事务处理中，通常采用手写签名、印章等方式作为书面签名，具有 法律意义。但在电子邮件，电子商务等数字通信中，传统的书面签名因为可以被 任意的拷贝而失去了它的现实意义，于是数字签名技术的产生很好地解决了上述 问题，而且只有在公开密钥密码体制于1 9 7 6 年由d e f f i e 和h e l i m a n “。提出后， 数字签名的出现和发展才有了可能。 1 2 1 公钥密码体制在数字签名中的应用 公钥密码学的出现【3 】【4 】，使得现代密码学终于有了划时代的发展。传统的单 钥密码体制( 又称为对称密码体制) 使用相同加密解密密钥对消息进行加密和解 密，所以必须对密钥严格保密，以防止密钥丢失会造成对加密信息的泄露。公钥 密码体制( 又称为非对称密码体制) 与传统密码体制的根本不同在于它拥有 一对不同的加密密钥和解密密钥，加密密钥可以公开，不用保密；而解密密钥只 要不能在合理的时间内根据公开的加密密钥计算出来即可，这样就给密钥管理提 供了更大的发挥空间。公开密钥密码体制可以在以下两方面得到应用：一方面是 信息的加密，即发送方用接收方的公钥加密某一消息得到秘密信息，而接收方用 自己的私钥解密，从而恢复这一消息；另一方面是公钥体制新发展出的应用 数字签名，即发送方用私钥加密某一消息( 或其单向函数散列值) ，得到秘密信 息，接收方用发送方的公钥恢复出发送方的信息；这种应用的重点不在于加密， 而是验证，即只要接收方可以确定发送方的身份即可，而不用在意这条消息是否 保密。一 就加密而言，发送者以接收者的公钥作为加密密钥，接收者阻自己的私钥作 为解密密钥，则可实现发给接收者的消息只能由接收者解密；反之，发送者以自 己的私钥作为加密的密钥而以公钥作为解密密钥，则可实现对发送者身份的认 证。显然，公钥体制适合于数字签名的构造。因为，一个签名实体用自己独有的 私钥对不同消息进行签名，从而产生的不同信息签名，应该不能被其他实体所伪 造，而且也可以被不同的接收实体所验证，而这正是数字签名的基本要求。 1 2 2 数字签名概念及特点 数字签名由消息摘要( m e s s a g ed i g e s t ) 和签名( s i g n a t u r e ) 构成。其中消 息摘要是由单向散列函数在消息上进行计算所得到的函数值。签名是用发送者的 沈阳航空工业学院硕士学位论文 私钥对消息摘要进行加密后的数据。数字签名既可以防止文件被篡改，保证信息 的完整性；又可以防止消息发送方对发送数据的否认，从而使数据具有法律上的 意义。数字签名和传统签名的区别在于同一个人对不同的文件的数字签名并不相 同，在互联网上，任一个文件的数字签名不可能被直接复制到另外不同的文件上 进行伪造签名，从而可用来保护信息的真实性、完整性和信息的来源的可信性。 一个安全的数字签名方案作为保障网络信息安全的手段之一，应具有以下特 点： ( 1 ) 签名可以验证：签名的接收者可以根据签名来判断签名者的身份和签名的有 效性。 ( 2 ) 签名不可伪造：除了合法的签名者之外，任何其他人伪造其签名是困难的。 ( 3 ) 签名不可重用：对一个消息的签名只能是对这个消息的签名非法用户不 可能将对a 消息的签名不经任何修改就再一次地用到b 消息上。 ( 4 ) 签名消息不可篡改：经签名的消息不能被篡改。一旦对某消息进行签名，消 息即不可更改。如要对消息进行修改，则必须进行新的签名过程。 ( 5 ) 签名不可否认( 抗抵赖) ：签名一旦生成，签名者就不可以否认曾经对某一消 息签过名，而签名接收方也不可否认曾经接收过某签名。 数字签名也可以应用于认证技术，对下列对象进行以下方面的认证： ( 1 ) 实体认证：在报文通信之前，采用可鉴别协议来认证通信是否在协定的通信实 体之间进行。 ( 2 ) 报文认证：经实体认证后，双方通信实体便可进行报文通信。为了保证数据的 真实性，应对报文进行认证，即接收实体使用数字签名技术验证报文的来源、时 间性与目的的真实性。 ( 3 ) 身份认证：对用户身份进行认证是防止数据被非法用户访问的首要选择。除了 口令控制外，在身份认证环节采用数字签名技术也可以提高对访问安全性的控 制。 1 2 3 数字签名方案基本实现过程 1 9 7 6 年，在密码学的新方向( 文献 2 ) 一文中，d i f i e 和h e l i m a n s 1 用 公钥密码学的思想提出了数字签名的概念。一般来说，一个数字签名体制由以下 要素组成： 沈阳航空工业学院硕士学位论文 一一一 一个随机参数空间胄： 一个秘密密钥空间s k ： 一个公开密钥空间p k ： 一个消息空间m ； 一个签名空间s ； 一个单向散列函数h ； 一个密钥生成算法g e n ：r 斗s k + p k ： 一个关于脉的签名生成算法s i g ：h ( m ) * s k _ s ： 一个关于麒的签名验证算法您r ：p k s + 疗( m ) - - t r u e ，f a l s e 三个相关算法：密钥生成算法、签名算法和验证算法，可定义为一个三元组 ( g e n ，s i g ，v e r ) ，数字签名模型如下图所示： h ( m ) s i g n a t u r es 图1 1 数字签名模型 1 3 论文主要研究工作及内容安捧 本文主要介绍了数字签名和门限秘密共享方案的概念、主要发展方向及其实 际应用。具体的研究思路是；在总结近几年门限数字签名和证实数字签名方案等 方面的研究结果的同时，希望能够提出适应一定需求的门限数字签名及证实方 案。基于这样的研究思路，论文中主要描述了如下工作： 第一，在系统研究和分析了普通数字签名方案、门限秘密共享体审及两者相 4 沈阳航空工业学院硕士学位论文 结合的门限数字签名方案的基础上，利用现有的门限证实数字签名协议构建出一 令适用于某些应用的双重门限证实数字签名方案( d o u b l e t h r e s h o l dc o n f n m e r d i g i t a ls i g n a t u r es c h e m e ) ；第二，从算法的安全性和正确性两方面对新的数字签 名算法进行了系统分析，分析结果表明，新设计的算法具有较好的安全强度。 论文章节安排如下： 第二章介绍数字签名的基础理论，包括计算性困难问题以及给出数字签名的 一般构建和详细的安全定义，并重点介绍和分析了r s a 签名和e l g a m a l 签名等 常用签名体制，包括签名方案的构建和安全性分析，最后详细介绍与本文提出方 案密切相关的不可否认签名、证实签名等签名方案的提出及方案构造过程。 第三章研究门限秘密共享方案。首先介绍秘密共享方案的提出以及研究进 展，分析了现有模型的算法组成和安全性定义。 第四章提出一种新的双重门限证实数字签名方案，首次在证实签名产生阶段 引入了门限方案，将门限方案和证实方案的功能结合起来，并对新方案的正确性、 安全性作了分析。 第五章具体描述了在实现新方案的过程中，各模块的具体实现过程：包括公 钥证书的分发，签名、证实算法的实现过程，系统构建的解决办法等。 第六章总结全文，并提出了下一步需要考虑的问题。 沈阳航空工业学院硕士学位论文 第二章数字签名方案 数字签名从基本上来说，是加密算法的逆过程，是密码学中的重要问题之一， 传统手写签名的任何场合理论上都可以由数字签名来代替。一次完整的数字签名 过程需要用到很多相关的密码学知识：如从哪个数域上选择相关系统参数；素数 的选择与判定；单向散列函数的选择等。 2 1 相关密码学知识 2 1 1 有限域的选择 有限域( f i n i t ef i e l d ) 【5 】，又称为伽罗瓦域( g a l o s i 域，g f ( p ) ) ，在有限域 上，非零元的加、减、乘、除均有定义。当p 是素数时，会有唯一的逆元。存在 秩( 域中元素的个数) 为p 的有限域，这样的域用巴表示。如果p = 矿，g 是 个素数，聊为正整数，便称q 为c 的特征值，l 为巳的扩充度( e x t e n s i o n d e g r e e ) 。 密码设计者可以在下面三个有限域的离散对数群上构建自己的密码算法： 1 ) 素数域的乘法群：g f ( p ) 。这个有限域上的数通常是由于其特殊的交换 能力而倍受重视。 2 ) 特征为2 的有限域乘法群：g f ( 2 ”) 。这个有限域上的运算通常比普通 有限域上的运算要侠得多，而且计算域上的乘幂要有效得多，所以很适 合用于计算离散对数。 3 ) 有限域f 上的椭圆曲线群：e c ( f ) 。目前制订的大部分标准限制指定椭 圆曲线密码技术只能使用单个素数( q = p ) 的基本有限域，或者特征 值为2 ( g = 2 ”) 的有限域，因为椭圆曲线群所使用的密钥长度最短， 从而使得椭圆曲线数字签名算法( e c d s a ) 的执行速度更快、占用存储 空间更小、效率更高。这些优点使得e c d s a 相对于其他公钥算法更具 有吸引力。 2 1 2 单向散列函数的使用 6 沈阳航空工业学院硕士学位论文 单向散列函数( o n e w a yh a s hf i a n c t i o n ) ，即单向哈希函数，是现代密码学的 一个重要元素，是一种将任意长度的消息压缩到某固定长度的消息摘要的函 数。单向散列函数是在一个方向上工作的散列函数：从预映射的值很容易计算其 散列值，但要使其散列值等于一个特殊值却很难。好的散列函数必须具备这样的 性质：单向性、定长性、非线性性、伪随机性和抗碰撞性【6 】。 在数字签名方案中，首先对消息做散列，产生一个固定长度的消息摘要，然 后再用签名者私钥对摘要进行签名，这样，一旦接收者用签名者公钥解密并与原 消息对照后，就可以确认是签名者本人已经了解了这个信息。将哈希函数应用于 数字签名中有很多优点，包括：提高计算速度；破坏数字签名的某种数学性质， 如同态性；签名中不包括可识别的原消息，增强保密性，节省存储文件空间，签 名和文件可以分开保存等。 数字签名方案需要的是强抗碰撞散列函数，这类函数必须满足以下的安全性 要求：即给定一个哈希函数( ) ，想找到两个不同的消息m 和所，使得满足 h ( m ) = h ( m ) 在计算上是不可行的。 一个安全的单向迭代函数是构造安全消息散列值的核心和基础，有了好的单 向迭代函数，就可以用合适的迭代方法来构造迭代散列函数。到现在为止关于散 列函数的安全性设计的理论主要有两点：一个是函数的单向性，二是函数映射的 随机性。一个单向散列函数的安全性取决于散列函数抗击各种攻击的能力，对手 的目标是找到两个不同消息映射为同一散列值，好的散列算法应该具有这样的特 点：在任何输入串中单个比特的变化，将会导致输出比特串中大约一半的比特发 生变化。 常用的散列算法有利用某些数学难题而设计出的算法：如d a v i e s p r i c e 平方 散列算法、d a m g a r d 背包散列算法、s c h n o r r 的f f t 散列算法等，m d 5 和s h a - 1 是 目前许多金融机构用于电子签名的最重要的哈希函数。本文在第五章的模型系统 中使用了s 姒1 散列算法，主要是因为这个哈希函数的散列长度是1 6 0 一位，比其 他1 2 8 位哈希函数能更有效地抵抗来自敌手的穷举攻击。 2 1 。3 素数的判定 公开密钥算法需要随机产生的素数应用于现实生活中网络安全的公钥算法 7 沈阳航空工业学院硕士学位论文 更需要大量的随机素数，所以素数的产生、选取与判定也是公钥算法成功与否的 关键一步。 2 1 3 1 素数产生 在现有的技术条件下，真正可以做到随机产生的随机数发生器并不存在，一 般都是从随机源中选取，或是采用伪随机数发生器来产生密码学所需要的大素 数。好的随机序列应具有良好的统计特性，即分布一致性( 序列中出现频率大约 相等) 和独立性( 序列中任何数不能由其他数推导出) 。下面就是一种常用的伪 随机序列数发生器b b s ( b l u m b l u m s h r u b ) 伪随机序列数发生器【7 1 的工 作原理。 b b s 伪随机数发生器的理论基础是模一的二次剩余的计算。 1 )首先找到一个b l u m 整数( 即一个合数n = p q ，其中p 和g 是两个大素 数，p5qz 3 ( m o d 4 ) ) 。 2 1选择另外一个与互素的随机整数x 。计算 x o = 石2 r o o d n 则就是发生器的种子。现在计算位序列。第f 个伪随机位是蕾的最低位， x o ，五= x 0 2 n x x t n , 薯= 薯_ 1 2 m o d n b b s 发生器最明显的优势是不必为了得到第i 位而迭代所有i - 1 位，若已知p 和 q ，可以直接计算第i 位： ，一( 2 i ) m o 艄p l x q - o ) 1 一 如果不知道发生器种子，那么随机序列的最低比特在计算上等价于分解肋册 整数。 2 1 3 2 常用的素数判定方法 由伪随机数发生器产生的素数的性质仍有待判断这是由于密码学中所 使用的素数都非常大，利用人工判断显然不合实际，所以需要有效的素数测试算 法来正确判定素数的真伪。常用的素数判定法有s 0 1 0 v a 哥s t r a s s e n 素数测试算法、 r a b i n m i l l e r 素数测试算法等，这样做并不能因此而完全确定是素数，但非素数 沈阳航空工业学院硕士学位论文 的概率很小，可以忽略不计。 2 1 4 数学难解问题 公钥密码体制的加密算法大多基于些公认的数学中的难题，最重要的两类 问题是：大整数因子分解问题和离散对数难解问题。 2 1 4 1 大整数因子分解问题 如果已知两个数p 和q ，求其乘积= p q 会非常容易；但如果已知的是 乘积，那么分解这个乘积以解出两个因子就不那么简单了，尤其当这个乘积 是一个大素数( 如超过1 0 2 4 位) 的时候，而这也是现代密码学公钥密码体制 提出的数论理论基础。 正因为大整数的难分解性，r s a t 8 1 公钥密码体制才能安全地应用于消息加 密、数字签名等领域中。 2 1 4 2 离散对数问题( d l p ) 另一个频繁地用于密码学的数学难解问题是模指数运算，这是另一种单向函 数。比如，已知口，x ，”，计算下面这个表达式很容易： 矿m o d h 模指数运算逆问题是找出一个数的离散对数，这就是一个很困难的问题。比 如，已知口，b ，n ，求解x ，使得： 矿i b m o d n 这个问题显而易见的难解性使得e l g a m a l 9 1 、d s a 1 0 1 等算法的安全性有了坚 实的数学理论依据。 2 2 几种主要的数字签名算法 数字签名的理论基础是密码算法，目前世界上普遍使用的一般数字签名方案 都是基于常用的加密算法，有r s a 数字签名方案，d s a 数字签名方案，e c d s a 数 字签名方案，美国国家标准技术研究所( n i s t ) 已经指定这三种签名方案为数字签 名标准，同时它们都已经形成商业的签名软件供用户使用。 数字签名按其对被签消息的种类进行划分有两种：一种是对整体消息的签 沈阳航空工业学院硕士学位论文 名，它是对消息的整体进行加密形成签名；一种是对消息的h a s h 值进行签名， 它附加在被签名消息之后或某一特定位置上的一段签名图样。若按明、密文的对 应关系划分，每一种中又可分为两个子类：一类是确定。n ! ( d e t e r m i n i s t i c ) 数字签 名，其明文与密文一一对应，它对一特定消息的签名不变化，如r s a 、r a b i n 等 签名：另一类是随机化( r a n d o m i z e d ) 数字签名，它对同一消息的签名是随机变化 的，取决于签名算法中的随机参数的取值。一个明文可能有多个合法数字签名， 如e 1 g a m a l 等签名。 2 2 1r s a 算法 r s a 算法以它的三个发明者r i v e s t ，s h a m i r 和a d l e m a n 的名字命名，他们 于1 9 7 8 年提出了r s a 加密算法，这是第一个较完善的公开密钥算法，它既能用 于加密也能用于数字签名，而签名过程相当于保密过程的逆过程。在己提出的公 开密钥算法中，r s a 是最容易理解和实现的，这个算法也是最流行的。 ( 1 ) 签名算法描述： 密钥生成g e n ： 随机选择两个素数p 和g ，满足 i 计算n = p q ；( p 和g 必须保密) ； i i 计算妒( ) = ( p - 1 ) ( q 一1 ) ： 斌随机选择整数d ，计算整数e 妒( ) 满足 e di l m o d 妒( n ) 公开( ，e ) 作为公钥，销毁p ，目和伊( ) ，并保留d 作为私钥。 签名生成s g ： 已知消息掰，用户用自己的私钥生成签名如下。 s = s t g d 壬- 甜r o o d n 签名验证v e t ： 当埘= ，m o d n 时，妇“埘( 历，j ) = t r u e ( 2 ) 安全性分析 1 0 沈阳航空工业学院硕士学位论文 r s a 加密和解密算法是一样的，而签名过程相当于保密过程的逆过程。这 使得r s a 算法非常易于理解和使用软硬件实现。 r s a 的安全性建立在大整数素因子分解困难的基础之上，其公开密钥和私 人密钥是一对大素数。从一个公丌密钥和密文中恢复出明文的难度等价于分解两 个大素数之积。 通过分析r s a 算法的安全性可知，若n = p q 被因子分解成功，则私人密钥 d 便非常容易被计算出来，r s a 便被攻破。因此，必须非常注意两素数p 和g 的 选取，例如从强安全素数中选取满足这样条件的大素数：p 和q 的长度相差不大； p 一1 和叮一1 有大素数因子，且公因子很小：三 和字同样是大素数等等，以 提高r s a 算法的安全性；另一种方法是加大密钥长度，不过这将导致计算量的 剧增。当前使用的l i s a 密钥通常都采用1 0 2 4 比特。 2 2 ，2e l g a m a l 签名体制 一般离散对数签名方案都被称为广义的e i g 锄a l 加密体制，专门为设计签名 用，方案的安全性基于求离散对数的困难性，e l g 锄a l 签名体制也是许多其他数 字签名体制的原型，蝴i s e h n o r r t ”】和d s a 这些签名体制都属于类e l g a n l a l 签名 体制族。 ( 1 ) 签名算法描述 密钥生成g e n ： i 用户a 随机选取大素数p ； i i 计算= ：的一个随机生成元g ； 试随机选取x 作为私钥； i v 计算公钥 y = g 。r o o d p v 公开公钥( 只g ，y ) ；保存私钥x 。 签名生成s i g ： 对于待签名的消息m ，a 进行以下步骤： 沈阳航空工业学院硕士学位论文 i 计算m 的散列值h ( m 1 i i 选择随机数七，k z ：，计算 r = g m o d p ： i i i 计算 h ( m ) = ( k s + x r ) m o d ( p - 1 ) ( 1 ) ，即 s = k - 1 ( h ( m ) 一x r ) ( m o d p 一1 ) 以( ，j ) 作为生成的数字签名。 签名验证v e t ： v e r ( y ，p ，j ) ，丑( 聊) ) = t r u e 营j ，7 r 5 拳g 胛g b = g 盯+ h m ) 一”= g h ( m ) m o d p ( 2 ) 安全性分析 e l g a m a l 体制是一种非确定性的公钥体制f 1 2 1 ，即对同一明文消息，由于随机 参数选择不同而有不同的签名。 从上述算法可知，从公钥想推出私钥或者随机数k ，便是求解离散对数问题。 使用e l g a m a l 算法进行的每一次签名都需要一个新值k ，并且该值必须随机选 择，这是因为如果恢复了后，便可恢复出私人密钥；那么当获得使用同一个k 签 名的两个消息时，即使不知道k 的任何信息，也可恢复私人密钥，其过程如下： 假设攻击者得到了两份签名者a 签名的消息和签名( m ，( r ，置) ) 和( ，s 。) ) ( _ 为签名者的私钥，因为随机数七不变，所以签名对中的r = g r o o d p 不变) ， 那么由以下两式， 鼢l = ( 打( m ) 一x a r ) m o d ( p 一1 ) k s 2 = ( 日( 州) 一h r ) m o d ( p 一1 ) 得至0 k ( s l 一屯) s ( ，确一m 2 ) m o d ( p 一1 ) 因为k - l 存在，且嘲m 2 ，于是 一一堕塑堕窒三些堂堕堡主兰垡堡奎 k 一1 垫二型m o d ( p - n 啊一鸭 至此已得到了k 一，于是由上式( 1 ) 可得出签名者a 的私钥 _ ：( m i - k s l 一) m o d ( p - 1 ) 因而在e l g a m a l 算法中，一个好的随机数发生器对系统安全是至关重要的； 2 3 零知识证明 零知识证明属于密码学中的高级协议部分，所谓零知识证明就是允许一 人( 证明者p ) 使另一人( 验证者v ) 相信某事实而不暴露有关证明的任何信息。 它又可分为交互式零知识证明和非交互式零知识证明。零知识证明是数字签名中 有着重要应用价值的一个部分。 零知识证明系统的交互式证明【14 】就是为了证明p 知道一些事实，希望验证者 v 相信p 知道的这些事实而进行的交互。交互式证明是由规定的轮数组成的一个挑 战应答协议( c h a l l e n g e r e s p o n s e ) ，通常每轮由验证者v 的挑战( c h a l l e n g e ) 和示证者p 的应答( r e s p o n s e ) 组成。在协议结束时，v 根据p 是否成功地回答所有 的挑战来决定是否接受p 的证明。如果满足以上条件，就可以定义这个协议是判 定问题的一个交互式证明系统。如果v 遵循协议，那么这个协议满足完备性和可 靠性这两个特性。 非交互式零知识证明 1 5 j 不需要任何交互，p 可以公布它们，从而向任何花时 间对此进行验证的人证明协议是有效的。这个基本协议类似于并行零知识证明， 不过只是用单向h a s h 函数代替了v 。这样，p 就可以公布一些不含有她的秘密的信 息，却能让任何人相信这个秘密的存在 零知识证明广泛地应用到许多数字签名方案中，包括不可否认数字签名方案 和证实数字签名方案，这两个方案在执行证实与否认协议时，都需要用到零知识 证明以防止泄露任何有关原始签名的信息。 2 4 几个重要的数字签名方案 数字签名可以应用于不同的应用背景，在不同的环境下对数字签名的要求也 沈阳航空工业学院硕士学位论文 是完全不同的。面对这样的需求，人们提出了各种各样具有特殊用途的数字签名 方案，并因此形成了数字签名研究的多个值得关注的研究方向。 本文着重探讨与证实数字签名方案有关的数字签名理论和技术，所以，下面 将会介绍一些与证实数字签名方案密切相关的数字签名协议和方案。 2 。4 ，1 不可否认签名( u n d e n i a b l es i g n a t u r e ) 在通常的数字签名方案中，签名一旦生成，任何拥有公钥的人都可以验证签 名的有效性，但是有时候签名者只是希望特定的人能够验证签名的有效性，因为 签名可能带有签名者的一些秘密信息，这样就产生了不可否认签名。 不可否认签名的概念首先由c h a 啪和a n 嗍e n 【16 】【1 7 】提出，这是一种特殊的 数字签名，兼顾了签名者和接收者的利益，既保证签名不能被接收者滥用，又能 够在以后使签名让其他的人相信。不可否认性包括两层含义；签名的证实和否定 必须与签名者合作完成，这一点可以有效地防止一些有价值的文件被随意的复制 或分发：签名者不能抵赖他曾签过的签名，由于签名者可以通过拒绝执行证实协 议来否认他曾签过的签名，为了防止此类事件发生，不可否认签名增加了一个否 认协议，签名者可以利用否认协议证明一个伪造的签名是假的：而如果签名者拒 绝执行否认协议，就表明签名事实上是由他签署的。 通常不可否认签名由三部分组成： 1 ) 签名生成算法：合法的签名者s i g n e r 可以使用该算法生成有效的数字签名， 其他的任何人都不能伪造签名者的签名。 2 ) 签名的验证协议：签名者s i g n e r 和验证者v e r i f i e r 执行交互式协议，验证协 议必须具备完备性和合理性完备性：只要签名者s i g n e r 和验证者v e r i f i e r 都是诚实的，则签名者s i g n e r 签署的签名总是能够通过验证协议，从而被验 证者v e r i f i e r 接受及合理性；一个不是由签名者s i g n e r 签署的签名，无论签 名者如何狡辩，要使得签名通过验证协议，并使得验证者接受的概率是可以 忽略的。 3 ) 签名的否认协议：签名者s i g n e r 和验证者v e r i f i e r 执行交互式协议，使得签 名者能够向验证者证明某个签名不是自己签署的。否认协议同样也必须具备 完备性和合理性。 下面给出一个最初的不可否认签名体制： 4 沈阳航空工业学院硕士学位论文 1 ) 体锖参数 q ：大素数； p ：大素数，p = 2 q + l ，且乙中的离散对数求解是困难的； g ：z 。中的一个q 阶元素； 用户的私钥i 1 工p - 1 ，x z p ； 用户的公钥：y = g r o o d p ； g ：阶为g 的z 。的乘法子群 公开( p ，g ，y ) ，保存私钥x 。 2 ) 签名过程 对待签消息朋，m g ，计算 s = s i g ，( m 、= m 。m o d p s 是对消息m 的签名，因为签名过程中使用了签名者的私钥，而且算法基于离散 对数难题，即使知道了签名者公钥也无法解密签名，所以除签名者外，s 不能被 其他人所证实。 3 ) 签名的证实协议 s t e p l 验证者选择两个小于p 的随机数d ，b ，计算： c - - - - s 。y 6m o d p = ，( ) 6m o d p 将此质询发送给签名者； s t e p 2 签名者计算，= 工m o d ( p 1 1 ，并发送给验证者： d = r o o d p( d 即为零知识证明中的“承诺量”) s t e p 3 验证者进一步确认 d ；m 4 9 6 r o o d p 如果此式成立，验证者就认为该签名为真，这是因为 d ：c ，：c z ：( j 4 y 6 ) ：8 a x - i ( g “一。) 6 = ( s x - ) 4 9 6 = m 4 9 6 r o o d p 4 ) 签名的否认协议 沈阳航空工业学院硕士学位论文 s t e p 上述等式若不成立，则可继续执行： s t e p 2 验证者以口，6 为输入生成第二次质询再执行一次证实协议，同样验证： d i 卅i 9 6 + m o d p 若等式成立，则停止，验证者认为该签名为真，否则继续执行： s t e p 3 验证者最后验证： ( 露一6 ) i = ( d g - b ) 4 若等式成立，验证者接受签名无效。 因为该协议中签名者未选择任何随即数，并且直接将他的私钥作用于对验证 者的质询上，所以不是零知识的。 2 4 2 可转换的不可否认签名方案 研究不可否认签名时，考虑到很多不可否认签名有时效性，即用不可否认签 名签署的文件在若干年后可能并不再有敏感性，可以被任何人使用，它的签名也 应该能够被所有人验证，所以出现了可转换的不可否认签名( c o n v e r t i b l e u n d e n i a b l es i g n a t u r e ) 。 可转换不可否认签名最初是由b o y a r l l 8 】等人提出