（计算机应用技术专业论文）椭圆曲线算法研究与应用.pdf

西南交通大学硕士研究生学位论文第f 页 摘要 椭圆曲线密码体制( e c c ) 是一种新的公钥密码体制，在保证相同安全强 度的情况下，所需密钥长度较其它公钥密码体制要短的多，所以特别适用于存 储空间和运算速度受限的移动设备。目前，在许多安全标准中，都用到了e c c 。 标量乘运算是e c c 的核心，它直接决定了e c c 的实现速度。因此，椭圆曲线 密码体制的快速实现成了许多密码学专家所关心的问题。 本文的主要工作总结归纳为以下几方面： 首先介绍了椭圆曲线的数学基础和基本概念，对有限域上椭圆曲线进行基 本运算进行了讨论；通过分析对椭圆曲线离散对数问题的常用攻击算法，给出 了选取安全椭圆曲线的原则。 其次，对各种单标量乘算法进行了分析和比较，并引出了双标量乘算法。 双标量乘是数字签名的核心，它直接决定了签名的实现效率。j s f 算法是当前 最流行的计算椭圆曲线双标量乘的算法。经过测试，发现j s f 算法运算量并不 是最低的。改进后的算法可减少乘法运算的次数，从而使总的运算量达到更低， 而运算效率更高。l i u d u o s 多标量乘算法是最近才提出的计算椭圆曲线的算 法。通过结合固定窗口算法对其改进，改进后的算法通过预计算，以空间换取 时间，达到提高运行效率的目的。 最后，设计了一个基于椭圆曲线的身份认证方案，对改进前后的两个算法 进行了软件实现，并经过测试得到实验数据。通过对实验数据的分析表明，改 进后的算法在效率方法确实得到了提升。从实验结果和理论分析结果来看，效 率提升情况基本一致。 关键词：椭圆曲线密码体制；双标量乘j s f 算法；多标量乘l i u d u o s 算法 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 s y s t e m ( e c c ) i san o v e lp u b l i ck e y c r y p t o s y s t e m c o m p a r e dw i t ho t h e rp u b l i ck e yc r y p t o s y s t e m s ，i th a sam u c hs m a l l e rk e yl e n g t h w i t ht h es a m es e c u r i t yl e v e l t h u s ，i ti ss u i t a b l ef o rw i r e l e s ss y s t e ma n dd e v i c ew i t h l i m i t e ds t o r a g e sa n dc a l c u l a t i o ns p e e d i th a sb e e na d o p t e db ym a n ys e c u r l t y s t a n d a r d s a n di sg o i n gt ob ea p p l i e di nt h en o tl o n gf u t u r e t h es c a l a rm u l t i p l i c a t i o n a l g o r i t h mi st h ek e yf a c t o ro fe c c ，w h i c hc a n d e t e r m i n et h ec o m p l e t i n gs p e e d d i r e c t l v e l l i p t i c c u r v ec r y p t o s y s t e mr a p i da c h i e v e m e n tq u i c k l y b e c a m et h e r e s e a r c hf o c u so fm a n yc r y p t o l o g ye x p e r t s t h em a i nw o r k so ft h ep a p e rc a nb es u m m a r i z e da sf o l l o w s ： f i r s t i n t r o d u c e db a s i cc o n c e p ta n dm a t h e m a t i c a lk n o w l e d g e o fe l l i p t i cc u r v e b a s i cc o m p u t i n go fe l l i p t i cc u r v ei nf i n i t ef i e l d sw a st a l k i n ge i t h e r f r o ma n a l y s i s o f 撇km e t h o do ne 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 ，t h es e l e c t e dp r i n c i p l e o fs e c u r i t ye l l i p t i cc u r v ew a st a k e no u t s e c o n d f r o ma n a l y s i sa n dc o m p a r i s o no fv a r i e t yo fs i n g l e s c a l a ra l g o r i t h m s ， d o u b l e s c a l a ra l g o r i t h mw a si n t r o d u c e d d o u b l e s c a l a ri s t h ec o r eo ft h ed i g i t a l s i g n a t u r eo fe l l i p t i cc u r v ec r y p t o g r a p h y ，w h i c hd i r e c t l y d e t e r m i n e st h ee f f i c i e n c yo f t h es i g n a t u r e j s fi st h em o s tp o p u l a rm e t h o do fc a l c u l a t i n gt h ee l l i p t i c c u r v eb y d o u b l e s c a l a ra l g o r i t h m t h r o u gt e s t ，f o u n dt h a tt h ec o m p u t i n ga m o u n t o fj s fi sn o t t h el o w e s t t h ei m p r o v e da l g o r i t h mc a nr e d u c et h et i m e so fm u l t i p l i c a t i o n ，a n dt h e n r e d u c et h et o t a lc o m p u t i n ga m o u n to fm u l t i p l i c a t i o nm a k i n go p e r a t i o n m o r e e f j f i c i e n c y l i u d u o sm u l t i p l e s c a l a rm u l t i p l i c a t i o na l g o r i t h mi s an e w l yp r o p o s e d a l g o r i t h mf o rc o m p u t i n ge l l i p t i cc u r v e i m p r o v i n gm u l t i p l e s c a l a rm u l t i p l i c a t i o n a l g o r i t h mb yc o m b i n i n g f i x e dw i n d o wa l g o r i t h m c a r l t m p r o v eo p e r a t l o n a i e f j i c i e n c yt h r o u g hp r e c o m p u t a t i o n , w h i c ha c q u i r e sl i t t l et i m eb y i n c r e a s es p a c e l a s t ，d e s i g n e da l l i d e n t i f i c a t i o ns c h e m eb a s e d o n e l l i p t i c c u r v e b o t h a l g o r i t h m sb e f o r ea n da f t e ri m p r o v e m e n t o ft h es o f t w a r eh a v eb e e nt e s t e d a n a l y s i s o fe x p e r i m e n t a ld a t as h o w st h a te f f i c i e n c y o ft h ei m p r o v e da l g o r i t h m sh a s 西南交通大学硕士研究生学位论文第l il 页 h e i g h t e n e da c t u a l l y t h ee x p e r i m e n t a lr e s u l ti sc o n s i s tw i t ht h e o r e t i c a la n a l y s i so n t h ee f f i c i e n c yu p g r a d e k e yw o r d s ：e l l i p t i cc u r v ec r y p t o s y s t e m ；d o u b l es c a l a rj s fa l g o r i t h m ；m u l t i p l e s c a l a rm u l t i p l i c a t i o nl i u d u o sa l g o r i t h m 西南交通大学四南交通大罕 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规 定，同意学校保留并向国家有关部门或机构送交论文的复印件和 电子版，允许论文被查阅和借阅。本人授权西南交通大学可以将 本论文的全部或部分内容编入有关数据库进行检索，可以采用影 印、缩印或扫描等复印手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密使用本授权书。 ( 请在以上方框内打“4 ) 筹焉：j 裔嚣嬲 吼1 ；， 日期：知产，一 西南交通大学学位论文创新性声明 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作所得 的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经 发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中作 了明确的说明。本人完全意识到本声明的法律结果由本人承担。 本学位论文的主要创新点如下： ( 1 ) 改进了椭圆曲线双标量乘j s f 算法，改进后的算法可减少乘法运算的次 数，从而使总的运算量达到更低，而运算效率更高。 ( 2 ) l i u d u o s 多标量乘算法是最近才提出的计算椭圆曲线的算法。通过结合固 定窗口算法对其改进，改进后的算法通过预计算，以空间换取时间，达到提 高运行效率的目的。 学位论文作者签名： 岛呻者 日期：砌哆- 多； 西南交通大学硕士研究生学位论文第1 页 1 1 信息安全技术 第1 章绪论 随着现代通信技术和计算机技术的兴起，尤其是网络技术和全球信息高速 公路的迅猛发展，网络在信息交流和信息处理方面发挥着越来越重要的作用， 给人们生活带来了极大的方便。人类社会已经进入信息时代，每天都有大量的 信息在网络上进行传输和交换，信息安全已经不再是政治、军事、外交的特有 问题，它更普遍地存在于人们生产和生活的各个方面。人们在高科技带来方便 的同时，对信息的安全存储、安全处理和安全传输也提出了更高的要求。信息 安全技术便是解决这一问题的有效手段n 3 。 信息安全有两层含义：一是信息系统整体的安全，即信息系统安全地、可 靠地、不间断地运行，为系统中的所有用户提供有效服务；二是信息系统中信 息的安全，即系统中以各种形式存在的信息不会因为内部或外部的原因遭到泄 露、破坏或篡改。针对信息系统中信息的安全问题，人们提出了数据机密性、 完整性、可靠性和不可否认性等安全需求，这些需求可以由密码系统所提供的 几种功能来解决比1 。 1 身份鉴别：消息的接收者应该能够确认消息的来源，入侵者不可能伪装 成他人。身份鉴别通过数字签名来实现。 2 数据完整性：接收者能够验证消息在传送过程中是否被篡改，入侵者无 法用假消息代替合法消息。数据的完整性通过数字签名来实现。 3 不可抵赖性：发送者事后无法否认他曾经发送过的消息，接收者可以向 中立的第三方证实发送者确实发送了某个信息。不可抵赖性通过数字签名来实 现。 4 机密性：消息在发送者和接收者之间秘密传输，非授权人员无法获取信 息。机密性通过数据加密来实现。 1 2 密码体制 密码学理论是信息安全的基础，它是一门古老而年轻的科学，起源于古罗 马时代。但是，直到近代，密码学才真正得到了快速发展和应用。各种密码技 西南交通大学硕士研究生学位论文第2 页 术都建立在一定的密码体制之上。根据加密密钥和解密密钥是否相同，密码体 制分为对称( 私钥) 密码体制和非对称( 公钥) 密码体制。 对于对称密码体制，通信的双方必须就密钥的秘密性和真实性达成一致。 然后，他们就可以利用对称加密来确保通信数据的安全性。应用对称加密算法 设计的方案称为对称加密方案。对称加密方案要求通信的双方共同拥有同一密 钥，并且通信双方需要相信对方不会将该密钥泄漏给第三方。对称加密方案的 优点是加解密速度快。但是，它也有一个缺点，对于有n 个通信方的网络来说， 一方与网络中任何一方进行安全通信，需要( n 一1 ) ( n 一2 ) 2 个密钥。若网络较 大，即n 值较大的时候，密钥量会大增，不便于管理。所以，对称加密方案适 宜在通信方较少的网络中使用。但是，在实际应用中，通常将对称加密算法和 非对称加密算法结合起来使用。 公钥密码体制与对称密码体制不同，通信双方拥有的不是同一密钥，而是 一对密钥，包括公钥和私钥。私钥不公开，只有自己知道；公钥公开，以便同 一安全方案下的参与方都知道。应用非对称加密算法设计的方案称为非对称加 密方案。对于n 个通信方的网络来说，一方与网络中任何一方进行安全通信， 只需要保存自身的一个私钥，与其他参与方通信的时候查找相应的公钥即可， 非对称加密方案很好的解决了对称加密方案中的密钥管理问题。公钥密码体制 的安全性都是基于求解某个数学问题的困难性，通过私钥可以很容易得到公 钥，而通过公钥却很难得到私钥。 1 3 椭圆曲线密码体制 椭圆曲线密码体制( e c c ) ，最早于1 9 8 5 年由m i l l e r 和k o b l i t z 分别独立 提出，它是利用有限域上椭圆曲线有限点群代替基于离散对数问题的密码体制 的有限循环群所得到的一类密码体制。与其它公钥密码体制相比，椭圆曲线密 码体制具有两大潜在的优点：一是有取之不尽的椭圆曲线可用于构造椭圆曲线 有限点群；二是不存在计算椭圆曲线有限点群的离散对数问题的亚指数算法。 因此椭圆曲线密码系统被认为是下一代最通用的公钥密码系统。 1 4 椭圆曲线密码体制的研究背景和意义 截止目前，应用较多的且具有一定安全性又比较容易实现的公钥密码体 西南交通大学硕士研究生学位论文第3 页 制，按照其所基于的数学难题，可以分为： ( 1 ) 基于大整数因子分解问题( i f p ) 的密码体制。这类密码体制以r s a 为代 表，是目前应用最广泛的公钥密码体制。它的安全性是基于大整数因子分解的 困难性。 ( 2 ) 基于有限域离散对数问题( d l p ) 的密码体制。这类密码体制以d s a 为代 表。它的安全性是基于离散对数问题求解的困难性。 ( 3 ) 基于有限域椭圆曲线离散对数问题( e c d l p ) 的密码体制。它的安全性是 基于椭圆曲线上离散对数问题求解的困难性。 椭圆曲线密码体制与所述其它两类密码体制相比，有以下优点： 第一，安全性高：椭圆曲线密码体制是目前已知的所有公钥密码体制中每 比特能够提供最高安全强度的一种公钥密码体制，且不容易被攻破，在抗攻击 方面具有绝对的优势。 第二，带宽低，实用性强：对长消息进行加解密，这三类公钥密码系统有 着相同的带宽要求。但对于短消息，椭圆曲线密码系统所要求的带宽要低得多。 采用e c c 所设计的安全服务、数字签名和密钥交换，都是基于短消息的，要 处理的数据量小。因此，椭圆曲线密码系统有着广泛的应用前景。 第三，节省处理时间：相对于其它的公钥密码系统，椭圆曲线密码系统需 要更少的计算时间。 第四，占用的存储空间小：在提供相同的安全级别的情况下，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 相对于其它公钥密码体制，有无可比拟的优势，但是，在实现 椭圆曲线密码体制的时候仍然有一些亟待解决的问题。其中包括两个方面，一 是随机安全椭圆曲线的选取问题，二是椭圆曲线密码体制的快速实现问题。由 于标量乘法是椭圆曲线密码系统实现过程中最基本、最耗时的运算，所以椭圆 曲线密码系统的快速实现的关键就是椭圆曲线群运算中的标量乘运算。 西南交通大学硕士研究生学位论文第4 页 1 5 椭圆曲线快速标量乘算法的研究现状 椭圆曲线标量乘运算指，给定椭圆曲线上一点p 和一个大整数k ，计算 k p ，即利用加法运算将点p 与自身相加k 次。在椭圆曲线密码体制的实现中， 标量乘运算是关键。它相当于有限域中的指数运算，它的逆运算，就是求解椭 圆曲线离散对数问题( e c d l p ) 。在椭圆曲线公钥密码体制中，数据加密和数 字签名都要用到标量乘运算，因此，快速标量乘算法对研究椭圆曲线密码体制 有重要意义。 对一些特殊曲线或固定基点尸，现在已经有了较好的算法。但是对一般曲 线或随机点p ，如何快速计算护仍无一个好的方法。要快速实现椭圆曲线密 码体制有很多技术问题需要研究。例如，根据实际需求，如何选取有限域，如 何选取安全的椭圆曲线，如何表示基域中的元素，采用何种坐标系及采用何种 计算方法。另外，各种攻击算法的出现，对椭圆曲线密码体制的快速实现也构 成了很大的威胁，因此，人们必须在速度和安全之间寻找最佳的结合点。 标量乘舻的运算可以分为两个不同的层次：一是上层运算，它是将k p 的 运算化简为椭圆曲线上的点加运算和倍点运算；二是底层运算，它是点加运算 和倍点运算在椭圆曲线e ( 厢) 上展开的运算。显然，上层运算是椭圆曲线 e ( 厢) 上的运算，其运算对象是e ( 厢) 中的元素，也就是椭圆曲线群运算。而 底层运算是有限域e 上的运算，也就是有限域中的算术运算，它的运算对象 是c 中的元素。显然，为了实现椭圆曲线密码体制的快速运算，这两层都需 要优化。 目前计算椭圆曲线单标量乘的算法主要有：二进制展开法、m 进制法、窗 口算法以及目前速度最快的也最常用的仿射坐标下的完全不连接形式 ( n o n a d j a c e n t f o r m ，n a f ) 二进制法。双标量乘算法有j s f ( j o i ms p a r ef o r m ) 算法。多标量乘有s h a m i r 算法，快速s h a m i r 算法，s h a m i r - n a f 算法等。 近年来，国内外众多学者在椭圆曲线密码体制的快速算法研究方面做了大 量的工作，提出了很多方法，而且有些算法仍在不断的研究和改进之中。本文 的两个改进算法正是在前人研究成果的基础上提出的。 西南交通大学硕士研究生学位论文第5 页 1 6 章节安排 本文共四章，其章节安排如下： 第一章绪论：介绍了椭圆曲线密码体制的研究背景、意义及标量乘快速 算法的研究现状，本文所做的主要工作和章节安排。 第二章椭圆曲线密码体制的理论基础：介绍了椭圆曲线密码体制的数学 基础、基本概念和有限域上椭圆曲线密码体制的运算；讨论了椭圆曲线密码体 制的离散对数问题和针对该问题的常用的攻击方法，并根据这些攻击算法，给 出了选取安全椭圆曲线的原则。 第三章椭圆曲线标量乘改进算法：介绍了椭圆曲线密码体制的各种单标 量乘算法，如二进制算法、m 进制算法、n a f 算法和固定窗口算法，并对这 些单标量乘算法的运算量和效率进行了分析和比较。讨论了椭圆曲线密码体制 的各种多标量乘算法并提出了基于标量乘运算的两个改进算法：j s f ( j o i n t s p a r s ef o r m ) 双标量乘改进算法和l i u d u o s 多标量乘改进算法。j s f 算法是目 前计算椭圆曲线双标量乘的最经典的算法，但是经过对该算法的分析和测试， 发现其中存在一个漏洞，通过对该漏洞产生原因的分析，提出了改进算法。 l i u d u o s 多标量乘算法是最近才提出的计算椭圆曲线多标量乘的一个高效算 法，本文通过对该算法引入适当宽度的窗口算法，使其运算量达到更低，而效 率更高。 第四章改进算法的应用：设计了一个基于椭圆曲线的身份认证方案，并 对改进前后的两个算法进行了软件实现，从软件测试结果来看，改进后的两个 算法性能较改进前有不同程度的提高。 最后是全文的总结与展望，对整个论文工作进行了总结并对下一步要研究 的内容进行了展望。 西南交通大学硕士研究生学位论文第6 页 第2 章椭圆曲线密码体制的理论基础 自1 9 7 6 年公钥密码体制的概念被提出以来，各种新的公钥密码体制如雨 后春笋，相继出现。但随着数学、计算机科学及密码学的发展，很多公钥密码 体制也相继被攻破，如6 4 位d e s 已被彻底攻破，r s a 也越来越不安全，而且 随着密钥尺寸的增长，加解密速度越来越慢。1 9 8 5 年，k o b l i t z 畸1 和m i l l e r 1 利 用椭圆曲线上的点构成的阿贝尔加法群实现了公钥密码体制上的 d i l y e h e l l m a n 密钥交换算法，椭圆曲线密码体制由此开始引起了人们的广泛关 注。 椭圆曲线密码体制具有良好的安全性，它的安全性是基于椭圆曲线上离散 对数问题求解的困难性。对它的攻击难度要远远高于对有限域上离散对数和大 整数因子分解问题的攻击。椭圆曲线密码体制只需要很短的密钥长度就可以达 到离散对数问题和基于大整数因子分解问题需要较长密钥才能达到的安全强 度。椭圆曲线密码体制可提供加密及数字签名等各种安全服务，在信息安全中 有着广阔的应用前景，尤其适用于运算速度较慢、存储空间受限的设备上。 椭圆曲线是代数几何中一类重要的曲线，而在密码学中所用的都是有限域 上的椭圆曲线。通过引入无穷远点，将椭圆曲线上的点和无穷远点组成一个集 合，并在该集合上定义一个运算，从而该集合和运算构成了群。常用到的有限 域上的椭圆曲线群有两种，分别是基于有限域g ( 只) 和二进制域g ( 只。) 上的椭 圆曲线群。它们各自有不同的群元素和群运算，因此要研究椭圆曲线，必须首 先了解基础的数论知识。 2 1 无穷远点 在平面上，任意两条直线之间的关系只有两种，相交和平行。为了将这两 种关系统一，引入了无穷远点的概念。无穷远点就是两条平行直线的交点。有 了这个概念，就可以认为平面上任意两条不同的直线都是相交的，对于平行的 直线，他们的交点为无穷远点。以下是无穷远点的几个性质： 1 ) 直线上的无穷远点只有一个； 2 ) 平面上一组相互平行的直线有公共的无穷远点； 西南交通大学硕士研究生学位论文第7 页 3 ) 平面上任何相交的两直线有不同的无穷远点； 4 ) 平面上全体无穷远点构成一条无穷远直线； 5 ) 平面上所有点和所有无穷远点构成射影平面。 为了从坐标上把其它点和无穷远点都表示出来，使用齐次坐标( x ，y ，z ) ( x 、】，、z 不全为o ) 来表示平面上的点。齐次坐标点( x ，y ，z ) 和普通坐标点 ( x ，y ) 之间的转化关系为x = x z ，y = 】，z 。之所以叫齐次坐标，是因为对 于任意数p ，( p x ，p y ，p z ) 表示同一个点。而无穷远点的齐次坐标表示形式为 ( x ，y ，0 ) ，无穷远直线的方程为z = 0 。假设普通坐标系下一条直线方程为 a x + b y = c ，则在齐次坐标系下该直线的方程为必+ 6 】，= c z 。任何曲线都可 以实现方程之间的转化，而且任何曲线都包括无穷远点。 2 2 数学基础 2 2 1 有限域 有限域运算和椭圆曲线上点的运算是椭圆曲线密码体制的数学基础。因 此，如果我们要研究椭圆曲线，就不得不提到有限域，因为我们研究的是有限 域上的椭圆曲线。 定理2 1 设f 是一个非空集合，若在集合f 上定义的加法运算+ 满足下列 条件，则称 是一个群盯3 。群是由一个非空集合及一个二元运算构成的 代数系统。 1 ) 对任何a ，b f ，有a + b f ； 2 ) 对任何a ，b f ，有( 口+ b ) + c = a + ( 6 + c ) ； 3 ) 存在单位元e f ，使得对任何a f ，有a + e = e + a = a ； 4 ) 对任何a f ，存在逆元a ，使得a + a = a 。+ a = e 成立，即a = 一a 。 若集合f 满足对任意a ，b f ，有a + b = b + a ，则称 为可交换 群，也称a b e l 群。 如果集合f 中只有有限个元素，则称 为有限群。此时，把集合f 中 元素的个数称为有限群 的阶。 设 是一个群，如果群f 中存在一个元素a ，使得对群f 中的任意 元素b 都存在一个整数f 使得b = a7 ，则称 是一个循环群，元素a 称为f 西南交通大学硕士研究生学位论文第8 页 的一个生成元。 定理2 2 域陋1 是对常见的数系( 如有理数q 、实数r 和复数c ) 及其基本 特征的抽象。域由一个集合f 和两种运算共同组成，这两种运算为加法运算和 乘法运算，加法记为+ ，乘法记为。如满足下列条件，则称( f ，+ ，) 是一个域。 1 ) ( ，+ ) 是可交换群，加法的单位元称为零元素，用o 表示； 2 ) f 中的全体非零元素对乘法构成可交换群，乘法单位元用1 表示； 3 ) 乘法在加法上可分配，即对任何a ，b ，c f ，有( 口+ 6 ) c = a t 7 + b c 。 若集合f 中元素的个数有限，则称其对应的域为有限域。有限域中元素的 个数称为有限域的阶。 定理2 3 若f 是域，则f 的特征为0 或者是一个素数p 。 定理2 4 环r 关于加法是一个交换群，且是一个二元运算的集合，该二元 运算分别称为加法和乘法，且对于尺中的任意元素a 、b ，满足以下公理： 1 ) 如果a 、b 都属于灭，则幻也属于r ； 2 ) 对于r 中的任意元素a 、b 、c ，有a ( b c ) = ( a b ) c 成立； 3 ) 对于尺中的任意元素a 、b 、c ，a ( b + c ) = a b + a c 和( 口+ b ) c = a c + b c 成立： 环r 如果还满足以下条件，则称尺为交换环： 4 ) 对于尺中的任意元素a 、b ，有a b = b a 成立； 定理2 5 设是p 奇素数，( a ，p ) = 1 ，若存在整数x 满足： a 是模p 的平方剩余，否则，称口是模p 的非平方剩余。 定理2 6 令p 为奇素数，a 为一整数，引进符号 f ，a 、i l ，a 是模p 的平方剩余 t p ) i 一1 ，口是模p 的非平方剩余 x 2 兰a m o dp ，则称 ( 2 1 ) 称为l e g e n d r e 符号。 定理2 7 素数域上的椭圆曲线e ：y 2 = x 3 + a x + b ，其中a b 0 ，且 口，b ，则 拌嬲h + ( 1 + ( 掣 协2 ， 其中x ，( 言 表示l e g e n d r e 符号。 西南交通大学硕士研究生学位论文第9 页 定理2 8 若p 是素数，则 阱阱孚 3 ， 即素数域g ( c ) 中，二次剩余的个数和二次非剩余的个数各占一半。 定理2 9 旧3 ：设聊l ，m 2 ，是两两互素的正整数，聊= m l 朋2 聊女，m = m f m ， 其中i = 1 , 2 ，k 。则同余式组 x 三b l ( m o d m i ) x 三b 2 ( m o d m 2 ) 的解为 x 三b k ( m o d m ) x 三m l m i b l + m 2 m 2 b 2 + + m 女m k b 女( m o d m ) ( 2 4 ) 其中m 1 m ：三l ( m o d m ) ，江1 , 2 ，k 。 下面的推论描述了在有限域g ( ) 上，求y 2 三彳( m o d p ) 根的问题。 推论0 i ：当p 三3 ( m o d 4 ) 或p 兰7 ( m o d 8 ) ，则 丛 y = 彳4 ( m o d p ) ( 2 - 5 ) 当p 兰l ( m o d 4 ) 或p 兰5 ( m o d 8 ) ，那么有两种情况： 旦兰p+3 若a4 = l ( m o d p ) ，则y = 彳8 ( m o d p ) ； 丝p+3 p 一1 若a4 = - l ( m o d p ) ，则少= 彳824 ( m o d p ) 。 2 2 2 素数域 有限域中元素的个数称为有限域的阶。一个阶为g 的有限域f ，当且仅当 g 是一个素数p 的幂，即q = p 7 ，其中p 是一个素数并称之为域f 的特征，r 为 一正整数。当，= 1 时，称域f 为素数域，1 时，称域f 为扩域n 。 西南交通大学硕士研究生学位论文第10 页 2 3 椭圆曲线的基本概念 2 3 1 仿射坐标 椭圆曲线e 上的任意一点可以由满足e 的g ( ) 中的两个元素x 、y 表示为 ( x ，y ) ，它们称为点的仿射坐标，注意：无穷远点0 没有仿射坐标。 域k 上的仿射平面是指集合 ( x ，y ) ix ，y k ) ，表示为a 2 ( k ) 。 2 3 2 射影坐标 射影坐标是相对于仿射坐标而言的，一个仿射坐标中的点( x ，y ) 的射影坐 标为( x ，】，z ) ，其中x = x z 2 ，y = y z 3 。一个点的射影坐标不是唯一的， 因为对于每一个旯g ( c ) ，( x ，y ，z ) = ( 矛x ，l 2 z ) ，无穷远点的射影坐标 是( 刀，0 ) ，其中旯0 。 射影坐标和仿射坐标之间可以相互转换，转换的目的是为了便于计算和存 储。一般在输入输出时，采用仿射坐标，而在计算时采用射影坐标，因为采用 射影坐标计算椭圆曲线上的点加运算不需要有限域中的除法，可以提高运算效 率。 射影平面是域k 上的点的集合构成的平面。 2 3 3 椭圆曲线的定义 椭圆曲线n 2 1 不是椭圆，之所以叫椭圆曲线，是因为其表达式和计算椭圆周 长的积分表达式有相似之处，这就是椭圆曲线名称的由来。椭圆周长的积分表 达式为： 、 售 ( 2 6 ) 。4 e ( x ) 其中e ( x ) 是x 的三次或四次多项式。 椭圆曲线定义的方法有很多种，但最常用的是维尔斯特拉斯方程所确定的 平面曲线。设k 为域，域k 上的维尔斯特拉斯方程为n 3 | ： y 2 + 口l x y + a s y 2 x 3 + 口2 x 2 + 口4 x + a 6 ( 2 - 7 ) 其中口j k ，定义变量如下： b 22 口? + 4 a 2 西南交通大学硕士研究生学位论文第11 页 6 4 = 口l a 3 + 2 a 4 b 62 口3 2 + 4 a 6 b 8 = a ? a 6 + 4 a 2 a 6 一口l 口3 a 4 + a 2 a ；一a ； a = 一6 ；6 8 - 8 b , 一2 7 酲+ 9 b 2 6 4 6 6 当a 0 ，域k 上点集为： e = ( x ，y ) iy 2 + 口1 x y + a 3 y = x 3 + 口2 x 2 + 口4 x + a 6 u d ) 其中 0 ) 为无穷远点，e 为域k 上的椭圆曲线。 在密码学中，主要研究和应用的椭圆曲线有以下两种： ( 1 ) 素数域上的椭圆曲线e ( c ) y 2 = x 3 + 似+ 6 其中，口，b c ，且满足4 口3 + 2 7 b 2 0 。 ( 2 ) 二进制域上的椭圆曲线e ( 只。) 2 + x y = x 3 +2+by x y a x+ 5x 。+ 。+ 其中口，b t ，且6 0 。 2 3 4 椭圆曲线的阶 ( 2 8 ) ( 2 9 ) ( 2 1 0 ) 是包含g 个元素的有限域，设k = f q ，e k 为定义在有限域上的椭圆 曲线。e ( k ) = ( 弘y ) ex ，y k u d ) ，为e 的k 一有理点集合，它是一个有 限集，把有理点的数目记为群e ( k ) ，称之为椭圆曲线e 的阶。 2 3 5 椭圆曲线上点的阶 设点p 是椭圆曲线e 上的任一点，若存在最小的整数1 l ，使得n p = 0 ，其 中0 是无穷远点，则称n 是点p 的阶。 西南交通大学硕士研究生学位论文第12 页 2 3 6 奇异椭圆曲线 若椭圆曲线上的某一个点( 口，6 ) ，满足丢l ( 口扪= 。和善l i 口= 。，则称( 口，6 ) 为 椭圆曲线上的奇异点。 包含奇异点的椭圆曲线称为奇异椭圆曲线，不包含奇异点的椭圆曲线称为 非奇异椭圆曲线。 2 3 7 超奇异椭圆曲线 设素数域上的椭圆曲线的特征值为p ，若p 能整除g + 1 一撑e ( ) ，则这 样的椭圆曲线为超奇异椭圆曲线。 2 4 椭圆曲线上的运算 2 4 1 群运算法则 椭圆曲线上的点所定义的加法运算构成一个阿贝尔群，这个群中的运算 对应于有限域上的运算，d 为无穷远点。令e 是由式( 2 7 ) 给出的椭圆曲线， 对所有的p 、q e ，有 ( 1 ) 尸+ 0 = d + p = p ； ( 2 ) 一0 = 0 ； ( 3 ) p + q = q + p ； ( 4 ) p = ( x ，y ) ，记尸关于x 轴的对称点为p = ( x ，- - y ) 则尸+ p = 0 ，称p 与p 互为逆元，即p = 一p ； ( 5 ) 若p q ，设过点尸和q 的直线交e 于另一点尺，r 为尺关于x 轴的 对称点，则有p + o = q + p = r 。 2 4 2g f ( q ) 域上椭圆曲线的加法运算 q 是一个大于3 的素数，有限域g f ( q ) i - _ 的椭圆曲线为： y 2 = x 3 + a x + b( 2 1 1 ) 其中口，b ，x ，y g f ( q ) ，4 a 3 + 2 7 b 2 o ( m o d p ) 。满足上式的椭圆曲线上的点和 蚤鬈怒麓溢滤嘉篙熬 余，o ，冬p 一1 ，这里的加法和托麴卜：三： t 竺竺f 整除的剩 p 加。”州l 、l 吲，燧里趵加是指艟 o - s 4 g ； 西南交通大学硕士研究生学位论文第2 2 页 5 ) 刀q ； 6 ) h 是一个小整数，一般要求1 h 4 ； 7 ) fe ( c ) = n h ； 8 ) g 0 ，0 为无穷远点； 9 ) t 的范围应满足1 f 0d o k 卜km o d 2 ； k 卜k 一吒； 西南交通大学硕士研究生学位论文第2 4 页 将吒添加到s 中。 k 七一k | 2 ： ，? 卜n + 1 ； o u t p u t ( s ) 。 算法3 2 护的二进制算法： q 卜o f o r 1 f r o mn 一1d o w nt o0d o q 卜2 q i f 乃= 1 d o q 卜q + p o u t p u t ( q ) 采用二进制法计算肛共需要n 一1 次倍点运算和珂