（计算机应用技术专业论文）盲签名理论研究与设计.pdf

湖北工业大学硕士学位论丈 摘要 随着计算机网络及通信技术的迅猛发展信患安全问题同益突出，其核心技 术基础之一的盲签名技术，被广泛应用于电子投票、电子现会等领域，由于它具 有盲性和不可链接性的特性，所以在需要实现某些参加者的匿名性的密码协议中 具有其它技术无法替代的作用。 本文系统地对盲签名理论、方法和应用进行了研究，重点研究了盲签名中的 若干关键技术问题，主要研究成果如下： 1 用c a p 软件实现了在盲签名中经常使用到的一些基础算法，如素性检测、 原根的生成算法、大数的模幂运算、大数的模逆运算等，并研究了如何利用c a p 软件对一段消息进行r s a 盲签名。 2 现有的s c h n o r r 盲化方案都是孤立提出的，缺少统有效的盲化方法，不 知道所给出的盲化方案是否是最优的。鉴于此，本文从盲化函数的代数形式入手， 结合签名方程的构造特点来研究s c h n o r r 型数字签名的一般盲化问题，提出了 s c h n o r r 盲签名方案的一般构造方法、参数选取所应满足的条件及其导出方案，并 对其安全性作了进步的理论分析和证明，在此理论基础上，从计算时间复杂性 的角度对这些方案的性能进行分析比较，从而得到该类方案中的最优方案，利用 密码分析软件c a p 进行简单实验，进一步说明所提方案的正确性和实际可操作性。 3 对一个基于身份的代理盲签名方案及其安全性进行分析，证明该方案存在 两个安全性缺陷，并对该方案加以改进，利用双线性映射理论，结合代理签名和 盲签名的优点，将代理签名技术融入到盲签名中，提出了新型的基于身份和双线 性对的代理盲签名方案；方案以身份为基础的公钥取代了以数字证书为基础的公 钥，省略了验证签名时从系统中获取公钥的步骤，减少了交互的次数，节省了存 储空间，并有效防止了原始签名人冒充代理签名人对消息进行签名，且限制了代 理签名人的代理签名权。 4 针对盲签名的应用，首先介绍了电子投票的一些初步知识，然后基于电子 投票系统应当满足的性质，结合实际需要，设计了一种较为实用的电子投票协议。 并对电子投票系统进行了系统设计，对各功能模块进行了详细设计。 关键词：盲签名，代理盲签名，基于身份，安全性分析，电子投票 湖北工业大学硕士学位论文 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fc o m 【p u t e ra n dc o m m u n i c a t i o nt e c h n i q u e , i n f o r m a t i o ns e c u r i t yh a sb e c o m em o r ea n dm o r ec r u c i a l t h eb l i n ds i g n a t t i r ew h i c hi s o n eo fk e yt e c h n i q u e si ni n f o r m a t i o ns e o l r i t yh a sb e e nw i d e l yu s e di ne l e c t r o n i cv o t i n g , e l e c t r o n i cc a s h ，e t c t h ed i s s e r t a t i o nh a sm a d eas y s t e m i cr e s e a r c ha b o u tt h et h e o r yo fb l i n ds i g n a t u r e a n di t s a p p l i c a t i o n e s p e c i a l l ya b o u ts o f t i ei m p o r t a n tf i e l d s t h ef o l l o w i n ga r et h e a u t h o r sm a i nr e s e a r c hr e s u l t s 1 w eh a v ei m p l e m e n t e dr s ab l i n ds i g n a t u r ea n ds o m eb a s i ca r i t h m e t i cj nc a p w h i c hi so f t e nu s e di nb l i n ds i g n a t u r e ，s u c ha sp r i m e t e s t ，a r i t h m e t i co fg e n e r a t o r , a l g o r i t h mo f m o d u l a rp o w e ra n dm o d u l a ri n v e r s e a n ds oo n 2 1 1 1 es c h n o r rb l i n ds i g n a t u r es c h e m e sw e r ep r e s e n t e da l o n e i nd e f e c to fu n i f o r m m e t h o d ，a n dw ec o u l d n tk n o ww h i c ho n ew a st h eb e s t t h e r e f o r e ，a c c o r d i n gt ot h e s t r u c t u r ec h a r a c t e r i s t i c so fs c h n o r rs i g n a t u r e , w eh a v ep r o p o s e dam e t h o dt og e n e r a t e s c h n o r rb l i n ds i g n a t u r es c h e l n e ，w h i c hc o n t a i n sa l m o s tt h ek n o w nt y p eo fs c h e m e s m o r e o v e r , t h e i rs e c u r i t i e sh a v e b e e np r o v e di nt h e o r ya n dt h ee x p e r i m e n tr e s u l ti nc a p h a si n d i e a t e dt h a tt h e ya r ef e a s i b l e s e c u r ea n do p e r a b l e 3 t h r o u g ht h ea n a l y s i so fa n d - b a s e dp r o x yb l i n ds i g n a t u r es c h e m e , i th a sb e e n p r o v e dt h a tt h es c h e m eh a v et w os c o u r t yd e f e c t s b a s e do nt h e o r yo fw e i lp a r i n ga n d i d b a s e dc r y p t o g r a p h ys y s t e m an e wi d - b a s e dp r o x yb l i n ds i g n a t u r eh a sb e e n p r e s e n t e d ，w h i c hs a t i s f i e st h es e c u r i t yp r o p e r t i e so fb o t hp r o x ys i g n a t u r es c h e m ea n d b l i n ds i g n a t u r es c h e m e ，t h es c h e m ew h i c hu s e si d b a s e dp u b l i ek e yt or e p l a c et h e d i g i t a lc e r t i f i c a t i o np u b l i ck e yc o u l de f f e c t i v e l yo m i tt h ep r o c e s so fg e t t i n gp u b l i ck e y f r o mt h es y s t e ma n dr e d u c et h ei n t e r a c t i o nt i m e sa n dt h em e m o r ys p a c e o t h e r w i s e i t h a sr e s o l v e dt w oi s s u e si nt h ef o r m e rs c h e m e ，w h i c hc o u l de f f e c t i v e l yp r e v e n to r i g i h a l s i g n e rf r o mf o r g i n gav a l i dp r o x yb l i n ds i g n a t u r ef o ra n yf i l ea n dr e s t r i c tt h ev i r t u a l p r o x yp o w e ro ：tp r o x ys t g n a t o r y 4 a st ot h eb l i n ds i g n a t u r es c h e m e sa p p l i c a t i o n s w eh a v ei n t r o d u c e ds o l n ei n i t i a l c o n c e p t so fe l e c t r o n i cv o t i n ga tf i r s t s e c o n d l y , a ne - v o t i n gp r o t o c o lh a sb e e np r o p o s e d b a s e do nt h ee s s e n t i a lp r o p e r t i e so f e v o t i n g , k e y w o r d s ：b l i n ds i g n a t u r e , p r o x yb l i n ds i g n a t u r e , d - b a s e d s e c u r i t ya n a l y s i s ，e l e c t r o n i cv o t i n g 诹 l 亡工繁火秀 学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作所取 得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经 发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均己在文中以明确方 式标明。本声明的法律结果由本人承担。 学位论文作者签名： 传卑 日期：加1 年f 月7 ；日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授 权湖北工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存和汇编本学位论文。 学位论文作者签名： 两算 日期：和7 年f 月乃日 揪獬：矽幺 吣i 硝y r 。j 湖北工业大学硕士学位论文 1 1 数字签名 1 1 1 信息安全的重要性 第1 章绪论 随着计算机网络及通信技术的迅猛发展大量敏感信息要通过公共通信设施 或计算机网络进行交换，与此同时，信息安全问题也闩益突出，网络入侵、信息 泄密及网络犯罪等案件也同益上升，因此，如何堵住网络的安全漏洞和消除安全 隐患已成为人们十分关注的问题，信息安全己成为信息科学领域的热点课题，对 此方向的研究不但具有理论价值，而且具有广泛的实际应用价值。 密码学为解决信息安全问题提供了许多实用的技术，它可用来对信息提供保 密性，对身份进行认证，保证数据的完整性和不可否认性。广泛应用的核心技术 有( 1 ) 信息加密算法，主要用来保护在公开通信信道上传输的敏感信息，以防被非 法窃取：( 2 ) 数字签名技术，用来对网上传输的信息进行签名，保证数据的完整性 和交易的不可否认性。数字签名技术具有可信性、不可伪造性、不可重用性和不 可否认性。数字签名技术可进一步细分为一般数字签名、盲签名、代理签名、多 重数字签名、门限签名、秘密共享多重签名、多重代理签名及门限代理签名等， 各种签名技术都有它特定的适用范围：( 3 ) 身份认证技术，网上银行、网上证券交 易、电子商务等许多网上通信业务都需要对双方或多方的身份进行确认，传统的 身份认证方式通常采用“用户名+ 口令”的形式来确认，但这种形式有许多缺点， 安全的身份认证方式是采用公钥密码体制来进行身份识别。 1 1 2 数字签名的概念 计算机网络的产生使得计算机通信逐渐被应用到政治、军事、外交、商业等 领域中，人们总是希望能通过网络通信传输对文件、契约、合同、信件和帐单等 进行数字签名来代替以往的手写签名。数字签名的目的是提供一种手段，使得一 个实体把他的身份与某个信息捆绑在一起。数字签名作为一种密码技术广泛用于 认证、授权和不可否认中。 1 手写签名与数字签名的区别 ( 1 ) 手写签名是所签文件的物理组成部分数字签名必须与所签文件捆绑在一 起 湖北工业大学硕士学位论文 ( 2 ) 手写签名通过j 标准签名比较或检查笔迹束验证，伪造签名比较容易。 数字签名是通过公丌的验证算法来验证。好的数字签名算法应该具有不可伪造性。 数字签名作为一种密码技术，具有以下功能和性质： ( 1 ) 可信性。签名的接收者相信接收到的签名确实是合法的签名者所签署的。 ( 2 ) 不可伪造性。只有签名者本人才能生成自己的签名。 ( 3 ) 不可重用性。签名含有文件的信息，不能作为其它文件的签名。 ( 4 ) 不可否认性。签名者事后不能否认自己的签名。 2 数字签名概念 d i i f i e 和h e l m a n 利用公钥密码体制的思想提出了数字签名的概念。一般 来说一个数字签名方案包括两个部分：签名算法和验证算法。数字签名的正式定义 如下： 定义1 1 一个签名方案是一个满足下列条件的五元组( p ，a ，k ，s ，n ： ( 1 ) p 是由所有可能的消息组成的一个有限集合。 ( 2 ) a 是由所有可能的签名组成的一个有限集合。 ( 3 ) k 为密钥空间，它是出所有可能的密钥组成的一个有限集合。 ( 4 ) 对每一个七k ，有一个签名算法s t g k j 平一个相应的验证算法8 v 对每 一个消息j p 和每一个签名：y a ，s i g , ：尸_ 4 和w ：p x a 斗 t r u e ，归b b ) 满足： 1 ，、ft r u e , y = s 辔i ( 石) v e t k “y 户1 如厶 j 氓( j ) 由工p 和y a 组成的数据对工，y ) 称为签名消息。 1 。1 3 数字签名的分类 按目的可以把数字签名分成普通数字签名和特殊数字签名f 如不可否认签名， 盲签名，代理签名等) 。 普通签名：就是由签名者自己用自己的私钥对消息进行直接签名。任何人都可 以用公钥来验证签名的有效性。这是一种最简单的数字签名，同时也是应用最广 泛的一种数字签名。 不可否认签名：任何人都可以验证普通签名，但现实生活中有时候需要在签名 者参加的情况下才能进行签名验证过程。满足这个要求的签名称作不可否认签名。 它可以使用在如下场合： o ) a 希望访问b 控制的“安全区域”。b 在授予a 访问权之前，要求a 对。访 问时间、日期”进行签名。另一方面，a 不希望别人了解这个事实，即没有a 的 2 湖北工业大学硕士学位论文 参与b 不能通过出示a 的签名及签名的验证，来证明“a 访问陔区域”这事实。 ( 2 ) 某公司a 开发的一个软件包。a 将软件包和他对软件包的不可否认签名卖 给用户b 。b 当场验证a 的签名，以便确认软件包的真实性。用户b 想把该软件 包的拷贝私自卖给第三者。由于没有公司a 参与，第三者不能验证软件包的真实 性，从而保护了公司a 的利益。 群签名：群签名的概念最早是由d c h a u m 和v a n h e y s t 提出，之后又有许多人 对它进行了研究。一个群签名方案允许群体中的任一个成员代表该群体签名，这 个签名是可用一个群公钥公丌验证的，同时它还实现了签名者的匿名性及签名文 件的不可链接性。 盲签名：是签名者在不知道签名消息具体内容的情况下对消息进行的签名。它 在电子支付系统与电子投票中均有重要的应用。盲签名是本文研究的对象。 1 2 盲签名的研究背景、目的及发展状况 盲签名是一种特殊的数字签名，它与通常的数字签名的不同之处在于，它使 得用户能够得到签名人的签名主口不让签名人知道他所要签发文件的具体内容。正 是这一特点，使得盲签名这种技术可广泛应用于许多领域，如电子投票系统和电 子现金系统等。1 9 8 2 年，d c h a u m 2 】首次提出了盲签名的概念。随后，人们分别基 于因子分解问题即f p ) 、离散对数问题( 即d l p ) 、二次剩余( 即q r ) 问题等相继提 出各种盲签名方案。1 9 8 3 年，c h a u m 3 基于r s a 公钥密码系统，首先提出基于因 子分解问题的盲签名方案，该方案可用于电子支付系统。s t a d l e r d 等1 4 1 建议在匿名 支付系统中应该建立一个可信的第三方。1 9 9 2 年，o k a m o t o 习基于s h n o r r 签名体 制，首先提出了基于离散对数问题的盲签名方案；1 9 9 4 年，c a m e n i s c h 掣6 】基于离 散对数问题提出了两种盲签名方案：第一种方案来源于d s a 的变形，第二种方案 以n y b e r g - r u e p p e l 签名体制为基础；1 9 9 6 年，f a n 等【7 】提出了安全性基于二次剩余 方根难解性的盲签名方案；1 9 9 8 年，f a n 等i s ! 提出了一种盲签名方案以增强c h a u m 盲方案的计算效率。2 0 0 0 年f a n 等1 9 】又提出了一种盲签名方案以增强c h a u m 盲签 名方案的随机性，这样攻击者就不能计算出签名者的签名以避免消息选择攻击的 威胁。国内最主要的成果是姚亦峰等1 1 0 】在广义e l o a m a l 签名盲化方面的工作：从 广义e i g a m a l 型签名方案出发构造相应盲签名方案的一般构造方法，并讨论了参 数选取所满足的条件。目前，除了己提出的各种基于不同困难性问题的盲签名方 案外，人们将盲签名和其他密码协议或方法相结合，譬如可证明安全性的引入， 基于身份的公钥密码体制的引入，椭圆曲线算法的引入，代理签名与盲签名结合 湖北工业大学硕士学位论文 的代理自签z 等等，提出了各种新型的亩签名方案【i - t s 。 尽管盲签名在理论和应用方面都取得了较快的发展，但也存在着许多问题需 要进一步研究和解决： 1 同一类型的盲签名方案不全、缺乏统一有效的盲化方法 现有的大部分盲化方案，如文献1 5 ，1 7 中的s c h n o r r 盲签名方案，都是孤立提出 的，缺少统一有效的盲化方法，不知道为什么要那样盲化，参数为什么要那样选取， 也不知道所给出的盲化方案是否是最优的，这些不足要求我们从更高的层面来研 究盲签名，研究统一的盲化方法。与浩如烟海的传统数字签名方案相比，盲签名 还存在同一类型的方案不全的问题。 2 盲签名方案的安全性有待进一步研究 很多盲签名方案本身存在着各种攻击手段( 如文献【16 】存在两个安全安性缺 陷) ，不但没有完全从理论上得以解决，而且还可能存在一些潜在的攻击手段，因 此，各种盲签名方案的安全性还有待进一步进行理论分析和实践检验。 3 盲签名方案不多、与盲签名相关的密码协议或方法的交叉研究不够 在各种签名技术及其相关技术( 代理签名、盲签名、基于身份的公钥密码体 制、椭圆曲线算法等) 之向很容易产生出新的数字签名技术，特别是与盲签名相 关的数字签名的研究还很不够。 1 3 论文的内容安排和主要研究成果 1 3 1 论文的组织与结构 论文围绕着目前盲签名领域存在的一些新闯题展开了研究和探讨，阐述了作 者三年来所做的工作。论文组织结构如下： 第一章介绍了盲签名的研究背景、目的及发展状况、本文的内容安排和主要 研究成果。 第二章首先介绍了相关的数学知识，特别介绍了在密码算法中经常使用到的 一些基础算法，如素性检测、原根的生成算法、大数的模幂运算、大数的模逆运 算等，并用c a p 软件加以实现：然后介绍了相关的密码学知识，如哈希函数、数 字签名等。 第三章首先对一些著名的盲签名方案的设计思想、方法和技巧进行深入研究 和分析；然后研究了如何利用c a p 软件对一段消息进行r s a 盲签名；接着研究了 s c b n o r r 盲签名的一般化问题，提出了s c b n o r r 型盲签名方案的一般构造方法、参 数选取所应满足的条件及其导出方案，并对其安全性作进一步的理论分析和证明； 4 湖北工业大学硕士学位论文 最后研究了代理签名和亩签名相结合i u j 题，对个基j ：身份的代理自签名方案及 其安全性进行分析。证明该方案存在两个安全性缺陷，对该方案加以改进，提出 了一个新型的基于身份和双线性对的代理盲签名方案。 第四章首先介绍了电子投票的一些初步知识，然后基于电子投票系统应当满 足的性质，结合实际需要，设计了一种较为实用的电子投票协议。并对电子投票 系统进行了系统设计，对各功能模块进行了详细设计。 第五章概括了全文的结论，并对未来的工作进行了展望。 1 3 2 主要研究成果和创新之处 作者取得了以下研究成果： 1 对一个基于身份的代理盲签名方案及其安全性进行分析，证明该方案存在 两个安全性缺陷，并对该方案加以改进，利用双线性映射理论，结合代理签名和 盲签名的优点，将代理签名技术融入到盲签名中，提出了新型的基于身份和双线 性对的代理盲签名方案；方案以身份为基础的公钥取代了以数字证书为基础的公 钥，省略了验证签名时从系统中获取公钥的步骤，减少了交互的次数，节省了存 储空间，并有效防止了原始签名人冒充代理签名人对消息进行签名，且限制了代 理签名人的代理签名权。 2 提出了s c h n o r r 型盲签名方案的一般构造方法、参数选取所应满足的条件 及其导出方案，并从盲签名方案的完备性、不可伪造性、盲性三个方面出发，对 其安全性作进一步的理论分析和证明。 3 用c a p 软件对一段消息实现了r s a 盲签名，并实现了在密码算法中经常使 用到的一些基础算法，如素性检测、原根的尘戍算法、大数的模幂运算、大数的 模逆运算等。 湖北工业大学硕士学位论文 第2 章数学基础和相关密码学知识 盲签名是一种特殊的数字签名，它与数字签名一样都是基于数学上某种在计 算上是困难性问题设计的，有较深的数学和密码学背景【2 0 1 。数论中的大数分解问 题( f p ) 、离散对数问题( d l p ) 以及密码学中的哈希函数和数字签名问题，都是 我们进行盲签名研究的基础。 2 1 数学理论基础 2 1 1e u i e r 定理与f o r m a t 定理 定义2 1 记0 = o ，n ，2 n ，) ，1 = 1 ，n + 1 ，2 n + 1 7 - - m ) ， 竹一l = 耳一1 ，开+ 弗一1 ，垃玎十以一l ，) ， 为方便起见，简i 己 o = 0 ，1 = i ，雄一1 = n 一1 则称集合乙：乙2 o ，l ，2 ，一一l 为模n 剩余类集，简称剩余集。 定义2 2e u l e r 函数侦| 1 1 ) 是指小于且与露互素的正整数的个数。 定理2 1 ( 整数唯一分解定理) 任一大于1 的整数能表示成素数的乘积，即对于 任一整数a l ，有 a = p l p 2 儿，p l p 2s 见 其中a ，p 2 ，见是素数，并且若 口= q l q 2 q 。，q l q 2 茎q 其中q l ，q 2 ，是素数，则 m = 一，p t = 吼“= 1 , 2 ，n ) 将相同的素数因子写成幂的形式，即其标准分解式为 a = p i p 2 。2 p 4 ，p i p 2 l ，( 参m ) = 1 ，则使得同余式9 7 = - l m o d m 成立的最小正整数y 叫 做g 对模m 的指数。若g 对模m 的指数是烈m ) ，则称g 为模数m 的一个原根。 定理2 6z 是域的充要条件是：p 为素数。 定理2 7 设奇素数p 满足如下标准素因子分解 p - l = n p 2 = p l p 2 p i = 1 型 又设整数g 满足如下条件( g ，p ) = l ，g “l ( m o d 力，i = 1 , 2 ，竹，则g 为p 的原根。 2 1 3 大数分解问题 整数唯一分解定理虽然在理论上阐明整数的可分解性，然而在现实中，我们 如果仅知道两个大素数的乘积，来求出这两个大素数也即对这个积进行分解却是 7 湖北工业大学硕士学位论文 极端斟难的。下面给出整数分解l i u 】题的定义： 定义2 5 设4 是一给定的j 下整数，求a 的素因子。即：把a 表示成 a = p l “p 2 0 p i “，其中p ，f - 1 , 2 ，k 是互不相同的素数，a ，1 ，i = 1 , 2 ，k 。 到目| j 为止，大数分解问题仍然是困难问题。许多密码技术的安全性都是基 于整数分解问题的困难性，例如现在广泛应用的r s a 体制签名方案被认为是安全 性最好的方案之一，它就是基于此问题提出的。 2 1 4 离散对数问题 到目前为止，离散对数问题仍然是困难问题。在密码学上，很多数字签名方 案的安全性都是基于离散对数问题的困难性，如数字签名标准( d s a ) 、e i g m a l 数字签名、s c h n o r r 数字签名等，下面给出离散对数问耐2 1 1 的定义： 定义2 6 设p 是一个大素数，g 是z ，的本原根，y 是z ，上的任一非零元素， 求唯一的整数x ，0 x p 一2 ，使得g 。= y m o d p ，记整数j 为l o g 。y 。 若我们知道g ，x , p ，则y 很容易被计算出。反过来，如果我们知道g ，y ，则 计算工是困难性问题。为了抵抗已经知道的攻击，一般p 至少取1 5 0 位，p 一1 应 该有大的素因子。 2 2 一些基础算法及其c a p 实现 本节主要介绍在盲签名中经常使用到的一些基础算法。比如，素性检测、原 根的生成算法、大数的模幂运算、大数的模逆运算等在很多公钥密码体制和签名 方案中使用。 2 2 1 素性检测 绘定一个正整数p ，判断p 是否是素数，称为素性检测。在本文所提的签名方 案中需要超大( 大于十进制1 0 0 位) 的素数。因此，素性检测是本文研究的一个 重要工具。目前有多种简单而且快速的素数判定定理，其中概率测试法是产生素 数最实用的方法。常用的概率测试法有以下几种： 1l e h m a n ( 勒曼) 测试法 该测试方法是由l c l l l l l 蛐【2 1 1 提出来的。测试算法如下： ( 1 ) 选择随机数a p ； ( 2 ) 计算v = 4 ”1 “m o d p ； 湖北工业大学硕士学位论文 ( 3 ) 如果、r 1 m o d t 7 ，或v 一l m o d p ，那么，肯定不是素数； ( 4 1 如果v = l m o d p ，或v = l m o d p ，那么p 不是素数的可能性最多是5 0 。 同样，如果p 是合数，随机数a 是p 为素数的证据的概率大于5 0 。对a 选择n 个不同的随机值，重复n 次这种测试，如果计算结果等于1 或一l ，并不恒等于l ， 那么p 可能是素数所目的错误风险不超过1 2 。当我们把n 取成较大的数值时， 基本上就能保证产生的足素数了。 2r a b i n m i l l e r 测试法 这是个帽对柬说很容易且广泛使用的简单算法，它基于g r a ym i n d 2 2 1 的部分 想法，由m i c h a e lr a b i n m l 发展。事实上，这是在n i s t ( 国家标准和技术研究所) 的d s s 建议中推荐的算法的一个简化版划。首先选择一个待测的随机数p ，计算 b ，b 是2 整除p 一1 的次数( 即2 6 是能整除p l 的2 的最大幂数) ，然后计算n l ， 使得p = l + 2 m 。测试算法如下： ( 1 ) 选择随机数a o 且z = 1 ，那么p 不是素数： 【5 ) 设j = j + l ，如果j 。 ( 2 ) 对于所有属于f 值域的y ，求解x ，使之满足f ( x ) = y 在计算上是不可行的。 也就是说，一个单向函数是个满足下列条件的函数：它将一个定义域映射到 一个值域，使得计算函数值很容易，但由函数值求解原条像在计算上是不可行的。 关于单向函数，b r u c es c h n e i c r 给出了一个生动地比喻：打碎盘子是一件很容易 的事情，然而，要把所有打碎的盘子的碎片在拼成一个完整的盘子，却是非常困 难的。 定义2 9 ( 单向散列函数) 单向散列函数在密码学中简称单向函数或h a s h 函数， 它是密码学中的一类特殊的函数。单向散列函数h ( x ) 作用于一任意长度的消息m ， 返回一固定长度的散列值h ：h = h ( m ) 。它具有下面的性质： ( 1 ) 给定m ，很容易计算h ： ( 2 ) 给定h ，根据h = h ( m ) 求解m 在计算上是不可行的； ( 3 ) 给定m ，要找到另外一消息m ，使得h ( m ) = h ( m ) 是不可行的。 性质( 2 ) 和( 3 ) 分别被称为单向性和无冲突性。单向散列函数虽然不是加密算法， 却在密码学中有着广泛的应用。与各种加密算法有着密切的联系。一般来说，散 列函数是公开的，对处理的过程不用保密。单向散列函数的安全性在于它的单向 性。正因为这样，单项散列函数广泛应用于密码学的各个领域：密码协议、密码算 法、数字签名等。 将h a s h 函数应用到数字签名里可带来以下好处： ( 1 ) 可破坏数字签名方案的某些数学性质，如同态性。 ( 2 ) 通过对消息摘要签名取代对消息签名，可以提高签名的速度。 ( 3 ) 签名可以不包括原消息。增强了保密性。 1 3 湖北工业大学硕士学位论文 ( 4 ) 可以用公钥密码实现保密刚私钥密码实现数签名，从而将签名和加密分 开处理。 h a s h 函数除了可用于数字签名之外，还可以用于其他方面，譬如消息的完整 性检测、消息的来源认证检测等方面。为保证消息的完整性，及时发现消息是否 被非法篡改，可以在消息传输之前先对消息做h a s h 变换，然后对消息进行传输， 对于接收到的消息也做h a s h 变换。将传输前的消息的h a s h 变换值与接收到的消 息的h a s h 变换值作比较，如果两者相同，则可以认为消息在传输过程中没有被篡 改，否则消息一定被非法篡改了。 h a s h 函数的安全性是指：在现有的计算资源下，找到一个碰撞是不可能的。 目前己经设计出大量的h a s h 函数，如r a b i nh a s h 方案、m e r k l eh a s h 方案、 n h a s h 算法、m d 4 算法、m d 5 算法、s h a 等。在2 0 0 4 年8 月1 7 只召丌的国际 密码学会议( c r y p t o 2 0 0 4 ) 上来自山东大学的王小云教授做了破译 m d 5 ，h a v a l 1 2 8 ，m d 4 和r i p e m d 算法的报告，引起全球密码学界的广泛关注。 2 4 数字签名体制 2 4 1r s a 数字签名 1 r s a 数字签名方案 r s a 数字签名方案是由r i v e s t ，s h a m i r 和a d l e m a n 联合提出的，是在r s a 公 钥密码系统上建立的一个重要的签名体制，它用到了初等数论中的一个重要定理 一欧拉定理，其安全性依赖于大数分解问题的困难性。其算法如下： ( 1 ) 系统初始化 随机选取两个大素数p ，q ， = p q ，妒( 甩) = ( p i x q - 1 ) ，随机选取p 满足 g o d ( e , 烈厅) ) = l ，1 e 烈以) ；利用扩展e u c l i d 算法由p 求出私钥d ，满足 d e = l ( m o d 烈月) ) ，公钥是( h ，0 ，私钥是d 。 ( 2 ) 签名阶段 假设消息为r n z ，签名人b o b 计算 j ：，n o m o d 并将签名的消息( r a ，s ) 传送给接收人a 1i c e 。 ( 3 ) 验证阶段 接收人a l i c e 接收到签名消息( m ，j ) 后，j 乙，计算 4 湖北工业大学硕士学位论文 m7 = p ( 5 ) = s 。r o o d n 并判断m 是否等于所，如果小= 用，则说明签名s 确实是用户a 所产生的，否则， 签名占可能是由攻击者伪造生成的。 注：本章中以后凡未特别说明，用m 代表待签名的消息：b o b 代表签名者， a 1 i c e 代表接收者。 2r s a 数字签名算法的正确性 签名算法的正确性表现在如果a 1 i c e 和b o b 成功地执行上述方案，则最后的签 名能够通过验证。本节将从数学的角度来验证r s a 签名算法的j 下确性，即要验证 m = m 是否成立。 证明要证明m ，= m ，即证明( m 。) 。；m ( m o d n ) 。 因为d e = i ( m o d 以n ) ) ，所以存在整数t l ，使得d e = f 烈n ) + l 。对于任意明文 m 2 。，当g c d ( m ，1 ) = l 时，由e u l e r 定理得 m 州4 l ( m o d n ) 从而 ( m 4 ) 。im 9 。卜。( r o o d n ) i 朋一8 ”m ( r o o d n ) ( 1 。) m ( m o d n ) im ( m o d n ) 当g e d ( m ，开) 1 时，因为n = p q 并且p 和口是两不同素数，所以g e d ( m ，n ) 一定 为p 或者毋不妨设g c d ( m ，n ) = p ，刚m 一定是p 的倍数。设胁= c p ，l s c q ，则 此时g c d ( m ，g ) = 1 ，由e u l e r 定理得m 州9 ii ( m o d q ) ， 根据模运算性质有【m 烈们】州；i ( m o d q ) ，即m 州l ( m o d q ) 。因此存在某整数k l 使得m 艇。= l + 幻。两边同乘h ( m ) = c p 后得 ，摊州1 + = c p + - 叼，碍= m + k c n 即m 州1 m m ( m o d n ) ，从而( m 4 ) 。i m ( m o d n ) 。 由此可见，r s a 数字签名算法是正确的。 3l i s a 安全性分析 对r s a 的攻击方法有： ( 1 ) 分解模数f l ： ( 2 ) 确定妒o ) ： ( 3 ) 直接确定d 首先，给定n ，确定( 月) 等价于分解模数n 。这是因为己知n 和( 厅) ，由刀= p q ， 烈刀) = ( p 一1 g 1 ) 得到p 2 - ( n 一矿o ) + 1 ) p + n = o 。该方程的两个根为p , q ，即能 湖北工业大学硕士学位论文 够分解i i 。反过来，知道模数n 的索凶，分解，自然可计算o ( n ) 。 显然，己知模数r l 的素因子分解，使用扩展的e u c l i d 算法可从e 计算出私钥 d 。反过来，如果有算法可以由公钥( ( n ，e ) 直接计算出私钥d ，利用它可以构造分 解模数n 的概率算法。由此可见，从公钥( n ，e ) 计算私钥d 与分解模数n 在计算上 是等价的。 另外从b k a l i s k i 和m r o b s h a w 在1 9 9 5 年发表的文章 2 8 知道，给定e 和 n 使用目前已知的算法求出d 在时制丌销上至少和因子分解问题一样大。为此我 们可以把“因子分解性能”作为评价r s a 安全性的基准。当数字n = p g 足够大时， 分解它的素因子是个困难问题。1 9 9 6 年使用较新的广义数域筛法分解长度为1 3 0 的十进制数n 的时i 日j 是5 0 0 个m i p s 年( 即每秒1 0 0 万条指令的处理器工作5 0 0 年) 。 当前整数素因子分解算法能分解十进制长度是1 3 0 ，故选取的素数p 和q 应该是长 度为1 0 0 的十迸制数( 相当3 2 2 位二迸制数) 。目前l i s a 的些硬件实现使用5 1 2 位二进制数n ( 相当1 5 4 位十进制数) ，所以不能提供长期的安全性。我们推荐7 6 8 位，长期安全应该至少使用1 0 2 4 位。 下面列举在实现r s a 时要注意的一些问题。 ( 1 ) 在构造n 时应选择p 和q 的长度差不多，数值上不要太接近，并且p 一1 和q l 有大的素因子。( p 一1 ，q 1 ) 应该较小。一般选择p 使得p 和( p 一1 ) 2 均是 素数。 ( 2 ) 每个用户必须有自己的模数n ，用户之问不要共享n 。有两个原因： i 某中心选择公用的r s a 模数n ，然后把( q ，d ，) 分发给众多用户。由任何一对 ( 岛，d ，) 都能分解模数n 。从而本质上任何用户都可以求出共享该模数的每个用户的 解密密钥4 。 i i 如果用户l 的公钥为n ，p 。，用户2 的公钥为n ，p 2 ，其中心，岛) = 1 。用户 3 要把同一条消息x 发给用户l 和用户2 ，它们分别为y l = p m o d n ，y 2 = j 。m o d n 窃取者截取y ，y ：就可以计算出x ，具体步骤是： 因( 巳，吃) = l ，可以计算出岛= 岛r o o d e 2 ，也= ( | l i ，e l - 1 ) e 2 ，故可计算 j = y l ( y z 也) m o d n 。 2 4 2s c h n o r r 数字签名方案 s c h n o r r 数字签名方案由c s c h n o r r 于1 9 8 9 年提出，它的安全性依赖于离散 对数问题的困难性。设待签的消息为胁z ，。其算法如下： ( 1 ) 系统初始化 1 6 湖北5 - 业大学硕士学位论文 设p ，q 为两个大素数，其中q 】p l ，p 2 5 ”，q 2 ( 以确保在z 。中求解离 散对数的困难性) ，g z ，且满足9 9 = l m o d p ( a pg 是z 。的本原根) 。签名人的私 钥为j e z q ，对应的公钥为y = 9 7 m o d p 。p ，q ，g ，y 为公钥，h ( ) 为具有无碰撞 性的哈希( h a s h ) 函数。 ( 2 ) 签名阶段 签名人b o b 随机选取k ，k z 。，计算 ，= g m o d p ， e = h ( r i l 肘) ， s = k + x e m o d q 并将签名结果( p ，s ) 发送给消息接受者a 1 i c e 。 ( 3 ) 验证阶段 a 1 i c e 计算 ，= g ym o d p ， e 7 = h ( r m ) 并验证e = p ，若等式成立，则签名有效；否则签名无效，输出。f a l s e ”。 2 5 本章小结 本章主要介绍了相关的数学知识和密码学知识，特别介绍了在盲签名中经常 使用到的一些基础算法，如素性检测、原根的生成算法、大数的模幂运算、大数 的模逆运算等，并用c a p 软件加以实现。 1 7 湖北工业大学硕士学位论文 第3 章盲签名 盲签名是一种特殊的数字签名，它与通常的数字签名的不同之处在于，签名 者并不知道他所要签发文件的具体内容。正是这一特点，使得盲签名这种技术可 广泛应用于许多领域，如电子