（系统分析与集成专业论文）椭圆曲线密码算法的研究.pdf

， ， l ，0，一r 原创性声明 本人郑剿：所星翅拌新擞是本人槲的指导下，独立懒 究所取得的成果。除文中已经注明弓用的内容外，本论文不包含饪伺其他个人 或觯副彩妨魅踏鹊过盼陴懈。对在艾i ! 黼眵舴出重霸稚舶价人和集 体均已槲以嘞觉靠妨硼。棚懒商虢由= 扣帆 关于学位论文使用授权的声明 本比电全了解山东大学葡多为艟、使用学位论如捌多8 j 毛同意学良保留或 向匡莉自关部门或删敝麴暖技韵复印件和电书瓦允潮翘确埕积浠腊阅； 本撖山东大学可叻翰挺雠翻越弼险部或部分内容编入有戋嘲静戳生行检 索，可趴衬聊、缩e i 】竞尉幽貅籽锻保存沦妇科豳耐蹲啦：敝。 饴溘论文拍释断勖溃鞠砒期固 一：雄一：蛳础俨 h 山东大学硕士学位论文 摘要。 a b s t r a c t 符号说明和缩略词 第一章绪论。 目录 i l 1 1 背景和意义1 1 2 椭圆曲线密码的研究现状3 1 3 本文的主要内容和创新点4 1 4 本文的组织结构5 第二章基础知识 6 2 1 群环域_ 6 2 2 椭圆曲线理论8 2 3 椭圆曲线离散对数问题1 0 2 4 本章小结1 1 第三章模乘实现。 3 1m o n t g o m e r y 算法介绍1 2 3 2 算法分析2 0 3 3 算法的改进2l 3 4 本章小结：2 4 第四章椭圆曲线标量乘运算2 6 4 1 常见的标量乘算法2 6 4 1 1 二进制标量乘算法2 7 4 1 2m a r y 算法2 8 4 1 3 非相邻形式( n a f ) 算法2 9 4 1 4 窗口虹标量算法3 2 4 1 5 滑动窗口标量乘。3 3 4 2 点加和点倍3 5 4 2 1 点加点倍运算。3 5 山东大学硕士学位论文 4 2 2 改进的点加点倍运算序列4 1 4 3 本章小结4 4 第五章结论和将来的工作 4 5 5 1 本文的主要工作4 5 5 2 进一步的工作4 6 参考文献 致谢 4 7 5 1 一 3 2a l g o r i t h ma n a l y s i s 2 0 3 3a l g o r i t h mi m p r o v e m e n t 2 1 3 4c o n c l u s i o n ：! z i 4t h es c a r l a rm u l t i p l i c a t i o n0 1 1e c c ： 6 4 1t h es c a r l a rm u l t i p l i c a t i o n 2 6 4 1 1b i n a r ym e t h o d 2 7 4 1 2m a r y 2 8 4 1 3n a f 2 9 4 1 4w 二n af 3 2 4 1 5s l i d i n gw i n d o w 3 3 4 2p o i n ta d d i t i o na n dp o i n td o u b l e 3 5 4 2 1i n t o r d u c t i o n 3 5 4 2 2o p t i m i z e 41 山东大学硕士学位论文 4 3c o n c l u s i o n 4 4 5c o n c l u s i o na n df u r t h e rr e s e a c h 4 5 5 1c o n c l u s i o n 4 5 5 2f u r t h e rr e s e a c h 4 6 b i b l i o g r a p h y a c k n o w l e d g m e n t 4 7 ， 山东大学硕士学位论文 摘要 自从1 9 8 5 年k o b l i t z 和m i l l e r 分别独立提出椭圆曲线密码体制( e c c ) 之后， 这种公钥密码的优势逐渐被人们所认同。与另一著名的公钥密码r s a 相比，椭 圆曲线密码体制需要的密钥长度短，相同位长安全性更高，运算速度快，存储 空间占用少和带宽要求低，它的这些优势使得业内人士普遍认为e c c 将成为下 一代最通用的公钥加密算法标准。在许多安全标准如i p s e c 、w a p i 中，都包含 了椭圆曲线密码体制的使用。因此，椭圆曲线密码具有广阔的应用情景。 标量乘是椭圆曲线运算中最耗时也是最基本的运算，目前标量乘的实现 快速算法主要有二进制法、m - a r y 方法、n a f 编码、窗口法以及滑动窗口法等， 本文对这些算法进行深入的分析和研究，同时标量乘又是由点加和点倍运算组成 的，在分析不同坐标系下点加点倍运算效率的基础上，依据并行运算的思想，优 化混合坐标下点加点倍的运算序列，使得改进后的运算序列可以并行运算。本文 通过对混合坐标j a c o b i a n 坐标下点加点倍运算序列的优化，使得运算的并行性 大大提高，在使用双乘法器的情况下使点倍的运算时间由1 0 个模乘周期变成5 个模乘周期，点加的运算时间由1 1 个模乘周期变成6 个模乘周期，运算效率提 高了接近2 倍。另一方面，点加点倍运算最终可以转换为有限域上的模运算，由 于模加模减相对于模乘而言，运算比较简单而且速度较快，因此我们主要考虑模 乘运算。早在1 9 8 5 年，p l m o n t g o m e r y 提出m o n t g o m e r y 算法，其思想是在 古典归约运算中用加法和移位运算代替高成本的除法。1 9 9 6 年，k o c 对各种 m o n t g o m e r y 算法的实现方法进行了详细的分析和总结，我们对这些算法进行分 析发现两次大整数乘之间，必须先求退位因子，这在一定程度上限制了数据的并 行运算，而一个算法的并行性的优劣，在密码芯片设计中是非常重要的，我们可 以利用脉动加流水设计理念，通过增加一定的硬件资源，使之能够并行运算，使 运算速度得到成倍的提高，基于这样的思想，我们给出了m o n t g o m e r y 模乘的改 进算法，改进后的算法省去求退位因子的过程，使算法的并行性得到了很大的提 高，经分析表明在双乘法器的情况下，运算效率提高了2 倍。 关键词：椭圆曲线密码；标量乘：m o n t g o m e r y 山东大学硕士学位论文 a b s t r a c t s i n c ee l l i p t i cc u r v ec r y p t o g r a p h yw a sp r o p o s e di n d e p e n d e n t l yb yn e a lk o b l i t z a n dv i c t o rm i l l e ri n19 8 5 ，t h ea d v a n t a g eo ft h i sp u b l i ck e ye r y p t o s y s t e mh a sb e e n r e c o g n i z e d c o m p a r e dt oa n o t h e rf a m o u sp u b l i ck e ya l g o r i t h mb a s e do nr s a ，e c c a l l o w sf o rs h o r t e rk e yl e n g t h ，h a sah i g h e rs a f e t yp r o p e r t y , f a s t e rs p e e d ，a n dr e q u i r e s f e w e rs t o r a g ea n db a n d w i d t h b e c a u s eo ft h e s ea d v a n t a g e s ，m a n y p r o f e s s i o n a l st h i n k t h a te l l i p t i cc u r v ee r y p t o - s y s t e mw i l lb et h em o s tc o m m o ns t a n d a r d so fp u b l i ck e y c r y p t o s y s t e m s i nr e c e n ty e a r s ，e c ch a sr e c e i v e di n c r e a s e dc o m m e r c i a la c c e p t a n c e 弱 e v i d e n c e db yi t si n c l u s i o ni ns t a n d a r d sb ym a n ya c c r e d i t e ds t a n d a r d so r g a n i z a t i o n s s u c ha si p s e ca n d 啪ia n ds oo n s c a l a rm u l t i p l i c a t i o ni st h eb a s i co p e r a t i o ni ne l l i p t i cc u r v e c r y p t o g r a p h y i nt h i s p a p e r , t h eg e n e r a la l g o r i t h m s ( s u c ha sb i n a r ym e t h o d ，n a f , s l i d i n gw i n d o wm e t h o d a n ds oo n ) f o rs c a l a rm u l t i p l i c a t i o na r ea n a l y z e da n dd i s c u s s e d ，o nt h eo t h e rh a n d ， s c a l a rm u l t i p l i c a t i o nc o n s i s t so fp o i n ta d d i t i o na n dp o i n td o u b l e ，o nt h eb a s i so f a n a l y z i n gt h es p e e do fp o 缸a d d i t i o na n dp o i n td o u b l eu n d e rd i f f e r e n tc o o r d i n a t e s y s t e m s ，w eo p t i m i z eo p e r a t i o n si np o i n ta d d i t i o na n dp o i n td o u b l ec o m p u t a t i o ni n m i x e dj a c o b i a nc o o r d i n a t e a f t e ro p t i m i z a t i o n ，i ne a s eo ft w om u l t i p l i e r s ，p o i i l t d o u b l ew h i c hc o s t s10m o d u l a rm u l t i p l i c a t i o nt i m ec o u l db ef i n i s h e di n5m o d u l a r m u l t i p l i c a t i o nt i m ea n dp o i n ta d d i t i o nw h i c hc o s t 11m o d u l a rm u l t i p l i c a t i o nt i m e c o u l db ef i n i s h e di n6m o d u l a rm u l t i p l i c a t i o nt i m e o nt h eo t h e rh a n d ，p o i n ta d d i t i o n a n dp o i n td o u b l ec a nb ei m p l e m e n t e db ym o d u l a rm u l t i p l i c a t i o ni nf i n i t ef i e l d a s e a r l y 罄19 8 5 ，p l m o n t g o m e r yp r o p o s e dm o n t g o m e r ya l g o r i t h m ，t h i sm e t h o d r e p l a c e dt i m e - c o n s u m i n gd i v i s i o nb ya d d i t i o na n ds h i f to p e r a t i o n s i n19 9 6 ，k o c d i s c u s s e sa n da n a l y z e ss e v e r a lm o n t g o m e r ym u l t i p l i c a t i o na l g o r i t h m s w ef m dt h a ta f a c t o rm u s tb ec o m p u t e db e f o r ec o m p u t i n ga n o t h e rt w ol a r g ei n t e g e r s m u l t i p l i c a t i o n , w h i c hh a m p e r st h ep a r a l l e l i s mo fc o m p u t a t i o n ap a r a l l e la l g o r i t h mi sv e r yi m p o r t a n t i nd e s i g no fc r y p t o s y s t e mc h i p s ah i 曲- s p e e dc h i pc o u l db ed e s i g n e du s i n ga9 0 0 d p a r a l l e l i s mo ft h ea l g o r i t h m , b yi n c r e a s i n gc e r t a i no fh a r d w a r er e s o u r c e sa n du s i n g j t m i v e ( ) z n h g c d ( x ，y ) e c c r s a n a f w - n a f 符号说明和缩略词 素数 含q 个元素的有限域 有限域上的椭圆曲线 模n 环 不大于x 的最大整数 x 和y 的最大公因数 e lli p ti cc u r v ec r y p t o s y s t e m r i v e s t s h a m i r - a d l e m a ne n c r y p t i o ns c h e m e n o n l a d j a c e n tf o r m w id t h - wn o n 。a d j a c e n tf o r m 山东大学硕士学位论文 1 1 背景和意义 第一章绪论 随着计算机网络的迅速发展和广泛的应用，信息安全也越来越引起人们的 注意。一方面网络的迅速发展给人们的生活带来了极大的方便，如电子商务，电 子政务，网上银行等已经逐渐融入人们的生活之中，成为人们生活中不可缺少的 一部分。另一方面在如此高度开放的网络环境中，黑客攻击，数据被非法窃取或 篡改，个人的隐私信息泄露等网络安全问题也日益增多。如何保证计算机网络信 息的安全已成为信息化建设的一个核心问题。网络安全涉及的内容很多，其中包 括数据加密解密、签名验证、访问控制等。密码学又是保障信息安全的核心理论 和技术。密码技术已经成为保障安全电子商务、安全支付、安全通信和保密的关 键手段。 1 9 7 6 年d e f f i e 和h e l l m a n 发表的“n e wd i r e c t i o n si nc r y p t o g r a p h y 一 1 ，提出了适用于网络通信的公钥密码学思想，拉开了公钥密码学的序幕，受他 们思想的启迪，在之后的二十多年里，很多密码学家提出了各种公钥密码体制的 实现方案。在这些方案中，研究比较充分而且在国际上公认比较安全的公钥密码 主要有三种：基于大整数因子分解困难性的r s a 密码 2 ，基于离散对数问题困难 性的e l g a m a l 密码 3 ，以及基于椭圆曲线离散对数困难性的椭圆曲线密码 4 。 在1 9 7 8 年，r i v e s t 、s h a m i r 和a d e h n a n 提出了r s a 公钥密码体制，其安全性基于大 整数因子分解的数学难题。r s a 是目前使用最多的公钥密码体制。但是随着计算 机性能的提高，为了保证安全，r s a 要求密钥必须在1 0 0 0 比特以上，随着密钥 长度的增加，其计算速度大大减慢。1 9 8 5 年，e l g a m a l 提出基于离散对数问题的 公钥密码体制 3 ，称为e l g a m a l 密码体制，为了满足实际的应用需求，e l g a m a l 的方法得到了不断的改进，其中一种改进的形式就是美国政府的标准签名算法 d s a 5 1 9 8 5 年，m i l l e r 6 和k o b l i t z 7 分别独立椭圆曲线密码体制。其安全 性是基于椭圆曲线离散对数难题，而椭圆曲线上的离散对数问题( e c d l p ) 到目前 为止并不存在低于幂指数复杂性的算法。因此与r s a 相比，椭圆曲线密码体制使 用较短的密钥就可以得到相同的安全性。也就是说相同安全强度下椭圆曲线密码 山东大学硕士学位论文 需要的密钥更短，这意味着在小功耗和小集成电路空间( 如智能卡、射频卡等) 的环境中椭圆曲线密码具有更多的优势。 相对r s a 而言，e c c 有着突出的优势： ( 1 ) e c c 具有更强的安全性。 r s a 中存在着一般数域筛( n f s ) 方法 8 攻击使得其安全强度为亚指数级，而 对于椭圆曲线密码而言即使使用目前国际上公认的有效攻击方法p o l l a d p 算 法 9 ，它的安全强度仍然为指数级。著名的c e r t i c o m 的实验表明，e c c 和其它 几种公钥密码系统相比，其抗攻击能力具有绝对的优势。其中，1 6 0 位的e c c 与 1 0 2 4 位的r s a d s a 具有相同的安全强度，而2 1 0 位的e c c 与2 0 4 8 位的r s a d s a 具有相同的安全强度。由此可见，在相同的密钥长度下，e c c 所能提供的安全性 要高得多。 ( 2 ) 计算量小、处理速度快 虽然r s a 可以通过选取位长较小的公钥( 一般取3 2 比特的素数) 来提高公 钥运算速度，从而提高加密和验证的速度，但在私钥的处理上，r s a 在密钥生成 以及解密和签名等处理上速度要远远慢于e c c ，c e r t i c o m 实验已经证明，在相同 的安全强度下，e c c 运算速度可比r s a 快一个数量级。 ( 3 ) 存储空间占用小 在相同安全强度下，e c c 的密钥长度与r s a 相比要小得多，意味着它所占用 的存储空间要小得多，这对于设计密码芯片特别是在受限环境中的应用具有特别 重要的意义。 ( 4 ) 带宽要求低 当对长消息进行加解密时，e c c 与r s a 具有相同的带宽要求，但当应用于短 消息时e c c 的带宽要求却低得多，因此e c c 在无线网络领域具有广泛的应用前景。 基于e c c 的优势，人们普遍认为，e c c 会取代r s a 而成为下一代最主要的公 钥密码体制。从1 9 9 8 年起一些国际标准化组织开始了对椭圆曲线密码的标准化 工作。其中，1 9 9 8 年底美国国家标准与技术研究所( a n s i ) 公布了专门针对椭 圆曲线密码的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 山东大学硕士学位论文 之一。2 0 0 0 年8 月，i e e e p 1 3 6 3 的最后文本已被工作组通过。标准化工作的进 行必定使椭圆曲线具有更广阔的应用前景。 1 2 椭圆曲线密码的研究现状 椭圆曲线的研究早就有一百年的历史，但直到1 9 8 5 年，m i l l e r 6 和 k o b l l t z 7 分别独立提出椭圆曲线密码体制，才引起了广大密码学者的注意， 并对该密码算法的研究形成了一个热点，经过多年的努力研究，无论在理论还是 应用实践中都取得了可喜的进步，首先，在1 9 8 5 年s c h o o l 最早提出计算椭圆曲 线阶的算法 1 0 ，后来a t k i n 和e l k i e s 1 1 ，1 2 ，1 3 在此基础上做了改进也就是 s e a 算法( s c h o o f e l k i e s - a t k i n ) 算法。而后又被s a t o h 、h a r l e y 、g a u d r y 等 人迸一步改进完善，解决了生成安全椭圆曲线的难题。另一方面椭圆曲线标量乘 的运算过于复杂，速度缓慢，随着研究不断深入，椭圆曲线的实现速度不断得到 了提高。另外，这一时期人们对椭圆曲线的安全性也进行了深入的研究，取得了 显著的成果。在接下来的十多年密码学家除了研究椭圆曲线密码算法外，开始偏 向实际应用。这一时期，各种椭圆曲线加密、签名、密钥交换的硬件实现也相继 问世，如著名的加拿大c e r t i c o m 公司，该公司在椭圆曲线密码方面已经有2 0 多 年的研究和实践，其产品主要包括椭圆曲线加密技术i c 实现、低功耗设备的设 计等。该公司已经设计出多个e c c 的i p 核，其中包括c e r t i c o me c c 的i p 核。 该i p 核主要是针对具有特征2 的椭圆曲线公钥密码运算。该i p 的设计适用于低 功耗且资源有限的嵌入式设备。经实际测试性能如下，在工作频率为4 姗z 的情 况下，密钥对产生要7 6 微秒，完成一次密钥签名为1 3 0 几个微秒，完成一次签 名验证大约需要2 0 0 微秒。另外如德国的i n f i n e o n 公司于2 0 0 1 年也推出一款实 现椭圆曲线数字签名的安全芯片，其性能如下，在工作频率为5 m h z 时，完成一 次签名需要2 8 0 多毫秒。m o t o r o l a 公司也推出相应的支持椭圆曲线运算的密码 芯片，美国的r s a 公司在1 9 9 7 年也公布了包含椭圆曲线密码的引擎的工具包。 现在，无论是椭圆曲线密码理论还是实际应用方面，美国和欧洲发达国家都 处于领先地位。但是国内的密码学者对椭圆曲线密码进行了大量深入的研究，不 仅在理论方面而且在实际应用方面也取得了进步，如清华大学微电子研究所设计 完成了产品型号t h e c c 2 3 3 的密码芯片，该密码芯片支持特征值为2 的有限域中椭 山东大学硕士学位论文 圆曲线运算，经实际测试，在工作频率为i o o m h z 的情况下，每秒可以完成数字签 名4 0 0 0 次。北京天一集团也成功研制了支持高速e c c r s a 密码算法的“天芯一号 芯片，其关于e c c 的主要技术指标可以达至u1 6 0 位e c c 运算速度2 0 0 0 次秒。另外北 京华大信安科技有限公司成功研制出支持素数域运算的高速e c c 芯片，工作频率 在l o o m h z 时，1 9 2 比特的点乘运算达到每秒6 0 0 0 次。另外其他一些公司如中兴集 成等也都研究并实现了支持椭圆曲线密码算法的芯片。 1 3 本文的主要内容和创新点 由于标量乘算法是椭圆曲线密码体制中最耗时最关键的算法，所以标量乘算 法的运算效率将直接影响到椭圆曲线密码体制实现的效率。如何设计高效的标量 乘算法，是椭圆曲线密码体制中的一个重要问题。本文详细介绍分析了椭圆曲线 标量乘的几种典型实现算法，并对组成椭圆曲线标量乘的点加和点倍运算进行详 细分析，并优化运算序列，提高了他们的并行运算效率，这在实际的密码芯片的 设计中具有十分重要的意义。 在椭圆曲线密码体制中，标量乘、点加、点倍最终都可以转换为大整数模运 算，而模加模减运算相对于模乘运算又较为简单，速度也快，因此这里我们主要 讨论大整数模乘。在大整数的模乘运算中，模n 的模约运算比乘法运算a b 更 费时，因此改进模归约是提高模乘运算效率的关键。m o n t g o m e r y 算法利用完全 剩余系的性质，避免了m o dn 的除法运算，是比较有效的大整数模乘算法。1 9 9 0 年，d u s s e 改进m o n t g o m e r y 模乘算法，将其中的大整数乘法分解为较少次数的 小整数乘法，而在本文中我们重点讨论如何提高小整数乘法之间的并行运算效 率，这对提高椭圆曲线密码甚至其它公钥密码体制的运算效率都具有重要意义。 本文的主要创新点如下： 1 m o n t g o m e r y 算法是实现大整数模乘运算的最有效算法之一，是实现椭圆 曲线密码运算中的基本运算。本文详细分析m o n t g o m e r y 模乘算法实现过程，在 运算过程中，退位因子的求解，使得小整数乘法不能很好的并行进行，为了使小 整数乘法并行运算，对m o n t g o m e r y 算法进行改进，改进后的算法双乘法器的情 况下运算效率提高接近2 倍。 2 综述了实现椭圆曲线标量乘的快速算法，并对这几种算法进行了深入分 4 山东大学硕士学位论文 析和比较。 3 比较不同坐标下点加和点倍的运算效率，为了使数据能并行运算，我们对 混合坐标下雅可比坐标的点加和点倍的运算序列进行合理的调整和优化，使得在 双模乘器的情况下，点倍能在5 个模乘周期内完成，点加在6 个模乘周期内完成， 使标量乘运算与单模乘器相比较效率提高接近2 倍。 1 4 本文的组织结构 本文各章节的组织结构如下： 第一章：绪论。论述了本文的背景和意义，介绍了国内外相关领域的研究现 状，总结和概括了论文的研究内容和主要创新点。 第二章：给出论文研究的背景知识，介绍相关的数学背景知识，包括近世代 数中群、环、有限域的概念和性质，椭圆曲线密码体制中的基本概念和运算。 第三章，深入分析m o n t g o m e r y 算法的运算过程，为了提高并行运算的效率， 对算法进行改进，省略求退位因子的过程，使得并行运算效率提高2 倍。 第四章综述椭圆曲线上标量乘的计算方法，分析各种坐标下点加和点倍的运 算效率，合理调整点加和点倍的运算序列，使得并行运算效率提高2 倍。 第五章，结论和展望。在指出论文的主要创新之处的同时，也指出了论文的 不足，针对其中的不足之处，拟定了下一步的研究重点和方向。 山东大学硕士学位论文 第二章基础知识 本章将简单介绍近世代数群、环、域的基本概念和性质，同时介绍椭圆曲线 密码体制中的基本内容，有限域算数运算的有效实现是有效实现椭圆曲线密码的 重要先决条件，因为椭圆曲线上点的运算是基于有限域的算术运算。由于篇幅的 限制，更具体的内容请参考下列文献，代数 1 3 ，椭圆曲线理论参考 1 4 ，3 5 2 1 群环域 本小节主要介绍群、环、域的基本概念和性质。 定义2 1 ( 群) 设g 是一个非空集合，如果在g 上定义了一个代数运算，记 作a b ，且满足以下条件： 1 ) g 中的任意元素口，b ，c ，有a ( 6 c ) = ( 口- 6 ) c ； 2 ) g 中有一个元素e ，对g 中的任意元素a 有口e = a ； 3 ) 对于g 中任意一个元素a ，都存在g 中的一个元素b 使a b = e ； 那么g 连同它上面的运算称为一个群。 如果对任意a ，b e g ，有a b = b a ，那么群g 又称为交换群或a b e l 群。 群g 中元素的个数称为群g 的阶，记作lgi 。如果lgl 为一有限数，s u g 称为 有限群，否则称为无限群。 设a g ，若存在最小的有正整数n 使得a n = e ，则称a 的阶为n ；否则规定a 的阶为。 定义2 2 设g 是群，g 是一个循环群如果存在一个元素a ，使得 = g ，如 果这样的a 存在那么a 叫作g 的生成元。 注意：循环群的子群也是循环群。并且设循环群的阶位n ，那么对于n 的每 一个因子d ，g 中都存在一个循环子群阶为d 。 定义2 3 设r 是非空集合，在r 上定义了两种代数运算，加法记为a + b ，乘 法记为a b ，则称r 是一个环，如果满足： 1 ) r 对加法是一个交换群； 2 ) 乘法的结合律； 6 山东大学硕士学位论文 3 ) 乘法对加法的分配律。 一个无零因子的交换么环，称为整环。 全体整数集合z 在加法和乘法运算下构成一个整环。模1 3 的整数集合z n 构 成一个环，记为z n z 。 定义2 4 设r 为一个整环，如果存在r 的乘法半群r 术= r 一 0 ) 到自然数系n 的一个函数d ( x ) ，使得对于任一对元素，a ，b r ，b 0 ，存在一对元素q 和r ： 满足：a = q b + r ；，其中r 0 或r = o ，但d ( r ) d ( b ) ，则r 称为一个欧几里得整环。 整数环z 和域f 上的一元多项式环f x 】，都是欧几里得整环。当i n - - 一l ，一2 ，一3 ， 一7 ，一1 l 时，虚二次数域q 【聊】上的代数整数环r 。是欧几里得整环。 定义2 5 设f 是有两种代数运算的非空集合，加法记为a 十b ，乘法记为a b ， 如果满足： ( 1 ) f 对加法是一个交换群； ( 2 ) f * = f - 0 ) 是一个交换乘法群； ( 3 ) 乘法对加法符合分配律； 则称f 是一个域。 域f 的单位元l 在加法群中的阶，称为域f 的特征，通常记为z ( f ) 。特征 为p 的有限域必定包含一个与素数域z p z 同构的子域：特征为0 的域( 单位元1 在加法群中是无限阶的) ，必定包含一个与有理数域q 同构的子域。 定理2 6 ( 欧拉定理) 设n 和x 是整数且x 与n 互素，那么有x 9 ( ) 暑l ( m o d 忉， 其中9 是欧拉函数。 定义2 7 一个环k 是交换环，且其上的非零元都是可逆的，那么k 是一个域。 定义2 8 设k 和l 都是域，如果存在一个k 到l 的同态，那么我们说l 是k 的一个扩域。这样的扩域表示为l k 。 定义2 9 如果域的阶是有限的，它就叫做有限域。有限域也被称为加罗瓦域。 定理2 1 0 对任意的素数p 和整数d ，都存在一个有限域，其中的元素个数 为9 2 p 。这样的域都是同构的，可表示为c 或者是g f ( q ) 。 注意，如果c 是有限域，那么f ，就是一个循环群。 7 山东大学硕士学位论文 2 2 椭圆曲线理论 椭圆曲线密码体制是由m i l l e r 和k o b l i t z 分别独立提出的，是基于椭圆曲 线上的离散对数问题的。本小节中我们给出有关椭圆曲线的基本概念和性质。 定义2 2 1 域k 上的椭圆曲线e 由下述方程定义： e ：y 2 + a l 砂+ a 3 y = x 3 + a 2 x 2 + q 4 x + a 6 其中a i , a 2 ，a 3 ，a 4 ，a 6 ，k 且0 ，是e 的判别式，为了使椭圆曲线是非奇异的， 需要满足f ( x ，y ，z ) = 0 在任何点上，其偏导数不为0 ，具体定义如下： = - d 2 2 d g - 8 d 4 32 7 d 6 2 + 9 d 2 d 4 d 6 d 2 = q 2 + 锄2 d 4 = 2 a 4 + a l a 3 d 6 = a 3 2 + 4 口6 d 3 = a 1 2 a 6 + 4 a 2 a 6 一a , a 3 a 4 + a 2 a 3 2 一a 4 2 若l 是k 的扩域，则e 上的l 有理数点的集合是： e ( ) = ( 工，y ) 工三：y 2 + 口1 砂+ a 3 y - x 3 - a 2 x 2 a l x - a 6 = o ) u o ) ，其中o 是无 穷点。 椭圆曲线e 的维尔斯特拉斯形式为：y 2 = x 3 + a x + b ，a ，b 是常数，另外还 要附加条件4 a 3 + 2 7 酽o 。 椭圆曲线通常定义在有限域上。f 是个特征值不等于2 或3 的有限域，若 x ，y ，a ，b 都在f 中，则称曲线e 定义在f 上，e 可以用以下点集形式表示： e ( f ) = ( x ，y ) e f , f iy 2 = x 3 + a x + b ) u o ) 其中o 是无穷远点。 设e 是素数域上的椭圆曲线，p 和q 是e 上的两个点。我们通过以下法则 来定义椭圆曲线上的运算。 给定椭圆曲线上两个不同点鼻( x 。，y 。) 和q ( x ：，y ：) ，我们通过下面的方法进 行点加运算，几何特性如图2 1 所示： 置 山东大学硕士学位论文 】j 一。 厂 一，一，一 、 ，7 k 尹弋 _ 图2 1 椭圆曲线点加几何特性：r = p + q 做一条直线l 通过p 和q ( 两者都不是无穷远点) 。则l 会与曲线交于第三点 r ，过点r 做x 坐标轴的垂线交椭圆曲线于另一点r 则r = p + q 。 如果p 是无穷远点o ，那么- p = 0 ，p + q = q 。于是，o 就是加法群中的 单位元( 即零元) 。所以下面的讨论中，假设p 和q 都不是无穷远点。 一p 就是保持其x 坐标不变，y 坐标取相反数，即一( x ，y ) = ( x ，一y ) 。明显， ( x ，一y ) 仍然在原椭圆曲线上。 同样，我门业可以得到，如果q = 一p ，那么p + q = 0 。 当p = q 时就是椭圆曲线点倍运算，其几何特性如图2 2 所示： 】j p “厂 l 一擎 图2 1 椭圆曲线点倍几何特性：r = 2 p 9 山东大学硕士学位论文 在几何上表现为p 点的切线，切线与椭圆曲线e 交于r 点，该交点关于 x 轴的对称点为r ，臣 i r = p + p = 2 p 这样的话，椭圆曲线上的点加上无穷远点就构成了一个点群。 椭圆曲线上的点加运算和有限域上点的集合构成阿贝尔群。 椭圆曲线标量乘运算是基于点加的运算，是椭圆曲线中最关键也是最为耗时 的运算。 已知一个点q = k p 与p ，求k 是很困难的，这一性质在密码学中得到运用， 这是e c - e 1 g a m a l 体制的基础。 设e 是定义在域上的椭圆曲线。椭圆曲线e ( ) 的点的个数称为域上 椭圆曲线e 的阶，记为# e ( ) 。h a s e s 定理给出了# e ( ) 的界限定理。 h a s s e 定理设e 是定义在有限域c 上的椭圆曲线，则有 q + l 一2 留e 0 艺) g + 1 + 2 g 区间 g + 1 一撕，q + l + 2 , f q ，称为h a s s e 区间。若e 是定义在域上的椭圆 一 曲线，则 f j e ( f q ) = q + l t ，其中，t 的绝对值l f l i 。r 是与m 互素的基数，通常r = 2 ，w 为整数。则存 在r 1 和m ，满2 ：o r 一1 m ，o m r j i r r 一m m - l 。给定大整数t ，其中0 t r m 。 输出：t r m o d m 。 1 g = ( t m ) r o o d r 2 p = ( r + q m ) r 3 i fp mt h e n 尸= p m 4 r e t u r np 证明如下：设r 是与m 互素的整数，记为( r ，m ) = 1 ，则存在r - 1 和m ，满足 o r - 1 m ，o m ， r 且足足一一 n ，= 1 即m m + 1 = 0 r o o