（计算机应用技术专业论文）基于椭圆曲线的多重数字签名方案的研究.pdf

摘要 在当今信息化社会中，信息安全问题正同益受到社会的密切关注。数字签名 技术是信息安全技术的核心技术之一。数字签名技术具有对签名文件进行认证、 不可否认和完整性鉴别等功能，在军事、电子商务和电子政务等领域有广泛的应 用前景。基于椭圆曲线公钥密码系统的数字签名体制较基于传统的离散对数问题 的签名体制具有安全性更高、计算负载更小、密钥尺寸更短和占用带宽更小等优 点，因此基于椭圆曲线的数字签名方案具有很大的应用价值。 本论文主要研究基于椭圆曲线的多重签名方案，作者取得的主要研究成果如 下：构造了一个新的广播多重盲签名方案，一个有代理的广播多重签名方案和一 个有代理的有序多重签名方案，并对三个方案的安全性和效率进行详细的分析。 此外，在第一章中对现有的典型的多重签名方案进行了全面的归类总结，在第二 章中对基于椭圆曲线的签名方案的研究现状也进行了详细的阐述。 本文第二章首先介绍了数字签名技术中需要运用到的数学知识，然后介绍了 数字签名的理论知识，重点阐述了多重签名方案。最后，详细描述了椭圆曲线的 公钥密码体制，介绍了基于椭圆曲线离散对数困难问题的数字签名方案。 本文第三章介绍了一个现有的基于传统离散对数困难问题的e 1 g a m a l 型广播 多重数字签名方案，并分析和指出了其缺陷。本文将此方案转化为基于椭圆曲线 的e 1 g a m a l 型广播多重盲签名方案，修正了其缺陷，并在该方案中引入了时间标 志和最大签名次数限制，进一步提高了方案的安全性。最后分析了该方案的安全 性和效率。 本文第四章介绍了一种现有的基于传统离散对数困难问题的有代理的多重签 名方案。该方案基于常见的应用需求提出，理论较为完善，并且有很好的应用价 值，但也有计算复杂和计算量大等缺点。本章基于椭圆曲线离散对数困难问题构 造了一个有代理的广播多重签名方案和一个有代理的有序多重签名方案，新方案 计算简单、计算量小，具有较好的实用性。最后详细分析了新方案的安全性，并 对比原方案分析了新方案的效率。 本文第五章对本文全部内容进行了总结和对以后的研究工作进行了展望。 关键词：数字签名；盲签名；代理签名；多重数字签名；椭圆曲线密码体制 a b s t r a c t i nt h ei n f o r m a t i o ns o c i e t y ，i n f o r m a t i o ns e c u r i t yp r o b l e m sa r ew i d e l yc o n c e r n e d b yt h ec o m m u n i t y i ti s o n eo ft h ec o r et e c h n o l o g i e so fi n f o r m a t i o ns e c u r i t y t e c h n o l o g i e s t h ef u n c t i o n so fd i g i t a ls i g n a t u r et e c h n o l o g yi n c l u d ea u t h e n t i c a t i o no f t h es i g n a t u r ef i l e ，u n d e n i a b i l i t y ，a n dr e c o g n i t i o no ft h ei n t e g r i t y i th a sb e e nw i d e l y u s e di nt h em i l i t a r y ，e c o m m e r c e ，e g o v e r n m e n ta n dm a n yo t h e ra r e a s d i g i t a l s i g n a t u r eb a s e do ne l l i p t i cc u r v ec r y p t o s y s t e m ( e c c ) a r em o r es e c u r e ，w i t hs m a l l e r c o m p u t i n gl o a d ，s h o r t e rk e ys i z e sa n ds m a l l e rb a n d w i d t ht h a nt h ed i g i t a ls i g n a t u r e b a s e do nt h et r a d i t i o n a ld i s c r e t el o g a r i t h m p r o b l e m t h e r e f o r e ，d i g i t a ls i g n a t u r e s c h e m eb a s e do ne l l i p t i cc u r v ei so fg r e a ta p p l i c a t i o nv a l u e t h em u l t i s i g n a t u r es c h e m e sb a s e do ne c ca r em a i n l yr e s e a r c h e di nt h i sp a p e r an e wm u l t i b l i n ds i g n a t u r es c h e m e ，ab r o a d c a s tm u l t i - s i g n a t u r es c h e m ew i t hp r o x y s i g n e r sa n das e q u e n t i a lm u l t i s i g n a t u r es c h e m ew i t hp r o x ys i g n e r sa r ec o n s t r u c t e d ， a n dt h e i r s e c u r i t y a n d e f f i c i e n c y i s a n a l y s e d i n d e t a i l b e s i d e s ，e x i s t i n g m u l t i s i g n a t u r es c h e m e sa r ec l a s s i f i e da n ds u m m a r i z e dc o m p r e h e n s i v e l yi nt h ef i r s t c h a p t e r ，t h er e s e a r c hs t a t u so fs i g n a t u r es c h e m e sb a s e d o ne c ci sd e s c r i b e di nd e t a i l t h em a t h e m a t i c a lk n o w l e d g eu s e di nd i g i t a ls i g n a t u r et e c h n o l o g yi si n t r o d u c e d i nt h es e c o n dc h a p t e ra tf i r s t ，a n dt h e nt h et h e o r e t i c a lk n o w l e d g eo fd i g i t a ls i g n a t u r e i si n t r o d u c e d ；t h et h e o r yo fm u l t i - s i g n a t u r ei sd e s c r i b e da sak e y f i n a l l y ，e c ci s d e s c r i b e di nd e t a i l ，t h es c h e m e sb a s e do ne c ca r ei n t r o d u c e d a ne x i s t i n ge 1 g a m a lt y p eb r o a d c a s t i n gm u l t i - s i g n a t u r es c h e m ew h i c hi sb a s e d o nt r a d i t i o n a ld i s c r e t el o g a r i t h md i f f i c u l tp r o b l e mi sd e s c r i b e dt h et h i r dc h a p t e r ，a n d i t ss h o r t c o m i n g sa r ep o i n t e do u ta n da n a l y s e d i nt h i sp a p e r ，t h ed i f f i c u l tp r o b l e mo f s i g n a t u r es c h e m ei s t r a n s f e r r e df r o mt h et r a d i t i o n a ld i s c r e t el o g a r i t h mt od i f f i c u l t d i s c r e t e l o g a r i t h mp r o b l e mb a s e do ne c c ，a n d t h es c h e m e ss h o r t c o m i n g sa r e r e p a i r e d f i n a l l y ，t h es a f e t ya n de f f i c i e n c yo f t h es c h e m ei sa n a l y s e d am u l t i s i g n a t u r es c h e m ew i t hp r o x ys i g n e r sw h i c hi sb a s e do nt r a d i t i o n a l d i s c r e t el o g a r i t h mp r o b l e m si sd e s c r i b e di n t h ef o u r t hc h a p t e r t h es c h e m ei s p r o p o s e db a s e do nc o m m o na p p l i c a t i o nr e q u i r e m e n t s ，a n dt h e r ei s ap e r f e c tt h e o r y a n do fg r e a ta p p l i c a t i o nv a l u e ，b u tt h e r ea r ea l s os o m ed i s a d v a n t a g e s ，s u c ha sl a r g e a m o u n to fc o m p u t a t i o n a l ，c o m p l e xc o m p u t a t i o n sa n ds oo n i nt h i sc h a p t e r ，a b r o a d c a s tm u l t i s i g n a t u r es c h e m ew i t hp r o x ys i g n e r sa n das e q u e n t i a lm u l t i s i g n a t u r e i i s c h e m ew i t hp r o x ys i g n e r sb a s e do ne c ca r ec o n s t r u c t e d t h e ya r ee a s yi nc o m p u t i n g ， w i t hs m a l la m o u n to fc a l c u l a t i o na n db e i n gp r a c t i c a l f i n a l l y ，t h es a f e t y o fn e w s c h e m e si s a n a l y s e di nd e t a i l ，a n d t h ee f f i c i e n c yo fn e ws c h e m e si sa n a l y s e d c o n t r a s t i n gt ot h eo r i g i n a ls c h e m e t h em a i nc o n t e n t so ft h i sp a p e ra r es u m m a r i z e da n df u r t h e rr e s e a r c hw o r ki s p o i n t e do u ti nf i f t hc h a p t e r k e yw o r d s ：d i g i t a ls i g n a t u r e ；b l i n ds i g n a t u r e ；p r o x ys i g n a t u r e ；m u l t i - d i g i t a l s i g n a t u r e ；e l l i p t i cc u r v ee r y p t o s y s t e m i i i 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作者签名： 薹豸 日期：爿9 年妇弓日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内容 编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和 汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“4 ”) 作者签名： 日期：神年 l ，且仅能被1 和它自身整除，而不能被其他整 数整除，则称整数p 为素数。 定义2 2 最大公约数：设口，b 为整数不全为0 ，能同时整除a 和b 的最大正 整数称为最大公约数，记为g c d ( a ，6 ) ，有时简记为( a ，6 ) ，它的等价表示形式为 g e d ( a ，b ) = m a x kkla 且k6 ) 。 定义2 3 模运算：如果a 是一个整数，n 是一个正整数，口除以n 的余数用 a ( m o d n ) 表示，n 称为模。若( a b = l ( m o d n ) ，则称b 为a 在模疗下的乘法逆元，b 表 示为a - i ( m o d n ) 。若r i - b ) ，( a ，b ，n 都为整数) 即口一b = k n ，则称a 和b 模n 同余， 记为a 兰b ( m o d n ) ，n 被称为这个同余式的模。模运算的特点是所有的运算是限定 7 在一定的范围之内的，例如a 三b ( m o d n ) 的结果就是在1 和刀一1 之间的。这样的好 处是在处理大数之间的运算时任何运算都不会超过一个界限，可以将结果限定在 一定的范围之内，提高运算的效率。模运算满足分配律、交换律和结合律。 定理2 1 对于任何非负整数a 和b ，有g c d ( a ，6 ) = g c d ( b ，a ( m o d b ) ) 。 可以重复利用定理2 1 求出最大公约数，这个定理反映的思想正是求最大公 约数的欧基里得算法。 定义2 4 剩余类：在模数为n 的运算中，将所有同余的整数称为剩余类。因 此，模疗的剩余类元素有 0 ，1 ，2 ，n - l ，用乙表示，称为完全剩余类。在模n 的完 全同余类中，若将所有与n 互素的同余类形成一集合，则称此集合为模n 的既约 剩余类，用乏表示。 定义2 5 欧拉函数：令( 胛) 为小于n ，且与n 互素的所有整数的个数，即( 刀) 为模n 既约剩余类中所有元素的个数。 定理2 2 欧拉定理：若( a ，n ) = l ，则a 似帕誊l ( m o d n ) 。 定理2 3 费尔马定理：若p 为一素数，且( a ，p ) = 1 ，则a 尹1 = 1 m o d p 。 定义2 6 生成元：也称本原元。当p 是素数时，若存在一个整数a ，使得它的 不同幂对应模p 的非零剩余类，也即模运算a ( m o d p ) ，a 2 ( m o d p ) ，a p - i ( m o d p ) 是 各不相同的整数，并且组成了从1 到p 的所有整数，则称这个整数a 为素数p 的 本原元。 2 1 2 群论 群是抽象代数中最早的而且是最基本的一个代数系统，它也是现代数学中一 个极其重要的概念。它是研究椭圆曲线密码系统的基础，本节以下介绍了椭圆曲 线密码系统中所使用的群的概念和基本性质。 定义2 7 设g 是一个非空集合，若在g 上定义一个二元运算”+ ”满足下列条 件，称( g ，+ ) 是一个群。 ( 1 ) 封闭性：对任意a ，b g ，有口+ 6 g 。 ( 2 ) 结合律：对任意a ，b ，c g ，有( a + 6 ) + c = 口+ ( 6 + c ) 。 ( 3 ) 单位元：存在唯一的元素e g ，使得对任意口g ，有口+ e = e + a = a 。称 e 为g 的单位元，有时用1 表示。 ( 4 ) 逆元：对任意a g ，存在逆元一口g ，使得a + ( 一口) = a a = o k 立。 ( 5 ) 交换律：对任意a ，b g ，有口+ 6 = b + 口。 只满足( 1 ) ( 2 ) 两个条件，称( g ，+ ) 是一个半群。 定义2 8 若群g 满足交换律，则称g 为可交换群或阿贝尔( a b e lg r o u p ) 群。 8 定义2 9 群g 中的元素个数称为群g 的阶( o r d e r ) ，记作撑g 。若群g 的阶为 有限数，即群g 中的元素个数lgi 有限，则称g 为有限群；反之，称为无限群。 群具有以下性质： ( 1 ) 群中的单位元是唯一的； ( 2 ) 消去律成立，即对任意的口，b ，c g ，如果a + 6 = 口+ c ，则b = c ：如果 b + 口= c + 口贝0b = c ； ( 3 ) 群中的每一个元素其逆元是唯一的。 2 1 3 有限域理论 1 域和有限域 定义2 1 0 域由一个非空集合f 组成，在集合f 中定义了两个二元运算符： ”+ ”( 加法) 和”( 乘法) ，并满足： ( 1 ) f 关于加法”+ ”是一个交换群，其单位元为”0 ”，g 的逆元为一口； ( 2 ) f 关于乘法”是一个交换群，其单位元为”l ”，口的逆元为a ； ( 3 ) 分配律：对任何a ，b ，c f ，有a ( 6 + c ) = ( 6 + c ) 口= a b + 口c ； ( 4 ) 无零因子：对任何口，b f ，如果有a b = 0 ，则a = 0 或者b = 0 。 这样的集合f 称为域，记为 f ，+ ，) 。 定义2 1 1 在域f 中，定义减法”一”为a b = a + ( 一6 ) ，定义除法”为 口b = a b 一。 域是一个可以在其上进行加法、减法、乘法和除法运算而结果不会超出域的 集合。如有理数集合、实数集合、复数集合都是域，但是整数集合不是域( 因为 除法得到的分数超出了整数集合的范围) 。如果f 中只包含有限个元素，则称其 为有限域。有限域中元素的个数称为有限域的阶。关于有限域，有以下两个结论 成立。 定理2 4 每个有限域的阶必须为素数的幂。 定理2 5 对任意素数p 与正整数疗，存在p ”阶域，记为g f ( p ”) 。当”= 1 时， 有限域g f ( p ) 也称为素数域。 在密码学中，最常见的域一般为素数域g f ( p ) 或阶为2 m 的域g f ( 2 ”) 。 2 有限域的计算 有限域g f ( p ) 定义为整数 0 ，1 ，2 ，p 1 ) 的集合，相应的运算为模p 的代数运 算，即定义加法：如果口，b g f ( p ) ，则a + b = ( a + b ) ( m o d p ) ；定义乘法：如果 口，b g f ( p ) ，贝0a b = ( a b ) ( m o d p ) 。 定义2 1 2 一个多项式在f 域上，若不能表示为两个低次幂的多项式之积，则 称该多项式是f 域上的不可约多项式。 9 定理2 6 设( x ) 是系数在有限域g f ( p ) 上的m 次既约多项式，则所有次方小 于等于m l 并且系数在g f ( p ) 上的所有多项式关于m o d ( f ( x ) ) 构成一个阶为p ”的 有限域g f ( p ”1 。 当p = 2 时，构成特征为2 的有限域g f ( 2 ”) ，我们以后将在此域中运算。如 果口是g f ( 2 ) 中的本原域元素，则g f ( 2 ”) 中的元素可以由 1 ，a ，口2 ，a 矿一1 ) 完全来 表示，椭圆曲线上的点常用这种表示方法。 在g f ( 2 ”) 中的运算定义如下： 力口法：模f ( x ) 力口法，a ( x ) ，b ( x ) g f ( p ”) ，口( x ) + 6 ( x ) = c ( x ) ，c ( x ) 是口( x ) + 6 ( x ) 被 厂( x ) 除所得多项式，c ( x ) g f ( p ”) 。 乘法：模f ( x ) 乘法，口( x ) ，b ( x ) g f ( p ”) ，口( x ) b ( x ) = c ( x ) ，c ( x ) 是口( x ) b ( x ) 被f ( x ) 除所得多项式，c ( x ) g f ( p ”) 。 求逆：a ( x ) 是g f ( p 册) 中的元素，a ( x ) 的逆元就是g f ( p ”) 中的唯一元素c ( x ) ， 且满足口( x ) c ( 石) = l 。 2 2 数字签名简介 2 2 1 数字签名的定义和分类 数字签名方案普遍都是基于某个公钥密码体制，签名者用自己的私钥对消息 进行签名，验证人用相应的公钥对签名进行验证。从表面上看，数字签名与公钥 加密时用密钥的顺序不同。实际上，数字签名与公钥加密一样也是用单向陷门函 数确保其安全性。本质上，大数分解困难问题和离散对数困难问题等各种计算困 难问题的存在是安全的数字签名方案存在的根本。 数字签名方案通常包括三个主要过程：系统的初始化过程、签名产生过程和 签名验证过程。系统的初始化过程产生数字签名方案中用到的一切参数；签名产 生过程中，用户利用给定的算法对消息产生签名；签名验证过程中，验证者利用 公开的验证方法对给定消息的签名进行验证，得出签名是否有效的结论。数字签 名的形式化定义是数字签名描述性定义的一种抽象和形式化的概括。签名过程和 验证过程本质上是两个不同的算法。 定义2 1 3 称有3 个集合：消息集合m 、密钥集合k 、签名集合s 和2 个算 法，即签名算法s i g 、验证算法v e r 组成的5 元组( m ，s ，k ，s i g ，v e r ) 为一个数字签 名方案，其中k 是包括公钥和私钥在内的所有密钥的集合，并要求满足以下条件： ( 1 ) 签名算法对于密钥集合足，相应的签名算法为s 概s i g ，s i g , ：m 专s ，对 任意的消息m m ，有s = s i g 。( 聊) ，那么j s 为消息m 的签名，将( m ，s ) 传送到签名 验证者。 ( 2 ) 验证算法对于密钥集合k ，有签名验证算法 1 0 v e t k ：m 宰s 寸 t r u e ，f a l s e 当y = s i g k ( x ) 时，v e r k ( x ，y ) = t r u e ； 当y s i g t ( x ) 时，v e r k ( x ，y ) = f a l s e 。 签名接收者或验证者受到( m ，s ) 后，计算v e r k ( x ，y ) ，若v e r , ( x ，y ) = t r u e ，则签名 有效；否则，签名无效。 数字签名通常按以下方式分类： ( 1 ) 基于数学难题的分类 根据数字签名所基于的数学难题，数字签名方案可分为基于离散对数问题的 签名方案、基于素因子分解的签名方案、基于椭圆曲线离散对数问题的签名方案、 基于离散对数和素因子分解的签名方案、基于二次剩余问题的签名方案等。 ( 2 ) 基于签名用户的分类 分为单用户签名和多用户签名的数字签名方案。多个用户的签名方案又称多 重数字签名方案。根据签名过程的不同，多重数字签名方案可分为有序多重数字 签名方案和广播多重数字签名方案。 ( 3 ) 基于数字签名是否具有恢复特性的分类 一类是不具有消息自动恢复的特性，另一类是具有消息自动恢复的特性。 ( 4 ) 基于签名人对消息是否可见的分类 分为普通数字签名方案和盲签名方案。盲签名方案表示签名者对消息不可见， 但事后可以证明消息的存在。又根据签名者是否可以对消息拥有者进行追踪分为 弱盲签名方案和强盲签名方案。 ( 5 ) 基于签名人是否受别人委托签名的分类 分为普通数字签名方案和代理签名的方案。如果授权的不是一个人，而是多 个人，这时的数字签名方案称为代理多重数字签名方案。 2 2 2 数字签名的安全性证明 数字签名方案的安全性都是基于某些数学难题的。这些数学难题主要有以下 三个：第一，素数域上的离散对数问题，这类应用特别广泛，如现在的大部分签 名方案。e 1 g a m a l 方案、d s a 方案和许多协议的设计都是基于此困难问题的；第 二：大合数的因子分解问题，主要有r s a 和r a b i n 体制等；第三：椭圆曲线问题， 这是近年来研究的热点，它与离散对数相比优点在于速度快得多，更加实用，但 缺点在于安全参数的选取比较复杂，而且很多人对它的安全性有一定的怀疑。数 字签名的安全性主要有以下三个证明方法。 ( 1 ) 可证明安全性 利用计算复杂性理论，将数字签名的安全性转化为一些已知的难题，如大整 数分解、离散对数或者一般n p 完全问题。值得指出的是，在这一方法下被证明 安全的数字签名方案普遍效率不高。 ( 2 ) 基于随机问答器模型的证明 由于数字签名方案经常使用哈希函数，使用h a s h 函数的目的是为了用一个 简短的签名来签署许多长的消息，同时，要求h a s h 函数是无碰撞的。后来，人 们认识到，为了增强签名方案的安全性，h a s h 函数的使用实质也是签名方案安全 性的一个本质要素。同样，为了给签名方案提供一个安全性证明，提出更强的假 设是有必要的，于是，一些学者建议将h a s h 函数看成是一个随机函数，并给出 了相应的模型，称为随机问答器模型。假设h a s h 函数是没有弱点的，则基于此 模型的证明能够保证一个签名方案的总体设计的安全性。例如，著名的s c h n n o r 签名方案在这一模型下被证明是安全的。 ( 3 ) 利用相互转换证明 虽然很多数字签名方案( 如e 1 g a m a l ) 的安全性并没有得到证明，但是十几 年来并没有明显的迹象表明这些方案是不安全的。因此把一些数字签名方案的安 全性转化为这些公认安全的数字签名方案的安全性，是一个有效的证明方法。例 如著名n y b e r g - r u e p p e l 消息恢复签名方案的安全性被证明与e i g a m a l 签名方案等 价。 2 2 3 数字签名方案的设计 ( 1 ) t y 案设计的基础或前提条件 一个单向陷门函数，正向计算时可行的，但逆向计算是不可行的，也就是说 不存在一个有效的多项式算法可以不可忽略的概率进行逆向计算。比如，r s a 数 字签名方案的单向陷门函数是f ( m ，1 1 ，p ) = m 。( m o d n ) ，输入m ，疗，e ，输出是密文 c ，c = m 。( m o d n ) 。反过来，已知( ，z ，c ) ，求m 是不可行的。但是，如果掌握私钥， 即陷门信息d ，则可计算m = c d ( m o d n ) 。因此，单向陷门函数的构造是关键。 ( 2 ) 方案设计的安全性需求 第一，防止完全攻破。这是最根本的安全基础，所依赖的是一个数学难题， 即数字签名方案所依赖的单向陷门函数，也就是说不可能由公共参数攻破陷门信 息。当不知陷门信息时，逆向求解在计算上是不可行的。除在密码算法中常见的 数学难题外，要设计符合这个要求的数学难题是困难的，因为要对这个算法进行 时间复杂度估计和实际计算效率比较。目前已经公布的数字签名标准所依赖的数 学难题都是经过数学家和密码学家长期研究形成的。 1 2 第二，防止一般伪造。这是最起码的要求，如果攻击者找到一个功能等效于 签名算法的有效算法( 基于可能不同但等效的陷门消息) ，这等于签名已被完全 攻破了。 第三，防选择性明文攻击。如果攻击者把签名者当作一个随机问答器，可以 有选择性地选取消息，并获得其签名，利用这些信息进行攻击。 第四，防确定性攻击。这是签名方案设计者最难克服的一种攻击手段。因为 只要符合验证算法要求，验证者就无从判断它的真伪，按照协议要求，认为签名 是正确的。 第五，防其他攻击。除了上述攻击以外，从理论上讲，应该还要能预防可能 存在的其他攻击。 只有当数字签名方案符合上述安全性要求时，一般认为，方案就是安全的。 但要证明一个方案符合这些要求是困难的。长期以来，数字签名方案的安全性一 直困扰着密码学家们，学者们提出的很多数字签名方案，漏洞是在所难免的。在 数字签名方案的研究中，较有趣的现象是当一种新的数字签名被提出后，往往出 现一大堆文章对它进行进一步的密码分析，因此，最近几年数字签名方案的安全 性证明也成为了一个研究热点。 ( 3 ) 方案设计的计算复杂度要求 计算复杂度是数字签名方案设计必须考虑的因素，我们在比较具有同等功效 的数字签名方案时，计算效率高的方案备受欢迎，特别是网络带宽有限的情况下， 优势更明显。实际应用中，既要安全性好，又要计算效率高。 2 2 4 多重数字签名介绍 现实生活中，往往需要参与的各方对某一重要文件进行签字或表决，比如合 同的签订、公司文件的发布和重要人事决定等。引申到数字签名领域，也就是要 求多个用户对同一消息进行数字签名，称实现多个用户对同一个消息进行签名的 数字签名为多重数字签名。根据签名顺序，可将多重数字签名方案分为顺序多重 数字签名和广播多重数字签名。顺序多重数字签名是指每一位签名者按照一定的 顺序进行签名，广播多重签名是指消息发送者发送给每一位签名者签名，然后签 名者将签名消息发送到签名收集者，由收集者对签名消息进行整理而形成签名。 一般来说，多重数字签名方案的参与者有消息发送者、消息签名者、签名验证者 和签名收集者。自1 9 8 3 年b o y d 提出多重数字签名的概念以来，基于不同数学 难题的多重数字签名方案应运而生。一方面，随着各种新的密码体制的提出，相 应的多重数字签名方案就随之产生；另一方面，很多学者通过不同的特殊签名方 案的组合发布了各种形式的多重签名方案，比如多重代理签名、多重盲签名、前 向安全的多重签名和具有特殊性质的多重签名，如多重不可否认签名等。 多重数字签名是指签名由多个签名人共同完成。一个多重数字签名体制由以 下几个部分组成： ( 1 ) 初始化过程。在这个过程中，选定签名体制的参数、用户的密钥等。 ( 2 ) 单个签名人签名的生成过程。在这个过程中，签名人按照协议要求对消息 进行签名。 ( 3 ) 签名产生过程。按照协议要求产生最后多重签名结果。 ( 4 ) 签名的验证过程。验证者验证签名的有效性。 根据多重数字签名的性质可知，它的安全性要求既有与单个数字签名相同的 地方，又有其自身要求的特殊之处。 ( 1 ) 不可伪造性。这是任何一种数字签名必须具备的性质，是指签名组成员共 同完成签名外，任何人不可能伪造多重签名，包括签名成员的一部分不可能合谋 产生有效签名。 ( 2 ) 不诚实签名者的可识别性。如果签名组成员中有不诚实者，试图伪造签名， 则在签名过程中或验证过程中能够发现。如果签名组中有不诚实者，那么签名无 法完成。 ( 3 ) 不可否认性。签名一旦形成，签名组全体成员不能否认其签名。 ( 4 ) 可验证性。接收人或验证人能根据协议要求，检验签名的真伪。 2 3 椭圆曲线公钥密码体制 2 3 1 公钥密码体制概述 1 9 7 6 年d i f f i e 和h e l l m a n 发表了著名论文密码学的新方向，提出了公钥 密码的思想。在此新思想的基础上，很快出现了“非对称密钥密码体制”，即“公 钥密码体制”，由于公钥密码体制加密密钥和解密密钥的不同，且能公开加密密 钥，仅需保密解密密钥，所以公钥密码中存在的密钥管理问题变得相对简单。公 钥密码的一个优点是拥有信息认证性等新功能。还提出了一种密钥交换协议，允 许通信双方在不安全的媒体上交换信息，安全地协商一致的密钥。d i f f i e 和 h e l l m a n 利用公钥密码学的思想提出了数字签名的概念。自从l9 7 6 年公钥密码的 思想提出以来，国际上已经提出了许多种公钥密码体制，但比较流行的主要有两 类：一类是基于大整数因子分解问题的，其中最典型的代表是r s a ；另一类是基 于离散对数问题的，比如e i g a m a l 公钥密码体制和影响比较大的椭圆曲线公钥密 码。由于分解大整数的能力日益增强，所以对r s a 的安全带来了一定的威胁。目 前7 6 8 b i t 模长的r s a 已不安全。一般建议使用1 0 2 4 b i t 模长，预计要保证2 0 年 的安全就要选择1 2 8 0 b i t 的模长，增大模长带来了实现上的难度。而基于离散对 数问题的公钥密码在目前技术下5 1 2 b i t 模长就能够保证其安全性。特别是椭圆曲 1 4 线上的离散对数的计算要比有限域上的离散对数的计算更困难，目前技术下只需 要l6 0 b i t 模长即可，适合于智能卡的实现，因而受到国内外学者的广泛关注。国 际上制定了椭圆曲线公钥密码标准i e e e p l 3 6 3 ，r s a 等，一些公司声称他们已开发 出了符合标准的椭圆曲线公钥密码。我国学者也提出了一些公钥密码，另外在公 钥密码的快速实现方面也做了一定的工作，比如在r s a 的快速实现和椭圆曲线公 钥密码的快速实现方面都有所突破。公钥密码的快速实现是当前公钥密码研究中 的一个热点，包括算法优化和程序优化。另一个人们所关注的问题是椭圆曲线公 钥密码的安全性论证问题。 2 3 2 椭圆曲线的基本概念和理论 所谓椭圆曲线是指由韦尔斯特拉斯( w e i e r s t r a s s ) 方程 y 2 + a l x y + a y = x 3 + a 3 x 2 + a 4 x + a 5 所确定的平面曲线e ，即满足方程的所有点的集合，外加一个零点或无穷远 点o 。其中a l f ，f 是一个域，可以是有理数域、复数域，还可以是有限域g f ( p 7 ) 。 椭圆曲线在密码学中的应用在于椭圆曲线上可以提供无数的有限a b e l 群，由于这 样的群结构丰富，易于实际计算，从而可以用于构造密码算法。在密码学中，常 把椭圆曲线改写为 2=x3+ by a xb= x 。+ 的形式，并要求判别式4 口3 + 2 7 b 2 0 。 实数域上的椭圆曲线定义为满足下列形式的椭圆曲线方程的所有点的集合： y 2 = x 3 + 甜+ 6( 口，b ，x ，少都是实数) 要求1 6 ( 4 a 3 - i - 2 7 b 2 ) 0 。因此，当且仅当4 口3 - i - 2 7 b 2 0 时，曲线是非奇异的。于是 椭圆曲线上点的“加法”可以简单的定义为：如果一个椭圆曲线上的三个点处于 一条直线上，则它们的和为o 。这个加法规则又称为“弦和切线”法则，可以很 形象地用几何图形来表示。 有限域g f ( p ) 上的椭圆曲线定义为对于固定的口和b 的值，满足形如方程 y 2 = x 3 + a x + b ( m o d p l 的所有点( x ，y ) 的集合，外加一个零点或无穷远点o ，其中口，b ，x 枷在有限域g f ( p ) 上取值，即在 0 ，l ，2 ，p 一1 上取值，p 是素数。 有限域g f ( 2 ”) 上的椭圆曲线定义为对于固定的口和b 的值，满足形如方程 y 2 + 砂2x 3 + n x 2 + 6 的所有点( x ，y ) 的集合，外加一个零点或无穷远点o 。其中口，b ，x ，y g f ( 2 ”) ) ， g f ( 2 ”) 上的点是m 位的比特串。密码学中使用的椭圆曲线是定义在有限域这样的 代数结构上，通常基于有限域g f ( p ) 或g f ( 2 ”) 进行讨论。常见的定义于g f ( p ) 上 的椭圆曲线为y 2 = x 3 + a x + b ( m o dp ) ，且a , b ，x ，y g f ( p ) ，p 是素数， 4 a 3 + 2 7 b 2 o ( m o d p ) 。 、 义；夕 z l l ； l m ? ? ? _ ? j ? ? ? u 1 、。 | x 图2 1 椭圆曲线上“+ 运算的 椭圆曲线上点的加法定义的描述如图2 1 所示。设p = ( x l ，乃) ，o = ( 屯，y 2 ) 是e 上 任意两点，是p q 连线( 若尸和q 重合于一点，则，为过尸点的切线) ，和曲线相 交于另一点r ，过r 点作垂直于x 轴的直线与椭圆曲线相交于另一点s ，则点s 就 是点尸和点q 的和，即定义“加法”s = 尸+ q 。如果尸和q 对称( 或重合于x 轴) ， 此时，q = - p ，尸q 的连线，与y 轴平行，显然，与曲线没有第三个交点，规定 尸+ ( 一尸) = 0 为它们的和，称为零点，表示此时连线，在无穷远处与曲线相交，也称 为无穷远点。为了便于理解零点( 或者无穷远点) 的涵义，对椭圆曲线y 2 = x 3 + 饿+ 6 进行变换z = x z ，y = y z 得】，2 z = x 3 + a x z 2 + b z 3 ，此时z 0 ，点( x ，j ，) 与( x ，】，z ) 相对应，对于任意常数n 0 ，( x ，y ，z ) 与( n x ，n y ，n z ) 表示同一个点。但是，当z = 0 时，以点( o ，1 ，o ) 为例，该点等效于( o ，1 ，p ) 当e - - 9 0 时的极限，此时我们认为y 坐标 趋向于无穷大，因此，定义无穷远点为零点。定义椭圆曲线上的加法的目的是为 了构造一个加法群。椭圆曲线上的点及无穷远点( 即单位元) 构成一个群。当然， 从密码学的应用角度，我们关心的是曲线上的整数点构成的群。在椭圆曲线上定 义的加法实际上是点的一种运算，椭圆曲线上的点再加上零点，构成一个加法群。 关于运算”+ ”有如下加法规则。 ( 1 ) 与零点相加对任意p e ，有尸+ 0 = 0 + p = p 。 ( 2 ) 对任一p e ，存在e 上一点，记为一p ，使得p + ( 一p ) = 0 。称一尸为尸的逆 元，它为椭圆曲线上点关于x 轴的对称点。 ( 3 ) 交换律对任意p ，o e ，有p + q = q + p 。 ( 4 ) 结合律对任意p ，q ，r e ，有( p + q ) + r = 尸+ ( q + 尺) 。 ( 5 ) 两相异点相加对任意p ，q e ，且尸q ，令p = ( x l ，y 1 ) ，o = ( 毪，y 2 ) ，此时 x 2 ，s = ( x 3 ，y 3 ) ，s = 尸+ q ，则有x 3 = n 2 一葺一屯，y 3 = ( 一一x 3 ) 一乃，其中 n = ( y 2 一y 1 ) ( x 2 一而) 。 1 6 ( 6 ) 两相同点相加对任意p e ，且p 一p ，令尸+ p = 2 p = ( x 3 ，儿) ，此时， x 3 = n 2 - 2 x i ，y 3 = n ( x l x 3 ) 一m ，其中n = ( 3 x 1 2 + a ) 2 y l 。 基于g f ( 2 ”) 的椭圆曲线y 2 + 砂= x 3 + a x 2 + 6 上的加法，其中口，b g f ( 2 ”) ，b 0 ， 关于点( x ，少) 的加法满足如下法则： ( 1 ) 对任意p e ，有p + 0 = 0 + p = p 。 ( 2 ) 对任意p = ( x ，y ) e ，有逆元一p = ( x ，- x - y ) = ( x ，x + y ) ，尸+ ( 一p ) = 0 。 因为p = ( x ，y ) e ，所以满足方程要y 2 + x y = x 3 + 麟2 + 6 ，易知点( x ，一x y ) 在 椭圆曲线上，因为y 2 + 砂= x 3 + 甜2 + 6 ，则( 一x - - 少) 2 + x ( 一x y ) = x 3 + 甜2 + 6 。又椭圆 曲线关于x 轴对称，因此，对称点( x ，x + y ) 也在椭圆曲线上。 由( x + 少) 2 + x ( x + y ) = x 3 + 饿2 + 6 得2 x 2 + 2 x y = 0 所以x = 0 。 ( 3 ) 对任意尸= ( 五，乃) ，q = ( x 2 ，y 2 ) e ，p 0 ，令s = 尸+ q = ( x 3 ，y 3 ) ，则有 x ，= n 2 + + 而+ 屯+ 口，乃= n ( x 2 + x 3 ) + 恐+ 奶，其中n = ( y l + 儿) ( 毛+ 恐) 。 ( 4 ) 对任意p = ( 五，m ) e ，p 一p ，令2 p = ( 恐，y 3 ) ，则有 x 3 = n 2 + n + 口，y 3 = n ( x l + 为) + 黾+ m ，其中n = 五+ y l 五。 上面主要讨论了与密码学相关的基于有限域g f ( p ) 和g f ( 2 ”) 的椭圆曲线上 的点的运算，实际上，在有限域g f ( p ”) 上的情况类似，这里不在赘述，它的运算 法则与c f ( 2