（应用数学专业论文）椭圆曲线在密码学中的应用.pdf

摘要 椭圆曲线在密码学中的应用 专业 硕士生 指导老师 摘要 应用数学 赵昌安 姚正安教授 基于椭圆曲线上的点组成的代数系统中离散对数的难解性，n e a lk o b l i t z 1 v i c t o rs m i l l e r 独立地提出了椭圆曲线密码体n e c c ( 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 具有 良好的数学性质和丰富的理论基础，尤其适合硬件及软件的有效实现，可有效的节省带 宽和提高存储效率这些优势使得e c c 成为目前公钥密码学中的研究热点 本文首先讨论了e c c 中的点压缩问题在r 上的椭圆曲线存在标准的点压缩技术，使 得仅需原来一半的比特数来表示e c c 中的点由于在f 2 。上的椭圆曲线存在一些良好的性 质，这使得在e g g 中的点能够进一步压缩进而提出了两种不i 划的更高压缩比率的方法 在使用点压缩后，传输时仅需更少的比特或存储时仪需更少的空间，可应用于内存和带 宽受限的情形，比如无线网络或智能卡等 一般的签名方案主要有两种使用模式：一种是与h a s h 函数结合使用：另外一种是在可 恢复消息的前提下与冗余函数结合本文最后提出了一种基于e c c 的可恢复消息的签名 方案使得签名时不需使用h a s h 函数因为能够恢复消息，可用冗余函数来保证签名的安 全性其优点是明显的：能较高效率地对短消息签名，仅需更少带宽，直接在其他方案中 应用，比如密钥分配和签密等 关键词：e c c ，点压缩，可恢复消息的签名，密钥分配，签密 第i 页，共4 4 页 英文摘要 a p p l i c a t i o n so fe l l i p t i cc u r v e si nc r y p t o g r a p h y m a j o r ： a p p l i e dm a t h e m a t i c s n a m e ：z h a oc h a n g - a n s u p e r v i s o r ：p r o f y a oz h e n g - a n a b s t r a c t b a s e do nt h ed i f f i c u r yo fs o l v i n gt h ed i s c r e t el o g a r i t h mp r o b l e mo nag e n e r a le l l i p t i c c u r v e n e a lk o b l i t za n dv i c t o rs m i l l e rp r o p o s e de l l i p t i cc u r v ec r y p t o s y s t e m ，c r y p t o s y s - t e r n sb a s e do ne l l i p t i cc u r v e so f f e rt h eb e n e f i t so fg o o dr e a l i z a t i o nu s i n gh a r d w a r ea n ds o f t w d x e ，s m a l l e rb a n d w i d t h ，s m a l l e rm e m o r ya n de t c t h e s em a k ee l l i p t i cc u r v ec r y p t o s y s t e m s b ean e wp r o m i s i n g8 x e ai np u b l i c - k e yc r y p t o g r a p h y w ed e s c r i b eh o wt or e p r e s e n tt h o s ep o i n t so fe c cu s i n gt h em i n i m u mp o s s i b l en u m b e r o fb i t si nt h ef i r s tp a r t t h e r ee x i s t sac o m m o np o i n tc o m p r e s s i o ni ne c ci fw o r k i n gi ne t h en u m b e ro fb i t si st r i v i a l l yr e d u c e dt oah a l fo ft h eo r i g i n a lp o i n tr e p r e s e n t a t i o n i nt h e c a s eo ff 2 。t h e r ee x i s t sb e t t e rw a y st or e p r e s e n tt h e s ep o i n t sw i t hf e w e rt h a nn + 1b i t s w ep r o p o s et w od i f f e r e n tw a y st or e p r e s e n tt h e s ep o i n t so fe c c w h e nr e s o u r c e ss u c ha s s t o r a g eo rb a n d w i d t ha r ea tap r e m i u m ，i ti sd e s i r a b l et or e p r e s e n tt h o s ep o i n t su s i n gt h e m i n i m u mp o s s i b l en u m b e ro fb i t s s u c h i i lw i r e l e s sn e t w o r k so rs m a r tc a r d t h eg e n e r a ls i g n a t u r es c h e m e sc a nb eu s e di nt w om o d e s ：w i t ht e x th a s h i n go rm e s s a g e r e c o v e r y w ep r o p o s ean e ws i g n a t u r es c h e m eb a s e do ne c c t h a tg i v e sm e s s a g er e c o v e r y t h en e ws i g n a t u r ec a na p p l yw i t hn oh a s hf u n c t i o n ，w h i c hc o m b i n e sw i t har e d u n d a n c y f u n c t i o ni ns e c u r i t y t h ea d v a n t a g e sa r eo b v i o u s ：s m a l l e rb a n d w i d t hf o rs i g n a t u r e so fs m a l l m e s s a g e s 、a n dd i r e c ti n t e g r a t i o ni n t oo t h e rs c h e m e ss u c h8 sk e ya g r e e m e tp r o t o c o l so r s i g n c r p t i o n k e y w o r d s ：e c c ，p o i n tc o m p r e s s i o n ，s i g n a t u r ew i t hm e s s a g er e c o v e r y , k e ya g r e e - m e n t ，s i g n c r p t i o n 第i i 页，共4 4 页 第一章前言1 帚一早日l j 函 1 1 信息安全概述 随着计算机科学、通信和网络技术的向前发展，人们开始将一些现实行为在网络上实 现例如网上付款、网络投票等：或者由于地域及其他条件的限制，需要在网络上进行 信息传输和代理签名等但是我们在利用网络进行创新和实现着许多繁荣的同时，也带 来了严竣的、不可忽视的问题信息安全问题，由此而衍生了信息安全技术信息安 全( i n f o r m a t i o ns e c u r i t y ) ：是指信息的保密性( c o n f i d e n t i a l i t y ) 、完整性( i n t e g r i t y ) 和可用 性( a v a i l a b i l i t y ) 的保持保密性定义为保障信息仅仅为那些被授权使用的人获取完整性 定义为保护信息及其处理方法的准确性和完整性可用性定义为保障授权使用人在需要时 可以获取信息和使用相关的资产信息的保密性是针对信息被允许访问( a c c e s s ) 对象的 多少而不同，所有人员都可以访问的信息为公开信息，需要限制访问的信息一般为敏感 信息或秘密，秘密可以根据信息的重要性及保密要求分为不同的密级例如国家根据秘密 泄露对国家经济、安全利益产生的影响( 后果) 不同，将国家秘密分为秘密、机密和绝 密三个等级，组织可根据其信息安全的实际，在符合国家保密法的前提下将其信息 划分为不同的密级；对于具体的信息的保密性有时效性，如秘密到期解密等信息完整性 一方面是指信息在利用、传输、贮存等过程中不被篡改、丢失、缺损等，另一方面是指 信息处理的方法的正确性。不正当的操作，如误删除文件，有可能造成重要文件的丢失 信息的可用性是指信息及相关的信息资产在授权人需要的时候，可以立即获得。例如通 信线路中断故障会造成信息的在一段时问内不可用，影响正常的商业运作，这是信息可 用性的破坏不同类型的信息及相应资产的信息安全在保密性、完整性及可用性方面关注 点不同，如组织的专有技术、市场营销计划等商业秘密对组织来讲保守机密尤其重要： 而对于工业自动控制系统，控制信息的完整性相对其保密性重要得多 在现在信息安全研究领域，主要集中考虑如下问题： + 信息的保密 信息的保密就是在如何有效传递信息的同时，确保信息内容不被第三方所窃取为了 第1 页，共4 4 页 1 1 信息安全概述 达到信息保密的目的，目前人们采用两种基奉工具：对称加密系统和公钥密码系统( 也 称作非对称密码系统) 下面简单介绍信息加密，首先给山密码系统中需要的几个基本概念，消 息( m e s s a g e ) 被称为明文( p l a i n t e x t ) ，用某种方法伪装消息以隐藏它的内容的过程称为 加密( e n c r y p t i o n ) ，被加密的消息称为密文( c i p h e r t e x t l ，而把密文转为明文的过程称为解 密( d e c r y p t i o n ) 首先建立通信模型，假设通信过程中的硬件和软件方面是不会有错误 的，也就是不考虑由网络不畅通、网络的传输发生错误以及数据在进行算法处理时偶尔 的出错等所引起的信息不完整性，而主要集中考虑在人为因素导致信息被篡改或伪造等 在通信模型中，通常有四个角色： a 信息的发送者，通常称之为a l i c e b 信息的接收者，或者是验证者，通常称之为b o b c 攻击者，或者说是分析者- ( e r y p t a n a l y s t ) ，通常称之为o s c a r o s c a r - - 图获 取a l i c e 和b o b 之间的秘密，或试图使a l i c e 和b o b 接受其伪造的信息通常o s c a r 对 于a l i c e 和b o b 来说是一个敌对者 d 可信任的第三方( t r u s t e dt h i r dp a r t y ) ，或者说是可信任的部n ( t r u s t e dc e n t r e ) 他 们通常做一些发行数字证书，充当仲裁者等工作 图1 1 表明了这个通信模型 a l i c et t pb o b o s c a r 图1 1 加密和解密 + 知识的证明 知识的证明就是确认某一方拥有一些特定的不为人所知的信息( 确认的过程就是证 明) 而在证明完以后，这些特定的信息仍然不被人所知，不会泄漏而数字签名就是知 识证明中的一种，主要用来保证数据传输的完整性信息以及发送者身份的确认性、不可 否认性以及不可修改性具体来说，一般希望数字签名达到如下目的： 第2 页洪4 4 页 零鼢锇善 签名是可信的签名使文件的接收者相信签名者是慎重地在文件上签字的 签名不可伪造签名i f 明是签字者而不是其他人慎重地在文件卜签字的 签名不可熏用签名是文件的一部分，不法之徒不可能将签名移到不同的文件，【： 已签名的文件是不可改变的在文件签名以后，文件不能够改变 签名是不可抵赖的签名者事后不能够声称他没有签过名 信息的保密与知识的证明有着内在的联系，他们之间的联系就是“知识的特有性”而且 也可以看到二者的模型也有若天然的相似，图1 2 就是对信息的签名与验证的过程 a l i c e t t pb o b o s c a r 图1 - 2 信息的签名与验证 1 2 数字签名 数字签名的思想首先由d i 伍e 和h e l l h l a n 1 1 在1 9 7 6 年提出，进而到1 9 7 8 年 f n r i v e s t 、s h a m i r h a d l e m a n 在【2 1 提出了第一个公开的数字签名算法而r a l p h c m e r k l e 也声称在1 9 7 4 年就独自发现了数字签名的思想，由于当时教授其计算机安 全的老师l a n c eh o f f m a n 不能理解他的想法，最终使其放弃了这门课程他在1 9 7 8 年 才发表了他的这些成果 3 】，r a l p hc m e r k l e l 堑j 技术基于：发送者和接收者解决难题 ( p u z z l e s ) 比窃听者更容易 目前使用最广泛也是最基本的数字签名分为两大类：第一类是基于大数分解困难性 的r s a 签名方案【2 1 ；另一类是美国国家标准局( n i s t ) 所制定的d s a ( d i g i t u ls i g n a t u r e a l g o r i t h m ) 算法签名方案【4 】，其可靠性是基于在模p 中离散对数计算的困难性 数字签名目前主要有两种使用模式：文本h a s h 模式和恢复消息模式 d i f f i e r h e l l m a n 在最初提出数字签名思想的同时只是考虑可恢复消息的签名，最早 的附加性签名协议由m e r k l e 和h e u m a n 在5 1 中提出出于安全性考虑，很多签名方案为了 抵抗一些攻击( 比如已知签名攻击) ，必须对所签名的消息进行h a s h 函数变换，然后进 行签名因而目前的数字签名方案以这两种使用模式为主流 第3 页，共4 4 页 13 本文的体系结构 r s a 签名方案在两种模式下都可以使用，但是d s a 方案只能够在文本h a s h 模式下使 用n y b e r g l j r u e p p e l 在 6 】中分析了基于b 中离散对数问题的e l g a m a l 型数字签名方案， 提出了一系列的改进方案，使所有基于e 1 g a m a l 密码体制的签名方案能在恢复消息模式下 使用并存 6 】中提出在椭圆曲线密码体$ 1 j e c c ( e l l i p t i cc u r v ec r y p t o s y s t e m )由于同样 存在离散对数计算困难问题，那同样形式的e 1 g a m a i 签名方案也存在，改进后也可在恢复 消息模式下使用 从安全性及有效性来看，e c c 密码系统有着重要的应用前景，是一种可能在近期某 些方面取代r s a 等现存系统的密码系统，现已逐渐形成了研究的重点这种密码系统的诱 人之处在于安全性相同的前提下，可使用较短的私钥一般认为，在q 位有限域上的椭圆 曲线密码系统，当q 的长度为1 6 0 t f ：特时，其安全性却相当于r s a 使用1 0 2 4 l l 特模数，私 钥较短意味着所需要的带宽和内存较小，这在计算机网络应用中( 比如无线网络) 有时 候是决定性的关键 本文主要考虑了在e c c 中的点压缩问题，讨论了在马。上椭圆曲线进一步点压缩的两 种方法其研究意义是明显的：在传输过程中所需要的带宽较少，在存储时所需要的磁盘 空间较少，能够在带宽和内存受限的环境下应用，比如智能卡和无线网络中 另外提出一种基于e c c 的可恢复消息签名方案，与以往的签名方案相比，本方案有 以下特点： 由于使用e c c 密码系统，其私钥和公钥都相对较短，进而在应用中所需要的带宽和 内存都相对较少，而安全性和效率不会降低 由于修改后的方案能够在恢复消息模式下使用，因此在应用时可避免使用h a s h 函 数，特别是目前公开发现不安全的h a s h 函数 对短消息签名非常有效，只需要更小的带宽 可在其他方案中直接应用，比如应用于只需一次传输的密钥交换协议 1 3 本文的体系结构 在第一章，概述了信息安全的背景以及数字签名的基本应用，并概述了本论文的研究 工作意义在第二章，简要给出了数字签名概念及其直接应用，以及用于密码系统的有限 第4 页，共4 4 页 第章前畜 域上椭圆曲线的基本概念在第三章研究了在有限域上椭圆曲线的点压缩问题，并着重分 析了在特征为2 的有限域巾的情况在第四章讨论了e g a 巾基于e 1 g a m a l 密码体制的签名 方案，使之能够在恢复消息模式下应用并简单讨论数字签名方案在文本h a s h 模式下使用 和在恢复消息模式f 使用的区别最后分析本方案的安全性，并给出它存密码学中的一些 应用 第5 页，共4 4 页 2 1 数字签名 2 1 1 数字签名的背景 第二章预备知识 弟一旱珙亩大h 以 传统的手写签名是用来确定签名者对签署的文件应负有一定的责任生活中经常需要 签名，比如写信、在银行取款以及签署合同等等，以便在法律上能够认证、生效和核准 随着电子计算机和互联网的出现，人们的文件已经数字化。往往需要对数字化的文件进 行签署，能够在计算机中存储或者通过计算机网络传输与传统的签名相比，数字签名有 一些基本的区别 首先是进行数字签名时产生的问题对于传统签名来说，某人的签名在“物理”上就 是需要签署的文件的一部分但是数字签名并不是在“物理”上与之附在一起，所以设计 的签名算法需要将签名与所签署的文件“绑”在一起 其次是对数字签名验证时引发的问题传统验证签名的方法是将签名与可以肯定正确 的签名进行比较当然这并不是一个非常可靠的办法，相对比较容易被别人伪造而数字 签名是通过一个公开算法来进行验证因此，理论上任何一个人都能够验证签名一个安 全可靠的数字签名应该能够防止被伪造或被篡改 另外一个基本区别在于：对于一个数字签名的“复制”版本与原始的数字签名应该是 不同的，这样防止一个有效的数字签名被重用比如：如果b o b 得n a l i c e 签署的1 0 0 美元 电子支票，那么他只能够用这张支票从银行取款一次于是消息本身应该包含一些信息， 比如时间戳，防止数字签名被重用 数字签名在信息安全领域中具有重要的作用，特别是在大型网络安全通信中的密钥分 配、认证以及电子商务系统中广泛应用 2 1 2 数字签名的概念 下面讨论的数字签名都是基于公钥密码系统上的，数字签名应该包含最基本的两部 分：一个是签名算法，一个是验证算法a l i c e 能够用一个签名算法s i g 用自己的私钥对消 第6 页，共4 4 页 息( 或者称为文件) z 进行签名，而，“生的签名成9 俐能够被一个公丌的验证算法v e t 进 行验证下面给出一。个较为正式的数字签名的定义： 定义2 1 一个数字签名协议由三元组r e s i g ，饨r j 算法组成： 一g 是一个生成密钥对的概率型算法它在多项式时间内，以安全参数为输入，输出密 钥对r p ，研，其中p 为公钥，s 为私钥 一s i 9 是一个产生签名的概率型算法它在多项式时问内，以安全参数、私钥s 、以及 消息x 为输入，输出信息y ，称y 是对z 的签名用y = s i g 阮剀表示y 是消息x 的签名 一v e r 是一个对签名进行验证的算法它在多项式时间内，以公钥p 、信息z 以及它的 签名y 为输入，输出n m e 或者f a l s e ，分别代表签名是有效的还是无效的 一一个数字签名，对于一个多项式时间内的概率型攻击算法来说，它应该是安全的 一般来说，一个签名不可能是无条件安全的，既然验证算法是公开的，对于消息z ， 可以穷举所有的签名y ，最终找到满足验证关系的正确签名所以一般的数字签名只 是计算性安全的 2 1 3 数字签名的安全性 在本节中，给出一些数字签名的安全性描述，有关其安全性定义的详细描述可参 见g o l d w a s s e r 、m i c a l i 和y a o 7 ，其后有更进一步的发展 对数字签名的攻击： 1 唯密钥攻击：在这种形式的攻击中，分析者只知道签名者的公钥，也即他只能验证 消息的签名是否有效 2 已知签名攻击：在这种形式的攻击中，分析者除了知道签名者的公钥之外，还知道 一些有效的消息一签名对在现实应用中，分析者一般都能够做到这种程度的攻击 3 选择消息攻击：在这种形式的攻击中，分析者可以选择对他有利的消息，并让签名 者对其签名这种选择可以是基于他以前所获得的“知识”( 比如已知的消息一签名 对) 第7 页，共4 4 页 2 1 数字签名 对数字签名的攻击程度： 下而从低到高的给出对一个签名算法的攻击程度，它们代表了一个分析者对签名算法 的攻击有多人程度， i 的成功 1 存在性伪造：分析者至少可以对一个消息进行签名，而不管这个消息是否是他自己 选择的 2 选择性伪造：分析者可以对他选择的一个消息进行签名 3 全局性伪造：分析者虽然无法获得签名者的私钥，但他可以对任何一个消息进行签 名 4 彻底攻破：分析者可以计算出签名者的私钥 不同的应用需要不同的安全性定义有时，人们要求能够进行已知签名攻击的分析者 不能够进行选择性伪造而在另一些应用里( 例如签名者为公众服务者，比如公证员) ， 则要求能进行选择消息攻击的分析者不能够进行存在性伪造 2 1 4 典型的两类签名方案 目前有两大类签名方案广受关注：一个是基于大数分解困难问题的r s a 签名【2 ；另一 个基于离散对数计算困难问题的e l g a m a l 型数字签名| 4 】下面简要说明这两种算法并分析 其安全性 1 r s a 签名方案 假设n = p q ，其e p p 和q 都是大素数消息集合和签名集合都是磊，签名者a l i c e 的私 钥a 是一个与欧拉函数( 扎) 互素的数，且有 a b i1 m o d 妒( n ) 其中1 1 和b 是公钥，而鼽q f f 硼a 是私钥 签名过程：对任给的消息x 磊，a 5 c e 用如下定义的签名算法对x 进行签名： y = s i g ( x 1 = 。m o d 他， 验证过程：当b o b 接受到签名对( z ，g ) 后，通过如下的验证算法进行验证： v e r ( z ，y ) = t r e 甘z iy b ( m o dn ) 第8 贞共4 4 页 第：_ = 章静! 爸菇识 下面证明验证算法的正确性对r s a 签名来说，也就是签名算泫和验证算法恰好是互 逆的一对运算由 a b i1 ( m o d 妒m ) ) ， 有 a b = 曲( n ) + 1 _ 其中t 为某个整数如果z 编，有 y 6e ( z 8 ) 6 z 。( “) + 1 ( r o o dn ) ；( 。( n ) 。( m o dn ) il t x ( m o d n ) ；x ( m o dn ) 当。磊z 时，贝l j g c d ( x ，n ) l ( g c d ( x ，n ) 表示x 与n 的最大公因子) 由n = p q ，则z 只 有两种形式，要么zei p ( m o dn ) 或zij q ( m o dn ) ，其中l j p 一1 ，l i 兰q 一1 由对称性，只需分析。；i p ( r o o d ，；) 的情况： y 6 ；( x a ) 6 i ( i p ) “( m o dn ) i ( i p ) + 1 ；( i ) 。p 十( 呐+ 1 i - - - - i p ( “) + 1 ( m o dn ) 下面证明4 ( “) + 1 兰p ( m o dn ) ，由 ( n ) = ( p ) 庐( q ) = ( p 一1 ) ( g 一1 ) 而j e g c d 0 ，q ) = 1 ，所以有 ，4 e ( ( 对) 9 ( 曲；1 ( r o o dg ) 】 因而( p t 4 ( “) 一1 ) 能被q 整除，贝牺( p 口( ”) 一1 ) 能被阳= n 所整除，即得 p ( p 坤( “) 一1 ) i0 ( m o dn ) 也即 p t 4 ( 8 ) + 11p ( r o o dn ) ， 所以 y 6 i i p iz ( r o o dn ) 第9 页共4 4 页 21 数字签名 由此可知验证算法是正确的如果没有与其他机制结合起来，r s a 签名是不能抵抗已 知签名攻击的：比如分析者o s c a r 获取了一个有效的签名对( x ，y ) ，那么她就可以伪造有效 签名对( z 一，y - i ) 如果她获取到了两个有效签名对( z 。，y 1 ) 和( z 2 ，y 2 ) ，那么她就能伪造更 多的签名剥，l l 女h ( x l x 2 ，y l y 2 ) ，扛1 。i 1 ，y l 酊1 ) ，扣i 1 。2 ，玎1 驰) ，如i l z i 2 ，酊1 蚵2 ) 为了抵抗这些基本攻击，一般有两种办法：第一种办法就是在消息中含有冗余信息， 使得伪造的签名以非常小的概率对应个“有意义”的信息以这种方法使用时，因为能 够恢复出原来的消息，称之为恢复消息模式，通常对于短消息比较有效而对于比较大的 消息需要签名时，通常采用第二种办法，也就是将h a s h 函数与签名方案联合使用，先对 比较火的消息用h a s h 甬数做摘要，变成固定长度的输出，然后对这个输出进行签名这就 是文本h a s h 模式 2 e 1 g a m a l 型签名 下面介绍e l g a m a l 型的签名，是由n i s t 4 所提出的d s a 算法 假设p 是一个大素数，并且在z p 中离散对数计算问题是困难的假设口是整除p l 的大素 数，并且n 零，是模p 的g 阶元，即q 的阶为g ，a l i c e 的私钥为，公钥卢三0 4 ( r o o dp ) ， 其中p 、g 、和卢是公开的 签名过程：对任给的消息z 召，a l i c e 秘密随机选取七，其中1 k q 一1 ，签名定 义为： s i a ( x ，k ) = ( 7 ，6 ) 其中 7 = ( 舻m o dp ) r o o dq ， d = h + a t ) k r o o dq 验证过程：b o b 接收到三元组( z ，7 ，6 ) 后，首先计算 g l = x 5 m o dq 8 2 = 1 6 m o dq ， v e r ( x ，7 ，j ) = t r u e 铮( 1 p 8 2 m o dp ) r o o dq = 7 下面证明验证过程是正确的，b o b 由( x ，7 ，6 ) 先计算出如上的e 1 和e z ，然后验证 ( 酽1 伊2 m o dp ) = ( n 8 1 a ”m o d p ) m o d q 第l o 页，共“页 = ( 。( x + a t ) ”1 m o dp ) = 7m o d q 同样，如果分析者o s c a r 获取到有效的签名对( z ，y ) ，同样可以伪造其他有效的签名三 元组同r s a 一一样，不能抵抗已知签名攻击而目由于从验证函数的计算中不能够恢复出 原来的消息。，因此原始的e 1 g a m a l 签名不能够在恢复消息模式下使用，只能够t 与h a s h 函 数结合起来进行签名本文将在后面讨论在e c c 中的e 1 g a m a l 型签名，并能够恢复消息， 使之在两种模式下都能够使用 2 2 有限域 有限域是计算机科学和数字通讯领域最基本的数学工具之一下面给出有限域的概念 和有限域中的一些基本性质详细的介m 嗍 8 1 所谓有限域就是有限个元素所组成的域设1 是f 中的单位元，f 对加法是有限交换 群，所以f 中每个元素n 对加法是有限阶的，即存在正整数n ，使n o ：为0 这也是有限域与 无限域( 比如复数域、实数域及有理数域等) 不同的一个特点 f 中满足n 1 = o 的最小正整数n 叫做是有限域f 的特征 下面给出有限域中的一些结论，限于篇幅，不给出具体证明 ( 1 ) 有限域f 的特征必然是素数，从而f 必有p 元子域b ( 2 ) 有限域f 的元素个数q 必然是p 的方幂：q = 矿，从而f 是昂_ l 懿j n 维向量空间，f 的 加法群是n 个p 阶循环群的直和 ( 3 ) q 元有限域f 的非零元素全体形成的乘法群f + 是g 一1 阶循环群于是存在q f ，使 得f = b ( a ) ( 4 ) 对于每个正整数n ，存在昂唯一的一个代数闭包日( 其中q = 矿) ，它是由方 程护一o = 0 的全部解组成的集合 ( 5 ) 设b 和f 0 ，是有限域则日为l ，的子域当且仅当存在正整数f ，使q7 = q 特别 地，哆是0 m 的子域n r 1 r n n l m ， ( 6 ) 对每个扎1 ，b 【卅中必存在n 次不可约多项式f ( z ) ，并且对于f ( z ) 在日中的代数闭 包中的任一个根o ，最m = r ( 口) ；日n 第1 1 页洪4 4 页 23 有限域上的椭圆曲线 卜i 面给出有限域中一个较为常用的定义及结论： 定义2 2 设”是旷个元素的有限域，它包含有f 口作为子域，设o n ，定义 t r f 晶( 。) ；a + a 。+ 口矿+ + o 矿一1 把它称为局n 中的元素q 相对于r 的迹，也把n 曰日( 。) 简记做t r ( o ) 或者n a 下面是一个关于迹函数的重要结论： 设。是局n 中任一个元素，那么n ( o ) r 2 3 有限域上的椭圆曲线 在前面所述的离散对数问题中利用了乘法群z ，这是一个p 一1 阶的循环群取此群 的一个生成元9 ( 即g 为模p 的原根) 则z 中每个元素。均可表成n = 矿( osi p 一2 ) 由。，g 求i 即为离散对数问题 这个问题自然推广到任意有限群g 的离散对数计算困难问题d ： n e a l k o b l i t z 9 和v i c t o rs m i u e r 1 0 分别独立提出了椭圆曲线密码体制的思想就是利用 有限域上的椭圆曲线中的点按照某种运算( 即切割线法) 构成的有限交换群，也存在形 式的离散对数计算困难问题详细的介绍可参见f 1 1 1 在实数域r 上的椭圆曲线的形式如下： 定义2 3实数域r 上的一条椭圆曲线，是指实平面上由方程： e ：y 2 = 。3 十n 。+ b 给出的曲线b 其中a 和b 是实数，并且她3 + 2 7 6 2 0 由这个曲线上的全部( 实坐标) 点 和一个无穷远点0 构成的集合表示成e 俐，即： e 俐= p = 0 ，y ) r 2 l y 2 = z 3 + a x + b ) u 0 ) 在公钥密码学中，主要是使用有限域日上定义的椭圆曲线在这里主要是考虑g 是素 数p ( p 5 ) 或者q 是2 的方幂的情形 定义2 4 设p 为素数，p 5 ，有限域r 上的一条椭圆曲线是指： e ：y 2 = 护+ a x + b ( m o dp ) ， 第1 2 页，共4 4 页 第章预备如；t 其中n ，be f p 并且4 0 3 + 2 7 b 2 0 b 以e ( k ) 表示曲线e 在b 上的所有点( 加上无穷远 点0 ) 构成的集合 e ( 耳) = p = ( 口，卢) 砖：卢2 = “3 + o o + 6 ) u o ) 这是一个有限集合同样的，按照实数域中的切割线法来形式地定义两点之间的运算，得 到这个有限集合作成有限交换群，零元素为o 其中有如下的运算： 1 假设p 1 = ( z 1 ，y 1 ) ，, l j - p = ( z 1 ，一1 ) 2 ，假设p l = ( z 1 ，y 1 ) p 2 = ( z 2 ，0 2 ) ， 当1 。2 时，定义a = ( y 2 一y 1 ) ( 如一如) ： 当z 1 = 现，y l o 时，定义 = ( 3 x + o ) 2 y 1 如果p 3 = ( z 3 ，y 3 ) = b + p 2 o ，则 z 3 一a 2 。1 一z 2 ， y 3 = ( x l z 3 ) a y 1 ) 定义2 , 5 设g = 2 r * n 1 t 此时在f q 上的椭圆曲线方程为： j 矗2 ，：y 2 + x y = 3 ：3 + a 2 x 2 + 5 ， 其中n 2 ，a 6e f ；以e ( f 2 n ) 表示曲线e 在f 2 n 上的所有点( 加上无穷远点0 ) 构成的集合 下面同样给出其中点的基本运算： 1 假设只= ( x l ，乳) ，j - p = ( z 1 ，y 1 十z 1 ) 2 假设只= ( z l ，y 1 ) ，b = ( z 2 ，y 2 ) ， 当z l z 2 时，定义a = ( y 2 + 掣1 ) ( z 2 + x i ) ，肛= ( 可l z 2 + y 2 x 1 ) ( z 2 + z 1 ) 当z l = x 2 ，y l o 时，定义a = ( z + y 1 ) x 1 ，p = 。i 如果恳= ( ，驰) = 毋+ 恳o ，则 z 3 = a 2 + a + 0 2 + 14 - x 2 ， y a = ( a + 1 ) x 3 + p = ( x l + z 3 ) a + z 3 十y 1 第1 3 页，共4 4 页 2 4 本章小结 本章给出了数字签名以及数字签名安全性等密码学中的基本概念，以及有限域和有限 域上的椭圆曲线的基本概念及其简单性质，使得本论文可自成体系对于有限域上的椭圆 曲线更详细的介绍可参考 1 1 第1 4 页洪4 4 页 第二露椭麓f 曲线已的点压缩 第三章椭圆曲线中的点压缩 在有限域上的椭圆曲线e 中所有点的有限集合按照“切割线”运算，形成有限 交换群，其中存在离散对数困难问题，使其可用于公钥密码体制自从椭圆曲线中 的e 1 g a m a l 密码体制提出以来，就已成为整个公钥密码学中的热点凶为与r s a 等其他公 钥密码系统相比，椭圆曲线密码体铝t e g c ( e l l i p t i cc u r v ec r y p t o s y s t e m ) 具有所需内存 少、通信量小等无法比拟的优点 本章分析了在常用两类有限域上椭圆曲线中的点压缩问题，使得在使用e e g 时，通 信双方所需要交换的信息量减少当然为了能进行压缩后坐标的完全恢复，与原来的传输 方式相比，需要增加一定的计算量但这在带宽或存储空间受限的情形下，以不复杂的运 算量换取较多的空间资源节省是值得的 3 1 椭圆曲线密码体$ , i e c c 下面简要给出椭圆曲线密码体制模型，其加密思想类似初始的e 1 g a m a l 公钥密码体制 椭圆曲线密码体制建立在椭圆曲线上点群离散对数问题的难解性基础之上的 3 1 1 系统的建立和密钥的生成 ( 1 ) 系统的建立 选取一条计算安全的有限域上的椭圆曲线e ，记椭圆曲线e 上点的个数为l e l ，一 般i e i = h p 。其中7 l 是一个很小的数。而p 为大素数由群论知识，在f 中存在阶为p 的有限 子群，记为g 假设点p 是g 的生成元，p 的坐标用( 唧，蜘) 表示 有限域耳，椭圆曲线参数( 亦即定义椭圆曲线的域元素蚜口b ) ，点p 和阶p 是公开信 息 ( 2 ) 密钥的生成 a 1 i c e 选择私钥d 蜀，计算公钥q = 同p ( 即d 个p 相加) 在e g e 中，椭圆曲线e 、 点p 和0 都是公开的 第1 5 页共4 4 页 3 2 在昂上的点压缩 3 1 2 椭圆曲线加密体制e e e 加密过程当b o b 发送消息m 给a l i c e 时，b o b 执行如下步骤 查找a l i c e 的公开密钥q ， 将数据m 表示成一个域元素m k 在召中随机选取一个元素 计算点( z t ，y 1 ) = k p 计算点( z 2 ，y 2 ) = k q ，如果观= 0 ，则回到第3 步 计算c = m x 2 b o b 传送加密数据( z l ，y l ，c ) 给a l i c e 解密过程n a l i c e 需要解密从b o b 收到的密文( 规，y 1 ，c ) 时，a 1 i c e 执行如下步骤 使用其私钥d ，计算点( 茹2 ，钝) = d 】( z - ，y 1 ) 通过计算m = i 1 ，恢复出m 3 2 在r 上的点压缩 从安全性考虑，目前主要使用有限域b 扫3 ) 上和最m 上的椭圆益线，在f 2 m 上实现椭 圆曲线密码体制，可以得到更高的计算效率在硬件实现中尤其如此，因为硬件中存在着 用于有限域乘积的非常紧致的结构将椭圆曲线密码体制通信的有效性与利用这些实现得 到的计算效率结合起来，特别适合于在通信带宽、处理能力、可利用资源以及存储受限 的应用中这些应用包括无线通信、广播电台以及智能卡等 在椭圆曲线密码体制中，往往需要将一个点的z 坐标和y 坐标都传送给对方而要加密 的信息只是坐标的一部分，这样存在消息扩张问题另外在实际应用中，有时要求对通信 带宽有限制，需要比较短的密码传输下面讨论在椭圆曲线密码体制中可以使用“点压 缩”技术，使得传送一个点时，通信量减少近约一半当然通信量减少的代价是计算量增 加，接收方需要通过计算将点的坐标恢复出来这就是通常的标准“点压缩”技术f 1 2 1 第1 6 页，共4 4 页 第三章辅篷i 曲强搿豹点照娟 首先考虑在昂上椭圆曲线中的“点压缩”问题假设密码系统所用的基域是b ，定义 在尼上椭圆曲线如下： e ：y 2 = x 3 + a x + b ，a ，b 昂 对任给椭圆曲线上的点( z ，y 。) e ，发送方和接收方双方约定 1 如果y x 耳，且满足p 2 y l p 一1 ，则发送z 1 和1 给对方 2 如果可1 b ，且满2 = o y l p 2 ，则发送l 和。给对方 接收方收到z ，后，代入椭圆曲线方程求解y 即： y 2 = i + a x l + b ( m o d p ) 这就是相当于在b 中求解二次方程，求解出来有- ，- i , t u ”：，由。和l 来确定是i 还 是g ：这就是标准的“点压缩”技术 原来传送一个点( z ，g ) 需要2 l n p 位，但是如果用“点压缩”技术，传输一个点仅需 要l n p 十l 位，比原来减少了一半左右当p 较大时，通信量将大大减少而安全性仍没有 减低其代价是接收方仅需要一次求解开方运算，在对于通信量受限时，这往往是可以接 受的即在存储资源或传输带宽受限的情况下，以不复杂的运算量来替代通信量的减少是 值得的 3 3 在局。上的点压缩 在有限域f 2 n 上椭圆曲线玩。也有同样的标准“点压缩”技术考虑 昂2 m ：y 2 + x y = x 3 + a 2 x + 0 6 其中0 2 ，a 6 昂，对于任何一个点( 。l ，y 1 ) b 。，传送时仍可咀采用标准“点压 缩”技术，因为对应z 1 的只有两个候选值g ：和硝，仍然可以只用1 位来区别出它们这样 仅需n + 1 位来传送f 2 n 上椭圆曲线玩。中的点当然接收方需要增加计算量将坐标恢复 出来 但是对用于e c c 的点，由于在有限域易上的椭圆曲线本身存在一些良好的性质不 同的情形可以使用更少的比特表示下面讨论砖种不同的方法，可用更少的比特来传输或 表示这些点 第1 7 页共4 4 页 3 3 在足n 上的点压缩 3 3 1 有限域f 2 。的元素表示 我们的椭圆曲线建立在域马。上，因而椭圆曲线上点的表示也是基于域f 2 。上的构造 下面首先讨论利用多项式的加、乘、除和剩余来构造有限域详细的介绍可参见 8 】 令，( 。) 是f 2 上次数为n 的不可约多项式，( z ) 表示为： ，( z ) = 。“+ 厶一l x “一1 + + 危z 2 + ，l z + ，0 ，( f 2 ，0 is m 1 ) ， l i ( x ) 不能分解为f 2 上两个次数小于n 的多项式乘积有限域f 2 。由f 2 上所有次数小 于n 的多项式组成，即： f 2 n = a n - 1 x “一1 + a n - 2 x “一2 + + a l x + n o ：皿0 ，1 ) 域元素a n - 1 z ”1 + a n - 2 x “一2 + + a l x + a o 通常用长度为n 位的二进制 串0 n - 1 a 。一2 a l a o ) 表示，则 毋n =