（控制理论与控制工程专业论文）椭圆曲线数字签名的研究与应用.pdf

大连理工大学硕士学位论文 摘要 在网络得到快速发展和应用的现代社会，人们越来越重视网络上信息的安全问题。 公钥密码体制的数字签名技术作为保障信息安全的技术之，在确保信息完整性、不可 伪造性、不可否认性方面发挥了重要的作用。以椭圆曲线离散对数的难解性为基础的椭 圆曲线公钥密码体制作为当今安全性最高的公钥密码体制，成为国p q # t - 计算机密码学研 究的重要课题之一。本文通过深入研究椭圆曲线数字签名方案及以椭圆曲线为基础的门 限和代理方案，设计了一套应用于局域网的数字签名系统。 本文首先阐述了椭圆曲线密码学的研究背景和现状。本文刈椭圆曲线的常j 1 计算及 其实现方法进行了比较，对椭圆曲线离散对数的常用攻击算法进行了分析得出了安全椭 圆曲线的标准，该安全标准可以确保产生的椭圆曲线不是特殊曲线从而避免遭受常见的 攻击。然后对产生安全椭圆曲线的方法进行了研究。考虑到数字签名在不同的应用场合 的实际应用功能的多样化，本文在标准的椭圆曲线数字签名的基础上设计了基于椭圆曲 线的门限签名和代理签名。在理论研究的基础之上，本文开发了适用于椭圆曲线公钥密 码体制软件实现的功能模块，并在此模块基础上开发了适用于局域网的椭圆曲线数字签 名系统。 本文采用的基本签名方案、门限方案和代理方案具有较高的安全性，可挫败伪造和 合谋攻击。本文设计的功能模块具有易于扩展、可拆分使用、独立性强、可移植性强、 可变长等特点，实际应用证实该模块具有较强的稳定性，所设计的椭圆曲线数字签名系 统具有安全性高、操作简单、功能多样化的特点。 关键词：椭圆曲线；数字签名：门限签名；代理签名 椭圆曲线数字签名的研究与应用 r e s e a r c ha n da p p l i c a t i o no fe l l i p t i cc u r v ed i g i t a ls i g n a t u r e a b s t r a c t n o w a d a y s ，n e t w o r k st e c h n i q u ei sa p p l i e dm o r ea n dm o r e ，p e o p l ep a ym o r ea t t e n t i o nt ot h e s e c u r i t yo ft h ei n f o r m a t i o ni nn e t w o r k s d i g i t a ls i g n a t u r ei so n eo ft h et e c h n i ct h a te n s u r e i n f o r m a t i o ns a f e t y i t p l a y sa ni m p o r t a n tf a c t o r i n p r o t e c t i n gi n t e g r a l i t y ，u n f o r g e a b i l i t y ， u n d e n i a b i l i t ya n dv e r i f i a b i l i t yo ft h ei n f o r m a t i o n e l l i p t i cc u r v ec r y p t o g r a p h yi st h em o s ts e c u r e p u b l i ck e yc r y p t o g r a p h y ，w h i c hi s b a s e do nt h ei n t r a c t a b i l i t yo ft h ee l l i p t i cc u r v ed i s c r e t e l o g a r i t h mp r o b l e m ( e c d l p ) a n di th a sb e c o m eam a j o rs u b j e c to ft h ec r y p t o g r a p h ya th o m e a n db r o a d i nt h i sp a p e r ，t h eg e n e r a ls i g n a t u r e ，p r o x ys i g n a t u r ea n dt h r e s h o l ds i g n a t u r es c h e m e a r ed i s c u s s e di nd e t a i l t h e nad i g i t a ls i g n a t u r es y s t e mf o rl a ni sd e v e l o p e d f i r s t l y ，t h eb a s i cl “q o w l o d g eo f t h ee l l i p t i cc u r v ec r y p t o g r a p h yi si n t r o d u c e d t h e n ，g e n e r a l c o m p u t a t i o no ft h ep o i n t so nt h ee l l i p t i cc u r v ea n dt h ew a y st oi m p l e m e n tt h e ma r ed i s c u s s e d t h ec a p a b i l i t yt ow i t h s t a n dt h ea t t a c k st ot h ee c d l pi sa n a l y z e d ，a n dt h e nas e c u r i t yc r i t e r i o ni s p m p o s e d t h es e c u r i t yc r i t e r i o nc a np r e v e n tt h ee l l i p t i c c u r v ef r o mb e i n ga t t a c k e d t h e a l g o r i t h m st og e n e r a t eas e c u r ee l l i p t i cc u r v ea r ep r e s e n t e di nd e t a i l t om a k et h es i g n a t u r e f u n c t i o n ss u i t a b l ef o rv a r i a b l ec o n d i t i o n s ，at h r e s h o l ds i g n a t u r ea n dap r o x ys i g n a t u r es c h e m e a r ed e s i g n e db a s e do ne c d l p b a s e do nt h et h e o r ya b o v e ，a na p p l i c a t i o np r o g r a m m ei sd e v e l o p e d t h ea l g o r i t h mm o d u l e c a nb eu s e dt oi m p l e m e n tt h ea l g o r i t h m sb a s e do ne l l i p t i cc u r v e a n da ne l l i p t i cc u r v ed i g i t a l s i g n a t u r es y s t e mf o rl a nb a s e do nt h em o d u l ei sd e v e l o p e d t h eg e n e r a ls i g n a t u r es c h e m e ，t h e t h r e s h o l ds i g n a t u r es c h e m ea n dt h ep r o x ys i g n a t u r es c h e m ei nt h i sp a p e rh a v eh i g hs e c u r i t y ， t h e ya r ec a p a b l et ow i t h s t a n dt y p e so fa t t a c k s ，c o n s p i r a c ya t t a c ka n df o r g ea t t a c ki n c l u d e d t h e p r o g r a m m ed e v e l o p e di n t h i sp a p e rh a ss o m ec h a r a c t e r i s t i c si n c l u d i n ge x p a n d a b i l i t y ， d i v i s i b i l i t y ，i n d e p e n d e n c e ，p o r t a b i l i t ys t a b i l i t ya n dl e n g t ha d j u s t a b i l i t y t h ee l l i p t i ce u r v ed i g i t a l s i g n a t u r es y s t e mi nt h i sp a p e rh a sc h a r a c t e r i s t i c so fh i g hs e c u r i t y ，h a n d l i n gf a c i l i t ya n df u n c t i o n d i v e r s i f i c a t i o n k e yw o r d s ：e l l i p t i cc u r v e ；d i g i t a ls i g n a t u r e ；t h r e s h o l ds i g n a t u r e ；p r o x ys i g n a t u r e i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究 工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文r h 不包含其他人已经发表或撰写的研究成果，也不包含为获得 大连理工火学或其他单位的学位或证书所使用过的材料。与我一同工作 的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谓 意。 作者签名：妒日期型逊 火连理f 火学硕士学位论文 1 绪论 随着现代通信技术和计算技术的迅速发展，尤其是网络技术的迅猛发展，计算机网 络已经进入到了人类社会的诸多领域，人类社会已经进入信息时代。每天都有大量的企 业、机必和个人信息在网络上进行交换，信息安全已经不再是政治、军事、外交的特有 问题，它更普遍地存在于人们生产和人活的各个方面。信息的保密性、完整性得到了前 所未有的重视，计算机密码学的研究已经从秘密到公开，并成为与信息科学、数学、计 算机科学密切相关的一门新兴学科。 1 1 国内外椭圆曲线数字签名发展概况 密码学发展已经有上千年的历史，传统的密码学只是为信息提供加密和解密的功 能，从而实现信息的保密，使没有得到受权的人不能得到信息的实际意义。 随着现代科学技术的发展，密码学的理论和研究方法也在不断的丰富着。d i f i e 和 h e l l m o a a 于1 9 7 6 年在“密码学的新方向”一文中提出了公钥密码学的思想，引起了密码 学的又一次飞速发展。公钥密码体制的实现是以某种数学问题的难题性为基础的。 1 9 7 6 年以后，研究者提出了许多基于不同数学问题的公钥密码体制的实现方案，经过 长期的研究，目前认为具有较高的安全性和可行性的方案有如下三类f j j f 2 ： 一基于大数分解问题的公钥密码体制。其中包括r s a 体制和r a b i n 体制等。 基于有限域上离散对数问题的公钥密码体制。其中包括e 1 g a m a l 类加密体制和 签名方案，d i f i l e h e l l m a n 密钥交换方案，s c h o n r r 签名方案等。 基于椭圆曲线离散刑数问题的公钥密码体制。其中包括椭圆曲线d i f f i e - h e l l m a n 密钥交换方案，椭圆曲线型的密钥交换方案，椭圆曲线型的数字签名方案等。 椭圆曲线密码体制即基于椭圆曲线离散对数问题的各种公钥密码体制，最早于 1 9 8 5 年由k o b l i t z 和m i l l e r 提出，它是利用有限域上的椭圆曲线有限群代替基于离散对 数问题的密码体制中的有限群所得到的一类密码体制口j 。因此，严格地说它不是中新 的密码体制，它只是已有密码体制的椭圆曲线型的翻版。如果按照构造体制的方式分 类，前面的体制可归纳为两类，椭圆曲线密码体制应归于基于离散对数问题的密码体制 当中。但是，由于它有许多独特的性质，使得人们一丌始就对它进行单独考虑。本文也 正是对它的一种专门研究。 在椭圆曲线密码提出之初，并未引起太多注意，主要是因为当时还没有一种实际 有效的计算椭圆曲线上有理点数的有效方法，其次，与当时已有的r s a 公钥密码体制 椭圆曲线数字签名的研究与应用 相比椭圆曲线公钥密码体制中计算过于复杂，使得实现椭圆密码体制时速度较慢。1 9 9 0 年，m e n e z e s 曾使用了某些特殊曲线，这种曲线不仅其点数可直接算出而且实现起来非 常快。很快，在1 9 9 1 年m e n e z e s ，o k a m o t o 和v a n s t o n e 发现了一种有效的攻击椭圆曲 线离散对数问题的方法( 称为m o v 方法) 4 1 1 5 1 , 这种方法能够将一类被称作是超奇异的 椭圆曲线上的离散对数问题在多项式时间内约化到该椭圆曲线域的某个次数较低的扩域 上，进而可利用已有求解离散对数问题的算法对其进行求解。为了避免m o v 方法的攻 击，椭圆曲线密码体制不再使用特殊曲线。与此同时，为了解决曲线的选取问题，人们 对任意椭圆曲线上有理点个数的计算已有了重大突破。最初由s c h o o f 在1 9 8 5 年提出计 算椭圆曲线有理点- i 、数的算法i 6 j ，1 9 8 9 年到1 9 9 2 年之问a t i k i n 和e l k i e s 对其作出了 重大改进，而后在c o u v e r g n e s ，m o r a i n ，l e r c i e r 等人的完善下，到1 9 9 5 年时人们已经 能够较容易地计算出满足密码要求的椭圆曲线有理点的个数了。这使椭圆曲线的选取已 经不再是椭圆曲线密码实用化不可逾越的障碍了。自椭圆曲线密码提出后，人们在如何 才能快速实现体制方面做了大量的研究，并取得了许多重要的进展。人们不懈的努力使 得椭圆曲线密码体制的实现速度较椭圆曲线密码提出之初有了很大提高。 表1 1 椭圆曲线密码体制与r s a e 1 g a m a l 密码体制的安全性比较 c h a r t1 1 c o m p a r i s o n b e t w e e n e m p f i c c u r v ec r y p t o s y s t e ma n dr s a e i g a m a l c r y p t o 蹬! 堡翌 8 1 a ! 曼鬟掣嘤兰线密钥 密钥长度比所需工芝量 密钥长度( 比特)长度( 乩i t 忖i i + j n m i p s 年 19 7 8 年r s a 公钥密码体制和1 9 8 5 年e i g a m a l 型公钥密码体制提出后，人们对它 们的研究产生了浓厚的兴趣。值得注意的是对大数分解问题的求解和对有限域上离散对 数问题的求解在本质上具有某种一致性。借助于计算机技术的不断提高，经过人们的不 懈努力，目前人们别+ 两类问题的求解能力较过去有了很大的提高。这使得r s a 公钥密 码体制中使用的模数和e i g a m a l 型公钥密码体制中使用的有限域的大小越来越大。对这 两类体制，过去5 1 2 比特的密钥已经足够安全，但现在为了达到相同的安全性不得不使 一2 ， 大连理= 大学硕士学位论文 用1 0 2 4 比特或更大的密钥。相反地，人们对椭圆曲线离散对数问题的求解方法的研 究，几乎是毫无进展，目前对椭圆曲线离散对数问题最好的计算时间是指数级的，对椭 圆曲线密码体制，1 6 0 比特长的密钥所具有的安全性和前两类体制中1 0 2 4 比特长的密 钥所具有的安全性相当，其体的安全性比较见表1 1 t7 1 。椭圆曲线密码体制的优势逐渐 地体现出来，在这样的一种背景和椭圆曲线密码理论逐渐走向成熟的情况下，近几年椭 圆曲线密码已经成了密码学中的又一个研究热点。 1 _ 2 本文的研究工作 正是对数字签名的强大功能和椭圆曲线公钥密码体制的高安全性，作者在广泛阅读 椭圆曲线密码学的相关文献的基础上对椭圆曲线密码系统的实现、椭圆曲线数字签名方 案进行了深入的研究，设计基于椭圆曲线的门限签名方案和代理签名方案。为了满足在 密码学实现中对超大的数据进行准确而快速计算的需要，本文独立自主地开发了功能模 块。垓模块可以对密码学工程实践中的超大数据进行常用的数学计算、可以完成椭圆曲 线点的常用计算、可以完成椭圆曲线的产生及安全性检测等操作。 本文的主要目的在于对椭圆曲线密码学进行深入研究的基础之上，建立一套安全椭 圆曲线生成方法，并基于此建立稳定可靠的椭圆曲线数字签名系统。论文的后续章节安 排如下： 第二章：深入地研究了椭圆曲线的定义、椭圆曲线上点的运算，分析了椭圆曲线离 散对数问题的常用算法，在此基础上得出了安全椭圆曲线的标准，并研究了产生安全椭 圆曲线的方法。 第三章：研究了标准椭圆曲线的数字签名方案，以及基于椭圆曲线的门限签名方案 和代理签名方案。 第四章：分析了数字签名的系统的功能需求，开发适用于椭圆曲线密码学实现的功 能模块，并以此模块为基础开发了椭圆曲线数字签名系统。 第五章：对系统的抗攻击能力进行分析，并使用攻击算法对系统的进行了攻击实 验，通过对实验数据的分析，进一步印证其安全性。 第六章：对本文的工作进行了总结，并提出了对未来工作的展望。 一3 一 椭圆曲线数字签名的研究与应用 2 椭圆曲线密码学 2 1 密码学的发展 密码学是一门古老的学科，在军事和商业中有着广泛的应用。自上个世纪5 0 年代 以后，随着计算机技术的飞速发展，计算机的强大计算能力与密码学相结合产生了一个 新的学科，计算机密码学。 在密码学中，要传递的原始信息称为明文，明文加密后的信息为密文。由明文计算 计算得到密文的过程称为加密，该过程中使用的信息处理规则称为加密算法。由密文计 算得到明文的过程称为解密，该过程中使用的信息处理规则称为解密算法【8 】。典型的密 码学模型如图2 1 所示。 现代密码学中，加密和解密都是在密钥的控制下完成的，分别称为加密密钥和解密 密钥。密码体制的完全性依赖于密钥的安全生与算法的强度，而不依赖于算法的保密 性。 简单的密码应用模型由发送方、接收方、加密密钥、解密密钥、加密算法、解密算 法构成。发送方使用加密密钥通过加密算法对明文进行加密得到密文，并将密文发送给 接收方。接收方收到密文后使用解密密钥通过解密算法对密文解密得到明文。攻击者窃 听到发送方与接收方的通信内容后，所读到的是没有意义的密文信息，如果没有解密密 钥就无法获得明文信息。 公刑言道 加密密钥k 1i 攻击者i 解密密钥k 2 图2 。l 密码模型图 f i g 2 1c r y p t o g r a p h ym o d e l 一4 火连理工大学硕士学位论文 根据加密和解密过程中所使用的密钥是否相同，密码学可为对称密码学和非对称密 码学。在对称密码学系统中加密密钥和解密密钥是相同的，而在非对称密码学系统中加 密密钥和解密密钥是不周的，非对称密码学又可称为公钥密码学【9 】。 密码学应从以下几个方面保护信息的安全【8 】： 保密性任何人不可能在不使用解密密钥的情况下根据密文计算得到明文。 不伪造性任何人不可能冒充发送方向接收方发送某个信息并使接收方认为此信息 来自发送方。 完整性接收方可以确认密文信息在传送的过程中是否被篡改。 不可否认性发送方在发送文件后不能否认其发送行为。 对称密码学作为密码学的传统研究内容，只能保障信息的保密性，而公钥密码学则 可以同时满足以上要求。 公钥密码! 学的发展在绪论中已经进行了较详细的论述，在此不作赘述。 在公钥密码体制中密钥分为私钥与公钥。私钥由用户保管，公钥则在网络中发布， 以供加密或认征时使用。 使用公钥密码系统，可以达到下列功能： 一保护秘密信息。如果发送方需要将秘密消息 n 传送给接收方，发送方以接收方 的公钥作为加密密钥通过加密算法对m 进行加密，得到密文c 。只有使用接收方的的私 钥才能将密文c 成功解密得到明文m 。 一简化密钥分配及管理问题。网络上的每一个人只需要一个加密密钥( 公钥) 及一 个解密密钥( 私钥) ，就可以和其他人进行秘密的通信，而不需要和不同的人使用不同的 密钥进行通信。在保障安全性的同时简化了密钥分配和管理问题。 可达到不可否认和验证功能：在图2 1 中如果发送方使用自己的私钥对文件进 行加密生成密文，则任何人都可以使用发送方的公私将密文解密得到明文，并与原来的 明文对照。当日仅当使用私钥对文件加密得到的密文，才可以用对应的公钥解密得到正 确的明文，凶此使用私钥对文件的加密相当于对文件留下了特有的印记，称为签名，使 用其公钥可以证明是否对文件签名，任何人无法伪造，本人也不能否认。 公钥密码体制更大的作用在于应用上述的第三点功能为文件提供认证、防伪造、防 篡改和信息完整性服务。 5 椭圆曲线数字签名的研究与应用 2 2 椭圆曲线 2 2 1 椭圆曲线的定义 设足是一个给定域，称在射影平面p 2 ( 世) 上形式如( 2 1 ) 的等式为w e i e r s t r a s s 方 程。 y 2 z + a j x y z + a 3 y z 2 = x 3 + a 2 x 2 z + 日t x z 2 + a 6 2 3 其中q ，a 2 ，a 3 ，a 4 ，吒为域足中的数，假设其满足j a c o b i 条件，即若下式成立时 ( 2 1 ) r ( x ，y ，z ) = y 2 z + q x y z + a 3 y z 2 一( z 3 + a 2 x 2 z + a 4 x z 2 + a j 3 ) ( 2 2 ) 下列方程组( 2 3 ) 在k 上无解，由w e i e r s t r a s s 方程所确定的曲线为椭圆曲线，用e ( k ) 表示i o i 。 a f a x = 0 o f a t = 0 o f a z = 0 f ( x ，y ，z ) = 0 ( 2 3 ) 显然，对椭圆曲线，使坐标分量z = 0 的唯一彭j a j & ( o ，1 ，o ) ，称该点为无穷远点， 记为0 。 对于方程( 2 1 ) ，令x = 孑x ，y = 三，则( 2 1 ) 可变为： y 2 + 巩x y + a 3 y = z 3 + a 2 x 2 + 口4 x + a 6 ， q k 这时( 2 1 ) 的全部解s 可表示为如下形式 s = ( x ，y ，1 ) k 3 i ( x ，y ) 为方程( 2 4 ) 的解) u ( 0 ，1 ，o ) 1 记s = ( x ，y ) k 2 i ( x ，y ) 为方程( 2 4 ) 的解) u 0 ) 一6 ( 2 4 ) ( 2 5 ) ( 2 6 ) 大连理工大学硕士学位论文 并作由s 到s 的映射如下 ( x ，y ，1 ) 斗( 工，y ) ( 0 ，1 ，o ) 寸d ( 2 7 ) 显然这一映射是一对一的且是满的。于是，对于椭圆曲线，可用方程( 2 4 ) 的解集 合，外加一个无穷远点0 来表示，这时称( 2 4 ) 为曲线的仿射方程。相对于此，方程 ( 2 1 ) 称为曲线的射影方程。 刘于方程( 2 1 ) 或方程( 24 ) ，为了表述方便，以如下形式定义6 ：，氏，b o ，b 8 ，q ，c 。： i b 2 = q2 + 4 d 2 i 如= q d 3 + 2 i b 6 = a 3 2 + 4 口6 1 6 8 = a i - “6 + 4 a 2 a 6 一a t a 3 a a + a 2 a 3 2 f o = 6 17 2 4 b 4 i c 6 = 一6 2 3 + 3 6 b 2 b 4 2 1 6 b 6 则椭圆曲线耳硒的判别式定义为式( 2 9 ) a = 一b 2 1 b 8 8 玩3 2 7 b 6 2 + 9 b 2 b 4 b 6 甄固的- ，不变量定义为式( 2 1 0 ) 。 j ( e ) = 根据k 的特征值c 口，( k ) ，可得到以下几种简单形式1 。 1 ) c h a r ( k ) 2 ，3 c u j q - ，一般形式的方程( 2 4 ) 可以化为如下形式： y 2 = x 3 + 删+ 6 ， 口，b k 一7 - ( 2 8 ) ( 2 9 ) ( 2 1 0 ) ( 2 1 1 ) 椭圆曲线数字签名的研究与应用 此时，= 一1 6 ( 4 a 3 + 2 7 b 2 ) ，( e ) = 一1 7 2 8 ( 4 a ) 3 a 。 2 ) c h a r ( k ) = 2 可分以下两情况对方程( 2 4 ) 进行化简。 ( 1 ) _ ，( e ) 0 方程( 2 4 ) 可化为如下形式： y 2 + x y = x 3 + a ，工2 + 吒 其中，a 2 , a 6 ko 对方程( 2 1 2 ) ，显然有：a = a 6 , ( e ) = i 1 。 ( 2 ) j ( e ) = 0 ， 方程( 2 ，4 ) 可化为如下形式： y 2 + a 3 y = x 3 + d d x + a 6 ( 2 1 2 ) ( 2 1 3 ) 其中，吼，魄k ，剥方程( 2 1 3 ) 有：= 吩4 ，j ( e ) = 0 。 在椭圆曲线密码学中，只研究( 2 1 1 ) 和( 2 1 2 ) 形式的椭圆曲线。( 2 儿) 和( 2 1 2 ) 所 代表的椭圆曲线的特征值不同，但二者有着紧密的联系，其理论和研究方法是相通的。 因此，本文只研究( 2 儿) 所表示的椭圆曲线。 设p = 矿，其中g 为大于3 的素数，m o ，则p 定义了有限域c 。在有限域中有 如式( 2 1 4 ) 所示椭圆曲线： e ( c ) ：y 2 = x 3 + a x + b ，口，b ( 2 1 4 ) 如果有( x ，y ) ec 2 满足等式( 2 1 4 ) ，则称( 工，y ) 为椭圆曲线上的一个有理点，椭圆 曲线的全部有理点与无穷远点o 构成了椭圆曲线上的所有点1 2 1 。椭圆曲线密码系统就是 在椭圆曲线的这些点构成的有限群上构建的，因此不对椭圆曲线和椭圆曲线上的点加以 8 大连理工大学硕士学位论文 区分，通常以椭圆曲线e ( c ) ：y 2 = ，+ 甜+ 6 来指代曲线上的所有点。椭圆曲线上点的 总数为椭圆曲线的阶，记为# e l ：只) 。 无穷远点o 在椭圆曲线的点构成的有限群中起加法幺元的作用1 3 】，其作用相当于整 数加法群中的0 。横坐标相同、纵坐标相反的两个点互为逆点，互逆的两个点相加为 0 。 2 | 2 | 2 椭圆曲线点的运算 1 ) 椭圆曲线的点加运算 在椭圆曲线上规定，一条直线与椭圆曲线相交，所有交点的和为o 1 4 1 。 y 。 少 哆 。 u i y 。 l i 写 t 。 设有r = 月， 即q q 一吩q = 屯尸一包户， 从而有q = 等p ， 得 朋：皇上皇m o d 。此时( 一f ) 为f ：的整数倍。因此p o i i a r d 巾方法的实质就是要计算序 1 5 椭圆曲线数字签名的研究与应用 列r o ；r , ，r ：，并找到序列的周期。对于如何从序列中快速的找到其周期，同时又不占 用太多的存储空间，f l o y d ，b r e n t 等人做了大量的工作。 f l o y d 使用的方法： 对每一个i = 1 ，2 ，3 ，同时计算( r 。，a i ，t ) 和( r ，q ，6 2 ，) ，直到对某个i = r ，有 耳= r 2 ，。这时可确定序列的周期并可计算得到m 。如果序列的周期为，需要调用 3 ，：次迭代函数可以确定周期值。如果将每一次计算得到的r 的值保存并列表，可以将 调用迭代函数的次数降低至5 ，2 次，但列表中需要保存至少f ，4 个点的值。 将此方法稍加改变： 对每一个i = o ，l ，2 ，3 ，首先计算( r 2 ，a 2 ，b 2 ，) ，然后依次计算( r k ，a k ，钆) 其中 k = 2 十l ，2 + 2 ，2 “lt 并将r 与r 2 比较，直到对某个i 和k 【2 + l ，2 ”1 ，有 尺。= r k 。这时可确定序列的周期并可计算得到川。如果序列的周期为f ，需要调用2 次迭代函数可以确定周期值。 下面分析p o l l a r d - ) 算法的时间复杂度和空间复杂复。可以把序列r 看作是在包含 p 点的有限群中挑选出的，用m 表示迭代k 次后产生k 个不同的点胄，月：，r ，于是 ，2 事件m 的概率为( 卜专) ( 1 专) ( 卜与) * g 雨。由此能够得到在r 2 ，r 中存在 有重复点时k 的期望值是等，即p o l l a r d - p 算法的时间复杂度是0 ( 等) ，与大步小 步法的时间复杂度相当，但p o l l a r d - p 算法不需要预计算，与大步小步法相比节省了大量 的预计算时i e j 和空间丌销。p o l l a r d - p 是目前最有效的椭圆曲线离散对数攻击算法。 从以上看出，使用大步小步或是p o l l a r d - p 方法计算椭圆曲线问题，需要的时间与 生成元的阶的平方根大小有直接关系。因此，为了使椭圆曲线密码系统具有足够的安全 性，生成元的阶要足够大。目前认为当椭圆曲线的阶为1 6 0 位的二进制数进可以提供足 够的安全性。 4 ) p o h l i g - h e l l m a n 方法： 用n 表示p 的阶，并设月的标准素因子分解式是： n = p l l i p 2 n - p 7 1 6 一 ( 2 3 4 ) 立婆壁兰垦壁堡主堂垡堕壅 1 段如对每一个n 。( f - 1 ，2 ，r ) ，已经求出了m m o d p ，f ，则由中国剩余定理可立即 求出m 。拥此，p o h l i g 。h e l l m a n 算法的基本思路是：首先由椭圆曲线阶的素因子分解式 求出，z 的素因子分解式，然后对每一个f ，t i ，求出m m o d p ，最后由中国剩余 定理求出肌。其中，在求m m o d n 的过程中将问题转化为对离散对数问题q t = m l p 的 求解，而这时尸。的阶是n ，1 m 。p ，。下面对p o m i g h e l l m a n 的这一过程作进一步的 介绍。为此，不妨设椭圆曲线阶的标准素因子分解式如下式： = ”j 】，2 p ，4 ，q 1 ，i = 1 ，2 ， n h n l n ，所以对胛的素因子分解式，应有：o z q ，i = l ，2 ，。 ( 2 3 5 ) 首先由n 的素因子分解式求n 的素因子分解式。注意到n p = 0 ，所以当坐p 0 p i 时，一定有f = q ，而当苦j d = p 时，需继续判定是否尝尸= d ，如此下去在e j 步内 以p 2 。 一定能确定j ( f = 1 ，2 ，r ) 。因此，不难由| v 的标准素因子分解式求出n 的标准素因 子分解式。 现在对每一个f ( f = 1 ，2 ，) 考虑求肌m o d p ，。为了简化符号，下面用p 表示这 里的只，用厂表示这里的，并无妨设厂1 。 记m ，= m r o o d p ，并设可表示为如下形式： m f = + 口】p + a 2 p 2 + 口，1 p i - 10 4 x p ，所以 t = ，1 心+ t z m z + - + t k m k ( 2 4 3 ) ( 2 4 4 ) ( 2 4 5 ) ( 2 4 6 ) 显然上面的第一步和第三步都容易实现，所以s c h o o f 算法的关键是第二步即给 定素数，后如何计算t m o d 。 虽然s c h o o l 算法是一种