（计算机应用技术专业论文）椭圆曲线密码算法的快速实现研究.pdf

摘要 摘要 椭圆曲线密码是公钥密码的发展趋势，椭圆曲线密码算法的快速实现问题娃椭圆曲线密码尚待进一 步究的芙键问题，利州基丁有限域上的椭圆曲线密码可以实现数据加密、密钥交换、数字签名等密码 方案。本文主要阐述椭圆曲线密码的相关内容。在此基础上重点研究了椭圆曲线密码算法的 犬速实现方 法，升对椭圆曲线密码住密码方案中的两种席h j 一基丁椭锄曲线f | 勺密钥交换方案和数字签名方案进行 软件实现。全文共分四章叙述：第一章概述了课题背景、椭圆曲线密码的研究现状及本文所作的主要i ? 作：第一章论述了椭圆曲线密码学基础；第二章研究了椭圆曲线离散对数问题、椭圆曲线公钥密码的攻 一f 现状，椭圆曲线参数组构成，详细说明了椭圆曲线密钥交换方案平椭圆曲线数字签名方案：第网章首 先研究了椭圆曲线密码算法的快速实现方法，主要包括椭圆曲线上的点加、倍点、点乘运算实现，然后 对椭螂曲线密码在密码方案中的两种应用一一基于椭圆曲线的密钥交换方案e c d h 希l 数字签名方案 e c d s a 进行软什实现分析了实现过程中涉及的关键问题与解决方法，并详细说明了系统的具体功能。 关键词；椭圆曲线密码，椭圆曲线离散对数问题，点乘，e c d h ，e c d s a a b s t r a c t e l l i p t j c c u r v ec r y p t o g r 印h yi st h ed e v e l o p j n gt r e n do fp u b l i ck e yc r y p t o g r a p h yf a s ti m p l e m e n t a t o n p r o b i e m so fl h ee p f i cc u r v ec r y p t o g r a p h ya r i t h l n e t j ca r et h eh o t s p o td i r e c t i o ni nt h ee l l i i p t i cc u r v e c r y p t o g r a p h yr e s e a r c h e l | i p t i cc u f v ec r y p t o g r a p h yb a s e do nt h e 厅n t e 行e l d sa p p l i e sm a n yc r y p t o g r a p h i c s c h e m e ss u c ha sd a t ae n c r y p t i o n ，k e ye x c h a n g ea n dd l g j t a ls l g n a t u r e 1 nt h i sd l s s e r c a t i o n ，w j t ht h ee m p h a s j so f l h ea k o r i l h m sf o rt 1 1 ef a s ti m p l e m e n t a t i o no ft h ee l l i p t i cc u r v ec r y p t o g r a p hy t h ee 1 1 i p t i cc u r v ec r y p t o s y s t e m s a n dt h er e i a t e da i g o r i t h m sa r ei n t r o d u c e d t h ea p p l j c a t i o no fe l l i p t i cc u r v ec r y p t o g r a p h yi nc r y p t o g r a p h i c s c h e m e s ：1 l i p t i c c u r v ed i f n e - h e l l m a nk e ye x c h a n g e ( e c d h ) a n de 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 e a j g o r i t h m ( e c d s a ) a r ea l s oi m p i e m e n t e d i tc o n s i s t so ff o u rc h a p t e r s i nc h a p t e ro n e ，t a s kb a c k g r o u n d ，s o m e i n t t o d u c e dm a t e r i a l si n c l u d i n gt h em o t i v a t l o n sa n dr e c e n tr e s e a r c ho ft h ee i p t i cc u r v ec r y 舛o s y 科e m sa n d m a i nr e s e a r c hc o n t e n to ft h j sd i s s e n a t i o na r eb e 门ys u r v e y e di nc h a p t e rt w o ，s o m eb a s i cm a t er a i so ft h e e ip t i cc u r v et h e o r ya r ed i s c u s s e d i nc h a p t e rt h r e e ，t h ed i s c r e t ei o g a r i t h mp r o b l e mo fe l i i p t i cc u r v e ，l h ea c t u a i a l 协c k ，a n dt h es t r u c t u r eo f e l j i p t i cc u r v ep a r a m e t e r sa r ed i s c u s s e d c d ha n de c d s as c h e m e sa r e n t m d u c e d i nd e l a i nc h a p t e rf o u ln r s to fa i it h ef a s ti m p l e m e n t a t i o nm e t h o d so ft h ee l l i p i i cc u r v ec r y p t o g r a p h y a r i t h m e t i ca r es t u d i e d ，i n c l u d i n gp o i ma d d t i o n ，d o u b i e a d db a s i co p e r a t j o ni m p l e m e n t a t i o na n ds c a l a r m u l t i p l i c a t j o ni m p i e m e n t a t i o n t h e nt 、v oa p p l l c a t i o n so ft h ec r y p t o g r a p h i cs c h e m e sb a s e do ne l i l p t i c c u r v e ： e p t i cc u r v ed i m e h e l l m a nk e ye x c h a n g e ( e c d h ) a n de l i j p t i cc u r v ed i g j t a ls i g n a t u r ea 】g o t h m ( e c d s a ) a r ei m p l e m e n l e db yu s i n gc + + l a n g u a g e t h ek e yp m b l e m si ni t si m p l e m e n t a t i o na n dt h es o i u t i o n s a r ea n a l y s e dt h em a i nm c t i o n so f t h e5 y s t e ma r eb r i e n yd e s c r i b e d k e yw o r d s ：e l | i p t i cc u r v ec r y p t o g r a p h y e l l i p t i cc u r v ed i s c r e t el o g a r i t h mp r o b l e m ，s c a l a rm u i t i p l i c a t i o n e | l p t i cc u r v ed i 用e h e l i m a nk e ye x c h a n g e ( e c d h ) ，e i l p t i cc u r v ed i g i t a is i g n a t u r ea i g o r i t h m ( e c d s a ) 一2 一 首都师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取 得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰 写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名 欲 f ：| 期：确年如扣r 首都师范大学学位论文授权使用声明 本人完全了解首都师范大学有关保留、使用学位论文的规定，学校有权保留学位论文 并向国家主管部门或其指定机构送交论文的电子版和纸质版。有权将学位论文用于非赢利 目的的少量复制并允许论文进入学校图书馆被查阅。有权将学位论文的内容编入有关数据 鹳：礞噜慨小圳旬同 椭圆曲线密码算法的 吏速实现研究 1 1 课题背景 第一章绪论 随着计算机和网络的高速发展和广泛应用，通信的网络化、数字化、智能化的不断加 快，社会对计算机和网络的依赖性也越来越大，各行业、各领域越来越多地利用计算机网 络柬进行数据存储、传递和交换，用户对信息的安全保护需求愈益迫切。若计算机和网络 系统的安全受到危害，则会危及国家的安全，并造成重大的损失。因此，确保计算机和网 络系统的安全已经提升到关系信息化建设和发展的核心地位。确保信息系统的安全要从整 体考虑，如果浣硬件结构的改善优化以及操作系统的安全是系统安全的基础，那么系统安 全理论的核心密码就是关键技术。 密码技术是一门古老的技术，历史上记载的人类最早对信息进行加密可以追溯到古希 腊时代。两千多年的发展，密码学经历了由简单到复杂的过程，1 9 4 9 年s h a n l l o n 发表的题 为保密系统的信息理论的论文，该论文将密码置于坚实的数学基础之上。如今密码学 已经成为着重研究信息的变形及其合法复现的学科。现代密码学形成于2 0 世纪7 0 年代， 其重要标志有两个，一是美国制定并于1 9 7 7 年1 月1 5 日批准公布了公用数据加密标准 ( d e s ，d a t ae n c r y p t i o ns t a n d a r d ) ，公开它的加密算法，并批准用于非机密单位和商业。【：的 保密通信；二是1 9 7 6 年w - d i m e 和m e h e l l m a n 提出了公钥密码的概念，他们为解决密钥 管理的问题提出了一种密钥交换协议，允许在不安全的媒体上通信双方交换信息，安全地 达成一致的密钥，从而开创了一个密码新时代。 传统加密体制( 即对称密钥密码体制) 的安全性主要依赖于加密算法的强度和密钥保护， 使用完全相同的密钥进行加密解密，它的加密算法比较简便、高效，密钥简短，但是存在 着传输和保管密钥的困难问题。因为假设基于己知密文和加密解密算法的知识而能破译消 息是不实际的，换句话说，我们并不需要保密算法，而仅需要保密密钥，这样密钥就比任 何消息更有价值，对于广域分布的系统来说，密钥分配就成为一个困难问题，并且随着网 络用户的不断增加，对称密钥系统在不断产生密钥的同时，需要管理的密钥也不断增加， 从而制约了对称密码系统的规模，密钥分配和管理困难成为传统密码应用的主要障碍，另 外，传统密码不易实现数字签名，这也是制约其应用的原因之一。 公开密钥密码体制从根本上解决了传统密码面临的三大难题：密钥分配、密钥管理和 提供不可否认性，更适应网络环境中各种安全通信和商业活动的应用，是密码学由传统的 政府、军事应用领域走向民用、商用的基础。公钥密码的思想是：密码系统采用的加密密 钥和解密密钥是不同的，分别称为公开密钥( 简称公钥) 和秘密密钥( 简称私钥) ，由加密密钥 和密文很难求解出解密密钥和明文，密码系统的加密算法和解密算法可以公开，系统的安 全保密性完全依赖于秘密的解密密钥。公钥密码系统除了用于数据加密，还提供了数字签 名、保密通信、秘密共享、认证、密钥管理等功能。与传统密码相比，公钥密码有着诸多 优势，然而它的运算量却十分大。在实际应用中，经常采用对称密码系统与公钥密码系统 一1 一 椭圆蓝线密码算法的快速实现研究 的结合方式，例如使用高级加密标准( a e s ) 束加密需要传递的信息，而同时使用r s a 等公 钥密码来传递a e s 密钥，这样就可以有效发挥两种密码系统的优势，即对称密码加密的高 速、简便性和公钥密码密钥管理的方便性、安全性。 公钥密码的原理是基于单向陷门函数，简单地说，它的一个方向易于计算而反方向却 难以计算，但是如果知道了秘密陷门，就可以反方向计算这个函数。公钥密码系统中，加 密是容易方向，任何人都可以使用公钥进行加密，解密是困难方向，而秘密陷门就是私钥。 从数论的角度来讲，任何公钥密码系统的安全性都是基于求解某个数学难题，或者说 是建立在一个n p 问题之上，即对于特定的问题我们没有办法找到一个多项式时间算法求 解浚问题，一般求解此类问题的算法都是指数时间或亚指数时间。公钥密码体制根据其所 依据的数学问题难解性，一般分为三类： ( 1 ) 基于大整数因子分解问题的公钥密码体制，典型代表有r s a 体制和r a b i n 体制： r s a 是目前最著名的公钥密码之一，可用于数据加密、密钥交换、数字签名中， 它的优点在于原理简单，易于使用，但随着大整数因子分解方法的进步、计算 机计算速度的提高以及计算机网络的发展( 网络中成千上万台计算机同时进行 大整数因子分解) ，为保证r s a 使用安全性，最近这些年来其密钥的位数一直 在增加，目前一般认为r s a 需要1 0 2 4 位以上才能保证其安全性，在极其重要 的场合应该使用2 0 4 8 位。r s a 的保密强度是随着密钥长度的增加而增强的，而 密钥长度不断增加导致其加密解密速度大为降低，工业化实现越来越难以接受， 不利于其在大量安全交易的电子商务中使用，从而制约了r s a 的应用。 ( 2 ) 基于有限域上离散对数问题( d l p ) 的公钥密码体制，典型代表有e l g a m a l 类加密 体制和签名方案，d i m e h e l l m a n 密钥交换方案，s c h o o r 签名方案和 n y b e r g r u p p e l 签名方案等：从r s a 体制提出后，人们对大整数因子分解问题 的研究产生了空前的兴趣，而1 9 8 5 年e 1 0 a m a l 公钥密码体制的提出，也让人们 对有限域上离散对数问题的研究产生更浓厚的兴趣。出于安全性考虑，j ，为15 0 位以上的十进制数，且p 1 应有大素数因子。 ( 3 ) 基于椭圆曲线离散对数问题( e c d l p ) 的公钥密码体制，其中包括基于椭圆曲线 的d i m e h e l l m a n 密钥交换方案，椭圆曲线数字签名方案等：1 9 8 5 年，n e a l k o b l i t z 和v i c t o rm i l l e r 分别独立提出在公钥密码系统中使用椭圆曲线的思想。椭圆曲 线密码体制是利用基于有限域上的椭圆曲线上的点构成a b e l 加法群构造椭圆曲 线离散对数问题基础上的密码体制。严格的说，它不是一种新的密码体制，只 是已有的密码体制的椭圆曲线翻版。椭圆曲线密码的安全性基于椭圆曲线离散 对数问题的困难性，研究表明椭圆曲线离散对数问题比乘法群上的离散对数问 题更难，且加法群上的运算比乘法群上的运算更快，密钥长度比r s a 短得多( 1 6 0 位长的密钥具有的安全强度相当于r s a 体制中1 0 2 4 位长的密钥) 。与r s a 系统 相比，椭圆曲线密码系统安全性更高、计算量小、处理速度快、存储空间占用 少、带宽要求低的优势，后两点更使得椭圆曲线密码在i c 卡、智能卡和无线网 络等领域具有广泛的应用前景。 礴露盎线密码算法的快速实现研究 本文的研究课题背景是基于椭圆曲线密码的数字签名及其在电子商务中的应用研究与 实现，在此基础上初步实现一基于椭圆曲线密码的电子商务安全认证模拟平台。在这个平 台上_ ，不仅要产生大量的信息并使用计算机网络进行通信。还要实现数字化交易、身份认 证、数字签名、信息校验等各项功能。为了提高电予商务应用的安全性、保密性，我们需 要研制使用可靠性高的密码体制，且该密码体制可以易于实现数字签名。公钥密码体制中 的椭圆曲线密码体制正是当前的研究热点。它具有安全性能高、密钥长度短、处理速度快、 计算量小、存储空问占用小和带宽要求低等特点，易于实现数据加密、密钥交换、数字签 名等密码方案。许多标准化组织如a n s i 、n i s t 等已经把椭圆曲线密码作为新的信息安全 标准，制定和规范了椭圆曲线密码机制的签名、加密和密钥建立的标准和草案，使得椭圆 曲线密码在互联网协议安全、电子商务、移动通信、智能卡等方面的应用更为广阔。由于 椭圆曲线密码固有的特性，其用于数字签名具有无可比拟的优势。但是，椭圆曲线密码也 存在着计算复杂、运算速度慢的问题。椭圆曲线密码算法当前的研究热点之一就是它的快 速实现问题，快速实现问题的关键就是快速实现点乘运算。本文将对椭圆曲线密码算法的 快速实现进行研究，并对基于椭圆曲线的密码方案进行实现，提高椭圆曲线密码体制实际 应用时的运行速度，为其应用于信息加密、数字签名做有益的工作。本文的研究对椭圆曲 线密码算法的应用研究，特别是基于椭圆曲线密码的数字签名研究具有重要的理论意义和 学术价值，其研究结果对以低成本实现应用系统可以接受的椭圆曲线密码算法，实现基于 椭圆曲线密码的数字签名方案，推广椭圆曲线密码在电子商务、电子政务、电子银行中的 应用，具有重要的参考价值和实用价值。 1 2 椭圆曲线密码的研究历史与现状 在理论研究方面，最初的重点主要集中在对椭圆曲线阶的计算和对满足密码条件要求 的任意椭圆曲线有理点个数的计算，人们通过十年时间的研究，在这些方面取得了许多重 要的进展，比如最初的s c h 0 0 f 算法塔及之后对其的不斯完善，椭圆曲线的选取问题己鼻i 再 是椭圆曲线密码实用化的主要障碍，人们对椭圆曲线密码的研究从最初的仅是一种理论选 择到达了可实用化的程度，椭圆曲线体制的实现速度较椭圆曲线密码提出的最初有了很大 的提高。椭圆曲线密码是以有限域上的椭圆曲线理论为基础的，随着椭圆曲线密码研究的 不断深入，对它的研究也有力推动了椭圆曲线理论的发展。s c h o o f 算法最初是关于计算育 限域上椭圆曲线有理点个数的算法，发表于椭圆曲线密码体制提出之前，而后进行改进得 到了应用在椭圆曲线密码上的s e a 算法。在椭圆曲线密码的推动下，现在人们不仅在考虑 亏格大于1 的代数曲线中的有理点的计数问题，更进一步地考虑一般代数族上有理点的计 数问题。 椭圆曲线密码体制与前一节中所述的其他两类体制比较，其安全性首先表现为它在同 一确定的基域上的可选择性和丰富性。对于给定的基域q ，都惟一的对应一个r s a 算法或 e l g a m a i 算法。但对于椭圆曲线密码情况则不同，当掣按位数增大，椭圆曲线以g 尺q ) ) 可 取的条数也大大增加，增加的速度远远超过q 的增加速度，也就是说，在同一基域上，通 一3 一 椭圆曲线密码算法的快速实现研究 过改变椭圆曲线方程的系数就能够得到更多具体的算法。 其次是椭圆曲线离散对数问题的难解性，目前对椭圆曲线有效攻击是使用p 0 1 l a r d sr h o 方法p ，它的计算需要口( 叫2 ) q 。域大小) 步，每一步运算是椭圆曲线的点加运算。假设 l m i p s ( m i i j i o n i n s t r c t i o n s p e r s e c o n d ，每秒百万次指令) 机器每秒可以执行4 1 0 4 次椭圆曲 线点加运算，则1 m i p s 计算机在年中能执行椭圆曲线的点加运算次数约为2 4 0 次吼以 有限域大小为1 9 1 位的椭圆曲线为例，使用p o l l a r d sr h o 方法计算，约需要7 2 0 0 台计算机 一年的计算能力。 再次，椭圆曲线密码体制具有最强的单比特安全性，可在保持和r s a 体制同样安全性 的条件下大大缩短密钥长度。表1 1 给出了椭圆曲线密码体制和r s a 体制在同样安全性条 件下密钥的对应长度( 单位b i t ) 。 表卜1 同样安全性条件下的r s a 与e c c 韵密钥长度之比 r s a 密钥故度e c c 密钥k 度 r s a 和e c c 密钥k = 度之比 5 1 21 0 65 ：1 7 6 81 3 26 ：i 1 0 2 41 6 0 7 ：l 2 0 4 82 1 01 0 ：l 2 1 0 0 06 0 03 5 ：1 从表中可见，就安全性而言，每l 比特椭圆曲线密码体制的密钥至少相当于5 比特r s a 密钥的安全性，并且这种比例关系随密钥长度的增长呈上升趋势，同样安全性条件下，椭 圆曲线密码体制具有最短密钥和最强单比特安全性。 目前，国外对椭圆曲线密码的研究取得了不少的成果，众多标准化组织已经或下在制 定关于椭圆曲线的标准，1 9 9 9 年a n s ix 9 6 2 标准的发布成为椭圆曲线密码标准化的一个 重要罩程碑。同年美国国家标准与技术委员会( n t s t ) 发布了新的规定确定了椭圆曲线密码 的地位。现已颁布的有关椭圆曲线密码的标准有i e e ep 1 3 6 3 、a n s ix 9 6 2 、a n s tx 9 6 3 、 i s o 1 e c1 4 8 8 8 、i e t f 、a t mf o m m 等，这将提高椭圆曲线密码技术在世界范围内的通用 性，使它在全球的广泛应用成为可能。同时也有许多厂商已经或正在开发基于椭圆曲线的 产品。 国内关于椭圆曲线在密码学方面应用的研究几乎与国外同步。1 9 8 6 年曾肯成教授酋先 在中国科学院研究生院d c s 中心组织了“椭圆曲线密码e c c ”讨论班，对它的理论和算 法进行了深入的分析。在椭圆曲线密码算法方面的研究已达到国际先进水平。截止到2 0 0 2 年，国家商用密办已认定了至少5 个商用椭圆曲线密码算法( 包括s s f 3 2 - a 算法、s s f 3 2 - b 算法、s s f 3 2 c 算法、s s f 3 2 d 算法、s s f 3 2 e 算法) ，并且开始制订椭圆曲线密码算法的 国家标准。 随着人们对信息安全技术的要求逐渐提高，椭圆曲线密码得到越来越多的重视，它已 经成为继r s a 密码之后被高度重视的公钥密码之一，一些国际标准化组织已把椭圆曲线密 码作为新的信息安全标准。现在对椭圆曲线密码技术的研究方兴未艾，在实现椭圆曲线密 一d 一 椭圆曲线密码算法的快速实现研究 码体制时仍有一些关键的问题尚待进一步研究，主要集中在以下几方面：一是椭圆曲线的 随机选取问题。一般认为要取得最佳安全性必须采用随机曲线，对随机选取的曲线，虽然 有s e a 算法能计算所选曲线的有理数点，但是产生过程比较复杂，要找到一条合适的曲线 仍不容易；二是由于椭圆曲线密码的实用要求，要提高椭圆曲线密码的实现效率就必须提 高其最耗时运算标量乘法的快速实现，但是由于椭圆曲线的群运算较为复杂，当选耿 的有限域较大时，快速实现标量乘法也就比较困难：三是椭圆曲线密码系统的实现问题。 系统的软件实现并不具备硬件电路上实现的某些优势，比如在硬件电路上实现有限域p = 2 的椭圆曲线，可以方便地以逻辑值o 、l 表示，而软件实现就相对复杂，因为微处理器是 以字节为单位计算结果的，如何提高椭圆曲线密码体制在软件上的实现效率是需要解决的 问题。 在实际应用方面，椭圆曲线密码系统被认为是下一代最通用的公钥密码系统。随着信 息技术、通信技术的不断发展，提升网络的安全性成为目前亟待解决的问题。利用基于有 限域上的椭圆曲线密码算法可实现数据加密、密钥交换、数字签名等密码方案。尤其是椭 圆曲线密码系统，基于椭圆曲线密码的数字签名将成为电子商务、电子货币等应用中的安 全性基石。各种椭圆曲线加密、签名、密钥交换的软硬件相继问世，可应用的产品有：加 密卡、数字签名身份认证、安全通讯站、i c 卡、w a p 、指纹识别系统、付费电视加密转 播等，发展前景十分广阔，必将具有无限的商业价值。 1 3 本文的工作与组织结构 我们在较为广泛地搜索和调研整理国内外关于椭圆曲线密码技术的文献和研究成果 的基础上，针对椭圆曲线密码算法的快速实现问题作了以下一些工作：第一是研究了椭圆 曲线密码算法的快速实现方法，主要包括椭圆曲线上的点加、倍点、点乘运算实现，并进 行算法设计与分析；第二是应用研究的快速实现方法，对基于椭圆曲线的密码方案进行软 件实现，利用我们的椭圆曲线密码系统，可实现密钥交换和数字签名功能。 本文的其余部分是按以下顺序组织的： 第二章中详细论述了椭圆曲线密码学基础：包括椭圆曲线的数学基础、椭圆曲线的引 入、有限域上的椭圆曲线的基本概念和理论、点的表示与群上的运算法则。 第三章我们首先研究椭圆曲线离散对数问题，对目前椭圆曲线密码体制受到的攻击进 行简要介绍，讨论椭圆曲线及其参数选取问题，详细说明了椭圆曲线密码体制中的密钥交 换和数字签名方法。 第四章中，我们首先研究椭圆曲线密码算法的快速实现问题，重点研究椭圆曲线上的 点加、倍点、点乘运算。实现椭圆曲线密码的关键是计算椭圆曲线上基点g 的倍，称为 点乘或标量乘法，它决定了椭圆曲线密码体制的运算速度。点乘运算的快速实现，可以通 过对底层运算和高层运算进行改进：对底层运算，主要通过对椭圆曲线上的点加和倍点运 一5 一 椭圆曲线密码算法的快速实现研究 算进行改进采用雅可比射影坐标来定义椭圆曲线上的点，点加和倍点运算性能都较标准 射影坐标有提高：对高层运算，主要通过对椭圆曲线点乘算法进行改进，本文采用的滑动 窗口3 n a f 算法可以有效的提高点乘运算速度。然后在前几章节基础之上，应用研究的快 速实现方法，对基于椭圆曲线的密码方案密钥交换方案e c d h 和数字签名方案e c d s a 进行软件实现，详细介绍在软件实现设计过程中涉及到的关键问题与具体的解决方法，并 拙述了系统的具体功能。 一6 一 椭圆曲线密码算法的快速实现研究 第二章椭圆曲线密码学基础 本章给出的内容是椭圆蓝线密码学的基础椭圆曲线的基础理论。其中，首先给出 作为数学基础的群、域和有限域的相关概念，然后引入椭圆曲线的基本概念和基本特性， 介绍点的表示与群的运算法则，最后给出有限域上的椭圆曲线的基本理论。本章涉及的所 有椭圆曲线理论都是椭圆曲线密码学的基础理论，是后续章节的讨论依据，所有内容均可 在文献 3 】、 2 3 】、 3 2 、 3 4 】中找到，因此在本章的叙述过程中将省略大部分理论依据的出 处。 2 1数学基础 2 1 1 群、环、域的概念 ( 1 ) 群 群g ，有时记做f g ， ，是定义了一个二元运算的集合，这个二元运算可表示为，g 中每一个序偶( 口，6 ) 通过运算生成g 中的元素- 6 ) ，并满足以下公理： a 1 封闭性：如果口和6 都褐于g ，则口6 也属于g a 2 结合律：对于g 中任意元素d 、6 、c ，口( 6 c ) = 0 6 ) c 都成立 a 3 单位元：g 中存在一个元素p ，对于g 中任意元素d ，都有d p = p 日= 口成立 a 4 逆元：对于g 中任意元素d ，g 中都存在一个元素，使得式口口= 日d = p 成立 如果一个群的元素是有限的，则该群称为有限群。并且群的阶等于群中元素的个数。 否则，称浚群为无限群。 一个群如果还满足以下的条件，则称为交换群： a 5 交换律：对于g 中任意元素口、6 ，都有。6 = 6 口成立 ( 2 )纠、 坏r ，有时记做忸，+ ，) ，是一个有两个二元运算的集合，这两个二元运算分别称为加 法和乘法，且对于r 中的任意元素口、6 、c ，满足以下公理： a 1 a 5r 关于加法是一个交换群；也就是浇，r 满足从a 1 到a 5 的所有原则。对于此 种情况下的加法群，我们用0 表示其单位元，一口表示d 的逆元 m i 乘法的封闭性：如果口和6 都属于r ，则如也属于冠 m 2 乘法的结合律：对于r 中的任意元素玑6 、c ，有口( 6 c ) = q 6 一成立 m 3 分配律：对于月中的任意元素口、6 、。，式盯0 + c ) = 动+ 船和式0 + 6 = 邪十比总 成立 一一 一一塑里塑些查塑兰鎏塑堡垄壅望堡窭 坏如果还满足以下条件，则称为交换环： m 4 乘法的交换律：对于尺中的任意元素口、6 ，有的= 6 成立 交换坏还满足以f 条件，则称为整环： m 5 乘法单位元：在r 中存在元素l ，使得对于月中任意元素口，有口l = 1 a = 日成立 m 6 无零因子：如果有r 中元素d 、6 ，且础= o ，则必有d = o 或6 = o ( 3 ) 域 域，有时记为 f ，+ ， ，是有两个二元运算的集合，这两个二元运算分别称为加法和 乘法，且对于f 中的任意元素、6 、c ，满足以下公理： a l - m 6f 是个整环；也就是说f 满足从a i a 5 以及从m 1 m 6 的所有原则 m 7 乘法逆元：对于f 中的任意元素口( 除o 以外) ，f 中都存在一个元素a ，使得式 盯a = 0 一k = 】成立 除法定义为：吖6 = d ( 6 1 ) 2 1 ，2 有限域 如果一个域的元素个数是有限的，则称该域为有限域，这旱用g h g ) 表示，有限域的 元素个数称为有限域的阶。常用的有限域是素数域g 砸) ( 9 = p ) 和二进制域g ，( 2 “) ( 口= 2 ”) 。 ( 1 ) 素数域 设p 是一个素数域，以p 为模，则模p 的全体余数的集合 o ，1 ，2 ，p 一1 ) 关于模p 的加 法和乘法构成一个p 阶有限域，并用符号g h p ) 表示。我们称p 为g 闩) 的模。对于任意 的整数日，口m o d p 表示用p 除口所得到的余数r ，0 r p 一1 ，并称这种运算为求模，的 剩余。 ( 2 ) 二进制域 阶为2 ”的域称为二进制域或特征值为2 的有限域。构成g 只2 ”) 的种方法是采用多项 式基表示法。在这种表示法中，域g 只2 ”) 的元素是次数最多为埘- 1 次的二进制多项式( 多 项式的系数耿自g f ( 2 ) = 0 ，l ) ： g f ( 2 ) = 舀m 一1 三“叫+ a 。一2 z “一2 + + d 2 z2 + 口l z + 口o ：d f 0 ，l 硌 选择一个二进制域上的脚次既约多项式( z ) ，厂o ) 的既约性意味着，g ) 不能被分解成次数 低于m 的二进制域上的多项式的乘积。域元素的加法是两个多项式系数的模2 相加。域元 一8 一 椭圆曲线密码算法的快速实觋研究 素的乘法是两个多项式相乘后取模厂( z ) 。对于任意一个二进制域上的多项式盯( z ) ，“( ：) m o d 厂( z ) 表示一个次数低于聊的余式多项式，如) 。余式多项式，可用，o ) 辗转相除日0 ) 得到，这一运算称为求模，( z ) 的余式。 2 2 椭圆曲线的引入 椭圆曲线的研究来源于椭圆积分： 这晕段x ) 是x 的二次多项式或四次多项式，这样的积分不能用初等函数来表达，为此引入 了所谓椭圆函数。 定义2 1域彤上的椭圆曲线e 由下述方程定义： e ：y 2 + 口】掣+ d 3 y = z3 + 口2 x 2 + 口4 x + a 6 其中a i ，口2 ，国，国，吼足且0 ，是的判别式，具体定义如下： = 一d ；d 8 8 d ：一2 7 d ：+ 9 d 2 d 4 d 6 d 2 = 口? + 4 口2 d 4 = 2 d 4 + 日】d 3 d 6 = d ；+ 4 d 6 哦：d ? 日6 + 4 口2 d 6 一日l 口3 d 4 + d 2 d ；一口； 2 1 ) f ) 2 ) 若三是k 的扩域，则e 上的三有理数点的集合是 e 犯) = 融，y ) 三：_ y 2 + n 1 砂+ y x3 一口2 x2 一口4 x 一= o u 如) ，其中0 。是无穷远 点。 式( z 1 ) 称为w e i e r s t r a s s 方程；我们称e 是域k 上的椭圆曲线，这是因为系数口1 ，口2 啦，“4 ，矾 均为域k 的元素，有时我们将椭圆曲线汜为彤足以强调椭圆曲线e 定义在域k 上，并称世 为的基础域。注意，若椭圆曲线定义在域k 上，则也定义在五的扩域上；条件厶o 确保椭圆曲线是“光滑”的，即曲线的所有点都没有两个或两个以上不同的切线：点。是 曲线的惟一一个无穷远点，它满足投影形式的w e i e r s t r a s s 方程( 见2 | 3 节) ；曲线e 的有 理数点是满足曲线方程且坐标x 和y 属于上的点0 ) ，并认为无穷远点是k 的所有扩域 上的有理数点。 定义2 2由w e i e r s t r a s s 方程给出的定义在域k 上的两个椭圆曲线1 和历 一9 一 椭圆曲线密码算法的快速实现研究 e 1 ：y2 + 口l 叫+ 。3 y = x 3 + 以2 x 2 + d 4 工+ 口6 e ：y2 + 动+ 西= x3 + i 2 + 瓦+ i 被称为在域k 上是同构的，若存在t f ，s ，f k 且“o ，使得变量变换 ( x ，y ) 一02 x + 删3 y + “2 船+ f ) 把方程1 变成方程易。式( 2 3 ) 的变换称为变量的相容性变换。 ( 2 3 1 定义在域k 上的一个w e i e r s t r a s s 方程 e ：y2 + 臼1 砂+ 口3 y = x3 + 日2 x2 + 口4 x + d 6 能够用变量的相容性变换来简化，这种简化的方程将应用于本文其他部分。我们将分别考 虑域k 的特征值等于2 或3 和域的特征值不等于2 或3 两种情况。 ( 1 ) 若域k 的特征值不等于2 或3 ，则变量的相容性变换 把e 变换成曲线 x 一3 d ? 一1 2 d 2y 一3 口i x盯? ! ! ! ! ! 二! ! 竺! r 百一i v2 = x 3 + 甜+ 6 ( 2 4 ) 其中吼6 k ，且判别式为= 一1 6 ( 4 d 3 + 2 7 6 2 ) 。 ( 2 ) 若域k 的特征值是2 ，则考虑两种情况。若q 0 ，则变量的相容性变换 ，一卜帮y + 竽 把e 变换成曲线 y 2 + 叫= x 3 + 似2 + 6 ( 2 5 ) 其中口，6 k ，这样的曲线称为非超奇异的，且判别式为= 6 。若q = o 则变量的 相容性变换 ( x ，y ) b + 口：，y ) 把e 变换成曲线 y2 + 叫= x 3 + 甜+ 6 ( 2 6 ) 其中，6 ，c k ，这样的曲线称为超奇异的，且判别式为= c 4 。 ( 3 ) 若域k 的特征值是3 ，则也考虑两种情况。若口? 一d 2 ，则变量的相容性变换 堡要苎堡茎兰薹兰塑坚望茎望坚窒 ) 寸卜安 叩m 妾怕 其中d 2 = d ? + 2 ，d 。= 口。一口d 3 ，把e 变换成曲线 y2 = x + 甜2 + 6 f 2 7 1 其中d ，6 k ，这样的曲线称为非超奇异的，且判别式为= 一d3 6 。著n ? ：一“，则 变量的相容性变换 g ，y ) 斗( x ，_ y + d ，x + 盘3 ) 把e 变换成曲线 y2 = z 3 + “+ 6 ( 2 8 ) 其中a ，6 e 墨，这样的曲线称为超奇异的，且判别式为= 一。3 。 2 3 点的表示与群的运算法则 2 。3 7 坐标系转换 ( 1 ) 仿射坐标 椭圆曲线e 上的一个有理点可以出满足的方程的g 以g ) 中两个元素x 、y 表示，它们 称为点的仿射坐标。无穷远点d 没有仿射坐标，为了计算方便，我们用不在上的任一点 0 ) 表示无穷远点一般当6 = 0 时取d = ( o ，i ) ，否则取0 = ( o ，o ) 。 ( 2 ) 射影坐标 如果g 只g ) 中的除法代价是相对费时的，则我们可以采用射影坐标。一个仿射点( x ) 的射影坐标由陇f 刁给出，其中 xy 舻可y 2 可 一个点的射影坐标是不惟一的，这是因为对每一个 g h g ) ( ，y ，z ) = ( 刀，刀y ，a z ) 无穷远点的射影坐标是，刀，o ) ，其中丑o 。 在实现中，输入输出采用仿射坐标，这是为了传输和存储方便，荐计算中采用射影坐 标，这样椭圆曲线上的点加运算就不需要有限域中的除法了，可以提高速度，所以需要这 两个坐标系之闯的转换函数。 仿射坐标到射影坐标：( x ，y ) 一一，儿1 ) = ，】，z ) 椭圆曲线密码算法鑫快速实现研究 射影坐标到仿射坐标：( x ，z ) 一z2 ，y z3 ) = ( x ，y ) 2 3 ，2群的运算法则 令e 是一个定义在域k 上的椭圆曲线。按照代数几何的观点，在任一椭圆曲线的儿 素之间，有一个自然的群运算法则，根据“弦和切线”法则，( 厨上的两个点相加得到( 曲 上的第三个点。简占之，记中的点( o ，1 ，0 ) 为d ，对中的任意两点p ，q e ， 定存在另 外一点尺e ，使得，此时，称点月为p 和q 的和，记为户+ q = r ，点集合e ( 固及其这种 加法运算构成一个加法交换群，就是这个群被用束构造椭圆曲线密码体制。 我们作进一步的说明，这里将域足取为实数域，d 为其单位元，按照上述法则，具体 的群运算法则如下： ( 1 )单位元：对于任意的p e ( 的，尸+ ( ) = 0 伊= j p ( 2 ) 负元素：对于任j 惑的p 联的，设j p = 0 ，则d ) + ，叫) = d 。汜点扛，叫) 为p ，并 称其为| p 的负。p 出是上的一个点，一( ) = d 。 ( 3 ) 对于一般的两点尸，q ( 固( p q ) ，设通过尸，q 的直接交曲线e 于另外的点n 则尸，q 和，是e 上的三点，且在同一直线上。现设点r 关于x 轴的对称点为r ( 见图 2 1 ) ，有p + q = r ，也就是说尸与q 的和是过p 与q 的直线与曲线e 的第三个交点 关于x 轴的对称点。 l ：辟、芗 z r 一 月= h q ； 2 4 有限域上的椭圆曲线 图2 1一般的椭圆曲线 密码体制中最感兴趣的是定义在有限域上的椭圆曲线，即瞰) = o 的系数是有限域 g f ( g ) 的元素，椭圆曲线上的点形如p = 0 ) ，x 是域元素。令g 足q ) 是表示g 个元素的有限 域，g = ，7 ，p 是素数，2l ，令联6 ：乒) ) 表示定义在觎2 ) 上的一条椭圆盥线。 定理2 1 ( h a s s e 定理)令以g f ( g ) ) 是定义在有限域g 只g ) 上的椭圆曲线，e ( g 足q ) ) 的点 椭圆曲线密鹳算法的快速实理研究 数用# 以g h q ) ) 表示，则 1 # e ( g f ( q ) ) 一g 一1 l 2 打 h a s s e 定理是对椭圆曲线阶# ( g 默日) ) 的粗略估算。区间【g + l 一2 i ，q 十1 + 2 虿 称为h a s s e 区问。h a s s e 定理的另一种描述是，若e 是定义在域g 尺g ) 上的椭圆曲线，则# e ( g 凡g ) ) = q + l 一，其中，的绝对值 ds2 拿，f 称为域g 尺g ) 上椭圆曲线的迹。因为2 9 小于譬，所以我 们有# 以g r q ) ) 。9 。 下面分别对素数域( g 是素数) 和二元域( g = 2 ”) 的椭圆曲线运算进行讨论。 2 4 1 素数域上的椭圆曲线及其基本运算 定义2 3 设g 足9 ) 为一有跟域，g 3 是一个素数。蹿，6 g 只g ) ，满足铂3 + 2 7 6 2 0 ，由 参数a 和6 定义的g 以q ) 上的椭圆曲线是方程 y2 =x3 + 删+ 6 ( 】，9 ) 本文讨论的重点是素数域上的椭圆曲线，以及建立在此类椭圆曲线基础上的密码体制， 该椭圆曲线方程的所有解0 ) ，x g 足g ) ，y e g h g ) 连同一个称为“无穷远点”( 汜为d ) 的 元素组成的点集合。联g f ( g ) ) 的点数用# 凰g h g ) ) 表示。由h a s s e 定理可知 窜+ l 一2 q # e ( g f ( 叮) ) g + 1 + 2 吁 点集合g 尺日) 对应下面的加法规则构成个群，即 ( 1 ) 0 + 0 = 0 ( 2 ) 对所有( x ) e ( g 以g ) ) ，0 ) + 0 = ( x ) ( 3 ) 对所有( 工毯瞅朔，( x 力十阮劝= 试即点扛) 的逆为伍) ) ( 4 ) ( 两个不同且不互逆的点的加法规则) 令o l 】) 日g 只g ) ) ， 2 抛) e ( g 只g ) ) 是两个满 足x i x 2 的点，则0 l 1 ) + ( 2 ) = 0 3 3 ) ，其中 j x s = a 2 ，一x ，一f ： l 一3 = a ( x l x 3 ) 一y 1 ( ) i o ) ( 5