（计算机应用技术专业论文）椭圆曲线密码体制中标量乘算法的研究.pdf

摘要 摘要 椭圆曲线密码系统是迄今为止每比特具有最高安全强度的密码系统。与其他 公钥密码系统相比，椭圆曲线密码系统除了安全性高外，还具有计算负载小、密 钥尺寸短、占用带宽少等优点，现在密码学界普遍认为它将取代r s a ，成为下一 代通用的公钥密码系统，深入研究基于椭圆曲线离散对数问题的公钥密码具有很 大的现实意义。 本文主要研究椭圆曲线公钥密码的相关技术，介绍椭圆曲线密码体制的基本 概念和理论，并在这一基础上对椭圆盐线密码体制中标量乘k p 的计算进行了较 深入的研究，主要工作如下： ( 1 ) 对椭圆曲线密码体制和椭圆曲线标量乘的基础理论知识进行了总结。 ( 2 ) 从标量k 的有效表示入手，研究椭圆曲线标量乘舻算法。利用补码表示 的原理，结合标量k 的一种新的表示方式一f 、码表示，描述了由标量k 的二进 制表示方式向补码表示方式的快速转换方法，提出了椭圆曲线标量乘的补码方法 以及窗口补码方法，并从整数k 的序列长度、序列的汉明权值、零位的平均长度、 转换方向和窗口数等方面与其他方法进行比较，分析椭圆曲线标量乘的组合算法 的性能。 ( 3 ) 研究了在j a c o b i a n 投影坐标下的椭圆曲线标量乘运算。采用组合运算 的思想，结合椭圆曲线的点加运算的等z 坐标方法提出了椭圆曲线倍加运算 ( 2 p + q ) 的组合算法和椭圆曲线标量乘运算护的组合算法，并通过与传统方法 的比较分析了组合方法的性能。 关键词椭圆曲线密码体制；标量乘；补码算法；组合算法 a b s t r a c t a b s t r a c t 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 ) p r o v i d e st h eh i g h e s ts e c u r i t y s t r e n g t h p e r - k e y - b i t o f a n yc r y p t o g r a p h yk n o w c o m p a r e d 、) l r i m o t h e r p u b l i c - k e y c r y p t o g r a p h i e s ，e c cn o to n l yh a st h eh i g h e rs e c u r i t yb u ta l s oh a sl e s sc o m p u t a t i o n o v e r h e a d s ，s h o r t e rk e ys i z ea n dn a r r o w e rb a n d w i d t h t h e r e f o r e ，i ti sb e l i e v e dt h a t e c cw i l lb e c o m et h en e x tg e n e r a t i o np o p u l a rp u b l i c - k e yc r y p t o g r a p h y , a n dm a k i n g a ni n t e n s i v es t u d ya b o u tp u b l i ck e yc r y p t o g r a p h yw h i c hb a s e do i le c l i p s ec u r v e d i s c r e t el o g a r i t h mp r o b l e m ( e c d l p ) h a sg r e a tp r a c t i c a ls i g n i f i c a n c e t h i st h e s i sm a i n l ys t u d yt h et e c h n i q u e sa b o u tp u b l i ck e yc r y p t o g r a p h yw h i c h b a s eo ne c l i p s ec u r v e ，i n t r o d u c et h eb a s i cc o n c e p ta n dt h e o r yo ft h ee l l i p t i cc u r v e c r y p t o s y s t e m ，a n dm a k ead e e pr e s e a r c ho nt h ec o m p u t a t i o no fs c a l a rm u l t i p l i c a t i o ni n e l l i p t i cc u r v ec r y p t o g r a p h y t h em a i nw o r ki nt h i st h e s i si sa sf o l l o w s m a k eas u m m a r yo fb a s i ct h e o r i e sa b o u tt h ee l l i p t i cc u r v ec r y p t o g r a p h ya n d s c a l a rm u l t i p l i c a t i o no ne l l i p t i cc u r v e t h i st h e s i sm a k e sad e e pr e s e a r c ha b o u te l l i p t i ec u r v es c a l a rm u l t i p l i c a t i o ni n t e r m so fe f f i c i e n tp r e s e n t a t i o no ft h es c a l a rk i nt h i st h e s i s ，b a s i n go nt h ep r i n c i p l eo f c o m p l e m e n tr e p r e s e n t a t i o n ，an e w t r a n s i t i o nm e t h o df r o mb i n a r yc o d er e p r e s e n t a t i o n o fs c a l a rkt oc o m p l e m e n tr e p r e s e n t a t i o ni sp r o p o s e d i na d d i t i o n ，t h i st h e s i sa l s o p r o p o s e dc o m p l e m e n ta l g o r i t h ma n dc o m p l e m e n tw i n d o wa l g o r i t h m t oc o m p u t e s c a l a rm u l t i p l i c a t i o no ne l l i p t i cc u r v e m o r e o v e r , i no r d e rt oa n a l y s i st h ep e r f o r m a n c e o ft h i sa l g o r i t h m ，t h i st h e s i sm a k e sac o m p a r i s o nb e t w e e nt h en e wa l g o r i t h m 、) l ，i t l l o t h e ra l g o r i t h m si nt e r m so fd i g i t a ll e n g t h ，w e i g h t ，l e n g t ho fz e r o ，t r a n s f o r md i r e c t i o n ， n u m b e ro fw i n d o w s c a l a rm u l t i p l i c a t i o na l s oi ss t u d i e di nt h i st h e s i su n d e rj a c o b i a np r o j e c t e d c o o r d i n a t e i n t e g r a t i n gt h et h o u g h to fc o m p o s i t ea l g o r i t h ma n di d e n t i c a lz - c o o r d i n a t e a d d i t i o n ，t h i st h e s i sp r o p o s e dc o m p o s i t ea l g o r i t h mt oc o m p u t ed o u b l i n g - a d d i t i o n o p e r a t i o n ( 2 p + q ) a n ds c a l a rm u l t i p l i c a t i o nk p ，a n da n a l y z e di t sp e r f o r m a n c eb y m a k i n gac o m p a r i s o nw i mt r a d i t i o nm e t h o d k e y w 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 ；s c a l a rm u l t i p l i c a t i o n ；c o m p l e m e n ta l g o r i t h m ； c o m p o s i t ea l g o r i t h m i i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名： 嗍! 乒4 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：导师签名：日期： 第l 章绪论 第1 章绪论 2 1 世纪是信息的社会，信息在国民经济建设、社会发展、国防和科学研究 等领域的左右日益重要。随着由计算机技术与通信技术相结合而诞生的计算机 互联网络的迅速发展和广泛应用，它打破了传统的时间和空间的局限性，极大 地改变了人们的工作方式和生活方式，提高了人们的工作水平和生活质量。但 是，由于及互联网络的国际化、社会化、开放化、个性化的特点，使得它在向 人们提供信息共享、资源共享和技术共享的同时，也带来了不安全的隐患。例 如信息的泄露、篡改、假冒和重传，黑客入侵，非法访问，计算机犯罪，计算 机病毒传播等对信息网络已构成重大威胁。 密码技术是信息安全技术的核心，它主要由密码编码技术和密码分析技术 两个分支组成。密码编码技术的主要任务是寻求产生安全性高的有效密码算法 和协议，以满足对消息进行加密或认证的要求。密码分析技术的主要任务是破 译密码或伪造认证信息，实现窃取机密信息或进行诈骗破坏活动。这两个分支 既相对独立又相互依存，正是由于这种对立统一关系，才推动了密码学自身的 发展。 目前人们将密码理论与技术分成两大类，一类是基于数学的密码理论与技 术，包括公钥密码、分组密码、数字签名、密钥管理、p k i 技术等；另一类是 非数学的密码理论与技术，包括信息隐藏等。本文将探讨基于数学的一种密码 椭圆曲线密码的相关技术问题。 1 1 椭圆曲线密码的研究背景和意义 自1 9 7 6 年公钥密码体制问世以来，人们提出了大量公钥密码体制的实现方 案，所以这些方案的安全性都是基于求解复杂的数学难题。截至目前，既具有 一定安全性又能够比较容易实现的体制按照所基于的数学难题，有如下三类： ( 1 ) 基于大数分解的公钥密码体制。若r s a 体制【l 】等。 ( 2 ) 基于有限域上离散对数问题的公钥密码体制。如e 1 g a m a l 类加密体制和 签名方案【2 】，d i f f i e h e l l m a n 密钥交换方案【3 】等。 ( 3 ) 基于椭圆曲线离散对数问题的公钥密码体制。如椭圆曲线的数字签名算 法e c d s a 4 】等。 在过去2 0 年中，最著名、应用最广泛的公钥密码体制是r s a ，由r i v e s t 、 s h a m i r 和a d d m a n 在1 9 7 8 年提出，它的安全性是基于大数分解的难题，至今 没有有效的解决方法，从而确保了r s a 的安全性。由于r s a 的原理简单，且 北京t 业大学t 学硕十学位论文 易于使用，因而成为大多数公钥密码产品所使用的算法。 另一方面，自r s a 提出以后，人们对大整数分解问题的研究产生了空前的 兴趣，经过人们的不懈努力，目前人们对两类问题的求解能力较过去有了很大 的提高。这迫使r s a 体制中使用的模数和基于有限域离散对数问题的公钥密码 体制中的有限域越来越大。对这两类体制，过去的5 1 2 b i t 大小的密钥己足够安 全，但现在就不能保证它的安全性，不得不使用1 0 2 4 b i t 大小的密钥。密钥位数 的增加导致了其加密和解密的速度大为降低，存储空间增大，硬件实现变得越 来越困难。 1 9 8 5 年k o b h t z 5 1 、m i l l e r t 6 】等人分别独立提出椭圆曲线密码体制e c c ，即 基于椭圆曲线离散对数问题的各种公钥密码体制，它是利用有限域上的椭圆有 限有限群代替基于离散对数问题密码体制中的有限循环群所得到的一类密码体 制。e c c 与其它两类体制比较，有如下优点： 第一，椭圆曲线密码体制具有最强的单比特安全性。对椭圆曲线密码体制， 1 6 0 b i t 长的密钥所具有的安全性相当于前两类密码体制中1 0 2 4 b i t 长的密钥所有 的安全性，2 1 0 b i t 长的密钥所具有的安全性和前两类密码体制中2 0 4 8 b i t 长的密 钥所具有的安全性相当。这体现了e c c 具有强的单比特安全性。每一比特椭圆 曲线密码体制的密钥至少相当于5 比特长的r s a 密钥的安全性，并且这种比例 关系随密钥长度的增加呈上升趋势。椭圆曲线密码体制的这一特点，使得它在 未来计算能力逐渐提高的情况下与其它两类体制相比具有更强的竞争力。它所 具有的相对小的密钥长度尤其适合像i c 卡技术那样一种存储条件受到严格限 制的情况。 第二，在同样的基域下，椭圆曲线密码具有更多的可选择性。对给定的素 数p 或g ，唯一地对应一个r s a 算法或e 1 g a m a l 类算法。但是对于椭圆曲线密 码情况却不同。因为在同一基域上，通过改变椭圆曲线方程的系数就能够得到 更多具体的算法。特别是有限域只，二进制多项式表示的椭圆曲线，运算快、密 钥短，不仅可用软件实现，硬件实现也十分方便。 第三，可以主动选取基域g f ( p 1 中的素数p ，这样就可选取更便于计算机 处理的素数，如m e r s e n e 素数等。但是，对r s a 体制和e 1 g a m a l 体制则不能如 此对r s a 体制，素数的选取必须是随机的，对e 1 g a m a l 类的体制又必须选取使 p 一1 包含一个大的素因子的素数。 第四，椭圆曲线密码存储空间占用小。椭圆曲线密码的密钥大小和系统参 数相较r s a 体制和e 1 g a m a l 类的体制要小得多，这意味着它所占的存储空间要 小。这对于密码算法在资源受限制的环境( 比如智能卡) 的应用具有特别重要 第1 苹绪论 的意义。 第五，椭圆曲线密码的带宽要求低。对长消息进行加解密时，这三类公钥 密码系统有相同的带宽要求，但应用于短消息时椭圆曲线密码的带宽要求却低 得多，而公钥加密系统多用于短消息，例如数字签名和密钥交换，带宽要求低， 使椭圆曲线密码在无线网络领域具有广泛的应用前景。 e c c 的这些优点，使得人们普遍认为，e c c 会取代r s a 而成为2 1 世纪最 主要的公钥密码体制。从1 9 9 8 年起一些国际标准化组织开始了对椭圆曲线密码 的标准化工作。其中，1 9 9 8 年底美国国家标准与技术研究所( a n s l ) 公布了专门 针对椭圆曲线密码的a n s i f 9 6 2 和a n s i f 9 6 3 ，1 9 9 8 年i e e e p 1 3 6 3 工作组正 式将椭圆曲线密码写入了当时正在讨论制定的“公钥密码标准 的草稿中。在 该草稿中规定了三类构造公钥密码体制的数学难题，其中椭圆曲线离散对数问 题是其中之一。2 0 0 0 年8 月，p 1 3 6 3 的最后文本己被工作组通过。 e c c 是以有限域上的椭圆曲线理论为基础的，对它的研究有力地推动了椭 圆曲线或其它相关学科的发展。例如，1 9 8 5 年s c h o o f 在c o m p u t a t i o no f m a t h e m a t i c s 杂志上发表了一种计算有限域上椭圆曲线有理点个数的算法，即目 前人们知道的著名的s c h o o f 算法。从理论上讲，s c h o o f 算法已经是多项式算法 了，在椭圆曲线密码的拖动下，对其进行改进而得到了目前的s e a 算法，并且 现在人们不仅仅在考虑亏格大于l 的代数曲线中有理点的计数问题了，更进一 步地在考虑一般代数族上有理点的计数问题。实际上，在整个公钥密码学的有 力推动下，一门新的学科计算数论已经形成并引起了人们极大的兴趣。 e c c 的研究除能推动其它学科发展外，它的更重要价值还在于应用。就目 前已经建立或正在建立的各种安全信息传输和交换系统而言，它们的安全框架 都是按照公钥密码学理论构筑的，离开了这一理论，也就无从谈起它们的安全 性。按当前的电子信息化程度，它的应用主要在银行结算、电子商务和通信领 域等，以后必将会扩展到人们社会生活的各个层面。因此，由e c c 所发展成的 技术将具有无限的商业价值。 当前，国际上主流的公钥加密技术仍然采用的是r s a 密码体制。但是，先 进的椭圆曲线公钥密码体制已经得到了世界上广泛的认可。安全的电子商务协 议s e t ( s e c u r ee l e c t r o n i ct r a n s a c t i o n s ) 的制定者已经把椭圆曲线密码体制 作为下一代s e t 协议中默认的公钥密码算法，几个国际标准化组织也把椭圆曲 线密码体制作为新的信息安全标准。我国也已经将椭圆曲线密码体制作为“十 五”期间的重点研究课题。尽管美欧发达国家在密码技术的理论和应用研究上 都处于世界领先地位，并且已经有了基于椭圆曲线公钥密码体制的密码类产品 面世，但是有关国家对我国采取禁运的政策以及我国在密码管理上实行专控不 准使用进口技术和产品的要求，因此进行椭圆曲线密码体制的理论与应用研究 北京工业大学t 学硕十学位论文 就有着重要的现实意义。 总之，e c c 的研究，既具有理论价值又具有实用价值及现实意义。 1 2 椭圆曲线上点的标量乘法的研究现状 文献 7 】中指出，所谓椭圆曲线上点的标量乘法是指，给定椭圆曲线上点p 和一个大整数k ，计算k p ，即用椭圆曲线上加法将p 与自身连续相加k 次，称 为椭圆曲线上标量乘法。在椭圆曲线密码体制的实现中，标量乘法是关键。相 当于有限域中的指数运算，它的逆运算，即椭圆曲线离散对数问题( e c d l p ) 。 在椭圆曲线公钥密码体制中，加密以及验证的部分都需要用到标量乘法，在最 近几年出现的对称密码体制中，标量乘法更是对称密码计算的基础。 对一些特殊曲线或固定基点尸，现在已经有了较好的算法。但是在一般曲 线的情况下或对随机点p ，如何快速计算k p 仍无一个好的方法。除理论问题外， 要快速实现椭圆曲线密码体制还有很多技术问题需要研究。例如，根据实际问 题的要求，如何选取基域，如何选取曲线，如何表示基域中的元素，采用何种 坐标系及采用何种计算k p 的方法等都会是所遇到的技术问题。 分析椭圆曲线实现过程中的各种算法，可划分为两个层次，一是关于基域 g f ( q ) 及基域元素之i 日- j 的运算；二是关于椭圆曲线有限群e ( g f ( q ) ) 上基点元 素的运算，包括点加以及标量乘法，其中标量乘法是主要运算。这两个层次运 算虽然各具特点，但又紧密相连。如何使椭圆曲线密码得到快速实现，与这两 个层次运算直接相关，而本质上与下面几个因素有关：如何选取基域；如何表 示基域中的元素；如何选取安全椭圆曲线；采用什么坐标；采用何种计算标量 乘算法；通常，基域g f ( p ”l ( p 为素数) ，第一种情况是m = l 时，通常说的大 素域，而且通常取m e r s e r m e 素数；第二种是p = 2 ，m 为一正整数，但是往往 取一个素数，这样的曲线也就是通常所说的“子域曲线 ；第三种是p 3 ，其 中m 为一大于6 的正整数，一般素数p 等于或者接近于该密码体制所用的c p u 位数的一个数。现有的椭圆曲线密码均是在以上三种形式上实现，第一种形式 具有最大的安全性，第二种形式更适合在硬件上实现，第三种形式最适合椭圆 曲线密码在普通计算机上快速实现。基域元素的表示有两种：多项式基的表示 形式和正规基表示形式。这两种表示方法各有优点，多项式表示形式适合一般 的加和乘运算，而在正规基表示下，基域元素的p 次方的计算基本可以忽略不 计。 第1 章绪论 常用的表示椭圆曲线有限群点的坐标有：仿射坐标，射影坐标，j a c o b i n 坐 标等。不能说哪一种坐标就比另一种好，因为不同的曲线，不同的运算在不同 的坐标系中运行的时间也不同。有的研究综合了各个坐标系之长，采用混合坐 标系法计算标量乘法。 目前计算标量乘算法的算法主要有：二进制展开法，带符号的二进制法、朋 进制法、带符号的m 进制法、f r o b e n i u s 自同态法以及最近发展的利用复乘的 g l v 方法等。目前最快也最常用的是i e e e p l 3 6 3 标准中给出的仿射坐标下完全 不连接形式( n o n - a d j a c e n t f o r m ，n a f ) 二进制法，如今最快的标量乘算法还 是不能满足要求，如何提高运算速度成为当务之急。 总而言之，近年来，国内外众多学者在椭圆曲线标量乘法这方面做了大量 的工作，提出了不少方法，而且仍在研究中。本文将在这个内容的某些方面上 进行研究讨论。 1 3 本文主要工作 本文主要研究椭圆曲线公钥密码体制的相关技术，介绍椭圆曲线密码体制 的基本概念和理论，并在这一基础上对椭圆曲线密码体制中标量乘k p 的计算进 行了较深入的研究，主要工作如下： ( 1 ) 对椭圆曲线密码体制的基础理论知识进行了总结。 ( 2 ) 从标量k 的有效表示入手，研究椭圆曲线标量乘肛算法。利用补码表 示的原理，引出标量k 的一种新的表示方式补码表示，描述了由标 量k 的二进制表示方式向补码表示方式的快速转换方法，提出了椭圆曲 线标量乘的补码方法以及窗口补码方法，并从整数k 的序列长度、序列 的汉明权值、零位的平均长度、转换方向和窗口数等方面与其他方法进 行比较，分析椭圆曲线标量乘的组合算法的性能。 ( 3 ) 研究了在j a c o b i a n 投影坐标下的椭圆曲线的标量乘的组合算法。采用组 合运算的思想，结合椭圆曲线点加运算的等z 坐标方法提出了椭圆曲线 倍加运算( 2 p + q ) 的组合算法和椭圆曲线标量乘肛的组合算法，并通 过与传统方法在运算量等方面的比较分析了组合方法的性能。 1 4 论文的组织结构 本人在阅读了国内外大量文献资料的基础上，围绕着椭圆曲线的基本理论 和算法，对椭圆曲线的标量乘算法和明文嵌入方法进行了分析和研究，提出了 基于补码的椭圆曲线标量乘算法和j a c o b i a n 投影坐标下的椭圆曲线标量乘的组 北京t 业大学t 学硕十学位论文 合计算方法，并对椭圆曲线的明文嵌入方法进行了分析和总结。论文共分5 章， 其组织结构如下： 第1 章主要讲述了课题的研究背景、研究意义，国内外的一些研究现状及 本文的主要工作； 第2 章为椭圆曲线密码体制相关知识，介绍了椭圆曲线的定义、椭圆曲线 的离散对数问题、椭圆曲线密码体制的实现以及几个典型的椭圆曲线密码系统； 第3 章为椭圆曲线标量乘运算相关知识，介绍了椭圆曲线标量乘的定义、 椭圆曲线标量乘的数学层级模型以及椭圆曲线标量乘的相关基本运算。 第4 章为椭圆曲线标量乘的补码算法，用补码表示的原理，引出标量k 的 一种新的表示方式补码表示，描述了由标量k 的二进制表示方式向补码表 示方式的快速转换方法，提出了椭圆曲线标量乘的补码方法以及窗口补码方法， 并从整数k 的序列长度、序列的汉明权值、零位的平均长度、转换方向和窗口 数等方面与其他方法进行比较，分析椭圆曲线标量乘的组合算法的性能。 第5 章为椭圆曲线标量乘的组合算法，采用组合运算的思想，结合椭圆曲 线点加运算的等z 坐标方法提出了椭圆曲线倍加运算( 2 p + q ) 的组合算法和椭 圆曲线标量乘k p 的组合算法，并通过与传统方法在运算量等方面的比较分析了 组合方法的性能。 结论部分主要对全文进行了系统的总结，并提出了进一步的研究工作。 第2 章椭圆曲线密码体制 第2 章椭圆曲线密码体制 椭圆曲线密码体制，即基于椭圆曲线离散对数问题的各种公钥密码体制。 最早于1 9 8 5 年由m i l l e r 和k o b l i t z 分别独立地提出。它是利用有限域上椭圆曲 线的有限点群代替基于离散对数问题密码体制中的有限循环群所得到的一类密 码体制。对于椭圆曲线密码系统( e c c ) 的安全性，其数学基础是计算椭圆曲线离 散对数问题( e c d l p ) 的难解性。 因为椭圆曲线离散对数问题是比一般离散对数问题难解得多的困难问题， 因此与一般离散对数密码系统相比，椭圆曲线密码系统的比特强度最高。所以， 在相同安全级下，e c c 需要的参数比离散对数密码系统更小。小的参数能带来 许多的优点：计算量小、处理速度快、存储空间占用少、带宽要求低等。尤其 在计算能力、存储空间、带宽、功率消耗等资源受限制的环境，这些优点非常 重要【8 1 耻们。另外利用椭圆曲线建立密码体制具有两大潜在的优点：一是取之 不尽的椭圆曲线可用于构造椭圆曲线有限点群；二是不存在计算椭圆曲线有限 点群的离散对数问题的亚指数算法。因此椭圆曲线密码系统被认为是下一代最 通用的公钥密码系统。 2 1 椭圆曲线的定义 定义2 1 设k 是一个数域，则由w o e r s f f a s s 方程： t y + 口l 砂+ a 3 y 。x + a 2 x + a 4 石+ 在k 上的解集连同一个称之为无穷远点的特殊点。所确定一条曲线e ， 上的椭圆曲线。 若k 的特征值为2 ，则方程可以变换为： y 2 + 拶= x 3 + 甜2 + 6 若k 的特征值为3 ，则方程可以变换为： y 2 = ，+ 似2 + k + c 若k 的特征值大于3 ，则方程变换为： ( 2 - 1 ) 称为k ( 2 2 ) ( 2 - 3 ) y 2 = 夕+ a x + b ( 2 4 ) 定义2 2 设f ( x ，y ) = o 为上述各椭圆曲线方程的隐式方程，则若点p ( x ，y ) 使得a f o x ，a f 砂不同时为零，称p 为非奇异点。 一7 北京t 业大学t 学硕卜学位论文 2 1 1 实数域上的曲线 定义2 3 设e 是实数域上的一条曲线，p 、q 分别是e 上的两个点，0 为 无穷远点，定义下列运算p + q ： a ) 若尸= 0 ，则一尸= 0 ，o + q = q b ) 设尸的坐标为( x ，y ) ，p 0 ，则一p = ( x , - - y ) ，即p 与一尸关于x 轴对称 c ) 若尸q ，则直线魍与曲线e 有另一个交点r ，则p + q = - r 不难验证( e ，+ ) 构成一个以d 为单位元的a b e l i a n 。上述运算可借助图2 - l 来描述其几何意义。 l y 戳刁l厂刁 3 ，p 为素数) 上的椭圆曲线。上述规则( 3 ) 、( 4 ) 所定义的加法分别称为普 通点加和倍点运算。 以，、m 、s 分别表示有限域上的一次逆运算、乘法运算、平方运算( 加 法运算和其它相比可忽略) ，则不难得到，对于e ( ) ( 特征值p 3 ，p 为素 数) 上一次普通点加，在基域上需要，+ 2 m + s ；一次倍点运算，计算量为 i + 2 m + 2 so 一般地，对于有限域上椭圆曲线有以下基本定义： 定义2 - 4 设p 是域的特征值，e 是定义在域上的椭圆曲线，椭圆曲线 e ( c ) 的点的个数记为撑e ( ) ，并称为椭圆曲线e 的阶。有h a s s e 定理知 # e ( f n ) = q + l - t ，z , - 2 压f 2 虿，求解阶群e ( c ) 的算法有s c h 0 0 f 算法 和s e a 算法，可在多项式时间求出撑e ( c ) 。 定义2 - 5 若p i t 成立，则称曲线e 是超奇异的。若p i t 不成立，则称曲线e 北京工业大学工学硕上学位论文 是非超奇异的。因对超奇异椭圆曲线上的离散对数已有概率亚指数算法，一般 在构造椭圆曲线公钥系统时，将不采用超奇异椭圆曲线。 定义2 - 6 设尸e ( ) ，p + 户+ + 尸= k p ，k + p 自加，称为标量乘运算。 定义2 - 7 设尸e ( ) ，若存在最小正整数刀，使胪= d ，称，l 为点p 的阶， 则( d ，p , 2 p ，( 刀一1 ) p ) 构成一循环子群，_ l t nl 撑e ( 耳) 。 2 2 椭圆曲线上的离散对数问题 椭圆曲线离散对数问题的困难性是所有椭圆曲线密码方案安全性的基础。 定义2 8 椭圆曲线离散对数问题( e c d l p ) ：给定定义于有限域e ( r ol 上 的椭圆曲线e ，基点p e ( ) ，阶为刀，点q ，寻找一个整数， o ，n - 1 】 使得q = p 。整数，称为q 的基于p 的离散对数，表示为，= l o g 尸q 。 为了抵抗所有已知的对e c d l p 的攻击，密码方案中使用的椭圆曲线的参 数应该谨慎选择。最简单的求解e c d l p 问题的算法是穷举搜索：连续计算一 系列点p ，2 p ，3 p ，4 p ，直到得到q 。该方法的运行时间最坏情况下为 n 步，平均情况下为n 2 步。因此可以通过选择参数n 足够大的椭圆曲线，使 得穷举攻击的计算量不可实际实现( 如n 2 ) 。 目前已知的计算椭圆曲线离散对数问题的最好的算法是p o l a r d p 一方法，用 这种方法计算椭圆曲线的离散对数问题需要咒万2 ，其中n 是点p 的阶数，而 一步都是一个椭圆曲线点的加法。若我们用每秒可执行一百万次命令的计算机 通过p o l a r d p 一方法求椭圆曲线的离散对数问题，则可认为该密码系统是不可破 解的。 e c d l p 的实质是有限域乘法群上的离散对数问题在有限域椭圆曲线点群 上的推广。对一条适当选取的椭圆曲线和基点尸，目前e c d l p 还没有亚指数 时间的通用算法，其最好算法也是指数时间的，因此它比因数分解( i f p ) 和有 限域上乘法群的离散对数问题( d l p ) 要困难得多。e c d l p 的困难性为构造新 的密码体制提供了很好的理论基础，也是所有椭圆曲线密码方案安全性的基础。 现在一般认为，1 6 0b i t 密钥的e c c 所有的安全性和r s a 、d s a 中1 0 2 4b i t 密 钥的安全性相当。 第2 章椭圆曲线密码体制 2 3 椭圆曲线公钥密码体制的实现 2 3 1 安全椭圆曲线的选取 椭圆曲线密码体制的安全性取决于由椭圆曲线定义的群上的离散对数问题 的难度。一般的离散对数有有效的亚指数时间算法攻击一指数计算法( i n d e x c a l c u l u s ) ，而这种方法不能应用到椭圆曲线离散对数问题e c d l p 上。对e c d l p 的攻击可分为两类：对特殊曲线的离散对数攻击和对一般曲线的攻击。对一般 曲线的攻击方法有：大步小步法( b a b y - s t e pg i a n t - s t e p ) 、p o h l i g - h e l l m a n 算法、 p o l l a r dp 方法、x e d n i 算法。对特殊曲线的离散对数攻击的方法有：针对超奇异 椭圆曲线( 设的特征值为p ，e ( ) 的qi 玢f r o b e n i u s 变换的迹f 是p 的倍数时， e 称为是超奇异的) 的m o v 方法、针对撑e ( ) = g 这类“畸形 ( 设q = p ”， p 2 ，3 为素数，e ( ) 由方程y 2 = x 3 + 锻2 + 6 定义，p e ( ) 的阶为p 。当 p = q 时，异常曲线上的p 阶f r o b e n i u s 变换的迹( f = 1 ) 曲线的s m a r t 方法。 为了抗击我们所提到的攻击类型，我们在有限域乞上找的椭圆曲线e ( 乞) 应满足一下要求： ( 1 ) 撑e ( ) 有很大的素因子，素因子大于2 1 6 0 且大于4 g ，这样可以抗击 p o l l a r d p 方法的攻击。 ( 2 ) e ( ) 不是超奇异曲线，避免m o v 算法。 ( 3 ) e ( ) 不是“畸形曲线，可以防止s m a r t 攻击。 下面介绍3 中选择适宜的椭圆曲线的方法： ( 1 ) 仅限于有限域为只上构造椭圆曲线。其原理是将定义在特征值比较小 的有限域的椭圆曲线提升到该域的扩域上去，并且m 能被小整数k 1 整除。这 种方法简单，但是得到的曲线较少。 ( 2 ) c m ( c o m p l e xm u l t i p l i c a t i o n ) 法。根据给定的阶来选取符合此阶的椭 圆曲线。它的实现速度相对较快，但这种方法产生的椭圆曲线具有附带的结构 特征。从安全性角度讲这是一个潜在的威胁。 ( 3 ) 随机选取曲线随机选取曲线的参数口，b c 。如果g 是素数，则满足 北京- t 业大学t 学硕l ：学位论文 4 a 3 + 2 7 b 2 o ；如果g = 2 ”，则6 o ，然后计算“= 撑e ( ) 和大素数因子刀， 直到所选的曲线满足安全需求。这种方法比较理想，选取的曲线安全级别高， 它完全依赖于椭圆曲线阶的计算。 2 3 2 椭圆曲线的域参数 为了便于互操作性，有限域的大小g 及域上元素的表示有一些基本要求。 有限域的阶要么是q = p ，一个奇素数；或者是g = 2 ”，2 的幂。在g = p 的情 形，有限域是乞。在g = 2 肌隋形，有限域是f 2 m ，其元素由多项式或正规基表 示。 另外，为了避免一些已知的攻击，椭圆曲线及基点的选取也有一些限制。 为了避免p o l l a r d sr h o 和p o h l i g - h e l l m a n 对椭圆曲线离散对数的攻击，曲线e 在 域上的点数被一个足够大的素数n 整除是必要的。为了避免m e n e z e s 、 o k a m o t o 和v a n s t o n e ，f r e y 与r u c k 的还原算法，曲线应该是非奇异的。 e c c 的域参数由特征值为p 的有限域上的一条合适的被选择的椭圆曲线 e 和基点p e ( 乞) 构成。例如e c d s a 的域参数是一个七序偶 r = ( g ，r ，口，b ，尸，刀，h ) ，其中： g ：域大小g ，其中g = p ，一个奇素数，或者q = 2 ”； f r ：域坐标，指示域上元素的表示方式； 口，b ：有限域上的两个域元素，定义域上的曲线e 的方程( 若p 3 ， 那么y 2 = x 3 + 似+ 6 ；若p = 2 ，那么y 2 + 砂= ，+ 似2 + 6 ) ； p ：e ( ) 上点p = ( 昂，y p ) ，其中讳，y e ； 刀：点p 的阶，一个足够大的素数； h ：j j l = 撑e ( ) 刀 第2 章椭圆曲线密码体制 2 3 3 椭圆曲线阶的计算 从椭圆曲线的安全性来看，如果曲线的阶足够大，半万根攻击如s h a n k s b a b y - s t e pg a i n t s t e p 或p o l l a r d sp 方法就不太有效，要能抗击p o h l i g - h e l l m a n 攻 击，一个好的策略是确保曲线的阶撑e ( ) 中包含有大素数因子( 该大素数作为 所选取基点尸的阶) 使得p o h l i g - h e l l m a n 算法的。( 石) 计算量不能实现。由此 看来，计算撑e ( ) 是研究定义在有限域上的椭圆曲线的一个核心问题。 关于椭圆曲线e 的阶的计算，有定理如下： 定理2 - l ( h a s s e 定理) 设e ( ) 为有限域上的椭圆曲线，则 l 徉e ( ) 一g 一1 1 2 , f f ( 2 - 1 1 ) 如果撑e ( ) = g ，则椭圆曲线e ( ) 是一类特殊的椭圆曲线，称为“畸形” 曲线。 如果要准确求出椭圆曲线的阶，有定理如下： 定理2 - 2 给定椭圆曲线e ：y 2 = z 3 + a x + b ( 其中口，6 ) ，则： 稃e ( ) = - + ( + ( 兰二昙坐 ，cx ) c 2 - 2 ， 其中( ) 为勒让德符号 f i 当p 是口的平方剩余时 ( ) 七7 7 嚣的平方剩余时 对任意的x ，若gi ，+ a x + b ，方程y 2 = 工3 + 戤+ 6 有一个解，椭圆曲线 上有相应的一个点( x ，0 ) 。若矿+ a x + b 是q 的平方剩余，方程y 2 = ，+ a x + b f f 两个解，椭圆曲线上有两个以x 为横坐标的点。若x 3 + 似+ 6 不是q 的平方剩余， 方程y 2 = ，+ a x + b 无解，椭圆曲线上没有以x 为横坐标的点。 对任意x c ，+ a x + b 总是以上三种情况之一，因此椭圆曲线上以x 为 北京t 业大学t 学硕i ：学位论文 横坐标的点有( + ( 芏孑堂 个。 另外，椭圆曲线包括一个无穷远点o 。 所以有限域上椭圆曲线阶为：群e ( ) = + ( + ( ! 笋鱼 。 给定一条椭圆曲线e ( ) ，计算其上的点是非常有意义的工作，也是寻找 安全椭圆曲线最主要的过程。s c h o o f 提出了一种计算复杂度是多项式时间的算 法，所需的时间是o ( 1 0 9 “q l ，因为整个算法实现过程中所需存储量很大，所 以仍不太可行。a t k i n f 和e l k i e s 对s c h o o f 算法进行一些改进，即s e a 算法，其 时间复杂度为o ( 1 0 9 4 竹q ) ，s a t o h f 提出了一种时间复杂度为d ( 1 0 9 3 + 5g ) 新的计算 椭圆曲线上点的方法，这种方法适用于特征值p 比较d , r p 5 的有限域。同年 f o u q u e t 、g a u d r y 和h a r l e y f 将这种方法推广到特征值为2 和3 的域上，称这种 方法为s a t o h f g h ，这是目前最快的计算椭圆曲线上点的方法。 2 4 椭圆曲线的密码系统 设e 是定义在域e 上的一条椭圆曲线，在e 在选取一个点p 为基点，记p 的阶为n 通常要求n 是一个大素数。每个用户选取一个整数d ( d 1 ，n 一1 1 ) 作 为其私钥，而以点q = d p 作为其公钥，这样就形成了一个椭圆曲线公钥密码体 制( e c c ) 。定义e 的方程、基域只、基点p 及其阶咒、以及每个用户的公钥都 作为该系统的公开参数，每个用户的私钥都是保密的，仅本人知道。 很多基于有限域乘法群上的密码协议，例如d h 密钥交换、e 1 g a m a l 加解 密、e 1 g a m a l 数字签名、d s a 数字签名等都可以移植到椭圆曲线上，这样的椭 圆曲线密码系统具有与现存的公钥密码体制具有相同的安全性，但密钥长度却 相对要短。较短的密钥意味着较窄的带宽和较小的内存要求。这些密码系统在 某些内存和处理能力都受限的环境如智能卡的设计中相当重要。这些密码系统 大致可以分成以下几类：密钥交换密钥协商方案、消息加密解密方案、具有消 息恢复不具有消息恢复的数字签名方案、认证方案、r s a 类型的椭圆曲线密码 系统、建立在环上的椭圆曲线数字签名方案等。下面我们研究几类典型的椭圆 曲线密码协议。 第2 章椭圆曲线密码体制 2 4 1 密钥交换协议( e c d h ) 由于公钥体制比对称密码进行加解密速度慢很多，所以在实际的加密系统 中通常是利用会话密码( 分组密码或流密码) 对数据加解密，用密钥交换算法 如d h 传递会话密码，该算法允许通信双方在不安全的媒介上安全地交换密钥。 密钥交换过程如下： ( 1 ) 用户a 随机选择一个整数吃，1 d o n - 1 ，作为密钥，计算q 口= 吃尸 作为公钥； ( 2 ) 用户b 随心选择一个整数吃，1 吃n - 1 ，作为密钥，计算q 6 = 以p 作 为公钥； ( 3 ) 用户a 、b 分别由k = d o q 。和k = d 6 q o 产生双方共享的私密钥。这是因 为：k = d o q 。= 吃( 吃奉p ) = 以( 吃木p ) = 吃q 安全性：攻击者想要获取k ，则必须由q 和p 求出d o ，或由q 和p 求出以， 即需要求椭圆曲线上的离散对数，因此是不可行的。所以该密码协议的安全性 与求解椭圆曲线离散对数问题的困难性等价。 2 4 2e 1 g a m a l 圆曲线加密系统 现在描述利用椭圆曲线实现e 1 g a m a l 加密通信的过程：用户a 欲