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

河南大学研究生硕士学位论文第1 页 摘要 信息安全是一切基于计算机网络的通信活动得以正常运行的前提和基础。但 是，我国信息安全技术还处于低水平状态，因此我们在信息安全技术领域还有许 多工作要做。 1 9 9 6 年，m 锄b o ，u s u d a 和o k 锄o t o 首先明确提出并系统阐述了代理签名的 概念。在原始签名人与代理签名人之间的具有法律效力的协议下，代理签名人可 代替原始签名人对文件进行签署。代理签名一经提出便受到广泛关注，国内外学 者对其进行了深入的探讨与研究。代理签名的类别不断丰富，安全性要求也在不 断提高，出现了各种各样的代理签名方案。 椭圆曲线离散对数问题是目前公认的可用于密码体制的三大数学难题之一。 自1 9 9 7 年开始，国际上对椭圆曲线公钥密码体制进行了较为广泛的研究。目前， 椭圆曲线公钥密码体制已经开始从理论研究阶段走向应用实现阶段，但在我国还 尚处于起步阶段。 本课题对目前代理签名中较为典型的代理签名和门限代理签名方案进行了深 入研究，提出了新的方案，引入了身份识别和安全单向函数等机制，加强了安全 性，防止了有可能出现的争端以及保证了不可否认性，并进行了较为充分的安全 性分析。 主要工作包括： 第一，在深入研究各类代理签名方案优缺点的基础上，结合椭圆曲线密码机 制和代理签名的知识，提出一种改进的无需原始签名人参与的代理签名方案。并 对新方案的安全性给予分析和证明。 第二，结合门限密码学和代理签名的特点，提出一种基于离散对数密码机制 的无需原始签名人参与的门限代理签名方案，并对新方案的安全性给予分析和证 明。 关键词：代理签名；椭圆曲线；门限 第1 i 页河南大学研究生硕士学位论文 a bs t r a c t i n f o 肌a t i o ns e c u r i t yi st h ep r e c o n d i t i o na n db a s i so fe v e r y t h i n gt h a tc a nw o r k r e g u l a r l yb a s e do nt h ec o m p u t e rn e t w o r kc o m m u n i c a t i o n b u tm ei n f o n n a t i o ns e c u r i 够 t e c h i l o l o g yi si i ll o wl e v e li no u rc o u n 臼yw e h a v em u c hw o r kt od oi nt h i sf i e l d i i ll9 9 6 ，m a m b o ，u s u d aa n do k 锄o t of i r s tp u tf o n a r da n ds y s t e m i ce x p o u n dm e c o n c e p to fp r o x ys i 弘a t u r e u n d e rt h eo r i g i i l a ls i g n e ra 1 1 dp r o x ys i 印e r sp r o t o c o lw i t h t h ef o r c ea d e 日e c t ，t h ep r o x ys i g n e rc a ns u b s c r i b em ef i l e si n s t e a do ft h eo r i g i n a ls i g n e r b e c a u s et h ep r o x ys i 印a t u r ep l a y sa ni m p o n a n tr o l ei np r a c t i c a l 印p l i c a t i o n ，i ta t t r a c t s w i d e l ya t t e n i o nw h e na d v a n c e d 1 1 1 ed o m e s t i ca n df o r e i g ns c h o l a r sh a v ea ut a k e n d e e p l yr e s e a r c ht oe n r i c hm ec l a s so fp r o x ys i g n a t u r ea n de n h a n c et h ed e m a l l do f t h e s e c u r i 可v a r i o u so fp r o x ys i g n a t u r es c h e m se m e 唱e n c e s t 1 1 ee l l i p t i cc u n ，ed i s c r e t el o g a r i m mp r o b l e m ( e c d l p ) i sr e c o g l l i z e do n eo ft h e t h r e em a t h e m a t i c sd i 艏c u l tp r o b l e m sw h i c hc a nb eu s e dt od e s i g nc 巧p t o s y s t e ma t p r e s e n t s i n c e19 9 7 ，t h ep u b l i ck e yc r y p t o s y s t e mb a s e do ne c d l p h a sb e e nw e l ls t u d i e d i ni n t e m a t i o n a lc 唧t o g r 印h yf i e l d n o wt h ep u b l i ck e yc 哪t o s y s t e mb a s e do ne c d l p h a sa l r e a d yt u m e d 行o mt h e 向n d a m e n t a ls t u d ys t a g et ot h e 印p l i c a t i o nr e a l i z a t i o ns t a g e ， h o w e v e ri ti ss t i l li ns t a n i n gp h a s ei no u rc o u n t u n i ss u b je c tt a k e sd e e pr e s e a r c ho nt y p i c a lp r o x ys i g n a t u r ea n dt h r e s h o l dp r o x y s i 盟a t u r ea tp r e s e n t ，a n dp r o p o s e sn e ws c h e m e sw i t hi d e n t i 行c a t i o na n ds a f eo n e - w a y 如n c t i o nm e c h a n i s mi m p o n e d ，e n h a i l c em es e c u r i t ya n dp r e v e n tt h ep o s s i b l ei s s u e ， e s p e c i a l l yt oe n s u r et h en o n r e p u d i a t i o n m a i n l ys t l l d ya sf o l l o w s ： f i r s t l y ，t h i sp 印e rs u mu pt h ev i r t u ea i l dn a wo fm ee x i s t e n t k i i l d so fp r o x y s i g n a n 】r es c h e m e sa n dc o m b i n et h ec h a r a c t e r i s t i co ft h ee c d l pa n dt h ek o w n l e d g eo f p r o x ys i 印a t u r e ，t h e np r o p o s ea ni m p r c i v e dp r o x ys i g n a t u r e s c h e m ew i t h o u tt h e c o o p e r a t i o no ft h eo r i g i n a ls i 印e r w h i c h a l s oa n a l y s e sa n dp r o v et h es e c u r 峨 s e c o n d l y ，c o m b i n et h ef e a t u r eo ft h et h e s h o l da n dp r o x ys i g i l a t l l r e ，a n dp u t 河南大学研究生硕士学位论文第1 | i 页 f b r w a r dat h r e s h o l dp r o x ys i 印a t u r es c h e m eb a s e do nt h ed i s c r e t el o g a r i t l u l lc i p h e r m e c h 肌i s m ，w h i c hn e e d n tt h ec o o p e r a t i o no fm eo r i g i i l a ls i 印e r w h i c ha l s oa i l a l y s e s 觚dp r o v et h es e c u r i 够 k e y w o r d s ：p i o x ys i g n a t u r e ；e n i i ) t i cc u r v e ；t 1 1 r e s h o l d 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位申请。本人郑重声明：所呈交酌学位论文是 本人在导师的指导下独立完成的，对所研究的课题有新的见解。据我所知，除 文中特别加以说明、标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过百勺研究成果，也不包括其他人为荻得任何教育、科研机构的学住或证书而 段保存、汇编学位论文( 纸质文本和电子文本) 。 ( 涉及保密内容的学住论文在解密后适用本授权书) 学位获得者( 学位论文作者) 签名：! 主3 兰要 2 0 口g 卑占月d 日 学位论文指导教师签名：堡垒益 2 0 即年月日 河南大学研究生硕士学位论文第1 页 第1 章绪论 随着信息技术和网络技术的快速发展，大量的机密信息和重要数据得以不必通 过专用的设施进行传输和存储，大大降低了信息传输的成本，因此，基于计算机 网络的各种商务活动和政务活动也迅猛发展起来。相应地，在公共信道上传输信 息的安全问题也就显得更为突出。 密码学【l 】给解决信息安全问题提供了许多有效的核心技术，在保护信息安全方 面起着关键性的作用。而正是由于信息安全的重要性以及在信息安全中的重要作 用，现代密码学受到各国政府和研究机构的重视，有了长足的发展。现代密码学 不仅用于解决信息的保密性，而且也用于解决信息的完整性、可用性、可控性和 不可否认性。如今密码学的应用已经渗透到了社会的各个领域，如对计算机用户 的认证、数据加密、信息认证、1 网络安全、电予现金以及电子银行等。 1 1 选题的背景和意义 数字签名【2 。5 j 是现代密码学的重要组成部分之一。又有人称之为数字签字、电 子签名、电子签章等，是当前网络安全领域的研究热点。它是电子政务、电子商 务、电子银行、电子证券等系统必备的关键性技术，在日常的安全电子邮件中也 有大量的应用。美国、欧盟分别在2 0 0 0 年前后，j 卜式颁布了数字签名法律。随着 对数字签名研究的深入，研究者们提出了一些有特殊用途的数字签名方案。代理 签名【6 母】就是其中的一种，也称为委托签名，就是指定某人来代替自己进行签署。 与手写签名相同，数字签名也代表了签名人的一种权力，这种权力可以称为 签名人的签名权力。在手写签名中，签名权力依赖于签名人的书写习惯和书法特 征，在数字签名中，签名权力依赖于签名人的秘密密钥。在工作和生活中，常常 需要将这种签名权力委托给他人。当秘钥的所有者无法自己进行数字签名时，他 不得不指定别人来代替自己签署。 由此可见数字签名权力的委托是数字化信息社会必然遇到的一种情况，这也 将产生很多技术上的挑战。所以对代理数字签名问题的研究有着深刻的现实意义 和实用价值。而且随着对代理签名研究的深入，代理签名的应用也越来越广泛， 在电予现金系统，电子选举系统，公平交换协议，分布式计算机资源的安全访问 等领域都有着用武之地。 由于在实际应用中有着重要作用，代理签名一经提出便受到广泛关注，国内 第2 页河南大学研究生硕士学位论文 外学者对其进行了深入的探讨与研究；代理签名的类别及安全性要求也在不断丰 富，出现了各种各样的代理签名方案。 j 、_ j 限代理签名 】是代理签名的一种变换，它因具有良好特性而各受关注。 亿即) 门限代理签名的代理签名私钥由，2 个代理签名人分享保存，只有不少于f 个代 理签名人代表原始签名者共同运用各自的代理签名私钥才能产生对消息的签名， 少于f 个则不可能。但是目前的门限代理签名方案计算复杂度高，通信量大，执行 效率低，而且很多方案存在着安全隐患。所以对门限代理签名方案的分析和研究， 对于设计一个安全、有效、实用且具有不可否认性的代理签名方案有着重要的意 义。 1 2 研究现状 第一个门限签名方案足d e s m e d t 和f z a n k e l 于1 9 9 1 年提出的，该方案基fr s a 密码体制，采用了复杂的代数结构，比如代数扩张等。接着许多f 隈签名方案【。1 5 】 陆续提出。这一阶段对门限签名的研究，主要着眼于门限签名的构造问题，即如 何将门限方案与一般的签名体制有效结合。随着门限签名构造方法的逐渐成熟， 人们的研究重点转向门限签名的性质，对己有方案进行分析，总结门限签名方案 应具有的性质，并提出新的具有良好性能的方案。目前门限签名最新的研究方向 是具有特殊功能的门限签名，主要包括具有特权集的门限签名，门限失败停止签 名，前向安全门限签名和门限代理签名等。 代理签名的概念最初是由m a m b o 等人于1 9 9 6 年提出的。在代理签名体制中， 一个签名人，称为原始签名人，将自己的签名权力委托给一个指定的人，称为代 理签名人，使其能够代表自己进行签名。代理签名与【_ j 限签名结合起来，就形成 了门限代理签名。最早的门限代理签名方案是由z h a n g 【1 6 和k i m 1 7 1 于1 9 9 7 年分 别提出的，这两个方案采用s h a m i r 的门限方案，结合代理签名体制，实现了门限 代理签名的基本功能。但是，方案还存在很多不完善的地方：如无法确定完成二 个代理签名的真j 卜签名者等，z h a n g 的方案还不具有不可否认性。1 9 9 9 年，s l l l l 分析了z h a n 窟和k i m 的方案后，提出了一个可追查签名者的门限代理签名方案， 该方案采用p e t e r s e n 的可验证秘密共享方案实现代理密钥和群密钥在群组中的门 限共享，并在签名的验证方程中引入实际签名者的公钥以实现可追查性。自此以 后，许多学者沿着s 蚰的这条思路构造了很多门限代理签名方案，对方案的性能 和安全性不断进行改进。 河南大学研究生硕士学位论文第3 页 1 现有的代理签名方案【1 8 之4 】多数在性能方面还存在如下缺点： ( 1 ) 代理签名的安全性：目前很多代理签名方案存在安全隐患。例如，攻击者可 以从委托信息中获取原始签名人的私钥。 ( 2 ) 密钥管理中心欺骗问题：目前的代理签名方案中，密钥管理中心可以利用原 始签名人给的委托信息产生新的委托信息。 ( 3 ) 原始签名者在线问题：现有代理签名方案几乎都是原始签名者、代理签名者 和接收者之间进行的交互协议。由于在每次代理签名中都有原始签名者的参与， 这就违背了代理签名的初衷。因为从代理签名产生的背景知道，正是由于原始签 名者到外地出差或由于事务繁忙而无法脱身才将签名权给予可信的代理签名者来 行使其权力。因此，从本质上来说，真正的代理签名在签名过程中不可能有原始 签名者的参与。 ( 4 ) 原始签名人无法撤销代理的签名权力。 ( 5 ) 无法保护代理签名人的隐私，实现代理签名人身份隐藏。 2 分析现有的门限代理签名方案 2 5 。3 0 1 ，普遍存在以下问题： ( 1 ) 无法实现代理签名人身份的隐藏，并同时保证不可否认性。 ( 2 ) 无法做到代理签名的可追踪性，使得在签名后若发生争执时，无法确定代理 签名人的真实身份，实现对代理签名者的事后监督功能。 ( 3 ) 无法实现抗合谋等攻击。 1 3 本文研究的主要内容 本文主要研究特殊数字签名体制中的代理签名体制，并对代理签名和门限代理 签名的典型方案进行了充分的安全性分析和总结，提出了一个新的基于椭圆曲线 的代理签名方案和一个新的基于离散对数的门限代理签名方案。结果表明，两个 新方案都具有较好的使用性和安全性。 本文的创新点是： 1 提出了一个基于椭圆曲线的代理签名方案，该方案通过引入安全单向函数等机 制，解决了代理签名人的匿名隐藏问题，保护了代理签名人的隐私。通过密钥管 理中心的合理使用，保证了签名过程无需原始签名人的参与；增强了安全性。 2 通过在现有门限代理签名方案中引入安全单向函数和身份识别等密码机制，隐 藏了门限中子代理签名人的身份，解决了签名中普遍存在的参与者联合欺诈问题， 提出无需原始签名人参与的门限代理签名方案，并保证了了代理签名人的匿名追 第4 页河南大学研究生硕士学位论文 踪性和不可否认性。 1 4 论文组织安排 论文的具体安排如下： 第1 章概括介绍所选课题的研究背景和意义，详细分析现有的代理签名方 案和门限代理签名方案普遍存在的一些缺点，给出所选课题的研究现状。在此基 础之上确定了本文所研究的主要内容。 第2 章简要介绍本文研究所必需的基础理论知识。首先介绍了近世代数中 群、环、域和有限域的基础内容，以及椭圆曲线相关的理论知识。接着简要介绍 了本文研究所用到的密码学相关内容，包括公钥密码系统以及数字签名的基础知 识。研究这些是为了设计出更好、更安全的密码体制。 第3 章在本章中，对现有的典型代理签名方案进行了较为充分的安全性分 析和比较；并基于椭圆曲线密码体制和单向函数的安全性，提出了一个新的基于 椭圆曲线的代理签名方案。 第4 章在本章中，对现有典型门限签名方案进行了较为充分的安全性分析 和比较；并基于身份识别、离散对数问题和安全单向函数，提出了一个无需原始 签名人参与的化即) 门限代理签名方案。 一 最后，结束语中对全文的研究工作进行了总结，：并指出了可以继续探索的方 向。 本章小结 本章概括介绍了所选课题的研究背景和意义，分析了现有代理签名方案和门 限代理签名方案普遍存在的一些缺点，给出了所选课题的研究现状。在此基础之 上确定了本文所研究的主要内容。 河南大学研究生硕士学位论文第5 页 第2 章基础知识 密码学的理论基础是数学，其基本思想是隐藏、伪装信息，使未经授权者不 能得到消息的真正含义。本章主要介绍与本文研究课题相关的数学和密码学的理 论基础知识。 2 1 数学知识 本文中用到的数学知识主要包括代数和椭圆曲线的相关知识，在以下小节中 将逐一进行介绍。 2 1 1 代数基础 本节将垂点讲述文中涉及的代数知识 3 l 】。 2 1 1 1 群 群( g r o u p s ) 是抽象代数学的重要组成部分。本小节探讨群的有关概念和性质。 定义2 1 【3 l j 一个群( g ，) 由一个满足下列三个条件的二元运算“”构成： ( 1 ) 群运算是可结合的。 ( 2 ) 有一个称作单位元的元素1 g ，使得对所有的口g ，有口l = l 口= 口。 ( 3 ) 对每一个口g ，有一个称作口的逆元素6 使得6 - 口= 口- 6 = l ，把6 记为口。 一个群g 是a b e l 群，如果它还满足下列条件： ( 4 ) 对所有的口，6 g 有6 口= 口6 。 对加法群而言，通常用o 来表示单位元素，用口表示口的逆。 定义2 2 【3 l j 如果j g l 是有限的，那么群g 是有限群。一个有限群的元素个数称 为它的阶( o r d e r ) 。 定义2 3 【3 l j 设g 是一个群，如果g 中有一个元素口使得对每一个6 g 都存 在一个整数i 使得6 = 口，则称g 是一个循环群，口称为g 的一个生成元。 定义2 4 【3 l j 设g 是一个群，口g ，口的阶定义为使得= 1 的最小整数t 。 定义2 5 【3 l 】设h 是群( g ，- ) 的一个非空子集，如果h 本身在群g 的运算 “”之下构成一个群，则称h 是g 的一个子群。如果h 是g 的一个子群且h g ， 第6 页河南大学研究生硕士学位论文 则称h 是g 的一个真子群。 定理2 1 【3 1 1( l 哪n g e 定理)设g 是一个有限群，h 是g 的一个子群，则 刚ii g | o 关于循环群有以下基本性质： ( 1 ) 循环群的子群也是循环群。 ( 2 ) 设g 是一个群，如果口g 的阶是t ，则矿的阶是魄c d ( t ，k ) 。 ( 3 ) 设g 是一个阶为n 的循环群，d i n ，则g 恰有西( d ) 个阶为d 的元素。特 别地，g 有( n ) 个生成元。 2 1 1 2 环 环( r i n g ) 是抽象代数学的重要组成部分。本小节将探讨环的有关概念和性质。 定义2 6 【3 l 】一个环( r ，+ ，) 是由两个满足下列条件的r 上的二元运算“+ ” 和“”构成： ( 1 ) ( r ，+ ) 是一个a b e l 群，单位元用0 表示。 ( 2 ) 运算是可结合的，也就是说，对所有的口，6 ，c r ，有口( 6 c ) = ( 口6 ) c 。 ( 3 ) 有一个乘法单位1 ，使得对所有的口1 = 1 口= 口。 ( 4 ) 乘法和加法由分配律联系着，也就是对所有的口，6 ，c r 有 口( 6 + c ) = ( 口6 ) + ( 臼c ) 和( 6 + c ) 口= ( 6 口) + ( c 口) 。 如果一个环( r ，+ ，) 还满足条件：对所有口，6 r ，有口6 = 6 口，则环( r ， + ，) 为交换环。 定义2 7 【3 l 】设r 是一个环，口r ，如果存在一个元素6 r 使得口6 = 1 ，则 称口是个单位或可逆元素。 环r 的所有单位之集关于乘法形成一个群，称为r 的单位群。 定义2 8 【3 1 】假设p 是一个素数。定义z 。【x 】是变元x 的所有多项式集合。按照 通常多项式的乘法和加法定义( 并且模p 归约系数) ，它构成一个多项式环。对于 ( x ) ，g ( x ) z 。 x 】满足g ( x ) = g ( x ) 厂( x ) ，贝0 说( z ) 整除g ( x ) ( 记做：厂( x ) ig ( x ) ) 。 对于厂( x ) z x ，厂的阶数d e g ( 厂) 定义为的项中最高次数。假设厂( x ) ，g ( z ) ， 办( x ) z 。 x 】，且d e g ( 厂) = n 1 。如果厂( x ) l ( g ( x ) - 办( x ) ) 贝0 定义：g ( x ) 三以z ) ( m o d 厂 ) ) 。 定义2 9 【3 1 】如果不存在多项式彳( x ) ，厶( x ) z 。【x 】满足厂( x ) = 彳( x ) 左( x ) ， 则称多项式厂( x ) z x 】是不可约的。其中，d e g ( 石) o 和d e g ( 以) o 。 河南大学研究生硕士学位论文第7 页 2 1 1 3 域 域( f i e l d ) 是抽象代数学的重要组成部分。本节将探讨域的有关概念和性质。 定义2 10 满足下列条件的一个交换环称为一个域：所有的非零元素都有乘 法逆。 定义2 11 【3 1 1 设f 是一个域，如果对任何m 1 ，l + 1 + + 1 o ( m 个1 相加) ， 则称f 的特征为o ，否则，f 的特征是使得y 1 ：o 的最小正整数m 。 百 定理2 2 z 。是一个域，当且仅当，z 是素数。如果门是素数，则z 。的特征值 是胛。 关于特征值有以下重要事实：如果一个域的特征不是o ，则它的特征必是素数。 定义2 12 3 1 1 设e 是一个域，f 是e 的一个子集，如果f 关于e 的运算本身形 成一个域，则称f 为e 的子域，也称e 为f 的扩域。 定义2 13 3 1 1 对于多项式环z ， x ( 厂( x ) ) ，当且仅当厂( z ) 是不可约时，z p 【x 】 ( 厂 ) ) 是多项式域。 多项式域z 。b ( 厂 ) ) 中元素的乘法逆元可以直接通过改进的欧几里德算 法( e u c l i d e a na l g o r i t h m ) 计算。 2 1 1 4 有限域 密码学中用到很多有限域( f i i l i t ef i e l d ) 中的运算，因为可以应用数论中的理 论，保持数的大小在有限的范围内，且不会有取整的误差。 只含有有限个元素的域称为有限域。有限域中元素的个数是一个素数，或者是 一个素数的乘方，记为z ，或者f 。，其中p 为素数。 1 ， z d 是一个具有p 个元素的素数有限域。如果g = p ”，p 是素数，2 1 是整数， 则f 。是一个具有q 个元素的多项式有限域。有限域中元素的个数称为该域的阶。 ， 在有限域中，加法单位元是o ，乘法单位元是1 ，每一个非o 的元素都有一个 惟一的乘法逆元。有限域中运算满足交换律、结合律和分配律。 很多密码系统是基于z 刀的，为了使系统更复杂，可以使用多项式有限域只。来 构造密码系统。在对多项式有限域的实际研究中，用得最多的是有限域f 。，在硬 件上，利用线性反馈移位寄存器可以快速地实现只。上的运算。因此，只。上的计 算通常比z 。上的运算快。 第8 页河南大学研究生硕士学位论文 已经知道，乘法群z p + ( p 是素数) 是一个阶为p - 1 的循环群。事实上，任何 有限域的乘法群都是循环群：。 o ) 是一个p ”_ 1 阶的循环群。 定义2 14 3 1 1 多项式有限域中，生成元多项式称为本原多项式，且其系数互素。 2 1 2 椭圆曲线 椭圆曲线密码 3 2 。4 】是一种公钥密码，椭圆曲线密码不仅有比较好的安全性， 而且利用椭圆曲线离散对数问题可以同时构造三种基本形式的公钥体制，即公钥 加密体制，密钥交换协议和数字签名方案。目前，椭圆曲线密码正在被应用于解 决信息安全问题的实践中，而对椭圆曲线密码各种理论问题和实现技术的研究仍 然是密码学和信息安全中的一个热点。 已有的攻击算法表明，基于椭圆曲线离散对数问题( e c d l p ) 的困难性要高 于一般乘法群上的离散对数问题的困难性，且椭圆曲线所基于的域的运算位数远 小于传统离散对数的运算位数，很容易在计算机的软件和硬件上实现。 根据密码体系的研究需要，椭圆曲线指的是由威尔斯拉斯( w 萌e r s t r a s s ) 方程 y 2 + 口i 拶+ 吩y = x 3 + 吃x 2 + x + ( 2 1 ) 所确定的平面曲线。这一曲线在解析平面中表现为一条非奇异( n o n s i n g u l 撕t y ) 的三次平面曲线。若f 是一个域，口，f ( 江1 ，2 ，5 ) 。满足( 2 - 1 ) 的数偶( x ，y ) 称 为域f 上的椭圆曲线的点。f 域可以是有理数域，也可以是复数域，还可以是有 限域g f ( p ) 。本文所涉及的是有限域舒( p ) 上的椭圆曲线该域上的椭圆曲线可以 转化为如下形式： e ( ) ：y 2 = z 3 + 锨+ 6 ，口，6 0 ( 2 2 ) 其中，4 口3 + 2 7 6 2 0 。满足方程( 2 2 ) 的所有点( x ，j ，) 只e 加上一个无穷原点 ( 记为d ) 构成了椭圆曲线的点集，记为e ( x ，y ) 。这些点的加法如下定义： 椭圆曲线上任意两点尸，q ，通过该两点的直线上若与椭圆曲线有第三个交点， 记为一尺；一尺关于x 的对称点尺也在该椭圆曲线上。我们就定义： 尸+ q = 尺 ( 2 - 3 ) 定理2 3 【2 】如果尸和q 是椭圆曲线e 上任意两点，p ，q 连线交e 于另外一点尺，o 表示无穷远点，则：( 1 ) ( 尸+ q ) + 尺= d ，( 2 ) 尸+ d = 尸，( 3 ) 尸+ q = q + 尸，( 4 ) 若上存在一点q ，使得尸+ q = o ，这样的点用一p 来表示，( 5 ) 对于e 上的任一 点尸，q ，尺有p + q = q + 尸。 定义2 15 【2 】设p 是椭圆曲线e 上的一点，如果存在最小的整数，使得，尸= d ， 河南大学研究生硕士学位论文第9 页 其中d 表示无穷远点，那么称尸点的阶为，。 下面对素数有限域作一简单介绍： 素数有限域( p r i m ef i n i t ef i e l d s ) z 。的特征值为c h 矾f ) = p ，其中p 为大于3 的素数。由前文可知，此时的w - e i e r s 舰s s 方程式为 y 2 = z 3 + 以x + 6 ( 口，6 f ) 且( e ) = 4 口3 + 2 7 6 2m o d p 。 此时，椭圆曲线群上点的运算为： ( 1 ) 逆元公式： - p 2 ( x ，一y )( 2 - 4 ) ( 2 ) 加法运算： 为三( 五2 一_ 一屯) m o d p( 2 5 ) z - - 【乃三( 允( 五一而) 一y 1 ) m o d p 、。 其中， 2 2 密码学理论 l 丝丑尸q 肚 攀削 【2 m 。 本节将重点讲述文中所涉及的密码学相关基础知识。 2 2 1 公钥密码系统 ( 2 6 ) 公钥密码系统的概念是1 9 7 6 年d i 衔e 与h e l l m a n 在密码学的新方向一文 中提出的，开创了现代密码学的新领域。公钥密码体制的实现是以某种数学问题 的难解性为基础的。目前具有较高安全性和可行性的公钥密码体制有三类： 1 基于大数分解问题的公钥密码体制( 代表性的有r s a 体制) 。 2 基于有限域上离散对数问题( d l p ) 的公钥密码体制( 代表性的有e l g 锄a l 体 制) 。、 3 基于椭圆曲线离散对数问题( e c d l p ) 的公钥密码体制( 如e c d s a 体制) 。 其中基于椭圆曲线的公钥密码体制是单位比特安全强度最高的密码体制，具 有密钥长度短、运算开销小的特点。 第1 0 页河南大学研究生硕士学位论文 2 2 2 数字签名机制概述 数字签名是密码学的重要组成部分，是信息安全领域的研究热点。本小节将 对数字签名机制做一概述，主要包括签名技术、安全需求以及典型签名方案。 2 2 2 1 数字签名技术简介 信息时代的到来给我们提供了很多方便。政治、军事、外交、商业等方面的 文件，如命令、条约、契约，以及个人之间的书信等，传统上采用手写签名或印 签，以便在法律上能认证、核准、生效。手写签名或者印签可以提供以下功能： 1 消息的完整性：消息在被手写签名或盖上印签以后，不能再被修改。 2 证明消息的来源：任何读到文件的人都可以根据其上的手写签名或印签确 定签名人的身份。 3 不可抵赖性：签名人在签名以后，不能否认他签发的消息。 4 不可伪造性：任何其他人都难以伪造合法签名人的手写签名或印签。 手写签名和印签之所以能提供以上功能，是因为每个人的书法特征以及他掌握 的印章上的图案都具有唯一性。但在数字化的信息时代，传统的手写签名和印签 就很难发挥作用，尤其是人们通过数字通信网进行迅速的、远距离的交易时。所 以人们迫切需要一种类似于手写签名和印签的功能的数字化签名方法，称之为数 字签名。 数字签名的基础是公钥密码学，通过数学的手段来实现传统签名的功能。签 名方将要传送的文件通过哈希( h a s h ) 函数运算转换成消息摘要，然后用自己的私钥 对消息摘要进行签名后与明文一起传送给接收方。接收方将收到的文件转换成新 的消息摘要，并使用签名方的公钥进行验证，从而确定文件是否为签名方签署， 在传输过程中是否被篡改。 数字签名过程中除了对文件签名和对签名进行验证外，还有一个哈希函数操 作。哈希函数【3 5 0 7 】是被签名信息进入签名算法之前的一个预处理函数，它对任意 长度的消息进行处理，并保证输出的消息摘要值与原消息的每一位都相关。将h a s h 函数应用到数字签名中可带来如下一些好处： 1 可破坏数字签名方案中的某种数学结构，如同态结构。 2 h a s h 函数产生固定长度的输出给签名算法，避免签名算法直接逐位地处理 被签名消息，使消息的完整性得到了保障，并减少了签名算法的计算量， 提高了签名的效率。 河南大学研究生硕士学位论文第l l 页 目前常用的哈希函数有m d 4 ，m d 5 ，s h a 等，其中s h a 是美国国家标准局 为配合数字签名标准在1 9 9 3 年公布的散列函数。d i m e 和h e l l m a n 利用公钥密码 学的思想提出了数字签名的概念。 形式上，一个数字签名由以下的几个要素组成： 一个随机参数空间，尺； 一个秘密密钥空间，豚； 一个公开密钥空间，肷； 一个消息空间，m ； 一个签名空间，s ； 一个加密算法：勘洲：豚m s ； 一个密钥生成算法，劬g p 门：尺专胀； 一个签名验证算法，助：麒s m 专 乃甜p ，n 西2 l 。 他们具有以下性质： 对任意，尺，x 踊，y 尸k ，聊m ，s s ，如果( x ，y ) = 脚g 绷( ，) ， j = 勘咧( x ，聊) ，那么一个数字签名机制应该满足以下的条件： 1 由x 容易计算出y ，但是由) ，难以计算出x 。 2 附( y ，5 ，聊) = 乃甜p 。 3 如果不知道x ，则难以找到_ 个聊m 和一个s s ，使得 肋( y ，s ，聊t ) = 乃甜p 。 假设一个用户想在一个消息珑m 上签名。那么他首先随机选取一个参数 ，尺，计算( x ，y ) = 劬g p 门( ，) ，将y 公开，将( ，x ) 保密，然后计算出 s = 勘c 秒( x ，聊) 。当接受信息的用户收到( s ，所) 后，可以先查找该用户的公开密钥y ， 然后计算惭( y ，s ，聊) 。如果验证成功，那么s 可以被确认，是该用户在消息聊上的 有效数字签名；否则，这个签名被认为是无效的。 自从数字签名的概念出现以后，人们提出了许多不同的数字签名体制。比较 著名的数字签名机制包括：r s a ，r a b i n ，e l g a m a l ，s c h n o 玎，d s s ，o k 锄o t o ， f i a t - s h a m i r ，n y b e 唱一r u e p p e l 等。 2 2 2 2 签名方案的安全需求 这一节将研究什么是安全的签名方案，为此，需要确定一个攻击模型、攻击者 的目的以及方案所应实现的安全类型【3 8 1 。 1 攻击模型 攻击模型定义了攻击者可获得的信息，对于签名者来讲，经常需要考虑下列攻 第1 2 页河南大学研究生硕士学位论文 击模型： 惟密钥攻击( k e y o n l ya t t a c k ) ：攻击者拥有签名者的公钥，也即知道验证函 数v 。 已知消息攻击( k n o w n m e s s a g e a t t a c k ) ：攻击者拥有一系列由签名者签名的消 息。例如，( x l ，y 1 ) ，( x 2 ，y 2 ) ，其中x ，( 户1 ，2 ，) 是消息，而y ，( f _ 1 ，2 ，) 是签名者对这些消息的签名。 选择消息攻击( c h o s e nm e s s a g e a t t a c k ) ：攻击者请求签名者对一个消息列表签 名。即由他选择消息五，岛，让签名者提供这些消息的签名y ，( i _ 1 ，2 ，) 。 2 攻击目的 攻击者主要有以下几个目的： 完全攻破( t 0 t a lb r e a l ( ) ：攻击者能够确定签名者的私钥，即能够确定签名函 数。此时他能够对任何消息产生有效的签名。 选择性伪造( s e l e c t i v ef o 培e 巧) ：攻击者能够以某一个不可忽略的概率对另外 某个人选择的消息产生一个有效的签名。换句话说，如果给攻击者一个消息x ，那 么它能( 以某种概率) 确定签名y ，使得v 吒( x ，y ) ：t m e 。该消息不是签名者曾经 签名过的消息。 存在性伪造( e x i s t e n t i a lf o 玛e r y ) ：攻击者至少能够为一则消息产生一个有效 的签名。换句话说，攻击者能够创建一个( z ，y ) ，其中z 是消息且毗( x ，y ) 岛m e 。 该消息不是签名者曾经签名的消息，但不要求一定有明确的意义。 2 2 2 3 签名方案 1 签名体制定义 本节研究签名方案p9 1 。签名方案是一种以电子形式存储消息签名的方法，签名 之后的消息能通过计算机网络传输。 一个完善的签名方案至少应满足以下三个条件： ( 1 ) 签名者事后不能否认自己的签名。 ( 2 ) 任何其他人均不能伪造签名。 ( 3 ) 如果当事双方关于签名的真伪发生争执，能够在公正的仲裁者面前通过 验证签名来确认真伪。 下面对签名方案做一个正式的定义： 定义2 16 3 9 】一个签名方案是一个满足下列条件的五元组 ，月，瓦，j ，) ： ( 1 ) 曰是由所有可能的消息组成的一个有限集合； ( 2 ) 月是由所有可能的签名组成的一个有限集合； 河南大学研究生硕士学位论文第1 3 页 ( 3 ) 瓦为密钥空间，它是由所有可能的密钥组成的一个有限集合； ( 4 ) 对每一个k 瓦，有一个签名算法j 辔r j 和一个相应的验证算法 v 。每一个s ：曰专月和v ：口月j 护“p ，知居p ，对每一个消息 x 尸和每一个签名y 彳，都是满足下列条件的函数： y 啪功篙p 搿蘧暑 对每一个k 瓦，j 辔r 和v p k 应该是多项式时间函数。v 是公开的函数，而 s 辔r 是保密的。对于一个消息聊，攻击者想伪造签名者的签名在计算上是不可行 的。也就是说，给定一个消息x ，只有签名者能计算出签名) ，使得v ( x ，y ) = 护材p 。 签名方案不可能是无条件安全的，因为攻击者可以利用公开算法v 来测试消 息x 的所有可能的签名y ，直到他找到j 卜确的签名。因此在足够的时间内，攻击者 总可以成功伪造签名者的签名。因此，同公钥密码系统的情况一样，我们的目标 是寻找一个在计算上安全的签名方案。 签名方案几乎总是和一个非常快的公开h a s h 函数结合使用，将h a s h 函数应 用到数字签名中可带来下列好处： 。( 1 ) 可提高数字签名的速度。当签名者想签署一个消息x 时，他首先构造一 个消息摘要z = 办( 菇) ( 乃是一个h a s h 函数) ，然后计算签名) ，= s 堙+ ( z ) 。 ( 2 ) 无需泄露签名所对应的消息，可将签名公开，例如，对消息x 的签名是 ) ，二j 瓴( z ) ，其中z = 向( x ) ，可将( z ，y ) 公开，而保密x 。 ( 3 ) 可将签名变换和加密变换分开，允许用私钥密码体制实现加密，而用公 钥密码体制实现数字签名。 h a s h 函数和签名方案的结合思想如下：首先，把消息z 作为h a s h 函数的输入， 生成一个固定长度的消息摘要z = 乃( x ) ；然后，签名方案对该消息摘要进行签名运 算生成签名，即) ，= s 辔。( z ) 。然后把有序对( z ，y ) 在公共信道上传输；接着，验 证者通过公开的h a s h 函数力重构消息摘要z = j l z ( x ) ，并检查是否有1 ，p 以( z ，) ，) = t m e 。 当把h a s h 函数引入到签名方案中时，要使h a s h 函数满足一定的安全属性以 便阻止各种各样的攻击。 攻击者最显然的攻击是从一个有效的签名消息( x ，) ，) 开始，其中 y = s 辔。( 而( z ) ) 。然后他计算z = 办( x ) 并企图找到x x 使得力( z ) = 办( x ) 。如果攻击 者能够做到这一点，( x ，y ) 将成为一个有效的签名。这是一种使用已知消息攻击的 存在性伪造。为了阻止这种攻击，要求h a s h 函数办是第二原像稳固的。 另外一种攻击是：攻击者首先找到两条消息x z 使得办( z ) = 办 ) ，然后，他 将消息发给签名者，并让签名者对消息摘要厅 ) 签名以获得y 。那么( x ，y ) 是有效 第1 4 页河南大学研究生硕士学位论文 的签名，而y 是消息x 的伪造签名。这是一种利用选择消息攻击的存在性伪造。如 果h a s h 函数乃是碰撞稳固的，就可以阻止这种攻击。 第三种攻击是，攻击者要对某个消息摘要进行签名，他找一个消息z 使得 z = 办( x ) ，那么( z ，) ，) 就是有效签名，而y 是x 的伪造签名。为了阻止这种攻击， 要求h a s h 函数是原像稳固的。 2 典型的基于离散对数和安全单向函数的签名机制一般如下【4 0 】： ( 1 ) 体制参数 p ：大素数； 曰：为p 一1 或q l 的大素数因子； g ：g z ：，且9 9 = 1 ( m o d p ) ； h ( ) ：是安全的哈希函数； 用户的秘密密钥x ：l x q ； 用户的公开密钥y ：y = g 。( m o d p ) 。 ( 2 ) 数字签名的生成过程 对于要签名的消息聊，用户进行以下步骤： a ) 计算历的哈希值( m ) ； b ) 选择随机数克，l 足 g ，计算出r = g ( m o d p ) ； c ) 从签名方程础= 6 + 饿( m o d 印) 中解出s 。方程的系数口，6 ，c 有