（通信与信息系统专业论文）基于椭圆曲线可追踪门限数字签名方案的研究与实现.pdf

摘要 随着信息技术的飞速发展，网络的应用范围越来越广，信息安全 显得尤为重要，信息安全问题也成为近几年信息技术领域的研究热 点。数字签名技术是信息安全一个热门的研究课题，它的研究对于保 证信息的认证性、完整性有重要的意义。 ( t ，n ) 门限数字签名是对普通数字签名的推广，采用门限签名 方式可以实现权力分配，避免滥用职权。椭圆曲线密码体制的安全性 建立在椭圆曲线离散对数问题( e c d l p ) 的困难性之上。现在求解 e c d l p 的最好算法具有全指数时间复杂度。同其他密码体制相比较， 椭圆曲线密码体制可以用更短的密钥达到等同的安全强度。 本文的主要研究内容是基于椭圆曲线可追踪门限数字签名方案 的研究与实现。本文理论与实际相结合，以j a v a 为开发语言、 j b u i l d e r 为开发工具、s q ls e r v e r 为数据库管理系统，开发了一个电 子文件门限签名系统。本文主要完成了以下几方面的工作：在对现有 门限签名方案的研究基础上，分析并改进了一种安全的门限群签名方 案；对椭圆曲线密码体制进行研究，在素数域f ，上实现了安全椭圆 曲线的随机生成和基点的选取；设计了一种基于椭圆曲线可追踪门限 数字签名方案；在上述研究基础之上，实现了一个基于椭圆曲线可追 踪的门限数字签名系统，该系统可对电子文件进行离线签名。 关键词椭圆曲线密码体制，数字签名，门限签名，可追踪 a bs 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 fi n f o r m a t i o nt e c h n o l o g y , n e t w o r ki s a p p l i e di nm o r ea n dm o r ef i e l d sa n di n f o r m a t i o ns e c u r i t yb e c o m em o r e i m p o r t a n t i nr e c e n ty e a r s ，s e c u r i t yo fi n f o r m a t i o nh a sb e c o m eah o t r e s e a r c ha r e ai ni n f o r m a t i o nt e c h n o l o g y t h es t u d y i n go f d i g i t a ls i g n a t u r e i sa ni m p o r t a n ts u b j e c ti ni n f o r m a t i o ns e c u r i t y , a n di ti s s i g n i f i c a n tf o r g u a r a n t e et h ei n t e g r a l i t ya n da u t h e n t i c a t i o no fi n f o r m a t i o n t h e ( t ，n ) t h r e s h o l ds i g n a t u r ew a sd e v e l o p e df r o mn o r m a ld i g i t a l s i g n a t u r e at h r e s h o l ds i g n a t u r es y s t e mc a ns c a t t e rr i g h t sa n da v o i dt h e a b u s eo fp r i v i l e g e t h es e c u r i t yo f e l l i p t i cc u r v ec r y p t o g r a p h i c ( e c c ) s y s t e m i sb a s e do nt h e e l l i p t i c c 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 ) c u r r e n t l y , t h eb e s ta l g o r i t h mk n o w nt os o l v et h ee c d l ph a s f u l l ye x p o n e n t i a lr u n n i n gt i m e i no r d e rt oa t t a i nas a m es e c u r i t yl e v e l ， e l l i p t i c c u r v e c r y p t o g r a p h y s y s t e mc a n u s es h o r t e rk e yt h a no t h e r c r y p t o g r a p h ys y s t e m s s o ，e l li p t i cc u r v ec r y p t o g r a p h yh a sm o r el i t t l e k e y s ，u s e sf e w e rr e s o u r c e sa n dc a nb em o r ee a s i l yi m p l e m e n t e d t h i sp a p e rc o n t a i n t st h er e s e a r c ha n di m p l e m e n to ft r a c e a b l ed i g i t a l s i g n a t u r es c h e m e sb a s e do ne l l i p t i cc u r v ec r y p t o g r y a p h t h ep a p e rp u t t h et h e o r yi n t op r a c t i c e ，b yu s i n gt h ed e v e l o p i n gt o o l ss u c ha sj a v a ， j b u i l d e ra n ds q ls e r v e rd a t a b a s et oc o n s t r u c tat h r e s h o l ds i g n a t u r e s y s t e m ，w h i c hc a nb eu s e dt os i g n eo ne l e c t r o n i cf i l e s t h ef o l l o w i n g w o r kh a sb e e nc o m p l e t e di nt h i sp a p e r ：b ys t u d y i n gt h ec u r r e n tt h r e s h o l d s i g n a t u r es c h e m e s ，i ta n a l y s e sa n di m p r o v e sak i n do ft h r e s h o l dg r o u p s i g n a t u r es c h e m e ；b a s i n go nr e s e a r c h i n ge c c ，i th a si m p l e m e n t e d g e n e r a t i n gas a f ee l l i p t i cc u r v er a n d o m l ya n dc h o i c i n gb a s e p o i n t ；i nt h i s p a p e r , i td e s i g n sa t r a c e a b l et h r e s h o l ds i g n a t u r es c h e m eb a s e do ne l l i p t i c c u r v ec r y p t o g r a p h y ；at r a c e a b l et h r e s h o l d s i g n a t u r eb a s e do ne c c s y s t e mh a si m p l e m e n t e d t h i ss y s t e mc a nb ea p p l i e dt os i n g eo nf i l ew i t h o f f - l i n e k e yw o r d se l l i p t i cc u r v ec r y p t o g r a p h y ( e c c ) ，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 ，t r a c e a b l e 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了论文中特另t l d n 以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共 同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：j l 摊 日期：牛年月卫日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校有 权保留学位论文并根据国家或湖南省有关部门规定送交学位论文，允 许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名魁雄导师签名越嗍等年工月主日 硕士学位论文 第一章绪论 1 1 研究背景 第一章绪论 近几年，随着网络技术的飞速发展，网络得到广泛的普及和使用，其应用涉 及到政府、军事、文教、商业、金触等诸多领域，涌现了大量的网络应用系统， 如电子政务、电子商务、网络银行、网络科研、远程教育、远程医疗等系统。每 天都有大量的信息在网络上进行交换，如何保证这些信息的安全，是目前网络信 息安全领域需要解决的问题。 网络信息安全的研究内容主要为：保密性、认证性、完整性和不可否认性等 【1 1 。保密性是指只有授权的一方才能获取信息，即只有拥有正确的密钥才能解读 已经加密了的信息，没有密钥不能解读信息。完整性是指信息在发送端发送之后 不能被修改。认证性是指信息来源是可以得到确认的，这意味着接收方在收到某 个显示来源于发送方的信息时，可以采用技术手段确认其是否确实来源于该发送 方。不可否认性是指发送方在发送了某个信息后，不能在事后否认其曾经发送过 该信息。 数字签名是网络信息安全的重要手段之一。数字签名可以实现数据的完整 性、来源的真实性和不可否认性i 舶。因此，在进行身份认证、密钥分发、信息认 证等方面，数字签名都有重要的作用。在日常生活中，使用手写签名和印章很多， 而要在网络上实现电子文档的签名和印章，则需要数字签名。数字签名同手写签 名一样具有法律效力。 传统的数字签名中，对信息的签名只需要一个签名者，任何验证者使用签名 公钥就可验证签名的有效性。但是，一旦签名私钥泄露或被攻破，将导致签名无 效。使用门限签名一方面将私钥分散保管可以提高安全性；另一方面可以分散权 利，以防止权利过于集中。然而，在门限签名中，由于每次代表群体签名的签名 者都不尽相同，因此可能会出现签名者在签名后否认他曾参与的签名以逃避责 任。因此，如何能在事后确定某次签名的参与者身份就非常重要。另外，椭圆曲 线离散对数问题的困难性可以保证门限签名的安全。研究表明，基于椭圆曲线的 密码系统，能以更短的密钥实现更高的安全程度1 3 l 。因此，研究一种基于椭圆曲 线密码系统的高效率、可追踪的( t ，n ) 门限数字签名方案具有重要的现实和理 论意义。 硕士学位论文 第一章绪论 1 2 研究现状 1 2 1 椭圆曲线密码体系研究现状 r s a 密码体制是现在最著名的公钥密码之一，它的安全性建立在整数因子 分解的困难性之上。椭圆曲线密码体制( e c c ) 于1 9 8 5 年由n k o b l i t z 和v m i l l e r 提出，椭圆曲线密码可以提供同r s a 密码体制同样的功能，它的安全性建立在 椭圆曲线离散对数问题e c d l p 的困难性上。现在求解e c d l p 最好的算法具有 全指数时间复杂度，与此不同，整数因子分解问题却是亚指数时间算法。这意味 着对于达到同样期望的安全程度，椭圆曲线密码可以使用较r s a 密码更短的密 钥【3 1 。由于密钥短，工程实现的加、解密速度更快，并且可节省能源、带宽和存 储空间等。美国、加拿大、法国等很多密码学研究小组【4 】及一些公司实现了椭圆 曲线密码体制【5 1 ，我国密码学者在这方面也做了大量的研究工作【6 】，我国一些企 业和公司已经成功地研制了具有自主知识产权的椭圆曲线产品和专利【7 j 。许多标 准化组织已经或j 下在制定关于椭圆曲线的标准，同时也有许多的厂商已经或正在 开发基于椭圆曲线的产品。在椭圆曲线密码体制的标准化方面，i e e e 、a n s i 、 i s o 、i e t f 、a t m 等都作了大量的工作，它们所开发的椭圆曲线标准的文档有： i e e ep 1 3 6 3 i s l 、p 1 3 6 3 a 、a n s ix 9 6 2 t 9 1 、a n s ix 9 6 3 1 0 1 、i s o i e c l 4 8 8 8 等。 目前，椭圆曲线的研究热点主要有以下几个方面： ( 1 ) 快速产生椭圆曲线密码体制参数，选取理想的椭圆曲线。 ( 2 ) 椭圆曲线求阶算法的实现与改进。 ( 3 ) 选择适当的方法以提高标量乘的运算速度。 1 2 2 ( t ，n ) 门限数字签名研究现状 数字签名的概念由w d i f f i e 和m h e l l m a n 于1 9 7 6 年提出。目的是使签 名者对电子文档进行签名，以保证数据来源的可靠性。数字签名在信息安全，包 括身份认证、数据完整性、不可否认性等方面有重要应用，特别是在大型网络安 全通信中的密钥分配、认证以及电子商务系统中具有重要的作用。数字签名的实 现基础是加密技术，其使用公钥加密算法与散列函数。常用的数字签名算法有 r s a 、d s s 、e 1 g a m a l 等。 ( t ，n ) 门限签名是对普通数字签名的推广。( t ，n ) 门限签名系统是指由n 个签名者组成一个签名群体，该群体有一个公私密钥对，该群体内任意人数大 于等于t 个合法、诚实签名者的组合都可代表群体用私有密钥进行签名，群体外 任何人可利用该群体的公钥进行签名验证】。将团队的签名密钥分散给多人管 理具有很多好处： ( 1 ) 提高安全性。在同是攻击签名密钥的情况下，单人保管签名密钥时， 2 硕士学位论文第一章绪论 攻击者只要试图获取一个签名密钥，而采用门限签名时，攻击者则必须得到至少 t 个“部分密钥”。 ( 2 ) 即使某个或某些部分密钥丢失，整个密钥也不会丢失。 ( 3 ) 实现权力分配，避免滥用职权。 自1 9 9 1 年d e s m e d t f r a n k e l 首次提出门限签名方案以来【l 引，门限签名引起了 密码学界广泛关注和研究，并且提出了各种类型门限签名方案。按照不同的分类 标准，可以将这些签名算法进行归类。根据所使用的核心算法不同，可以分为基 于r s a l l 3 1 和e 1 g a m a l t l 4 1 的；根据是否使用椭圆曲线，分为基于椭圆曲线的【”】和 不基于椭圆曲线的1 6 】；根据是否有可信任中心，可以分为有可信中心【1 7 】和无可 信中心的f 1 8 】。经过分析可知，目前国内外对( t ，n ) 门限数字签名方案进行了一系列 的研究，分别从多个角度提出多种门限签名方案。但当前( t ，n ) 门限数字签名 方案存在以下一些不足；( t ，n ) 门限签名方案多数以r s a 、 e i g a m a 等为中心进 行构造，基于椭圆曲线体制的偏少；可追踪的门限签名很少，基于椭圆曲线可追 踪的门限签名就更少。 1 3 研究的主要内容与论文组织结构 1 3 1 课题研究目的和意义 本课题的研究目的在于，通过对数字签名和椭圆曲线密码理论的研究和分 析，在调研已经存在的门限签名方案的基础上，提出新的( t ，n ) 门限数字签名 方案，即基于椭圆曲线可追踪的门限数字签名方案，并在此基础上实现门限数字 签名系统。在理论上，构造以椭圆曲线为基础和核心的门限数字签名方案，以实 现用更短的密钥达到和r s a 同等安全强度的门限签名系统。同时，实现在事后 发生争执或需要追究责任时，可以通过仲裁机制追查出参与签名成员的身份。在 工程实现方面，将所构造的签名方案进行程序实现，以实现数字签名方案在网络 中的应用。 门限签名相比较普通签名的优势在于，一方面将私钥分散保管可以提高安全 性；另一方面可以分散权利，以防止权利过于集中。在同等安全程度下，基于椭 圆曲线的门限签名系统所使用的密钥比r s a 的更短。有报告指出，在椭圆曲线 上1 5 0 比特的密钥，对它进行攻击的工作量以每秒百万次的计算机要进行3 8 1 0 1 0 年。而一般r s a 密码系统，5 1 2 比特的密钥，对它的攻击只要3 x1 0 4 年【1 9 】。 由于密钥短，所以工程实现的加解密速度较快，更易于实现和方便使用。同时对 于门限签名，在事后发生争执或需要追究责任时，能够追踪某次签名有哪些成员 参与是非常重要的。另外，一个好的门限数字签名方案可以投入到各种应用中， 3 硕士学位论文 第一章绪论 如竞标、文件审批等，在实际应用中，一个好的门限签名系统可以保证信息的安 全，门限签名系统在电子商务、电子政务等领域都有广泛的应用空间和应用前景。 因此，基于椭圆曲线可追踪门限签名方案的研究具有重要的理论和工程意义。 1 3 2 研究内容及论文组织结构 本文结合数字签名理论和椭圆曲线密码体制理论，针对当前门限数字签名方 案存在的问题，改进了一种安全的门限群签名方案；在椭圆曲线密码体制的研究 基础上，在素数域上实现了安全椭圆曲线的随机生成算法和基点的选取，采用分 阶段预计算方式有效的提高了椭圆曲线生成的速度；设计并实现了一种基于椭圆 曲线可追踪门限签名方案；在工程上实现了一个电子文件审批系统，该系统实现 了基于椭圆曲线可追踪的门限数字签名，并且可对电子文件进行离线签名。将椭 圆曲线应用到门限数字签名中，有效地提高了门限数字签名的安全性，同时有效 地提高了门限签名系统的运算速度。 全文共分为五章，各章节的主要内容如下： 第一章介绍了课题研究背景并简单介绍了门限数字签名和椭圆曲线密码系 统的国内外研究现状。 第二章介绍了椭圆曲线密码体系的理论知识，包括椭圆曲线的定义、椭圆曲 线运算法则、椭圆曲线密码系统的安全性分析，椭圆曲线数字签名等内容，重点 介绍了有限域上安全椭圆曲线的生成和求阶算法。 第三章介绍了门限群签名的概念，对一种安全的门限群签名方案进行了分析 与改进。在椭圆曲线和门限数字签名的研究基础上，提出了一种基于椭圆曲线的 可追踪门限数字签名方案。该方案以椭圆曲线为基础，采用二次签名等方式，可 有效的避免前面门限群签名方案所暴露的缺陷和不足。 第四章介主要介绍了一个电子文件审批系统，该系统实现了第三章的基于椭 圆曲线可追踪门限数字签名方案，包括有限域上安全椭圆曲线的产生、基点的选 取、签名生成、签名发布、签名接收验证和身份追查等内容。 第五章结论部分对全文进行了总结，并提出今后的研究工作。 4 硕士学位论文第二章椭圆曲线密码体制 第二章椭圆曲线密码体制 椭圆曲线( e l l i p t i cc u r v e ) 作为代数几何问题，数学家对其已经研究了1 0 0 多 年，积累了大量的文献资料。但是，椭圆曲线在密码学中的应用直到上个世纪 8 0 年代末才开始。1 9 8 5 年，n k o b l i t z 和v m i l l e r 分别独立将椭圆曲线引入了密 码学领域【2 0 】【2 1j 。从此，椭圆曲线密码( e l l i p t i cc u r v ec r y p t o g r a p h y ，e c c ) 成为 了密码学领域一个重要的分支，研究者发表了大量有关椭圆曲线密码安全性和有 效实现的研究成果。 椭圆曲线密码体制的根据是有限域上椭圆曲线点群的离散对数问题 ( e c d l p ) 。椭圆曲线密码可以提供同r s a 密码体制同样的功能，但是它的安 全性是建立在e c d l p 的困难性之上。现在求解e c d l p 最好的算法具有全指数 时间复杂度，而整数因子分解问题却有亚指数时间算法。这就意味，对于达到同 样期望的安全程度，椭圆曲线密码可以使用较r s a 更短的密钥【3 】。 2 1 有限域f q 上的椭圆曲线定义及运算 2 1 1 有限域简介 域是对常见的数系( 如有理数，实数) 及其基本特性的抽象。域由一个集合 f 和两种运算共同组成。这两种运算是加法和乘法，分别用+ 和表示，并且满 足下列算术特性【3 j ： ( 1 ) ( f ，+ ) 对于加法运算构成加法交换群，单位元用0 表示。 ( 2 ) ( f ，) 对于乘法运算构成乘法交换群，单位元用1 表示。 ( 3 ) 满足分配律，即对于所有a , b ，c f ，都有( a + b ) c = a c + b c 。 对于域中的减法和除法，分别用加法和乘法来定义。具体定义如下：对于 a , b ef ，a - b = a + ( 一b ) ，其中- b 是b 的负元素，它是使b + ( - b ) = o 的唯一域元素。 类似的，对于a , bf ，b 0 ，a b = a b 一，其中b 叫是b 的逆元素，它是使得b b 叫= 1 的唯一的一个域元素。 对于一个元素有限的域称之为有限域，其中元素的个数就叫有限域的阶。存 在一个q 阶有限域f ，当且仅当q 是一个素数的幂，即q = p m ，其中p 是一个素 数，m 是一个j 下整数，把该域记为f 。，p 称为域的特征。m = l 时，该域称为素数 域，记为f p ，p 是大素数，域中的元素为 o ，l ，2 ，p 1 ) 。m 2 时，若p = 2 ， 则称为二进制域，记为只。：若p 2 否则称为特征为p 的扩域，简称扩域。 5 硕士学位论文第二章椭圆曲线密码体制 2 1 2 椭圆曲线的定义 定义2 1 域f q 上的椭圆曲线e 由下述方程定义口2 】： e ：y 2 + a l x y + a 3 y = x 3 + a 2 x 2 + a 4 x + a e公式( 2 - 1 ) 其中a l ，a 2 ，a 3 ，a 4 ，2 l 6 f 。，且0 ，是曲线e 的判别式，具体定义为： a = - d 2 2 d 。- 8 d 4 3 - 2 7 d 6 2 + 9 d 2 d 。d 6 d 2 = a 1 2 + 4 a 2 d 4 = 2 a 4 + a l a 3 d 6 = a 3 2 + 4 a 6 d 8 = a t 2 a 6 + 4 a 2 a 6 a ja 3 a 4 + a 2 a 3 z - a 4 z 上述2 1 式称为w e i e r s t r a s s 方程。 在曲线方程中，所有的系数都是域f 。中的元素。有时也将椭圆曲线直接记 为e ( f 。) 以强调椭圆曲线e 是定义在域f 。上的。条件o 用来确保椭圆曲线是 “光滑 的，这样可以保证曲线上所有的点没有两个或两个以上的不同切线。每 条椭圆曲线上都有一个唯一的无穷远点，记为0 ，它满足投影形式的 w e i e r s t r a s s 方程【3 】o 定义2 2 ( 椭圆曲线的阶) 设e 是定义在域f q 上的椭圆曲线。椭圆曲线 e ( f q ) 上点的个数记为 e ( f q ) ，并称其为域f q 上椭圆曲线的阶。 根据w e i e r s t r a s s 方程可知，对于每个x f q 最多有两个解，所以可以得知拌e ( f q ) 1 ，2 q + 1 。h a s s e 定理给出了拌e ( f q ) 更紧的界【3 1 。 定理2 1 ( h a s s e 定理) 2 3 1 设e 是定义在域f q 上椭圆曲线，贝i j # e ( f 。) = q + l - t ， 其中i ，喀2 9 。t 称为域f 。上椭圆曲线e 的迹。 对于2 1 式的w e i e r s t r a s s 方程，其系数个数较多，形式复杂，计算繁琐。因 此，可以使用变量的相容性变换对w e i e r s t r a s s 方程进行简化，以减少系数个数。 考虑到f 。的特征情况，将w e i e r s t r a s s 方程按照f q 的特征等于2 、等于3 和特征 既不等于2 也不等于3 三种情况进行考虑p 】。 l 、f 。的特征即不等于2 也不等于3 ，根据变量的相容性变换 y h 学，守一巫垫)j oz 1 0z 斗 把曲线e ( f 。) 变为 y 2 = x 3 + a x + b 公式( 2 - 2 ) 其中a ，b f 。曲线的判别式a ：- 1 6 ( 4 a 3 + 2 7 b 2 ) 。对于素域f ，中的曲线定义 ( 其中p 是大素数) ，今后都采用这个简化的w e i e r s t r a s s 方程来定义。 2 、f 。的特征等于2 ，则需要考虑两种情况。 若a 。0 ，则变量的相容性变换 6 硕：t 学位论文第二章椭圆曲线密码体制 线。 ( 训) 一( 口? x + 鱼，口i ；少+ 掣) 口l口i 把曲线e ( f 。) 变为 ) ，2 + x y = x 3 + a x 2 + b 公式( 2 - 3 ) 其中a ，b f 。曲线的判别式= b 。同时把这种曲线叫非超奇异的椭圆曲线。 若a l = 0 ，则变量的相容性变换 ( x ，y ) 一( x + a 2 ，y ) 把曲线e ( f 。) 变为 y 2 + c y = x 3 + a x + b 公式( 2 - 4 ) 其中a ，b ，c f q 。曲线的判别式= c 4 。同时把这种曲线叫超奇异的椭圆曲 3 、f q 的特征等于3 ，同样需要考虑超奇异和非超奇异两种情况。 若口? 一口：，则变量的相容性变换 ( 训) 专( x + 华，y + 叩+ 口l 华+ 口3 ) 以? + a ，口f + a ， 把曲线e ( f 。) 变为 v 2 = x 3 + a ) 【2 + b 公式( 2 5 ) 其中a ，b f q 。曲线的判别式= 一a 3 b 。这种曲线是非超奇异的。 若a ? = 一a ，则变量的相容性变换 ( x ，y ) 专( x ，y + 口1 x + a 3 ) 把曲线e ( f 。) 变为 y 2 - - - - x 3 嗽+ b 公式( 2 - 6 ) 其中a ，b f 。曲线的判别式= 一a 3 。这种曲线是超奇异的。 2 1 3 有限域f 。上椭圆曲线的运算 l 、椭圆曲线的运算法则 设e 是定义在域f 。上的椭圆曲线，曲线e ( f 。) 上任意两点相加可以得到第三 个点。曲线e ( f 。) 上所有的点和这种加法运算构成了一个加法交换群。 对任意p ( x i ，y 1 ) ，q ( x 2 ，y 2 ) e ( f q ) ，o 是曲线e ( f q ) 上的无穷远点。 ( 1 ) 单位元。o + p = p 且p + o = p 。 ( 2 ) 负元素。p 是使得p + ( p ) = o 椭圆曲线上唯一的点。 ( 3 ) 点加。p 、q 两点相加得到第三点r ，即p + q = r 。p + q = r 的几何含义是， 连接点p 和q 画条直线l ，直线l 与曲线相交与第三点，则该交点关于x 轴的对 称点就是点r 。几何示意图见图2 1 。 7 硕士学位论文 第二章椭圆曲线密码体制 p ( y ， q ( x 2 ，y 2 ) 份 矗，u ； x i 筹r ( x 3 。y 3 ) j 图2 - 1 相加p + q = r ( 4 ) 倍点。p 的倍点2 p = r ，其几何意义是，过p 点做椭圆曲线的切线，该 y 二j，1。 p ( x l ，y 1 ) ：， ，?；j7八 7 u x r ( x 3 ，y 3 ) l 图2 - 2 倍点2 p - - r 切线与椭圆曲线交于第二点，这个交点关于x 轴的对称点就是r 点。几何示意 图见图2 2 。 ( 5 ) 点乘。点乘k p = 是倍点和点加的推广。k p = 可以理解成 k p = ( k 1 ) p + p = 【( k 2 ) p + p 】+ p 。可以采用如下的算法进行点乘计算。 先将k 表示成二进制形式( k t - 1 ，k t - 2 k 2 ，k l ，k o ) 2 。 算法2 1 点剩3 】 输入：k _ ( k t i ，k t 2 2 “k 2 ，k l ，k o ) 2 ，p e ( f q ) 。 输出：k p 1 q = o 2 对于i 从。到t 一1 ，重复执行 2 1 若k ；= 1 ，则0 = o + p 。 8 硕士学位论文第二章椭圆曲线密码体制 3 返回q 。 上面把有限域中椭圆曲线的运算法则做了一个概括性的介绍，对于不同的 域，椭圆曲线的计算是有所不同的。例如，同样都是求p = ( x ，y ) 的负元素p ， 在素数域中- p = ( x ，一y ) ，二进制域的非超奇异曲线p = ( x ，x + y ) ，二进制域的 超奇异曲线p = ( x ，y + c ) 。 下面具体讨论一下定义在素数域上的曲线和二进制域上非超奇异曲线的运 算。 2 、素数域f p 上椭圆曲线的运算 对于素数域f p 上的曲线e ( f p ) ：) ，2 = x 3 + a x + b ，其运算的具体规则为： ( i ) 单位元。对于所有p e e ( f ，) ，p + o = o + p = p 。 ( 2 ) 负元素。若p = ( x ，y ) e ( f ，) ，则( x ，y ) + ( x ，一y ) = o 。记点( x ， 一y ) 为一p ，一p 也是e ( f 。) 上的一点，并称其为p 的负。 ( 3 ) 点加。设p = ( x t ，y 1 ) e ( f ，) ，q = ( x ：，y 2 )e ( f 。) ，p q ，则p + q = ( x 。，y 3 ) ，其中 轳( 嚣- - x 1 卜2 吒枷，= ( 嚣卜m ( 4 ) 倍点。设p = ( x 。，y 。) e ( f p ) ，p o ，则2 p = ( x 。，y 3 ) 。其中 铲( 等卜挑= ( 等卜一m ( 5 ) 点乘。k f = r 采用算法2 1 进行计算，其中涉及到的点加和倍点分别采 用上面第3 和4 条规则。 3 、二进制域f 。上非超奇异曲线的运算 对于二进制域只，上的曲线e ( f 2 。) ：y 2 + x 吊3 + a ) ( 2 + b ，其运算的具体规则为： ( 1 ) 单位元。对于所有p e ( c ) ，p + 0 = 0 + p = p 。 ( 2 ) 负元素。若p = ( x ，y ) e ( 只。) ，则( x ，y ) + ( x ，x + y ) = o 。记点 ( x ，x 十y ) 为一p ，一p 也是e ( 只。) 上的一点，并称其为p 的负。 ( 3 ) 点加。设p ：( x 。，y 。) e ( c 。) ，q = ( x 。，y 。) e ( c 。) ，p c = q ， 贝0p + q = ( x 。，y 3 ) ，其中 x 3 = 入2 + 入+ x l + x 2 + a 和y 3 = 入( x l + x 3 ) + x 3 + y i 而入= ( y 。+ y 2 ) ( x 。+ x 2 ) 。 ( 4 ) 倍点。设p = ( x - ，y - ) e ( 只。) ，p 0 ，则2 p = ( x 。，y 3 ) 。其中 x 3 2x , 2 + b x 1 2 和y 3 = x 1 2 + 入x 3 + x 3 而入= x l + y 。x 。 硕士学位论文 第二章椭圆曲线密码体制 ( 5 ) 点乘。k p = r 同样采用算法2 1 进行计算，其中涉及到的点加和倍点分 别采用上面第3 和4 条规则。 2 2 有限域上安全椭圆曲线 椭圆曲线离散对数问题的困难性是所有椭圆曲线密码( e c c ) 安全性的基础。 如果椭圆曲线曲线离散对数容易或者比较容易计算，则可以比较容易地从一个用 户的公钥推导出他的私钥，这样e c c 就不再安全了。 所谓有限域上安全椭圆曲线的生成，就是指在有限域上选择合理的曲线参 数，使得曲线可以抵抗求解椭圆曲线离散对数的攻击。 2 2 1 椭圆曲线离散对数问题及其攻击 定义2 3 ( 椭圆曲线离散对数问题e c d l p ) 给定定义于有限域f q 上的椭 圆曲线e ，基点p e ( f a ) ，阶为n 。点q ，寻找一个整数d 0 ，n 一1 使得o = d p 。正数d 称为q 基于p 的离散对数，表示为d = l o g ，q 。 在定义2 3 中， = o ，p ，2 p ，3 p ，( n 一1 ) p ) 是由p 生成的椭圆曲线 循环子群。 根据2 1 3 中的分析可以知道，对于已经知道p 和d ，要求出o = d p ，则只需 要进行点乘计算即可。换句话说，知道p 和d ，计算q 是比较容易的。但是反过 来，知道p 和q ，要求出d ，即求解d = l o g ，q 是比较困难的。由p 和q 求解d 就 是椭圆曲线离散对数问题( e c d l p ) 。 对椭圆曲线密码系统的攻击其实就归结为对椭圆曲线离散对数的攻击。下面 简单介绍一些目前已经知道对e c d l p 的攻击方法【2 4 - 2 5 1 。 ( 1 ) 穷举法。穷举法是求解e c d l p 问题的最简单方法。通过连续计算点p ， 2 p ，3 p 直到找到q 。该方法最坏情况下要计算n 步，平均情况为n 2 步。因 此可以通过选择足够大的参数1 3 ，使得穷举攻击的计算实际上不可实现。 ( 2 ) 大步小步法( b s g s ) 。根据已经知道的p 、q 等条件，求解d 使得o = d p 。 先令m = i 刀l ，则对于任意的1 f 。，l - a m + b ，o a ，b m ，其中a 和b 是唯一 的。因此，对于o = d p 中的d ，必定存在个a 和b 满足d = a m + b ，则q a m p = b p 。 m = l 行l 是已知的，所以计算m p 很容易，而a ，b 0 ，m ，采用穷举法求a 和b 。 先预计算a m p 并保存，a = 0 ，1 ，m 。然后穷举计算q 曲p ，并且每次都和a m p 比 较，直到相等为止。这样找到a 和b ，即找到d 。该方法是把穷举方法中的部分 时间转为存储空间。需要大约存储门点，最坏需要计算玎步。 ( 3 ) p o h l i g - h e l l m a n 方法。该方法其实就是将计算d = l o g ，q 约减为计算 的素数阶子群的离散对数问题。设p 点的阶n 因子分解为玎= p ；。p ：e z p 。对每 1 0 硕士学位论文 第二章椭圆曲线密码体制 个l i k ，计算d ，= d m o d 力，再对d 求解同余方程组d = d ，m o d p , 2 ，从而求 解出d 。 ( 4 ) p o l l a r d sr h o 方法。该方法的主要思想就是寻找模n 的不同( c ，d ) 和( c ”，d ”) ，使得c ，p + d q = c p + d ”q 。于是，( c - e ”) p ：( d ”一d ) q = ( d ”一d ) d p ， 且有( c c ) - - - - ( d ，- d ) d ( m o dn ) 。因此，d 可以通过计算d ( c 一c ) ( d ”- d 矿m o d 1 3 _ 求出。 除了以上提到的四种对e c d l p 攻击的方法以外，还有其他一些方法，如并 行p o ll a r d sr h o 方法【2 6 】、p o ll a r d 的袋鼠算法【2 7 】、索引计算攻击【2 8 】等方法，还 有一些是针对特定曲线的攻击方法【2 9 1 。目前，对于e c d l p ，最好的通用攻击方法 是将p o h l i g - h e l i m a n 和p o l l a r d sr h o 相结合，该方法的运行时间为完全指数 时间o p ，其中p 是点p 的阶n 的最大素因子。因此，为了有效抵抗这种攻击， 椭圆曲线参数的选择应该要求n 含有大素因子p ，即p 应该足够大，以使得p 的 计算实际不可实现。 2 2 2 椭圆曲线参数组的生成 在有限域上生成椭圆曲线，其实就是生成椭圆曲线的参数组。参数组中参数 的选择要能使e c d l p 抵抗所有已知的攻击。在实际选择参数的时候，还会出于 安全或实现等原因而有其他的约束。例如，曲线的阶# e ( f q ) 必须能被足够大的 素数n 整除，最好使# e ( f q ) 为素数或者接近素数。一般所选择的参数有以下几 个： ( 1 ) 域的阶q 。 ( 2 ) 有限域f 口，这里域可以是素数域，也可以是二进制域或者扩域，具 体的要看使用的环境和要求。 ( 3 ) 种子s 。如果曲线的生成采用随机法，则需要有一个种子。 ( 4 ) 系数a ，b f 。，是定义曲线方程时所需要的系数。如在素域或者二 进制非超奇异曲线的方程中都需要a 和b 。 ( 5 ) 基点p ( x ，y ) e ( f q ) 。 ( 6 ) 基点p 的阶1 1 。 ( 7 ) 余因子h = # e ( f q ) n 。 生成安全的椭圆曲线，也就是生成安全的椭圆曲线参数，一般有两种途径： 一种是通过选择一个满足安全性的阶n ，然后构造阶为n 的椭圆曲线，代表方 法是复乘法( c m 法) ；另外一种是通过随机方式生成椭圆曲线，即随机法。为 了防止针对特殊类型椭圆曲线的攻击，应该随机选择满足群e ( f q ) 能被大素数整除 的椭圆曲线。因为随机曲线具有较好的随机性，满足已知同构攻击的概率非常小 而可以忽略，因此已知攻击可以避免。同时，采用随机方式生成椭圆曲线可以避 硕士学位论文 第二章椭圆曲线密码体制 免故意构造有潜在弱点或陷门的曲线而窃取用户的私钥。以下主要讨论采用随机 方式生成素数域上椭圆曲线的方法。 参数组生成的一般步骤如算法2 2 所示。 算法2 2 参数组生成一般算法【3 0 】 输入：域的阶p ，域f p ，安全级别l 满足1 6 0 l l j b p j 和2 l 4 p 。 输出：参数组( p ，f p ，s ，a ，b ，p ，1 1 ，h ) 1 采用算法2 3 随机生成a ，b f p 。令s 是种子。 2 计算椭圆曲线的阶n ：# e ( f 。) 。 3 校验阶n 是否能被n 2 。的大素数n 整除。如果不能则返回1 。 4 校验n 对于所有1 k 2 0 是否能被p h _ 1 整除。如果能整除，则返回到1 。 5 校验是否n = q 。若n = q ，则返回l 。 6 计算h = n n 。 7 随机选择阶为n 的点p e ( f 。) ，则p 为基点。 8 返回( p ，f d ，s ，a ，b ，p ，n ，h ) 。 算法2 3 素数域f p 上随机生成椭圆曲线系数【3 0 】 输入：素数p ，k 比特杂凑函数。 输出：种子s ，a ，b f p 定义的曲线e ( f p ) ：y 2 = x 3 + a x + b 1 令t = l 却l ，s = l ( t 1 ) ，j ，v = t s l 。 2 选择任意二进制字符串s ，长度g k 。 3 计算h = h ( s ) ，令r 。为h 最右边v 比特的二进制串。 4 将r 0 位最左边的一位置0 。 5 z 是s 所对应的十进制数。 6 对于i 从1 到s ，重复执行 6 1 令s ；为整数( z + i ) m o d2 8 的g 位二进制表示。 6 2 计算r i = l l ( s ；) 。 7 令r = r 。i ；i | i | r 。 8 r 为r 的十进制表示的整数。若r = o 或者4 r + 2 7 - - = 0 ( m o dp ) ，返回到步 骤2 。 9 选择任意不全为0 的a ，b f p ，使得r b 2 兰a 3 ( m o dp ) 。 1 0 返回s ，a ，b 。 2 2 3 椭圆曲线求阶s e a 算法 椭圆曲线阶n 的计算是椭圆曲线参数组生成的关键步骤，尤其是通过随机 方式生成的椭圆曲线。椭圆曲线求阶的快慢直接影响曲线生成速度的快慢，能否 成功计算椭圆曲线的阶决定着能否顺利生成椭圆曲线。 1 2 硕士学位论文第二章椭圆曲线密码体制 椭圆曲线求阶最简单的方法就是点记数，即逐个将有限域中的元素代入曲线 方程，来计算满足方程点的个数。这种方法，在密码学中要求有限域非常大的情 况下是不现实的。目前，有限域上有效求阶算法可以归为3 类【3 1 】： ( 1 ) s e a 算法。1 9 8 5 年，s c h o o f 首先提出了一个时间复杂度为o ( 1 0 9 8 q ) 的多项式时间的求阶算法1 3 2 1 ，随后e l k i e s 和a t k i n 改进了该算法多项式时间的椭 圆曲线求阶算法【3 3 1 ，大大提高了实现效率，其时间复杂度为o ( 1 0 9 6 q ) ，如今被 人们称为s e a ( s c h o o f - e l k i e s a t k i n ) 算法。 ( 2 ) s a t o h 算法。2 0 0 0 年，s a t o h 对于特征大于等于5 的有限域上的椭圆曲 线的求阶提出了一个新算法，即s