（应用数学专业论文）群盲签名方案研究.pdf

河南大学研究生硕士学位论文第1 页 摘要 数字签名是当前网络安全领域的研究热点。特别是在电子商务、电子银行、 电子政务等应用领域。随着网络的发展和信息系统的广泛使用，适用于不同应用 环境的特殊数字签名也被提出，包括代理签名、群签名、盲签名、群盲签名等等。 群盲签名可以看成是群签名的一个变体，兼具了群签名和盲签名的优点，在 电子商务、网上银行等场合都起着重要作用。如何构造安全、高效的群盲签名方 案始终是密码学领域的一大热点。 本文首先阐述了盲签名方案的研究状况及背景，分析了典型盲签名方案的安 全性，并利用椭圆曲线“短密钥，高安全性 的特点构造一个基于椭圆曲线的盲 签名方案，并在此基础上设计了一个身份识别协议。其次对群签名方案的特性进 行了分析，研究了现有的一些群签名方案的安全性，并根据自己的研究提出一个 安全高效的群签名方案。最后，以提出的群签名方案为基础通过引入盲化知识签 名构造了一个安全高效的群盲签名方案，该方案能满足群盲签名的各种安全特性。 主要工作包括： 一设计了一个基于椭圆曲线的盲数字签名及其身份识别协议。 二对典型的群签名进行了分析，并提出一个安全高效的群签名方案，并分 析其安全性。此方案通过引入一次行密钥解决了现有签名方案中的抗合谋攻击的 缺陷，该方案的签名过程和验证过程计算量较小。 三以新提出的群签名为基础，结合盲签名的特性，构造一个安全高效的群 盲签名方案。 关键词：数字签名；群数字签名；盲数字签名；群盲数字签名； 第1 i 页河南大学研究生硕士学位论文 a b s l 撇t d i g i t a ls i 罂l a l m i st j b er e s e a r 曲向c 璐o f a m e n tn e 觚o r ks e c u r i 够f i e l d ，e s p e c i ：a l l y i ne l e c t r 0 伍cb 髑i n e s s ，e l e c 懒l i cb 锄k 艇l de l e c 仃i l i c 9 0 v e m m e n te t c w i n lm e d e v e l o p m e n to fn e 帆o r k 觚dn i eb r o a d 邺eo ft h ei i l 】衙m a t i o ns y s t 鼬s ，d i g 砌s i 舯加鹏 i sb r o a d l y 璐e d 嬲狮e l e c n d n i cs i l n u l a 土i 蚰o fh 锄d m j 缅gs i 驴a t u r e 晰mt h ed e 印 r e s 韶r c 也s o m e 蹦i a ld i 萄t a ls i 簿m m r e sf o r 吐i es p e c i f i c 钮v i r o m n e n _ t sa r ep i 0 p o s e d r w h i c ha 陀p r o x ys 适m m l r e ，磬0 u ps i 伊擒士u r e ，b l i i l ds i 粤谢t u r e ，罂0 u pb l i n ds i 孕硪t u r e 柚d s o o n g r o u pb l i i l l ds i 磬协加r ei sc o n s i d e r dt 0d e r i v e 伊o u ps i 弘a t u r e ，a sh o l d i l l g a d v u l t a g e so fb o m 訇0 u ps i 孕扭m r e s 粕db l i l i ds i 罂硪t u r e s ，g r o u pb l i n ds i 弭硪t u r eh a s p l a y e da ni m p o r t a i l tr o l ei ne l e c 缸。面cc c 咀蚰e r c e ，e l e c t r 0 i i i cv 0 t ee 乇c h o wt 0b u i l da n e 街c i 朗t 酗u pb l i n ds i 朗a 旬瞰i e l u t i o ni s 心嘲r y st l 尬h o t s p o t i nt l 抡f i e l do f c u r p t o g 伯p h y t 拉sp a p e ri i l 打o d u c e st h e a r c hb a c 和舢d ，s i g 面f i c a n c ea n d 也ea c 胁a l i 够o f r e s e a 眠i ha b o u tb l i i l ds i g n a t i l r es c h 锄e d e s c r i b l e 也e 锄l y s i so fs c c u d 锣o n 帅i c a l b l i n ds i 朗a t l 鹏血m eu s eo f “s h o r t 砸v a t ek e y s ，h i 曲s e c 嘶妒m ea u 也o rp r o p o s e da s e c u r eg r o l l ps i g i l 锨鹏锄di t si d 酬f i c 撕衄s c h e m e 孤dn l e i la i l a l y i z e st l l ep r o p e n i e s a n dm e 0 巧o f 毋1 0 u p s i 印a t l l r e ，咖d ym ep r e s e n t 磬0 u ps i 粤磁t u r e sa n dp r e s e n t e da s e c u r e a n de 伍c i e n t 鲫u ps i 鄂l a t u r e f i n a l l y ，璐堍n 圮i d e ao fb l i i l ds i g 舳：t i j r eo fk n o w l e d g e p r e s e n t e d as e c u r e粕de 伍c i e n t g r o u p b l 试d s i 掣l a ：t u r e s c h e m eb 弱e dl e a ：b 0 v e - m e n t i o n e d 罂o u ps i 舀m t u r e ，锄da l l a l y z e di t ss e c l l r i 吼t h es d 屺m eh 硒m e ta 1 1 s e c u “t ) ，r e q u i r e m c n t so f 邸u pb l i i l ds i 掣瞰u r e m a i m ys t u d ya sf o l l o w s ： f i i 枝，d e s i 印ab l i n ds i 舯纳瞰eb 嬲c d0 ne c d l pa n di t si d e 而6 c a t i o ns c h e m e ， a n a l y z i i i gi 招s e c 谢够 s e c o n d ，a i l a l y i z et ：h es e c u r i 锣o ft y p i c a lg 的u ps i 罂皿嘁a n dp r e s e n tas e c u r ea n d e 伍c i e n t 舒0 u ps i 舀擒l u r e ，w m c hi sd e s i g n e ds i i 】1 p l y nc a nr e s i s tt l l ec o m p 趾y a ：t t a c k 1 1 1 i r d ，b 2 l s e dn l e 粥wg r o u ps i 印a t i 聆，u s i n g 也ei d e ao fb l i n ds i 印a t u r co f k n o w l e d g ep r e s e r 她as e c 珈ea n de 岱c i e n t 毋_ o u pb 1 砌s i 毋1 a ：t u r es c h e m e k e ”o r d s ： d i g i t a ls i 印a t u r e ；掣o u ps i 孕l a ：眦； b l i n d s i 孕谢c u r e ；g r o u p b l i 芏l d s i 毋翰t l 鹏 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位中请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成的，对所研究的课题有新的见解。据我所知，除 文中特别加以说明、标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过的研究成果，也不包括其他人为获得任何教育、科研机构的学住或证书而 段保存、) 乌岛学位论文( 纸质又奉和吧亍又奉) o ( 涉及保密内容的学位论文在解窑后适用本授权书) 学住获得者( 学位论文作者) 签名： 王幺蜀 4 # 2 0 驴辨月，o 目 学住论文指导教师签名：丑墨：盗 2 0 昭年6 月厂。曰 河南大学研究生硕士学位论文第l 页 第1 章绪论 当今的社会己经进入了信息时代，因特网( i n t e r n e t ) 正发挥着越来越大的作 用，这无疑巨大的推动了社会经济的发展，同时，也给人们的日常生活带来了巨 大的便利。当使用因特网这样开放的网络进行通信和商业活动时，一个十分现实 和紧迫的问题就是要保证信息的保密性、完整性和可用性。解决这一问题的重要 方法就是密码和信息安全技术n 3 ，密码学盥1 的发展始终与信息社会的需求密不可 分。 1 1 选题的背景及意义 由于因特网的飞速发展，人们的生活方式也有所变化。越来越多韵人已经成 为网络用户，人们可以借助i n t e r n e t 进行证券交易、购物等商务活动。然而，现 代信息技术是一把双刃剑，它一方面给人们带来了巨大好处的同时，另一方却又 给人们带来前所未有的威胁 5 3 。因此，信息安全成为信息社会急需解决的重要 问题之一。 信息系统安全的中心内容是保证信息在系统中的保密性、认证性和完整性。 为了满足这一需要，数字签名技术应运而生。但是，随着数字化信息社会的发展， 对数字签名技术的要求也变得更高更迫切。在许多安全业务中，合法用户要求提 供匿名性保护，而可信机构又希望可以随时跟踪违法行为3 。在现有的签名体制口3 中，只有群盲签名满足上述两种性质。 群盲签名是一种具有盲性、匿名性等特性的数字签名9 3 技术，因此它能够为 用户提供盲性，为签名人提供很好的匿名性，同时在必要的时候，又可以通过唯 一确定的可信机构来撤销匿名性。再加上其他的安全特性，使得群盲签名在诸如 电子商务、电子银行中有着广泛的应用前景。 群盲签名在实际中的应用主要表现在在电子现金系统中的应用，而在电子现 金中的应用在于提供具体的解决方案。比如一个有多个银行组成的电子现金系统， 多个银行组成一个群，而为了保护消费者的隐私，在取款过程中，银行不能跟踪 电子现金的流动，也不能将特定的消费者与所提取的电子现金联系起来。这就需 要群盲签名来实现。虽然各种电子现金系统的要求不尽相同，但通常应满足不可 伪造性、匿名性、不可追踪性等特性，因此只有设计出安全、高效的群盲签名方 案才能保证网上银行的正确流通。 第2 页河南大学研究生硕士学位论文 1 2 群盲签名的研究现状 群盲签名是群签名的一种变体， 随着群签名和盲签名的发展而发展。 名和群签名的研究现状。 是在群签名的基础上增添了盲签名的特性， 因此要介绍群盲签名研究现状必先研究盲签 自d 。c h a u m 于1 9 8 3 年提出盲签名n 明的概念以来，盲签名便因其潜在的应用价 值而得到密码学界的广泛关注。于是，各种体制的盲签名如r s a 盲签名、e l g a i i l a l 盲签名等相继而出。盲签名在其发展过程中，经历了大致两个阶段。第一个阶段 是从1 9 8 3 年一2 0 0 1 年，这段时间对盲签名的研究还不是很活跃。第二个阶段是从 2 0 0 1 年至今，对盲签名的研究进入到比较活跃阶段，许多性能良好的盲签名n 0 1 6 1 8 1 都是在这一时期提出的，同时随着对盲签名理论研究的成熟，密码界学者开始尝 试把盲签名理论应用到实际当中。 随着盲签名的发展，做为特殊数字签名分支的群签名n 们也得到密码界人士的 关注，从1 9 9 1 年d c h a u m 和e v a nh e y s t 提出第一个群签名体制后n 引，群签名的发展 可以粗略分为两个阶段，第一个阶段是从1 9 9 1 年一1 9 9 7 年，这个时期对群签名的 研究处于不活跃的初步阶段，第二个阶段是从1 9 9 7 年至今，1 9 9 7 年j c 锄e n is h 和 m s t a d l e r 在文献 2 0 中首次提出了适用于大群体的群签名方案，群签名的研究 进入到一个非常活跃的发展时期【姗2 j ，虽然增加群成员方面的研究已经取得了很 大的成果，但在删除群成员方面的研究仍裹足不前。直到2 0 0 1 年，e b r e s s o n 和j _ st e r n 给出了基于c s 9 7 第二个方案的一个可撤消群成员证书的群签名方案，群签 名的研究才有了第二次突破性的进展。随后，密码工作者又相继提出了几个可撤 消的群签名方案心7 瑚瑚棚3 。但这些方案的效率仍不够理想，有待进一步探讨。 近几年来，密码界人士在群签名方面的研究取得了丰富的成果，而且发展非 常迅速。但是，群签名的使用还存在以下几个问题： ( 1 ) 群签名的长度比一般的数字签名的长度大得多，签名过程及打开过程都需 要较大的运算量，导致签名的效率很低，因而实用性差。 ( 2 ) 目前很多群签名算法、验证算法和群成员成线性依赖关系。 ( 3 ) 有些方案不能抵抗联合攻击。如晌l i e s e 和t s u d 设的文献1 2 5 捌中的方案等。 鉴于群签名中存在的这些缺陷和问题，密码界的学者提出了以下几个值得重 视的研究问题： ( 1 ) 如何安全有效地废除群成员。即如何设计一个废除群成员的方法，使得一 河南大学研究生硕士学位论文第3 页 个群成员被废除后，他原来的私密钥和成员证书不能再用于签名，而且不影响他 原来所做的签名的安全性。 q ) 如何设计高效的打开群签名的算法。即如何使群管理员不需要大的计算量 就可以打开签名而确定出签名人的身份。 h ) 群签名相关的数字签名及其应用。与群签名相关的数字签名及其应用的研 究还很不够。分级多群签名1 3 1 3 2 1 、群盲签名、多群签名和子群签名等都有实际应 用背景，然而对它们的研究处于起步阶段。 群签名、盲签名的迅速发展使密码界人士对群盲签名产生了兴趣，1 9 9 8 年 l y s y a n s k a y a 和r a i i l z a n 首次提出了群盲签名的思想和相应方案口3 刮。群盲签名方案 是以群签名方案为基础，并加上盲签名特性设计而成。因此安全、高效群签名的 提出对于群盲签名的设计有着非常重要的意义。近几年来，随着多银行电子现金 系统兴起，同时具有盲性和匿名性的群盲签名也倍受人们关注。为了保证电子银 行的正常流通，设计安全、高效的群盲签名方案已成为密码学研究的热点问题。 1 3 主要研究内容及结构安排 本文首先研究了盲签名的产生背景并对现有的盲签名方案进行了安全性分 析；利用椭圆曲线“短密钥、高安全性等特点提出一个基于椭圆曲线的盲签名 方案及其身份识别协议；接着对群签名方案的特性、设计原理进行了分析，研究 了现有的一些群签名方案的安全性，并根据自己的研究提出一个安全高效的群签 名方案；最后，以提出的群签名方案为基础通过引入盲化知识签名构造了一个安 全高效的群盲签名方案，该方案能满足群盲签名的各种安全特性。 本文的创新点如下： 一提出一个基于椭圆曲线的安全高效的盲签名方案并及其身份识别协议； 该方案具有高效率、高安全性等特点，设计的身份识别协议能正确识别主体的身 份。 二提出一个安全高效的群签名方案并分析了其安全性，该方案具有群公钥 为一常量且群签名长度独立于群成员个数，签名和验证过程计算量小等优点。然 后以新提出的群签名方案为基础，结合盲签名的特性，设计一个安全、高效且实 用的群盲签名方案。 本文的结构安排如下： 第l 章介绍了信息安全的重要性及群盲签名产生的背景及意义，并介绍了群 第4 页河南大学研究生硕士学位论文 盲签名的研究现状和现阶段存在的主要问题，指出设计安全、高效的群盲签名已 成为密码学研究的一个热点，最后给出了本文研究的主要内容和结构安排。 第2 章简要介绍本文所需的数学知识和密码学知识，其中数学知识包括给一 些代数的基础知识，离散对数问题和椭圆曲线的相关知识；密码学知识包括r s a 密码体制和椭圆曲线密码体制及h a s h 函数的想关知识。 第3 章介绍了盲签名的概念及其特性，对典型的盲签名方案进行了分析，设 计了一个基于椭圆曲线的盲签名方案及其身份识别协议。并对该方案的安全性进 行分析。 第4 章在介绍了群签名的概念和应满足的特性后，给出了一些典型的群签名 方案的安全性分析，最后，提出了一个新的群签名方案，并对其安全性进行了分 析。 第5 章先介绍了群盲签名的概念和应满足的特性，然后以新提出的群签名为 基础，结合盲签名的特性，构造了一个安全高效的群盲签名方案，并对其安全性 进行分析。 最后，结束语中对全文的研究工作进行了总结，并指出了可以继续探索的方 向。 本章小结 首先介绍了信息安全的重要性及群盲签名产生的背景及意义，接着介绍了群 盲签名的研究现状和现阶段存在的主要问题，指出设计安全、高效的群盲签名己 成为密码学研究的一个热点，最后给出了本文研究的主要内容和结构安排。 河南大学研究生硕士学位论文第5 页 第2 章预备知识 数学知识是信息安全保密技术的一个重要工具，大部分现行的公开钥密码体 制和计算机网络安全系统都是以数学问题为基础。本章将主要讨论文中用到的一 些数学知识及其涉及的密码学知识。 2 1 代数基础 本节将重点讲述文中涉及的代数知识。 2 1 1 群 群( 觚u p s ) 是抽象代数学的重要组成部分。本节探讨群的有关概念和性质【3 9 】。 定义2 1 一个群( g ，) 是由一个满足下列三个条件的二元运算“ 构成： ( 1 ) 群运算是可结合的； ( 2 ) 有一个称作单位元的元素l g ，使得对所有的口g ，有口1 = l 口= 口； ( 3 ) 对每一个口g ，有一个称作口的逆元素6 使得6 口= 口易= 1 ，把6 记为口- 1 。 一个群g 是a b d i 孤群，如果它还满足下列条件： ( 4 ) 对所有的口，6 g 有6 口= 口6 。 对加法群而言，通常用o 来表示单位元素，用口表示口的逆。 定义2 2 如果i g i 是有限的，那么群g 是有限群。一个有限群的元素个数称为 它的阶( o r d e r ) 。 定义2 3 设g 是一个群，如果g 中有一个元素口使得对每一个6 g 都存在 一个整数f 使得6 = 口，则称g 是一个循环群，a 称为g 的一个生成元。 定义2 4 设g 是一个群，口g ，口的阶定义为使得= l 的最小整数t 。 定义2 5 设h 是群( g ，) 的一个非空子集，如果h 本身在群g 的运算“ 之下构成一个群，则称h 是g 的一个子群。如果h 是g 的一个子群且日g ，则 称h 是g 的一个真子群。 关于循环群有以下基本性质： ( 1 ) 循环群的子群也是循环群； ( 2 ) 设g 是一个群，如果口g 的阶是t ，则矿的阶是z g c d o ，j j ) ； ( 3 ) 设g 是一个阶为疗的循环群，d 刀，则g 恰有) 个阶为d 的元素。特别 地，g 有中( ，z ) 个生成元。 第6 页河南大学研究生硕士学位论文 2 1 2 环 环( 慰n g ) 是抽象代数学的重要组成部分。本节将探讨环的有关概念和性质 1 4 0 4 l 】 口 定义2 6 一个环( r ，+ ，x ) 是由两个满足下列条件的r 上的二元运算“+ 和 “( ”构成： ( 1 ) ( r ，+ ) 是一个a b d i a n 群，单位用o 表示； ( 2 ) 运算是可结合的，也就是说，对所有的口，6 ，c 有口伯c ) = 6 ) c ； ( 3 ) 有一个乘法单位l ，使得对所有的口l = l 口= 口； ( 4 ) 乘法和加法由分配律联系着，也就是对所有的口，西，c r 有 口p + c ) = ( 口6 ) + ( 口c ) 和p + c ) 口= p 口) + 如口) 。 如果一个环( r ，+ ，x ) 还满足条件：对所有口，6 r ，有口6 = 6 口，则环偎， + ，) 为交换环。 定义2 7 设r 是一个环，口r ，如果存在一个元素6 r 使得口6 = l ，则称拉 是一个单位或可逆元素。 环r 的所有单位之集关于乘法形成一个群，称为足的单位群。 2 1 3 域 域( f i e l d ) 是抽象代数学的重要组成部分，本节将探讨域的有关概念和性质 邸，3 6 ，3 羽。 定义2 8 满足下列条件的一个交换环称为一个域：所有的非零元素都有乘法逆。 定义2 9 设f 是一个域，如果对任何m l ，l + 1 + l + l 0 ( 柳个l 相加) ， 则称f 的特征为o ，否则，f 的特征是使得1 = o 的最小正整数m 。 百 定理2 1 z 。是一个域，当且仅当月是素数。如果刀是素数，则z 。的特征值是玎。 关于特征值有以下重要事实：如果一个域的特征不是o ，则它的特征必是素数。 2 1 4 有限域 密码学中用到很多有限域h ( f i n i t ef i e l d ) 中的运算，因为可以应用数论 中的理论，保持数的大小在有限的范围内，且不会有取整的误差。 只含有有限个元素的域称为有限域。有限域中元素的个数是一个素数，或者 是一个素数的乘方，记为z p 或者叶，其中p 为素数。 z p 是一个具有p 个元素的素数有限域。如果g = p “，p 是素数，刀1 是整 河南大学研究生硕士学位论文第7 页 数，则f 是一个具有g 个元素的多项式有限域。有限域中元素的个数称为该域的 ， 阶。 在有限域中，加法单位元是0 ，乘法单位元是1 ，每一个非0 的元素都有一个 惟一的乘法逆元。有限域中运算满足交换律、结合律和分配律。 很多密码系统是基于z d 的，为了使系统更复杂，可以使用多项式有限域f ，来 构造密码系统。在对多项式有限域的实际研究中，用到最多是有限域e 。，在硬件 上，利用线性反馈移位寄存器可以快速地实现e 上的运算。因此，e 上的计算通 常比z 口上的运算快。 已经知道，乘法群z _ ( 矽是素数) 是一个阶为p 一1 的循环群。事实上，任何 有限域的乘法群都是循环群：b 0 ) 是一个矿一1 阶的循环群。 r 2 2 离散对数问题 离散对数问题是大量密码协议的基础，密码学中，常用的单向函数是按模指 数运算，求按模指数运算的逆运算问题就是计算一个数的离散对数问题。这里这 里只介绍文中所用到的素数有限域z 。上的离散对数问题。 一般地，一个群g 上的离散对数问题定义如下： 定义2 1 0 是一个有限a b e l 群，p ，q g 为g 的任意两个群元素。若已知存 在整数聊，使得q = p 成立，则由群元p ，q 及群g 求出胧的问题称为群g 上的离 散对数问题，简记为d l p ( d i s c r e t el o g a r i t h i i lp r o b l e m ) ，而称数肌为群元q 的离 散对数，称p 为群g 的生成元。 显然，对于有限a b e l 群g 上的任何d l p ，都能在d ( ig1 ) 的时间内通过穷举搜 索逐一计算p ，p 2 ，尸辫，得到求解。而在实际中，当群g 的阶足够大时，穷 举搜索是没有实际意义的。 由于定义在有限域上的离散椭圆曲线群是一个有限a b e l 加法群，其基本运算 是椭圆曲线群上的群加法运算，即点加运算。相应地，群运算p ”相当于椭圆曲线 群上的数乘运算。因此可以得到椭圆曲线离散对数问题的定义。 定义2 11 伊) 表示定义在有限域z 。上的椭圆曲线e 在扩域f 上的有理子群， 设任意两点p ，q e ( f ) ，若已知对某个整数聊有q = ，护成立，则称数肌为点q 的 椭圆曲线离散对数，简记为e c d l ( e l l i p t i cc u r v ed i s c r e t el o g a r i t h i l l ) ；而由p ，q 及e 求出朋的问题则称为e 上的椭圆曲线离散对数问题，简记为e c d l p ( e 1 1 i p t i c 第8 页河南大学研究生硕士学位论文 c u r v ed i s c r e t el o g a r i t h n lp r o b l e m ) ：相对于点q ，点尸称为基点( b a s ep o i n t ) 。 显然，椭圆曲线离散对数是不惟一韵。设p 点的阶是，且整数肌，z 均为e 的 椭圆曲线离散对数，则m ，露之间满足脚毫以啪d ，。故在椭圆曲线离散对数问题中， 约定椭圆曲线离散对数历是一个小于，的正整数。 与一般的有限乘法群上的离散对数阀题不同，有限域上韵椭圆曲线离散对数 问题的求解更难。 2 3 椭圆曲线问题 根据密码体系韵研究需要，这里将探讨韵是光滑的椭圆曲线阳3 。这一曲线在解 析平面中表现为一条非奇异( n o n s i n g u l a r i t y ) 的三次平面曲线。由r i e 唧a n r o c h 定理和亏格公式可知，任何一条椭圆曲线都可以用一个三次方程来表示，这个三 次方程一般称为w e i e r s t r a s s 方程。w e i e r s t r a s s 方程为： y 2 + q 砂+ 口3 y = x 3 + 呸x 2 + 口4 x + 氏 ( 2 1 ) 在仿射坐标系下椭圆曲线e ，可用w e i e r s t r a s s 方程式外加一个特殊的点d 来 表示。满足方程式w e i e r s t r a s s 的数偶( 毛y ) 为域f 上椭圆曲线上的点。其中， 域f 是代数闭域，它可以是有理数域酞，也可是有限域l 。 与椭圆曲线公钥密码学有关的有限域主要有三类：z ，哎和。这里只讨 论文中用到的z 。中的椭圆曲线问题。 2 3 1 椭圆曲线上点的运算 根据代数几何理论，椭圆曲线e 构成一个a b e l 加法群，d 是其单位元。椭圆 曲线上的点对应于a b e l 加法群中的元素。下面给出仿射坐标系下椭圆曲线上点的 运算公式。 ( 1 ) 求逆元 设p = ( x ，y ) e ，根据w e i e r s t r a s s 方程式，由根与系数的关系易知 一p = ( x ，- ) ，一q x 一口3 ) ( 2 2 ) ( 2 ) 求和 设p = ( j c l ，咒) 、q = ( 屯，咒) e ，且p _ q ，r = p 十q ，则点r ( 为，芘) 的坐标 为： j 黾2 兄2 + q 五一口2 一而一而 ( 2 3 ) 【乃= 弋五+ 口1 ) 毛一1 ，一呜 其中 河南大学研究生硕士学位论文第9 页 丝边 。i 吃一毛 旯= 13 砰+ 2 口2 而+ 口4 一q 舅 i2 咒+ 口l 五+ 吩 i 咒而一扔而 屯一而 ，= l 一# + 嘞x l + 弛一码力l 一坷+ 嘞x l + 弛一码力 【2 乃+ 口l 而+ 呜 尹q p = q ，q p = q ( 2 4 ) 2 5 ) 2 3 2 素数有限域椭圆曲线 素数有限域( p r i m ef i n i t ef i e l d s ) z 。的特征值为c h a r ( f ) = p ，其中p 为 大于3 的素数。此时的w e i e r s t r a s s 方程式为 y 2 = x 3 + a x + 6 ( 口，6 f ) 且( e ) = 4 口3 + 2 7 6 2h 如d p 。( 2 6 ) 此时，椭圆曲线群上点的运算为： ( 王) 逆元公式： 一p = ( 五一夕) ( 2 7 ) ( 2 ) 加法运算： j 屯量( 五2 一而一而) m o d p( 2 8 ) 【乃兰( 五( 五一黾) 一咒) m o d p 其中， i 丝边p q i 恐一毛 。 以2 1 2 ( 2 9 ) l3 + 口 w 叫 【2 乃 2 4 公钥密码学 在公钥密码学出现之前，人们采用的是相同密钥的密码学体制，称为对称密 钥密码体制，在这样的体制中，加解密规则或者相同，或者相互可以容易的推导 出来，这种体制的缺点是，在传输密文前需要使用一个安全的通道交换密钥，实 际上，这是很难达到的。为了解决这个问题，1 9 7 6 年d i f f i e 和h e l l m a n 1 提出了 公钥密码体制的思想，1 9 7 7 年由r i v e s t ，s h 锄i r 和a d l e m a n 3 提出了第一个公钥 体制r s a 体制。突破了传统密码系统的限制，其思路是根据一个数学计算难题构 第1 0 页河南大学研究生硕士学位论文 造单向陷门函数。 在基于数学的密码技术中，公钥密码的发展直接影响了众多其他密码技术的 发展。公钥密码体制的基本思想是：设龟是加密钥，吃是解密钥。如果给定气，根 据求解畋在计算上是不可行的。将公开，这样加密者利用公开的进行加密， 只有掌握了的碗解密者可以进行解密。 公钥密码体制从提出到现在，始终是研究的热点，在众多的公钥体制中主要 有两类：一种是基于大数分解问题的，其典型代表是r s a 公钥体制：一类是基于 离散对数问题的，其典型代表是e 1 g 撇1 公钥体制和椭圆曲线公钥体制等。 2 5r s a 公钥体制 r s a 密码体制乜3 利用瓦中的计算，其中刀是两个不同的奇素数p 和g 的乘积。 对于这样一个整数刀，注意到矿( 船) = ( p 一1 ) ( g 1 ) 。r s a 密码体制的简单描述如下： 密码体制2 1r s a 密码体制 设托= 脚，其中p 和g 为素数。设毋= 口= z 。，且定义 咒= 旭p ，q ，岛b ) ：a b 暑l ( m o d 妒( n ) ) 对于k = ( p ，譬，a ，6 ，定义g ) = 妒m o d 豫和喀( y ) = 少m o d 玎，o ，y z 。) 。咒和 6 组成了公钥，p ，q 和口组成了私钥。 r s a 密码体制的安全性是基于相信加密函数o ) = m o d 刀是一个单向函数， 所以对于一个敌手来说，试图解密密文将在计算上是不可行的。允许b o b 解密密 文的陷门是分解刀= 朋。由于b o b 知道这个分解，他可以计算出缈 ) = ( p 1 ) 国一1 ) ， 然后用扩展e u c l i d e a n 算法来计算解密指数口。下面给出r s a 密码体制的参数生成 过程： 算法2 1r s a 参数生成 s t e p l ：生成两个大素数p 和日； s t e p 2 ：刀卜朋，且伊( 聆) 卜( p 一1 ) 国一1 ) ； s t e p 3 ：选择一个随机数6 ( 1 6 3 是一个素数，e 是有限域e 上的由方程( 2 6 ) 表示的 椭圆曲线，e ( 砸 。) 是相应的a b e l i a n 群，g 是以f 。) 中具有较大素数阶玎的一个点； ( 2 ) 密钥生成：随即选取整数d ：2 d 彪一1 ，计算p = 粥。d 是保密的密 钥，尸是公开钥； ( 3 ) 加密运算：对任意明文聊= ( 码，鸭) 咒屹，随机选取一个秘密整数 七：1 七抑一1 ，使得( x ，y ) = 舻，满足x 与y 均为非零元素。并计算c o = 硒， q = x i n o dp ，乞= 鸭y m o d p ，明文m = ( ，) ，经加密后的密文为 ( c 0 ，c 1 ，c ：) ，密文空间为e ( b ) 吒b 。 ( 4 ) 脱密运算：对任意密文c = ( c o ，q ，c 2 ) e ( b ) 哆町，计算标量乘 妈= ( x ，y ) ，计算= c l x - 1m o d p ，= c 2 y - 1m o d p 。即得c = ( c o ，q ，c 2 ) ，脱密 后的明文为( ，z i ，) 。 第1 2 页河南大学研究生硕士学位论文 2 6 2 椭圆曲线离散对数问题的安全性 椭圆曲线密码体制的安全性是基于椭圆曲线离散对数问题的。如果e 吧) 中韵 点g 的阶是一个较大的素数，那么用穷举搜索法来解离散对数问题是不可行的。 解有限群离散对数问题的通用方法均可用来解椭圆曲线上a b e l i a n ( 点) 群上 的离散对数问题。但是关于解有限域乘法群上的指数演算法则对e c d l p 不适用， 即目前还没找到对e c d l p 适用的类似算法。已知的对e c d l p 最好的算法是( 并行) p 0 1 1 a r d p 算法，该算法的运行时间为o “万p ( 2 f ) ) ( 这里f 是并行处理器数) 。作 为p 的函数，另p ( 勿) 比指数演算法的运行时间o ( p 1 坨+ d 1 l n 曲k p ) 的增长要快得 多，这就意昧着解e c d l p 比解有限域上的离散对数问题f f d l p 要困难得多，因而 椭圆曲线密码体制比同等规模的z 。上的e l g 锄a l 公钥密码体制安全性要强得多。 2 7h a s h 函数 密码学上的h a s h 函数能保障数据的完整性。h a s h 函数通常用来构造数据的短 搿指纹；一旦数据改变，指纹就不再正确。即使数据被存储在不安全的地方，通 过重新计算数据的指纹并验证指纹是否改变，就能够检测数据的完整性。 设乃是一个h a s h 函数，x 是数据。作为一个直观的例子，不妨设x 是任意长 度的二元串，相应的指纹定义为y = 而 ) 。通常指纹也被称为消息摘要( m e s s a g e d i g e s t ) 。一个典型的消息摘要是相当短的二元串，通常是1 6 0 比特。 使用h a s h 函数的目的就是产生文件、消息和数据块的“指纹”。为了能够用 于消息认证，h a s h 函数日必须满足下列性质： ( 1 ) 日能够产生用于任何大小的数据块； ( 2 ) 日产生固定长度的输出； ( 3 ) 对于任何给定的数据块茗，日都能够相对容易的计算出日( x ) ，这样就使得 硬件和软件实现变得切实可行； ( 4 ) 对于任何给定的给定的值办来说，寻找满足h ( x 、) = h 的数据块x ，在计算上 不可行的。在文献中有时称这种性质为单向( o n e - w a y ) 性质； ( 5 ) 对于任何给定的数据块x 来说，寻找满足何o ) = 日( x ) 且y x 的数据块y ， 在计算上是不可行的。有时称这种性质为弱碰撞抵抗( w e a kc o l l i s i o n r e s is t a n c e ) ； ( 6 ) 寻找满足日 ) = 日 ) 的o ，y ) 对，在计算上是不可行的。有时称这种性质 为强碰撞抵抗( s t r o n gc o l l s i o nr e s i s t a n c e ) 。 河南大学研究生硕士学位论文第1 3 页 具有上述前五条性质的h a s h 函数称为弱h a s h 函数( w e a kh a s hf u n c t i o n ) 。 如果同时满足第六条性质，那么就称该h a s h 函数为强h a s h 函数( s t r o n gh a s h f u n c t i o n ) 。可以看到，给定消息的h a s h 函数值是确定的，伪造相同h a s h 值的不 同消息( 特别是同时具有意义的消息) 是困难的。 本章小结 本章重点介绍了本文所涉及的数学知识和密码学知识，在2 1 小结介绍了群、 环、域和有限域的基本概念及相关理论；在2 2 和2 3 小节，介绍了有限域上的 离散对数问题及椭圆曲线的离散对数问题；在2 4 ，2 5 和2 6 小节中介绍了密码 学中常用的r s a 密码体制和椭圆曲线密码体制，并给出其安全性分析；在2 7 小 节中，对h a s h 函数及其相关知识进行了介绍。这些基础知识为后面章节设计盲签 名、群签名和群盲签名提供了技术支持。 第1 4 页河南大学研究生硕士学位论文 第3 章盲数字签名 盲签名是一种特殊的数字签名，它与通常的数字签名的不同在于，签名者并 不知道他所要签署消息的具体内容。利用盲签名技术可以完全保护用户j g 隐私权， 因此，盲签名技术在很多的领域都有广泛的应用。 3 1 盲签名的概述及性质 关于盲签名，d c h a u m 用一个形象的事例说明了盲签名：所谓的盲签名，就是 先将文件放入一个带有复写纸的信封( 盲化) ，签名人直接在信封上签名，透过复 写纸写到文件上。这个过程中信封没有打开，所以无法了解文件的真实内容。而 除去盲因子的过程就是打开信封，签名者可以验证签名，但他不能在签名和文件 间建立联系。 3 1 1 盲签名的橛述 一般情况下，人们总是先知道文件的内容，然后再对该文件进行签名。而在 某些特殊的情况下，用户需要让签名者对文件进行数字签名，而又不希望签名者 知晓文件的具体内容，这就需要盲数字签名( b 1 i n dd i g i t a ls i g n a t u r e ) ，简称 盲签名。盲签名n 仉1 13 在诸如电子投票选举、电子支付等需要保护某些参加者的场合 中具有广泛而重要的应用n 2 1 5 j 。 当用户a 需要签名者b 对消息m 进行盲签名时，按下列操作步骤来完成盲签 名： ( 1 ) 用户a 首先对等待签名的消息m 进行盲变换f ，使得消息m 的具体内容 对于签名者b 而言是“盲”的； ( 2 ) 用户a 将变换后的消息肌( 即盲消息) 发送给签名者b ； ( 3 ) 签名者b 对接收到的盲消息聊进行数字签名，得到签名s ； ( 4 ) 签名者b 将盲消息朋及其签名s 一起交给用户a ； ( 5 ) 用户a 对收到的签名s 做逆盲变换丁，所得到的就是原消息m 的盲签名 s 。 图4 1 为上述普通盲数字签名的签名过程。 河南大学研究生硕士学位论文第1 5 页 图3 1 普通盲数字签名的签名过程 3 1 2 盲签名的性质和实现效率 一般来说，一个好的盲签名应该具有以下性质： ( 1 ) 盲性：签名者对其所签署的消息的具体内容是不可见的。 ( 2 ) 不可伪造性：除了签名者本人以外，任何人都不能以他的名义生成有效 的盲签名。这是一条最基本的性质。 ( 3 ) 不可追踪性：当签名信息被公布后，签名者不能将签名与盲消息联系起 来。 满足上面几条性质的盲签名，被认为是安全的。这些性质既是设计盲签名应 遵循的标准，又是判断盲签名性能优劣的依据。另外，方案的可操作性和实现效 率也是设计盲签名时所必须考虑的重要因素。 3 2 对现有盲签名体制的分析 近期，有很多学者提出了盲签名方案，下面简单分析两类典型的盲签名体制。 3 2 1d c h 锄盲签名方案 基于大数难解的盲签名方案是由d c h a u m n 0 1 首先提出的，它的安全性是基于 分解大数问题的困难性，d c h a u m 的盲签名方案的简单描述如下： ( 1 ) 初始化阶段 签名者b 随机选取两个大素数p 和g ，计算刀= p g ，妒( ，2 ) = ( p 一1 ) ( g 一1 ) ，选取 两个整数e 和d ，使得p d = 1m o d 伊 ) ，( p ，妒 ) ) = 1 。公开e ，门和一个安全的单向哈希 第1 6 页河南大学研究生硕士学位论文 函数办o ，秘密保存p ，口和d 。b 的公钥是o ，p ) ，私钥d 。 ( 2 ) 盲化阶段 设用户a 有消息撒巧，髓机选取一个整数，乏。计算明= ，。j i l ( 聊) m o d 丹，a 将掰发送给b 。 ：( 3 ) 签名阶段 签名者b 计算s = ( m 甲啪d 栉，将s 发送给a 。 ( 4 ) 脱盲阶段 用户a 计算s = s ，- 1m o d 心，则s 就是消息m 的签名。 ( 5 ) 验证阶段 a 可以验证式子( j ) 。薹办( 聊) n 1 0 d 拧是否成立，由此可确定签名是否有效。若成立， 则验证了s 是b 对历的签名，否则拒绝。 r s a 签名体制的安全性依赖大数分解的困难性，分解刀是最常用的攻击方法， 攻击者只要能分解咒，求出签名者的私钥是轻而易举的事。尽管目前大整数的素数 分解仍然是一个困难性问题，但由于计算能力的不断强大及大整数因子分解方法 的不断提高与改进，以前被认为相对安全长度的密钥已在越来越短的时间内被破 解，如1 9 9 4 年4 月，采用二次筛法在网络上通过分布式计算，用8 个月时间破解 了r s a 1 2 9 ；1 9 9 6 年4 月，利用广义数域筛法破解了r s a 一1 3 0 ；1 9 9 9 1 年8 月利用 推广的数域筛法破解了r s a 1 5 5 。所以当前应用r s a 密码体制一般建议采用2 0 4 8 比特的密钥。 另外，为了防止攻击者的穷举攻击，在构造时刀应选择p 和g 的长度差不多， 数值上不要太接近，并且p l 和g l 有大的素因子。一般选择p 使得p 和( p 1 ) 2 均是素数。可以有效防止攻击者迭代逐一测试攻击。 3 2 2d s a 盲签名方案 d s a 盲签名n 8 3 是由j a nl c 锄e n i s c h 等于1 9 9 5 年提出的。它是在d s a 签名的 基础上构造的，它的安全性基于求解离散对数的困难性，其具体描述见文献n 引： 该签名有不足之处，首先参数选取过多，计算量大。其次验证中要求待签名 消息的逆元，影响实现的速度。 从前面的介绍知道，在众多的公钥体制中，占主流的主要有两类：一种是基 于大数分解问题的，其典型代表是r s a 公钥体制；一类是基于离散对数问题的， 其典型代表是e 1 g 锄锄1