（计算机系统结构专业论文）椭圆曲线密码体制的研究与实现.pdf

上海交通大学硕士学位论文 摘要 f ( 椭圆曲线密码体制，即基于椭圆曲线离散对数问题的公钥密码体制最早于 1 9 8 5 年由m i l l e r 和k o b l i t z 分别提出，它是利用有限域上的椭圆曲线有限群代 替基于离散对数问题密码体制中的有限循环群后所得到的一类密码体制。与r s a 密码体制相比，椭圆曲线密码体制不存在计算椭圆曲线有理点群的离散对数问题 的子指数算法，因此在同等安全的前提下，椭圆曲线密码体制具有密钥长度短、 计算数据量小、运算速度快、灵活性好的优点：另外，椭圆曲线密码体制有取之 不尽的椭圆曲线可用于构造椭圆曲线有理点群。这些优点使得椭圆曲线密码成了 、 近年来密码学中的一个研究热点n 一 本文主要讨论了椭圆曲线公钥密码体制及其相关算法，包括有最优扩域上的 运算算法及椭圆曲线上的算法。主要内容如下：椭圆曲线上的基本算法及有限域 上的四则运算。椭圆曲线上点的大数倍数的有效算法。对椭圆曲线密码的攻击及 适合密码体制的安全椭圆曲线的讨论。全文由五章组成，第一章主要介绍了椭圆 曲线密码研究的背景、意义和现状。第二章给出了公钥密码的基本概念和基本理 论，并着重给出了椭圆曲线密码体制的基本理论，第三章研究了椭圆曲线离散对 数问题的一般求解方法和特殊求解方法。第四章研究了椭圆曲线密码体制的实现 方法，包括有最优扩域的定义，最优扩域上基于多项式的运算，椭圆曲线的有效 选取算法，点的加法和乘法运算、f r o b e n i u 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 ) ，t h ep u b l i c k e yc r y p t o s y s t e mb a s e do ne l l i p t i c c 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 ( e c d l p ) ，w a sf i r s tp r o p o s e di n1 9 8 5i n d e p e n d e n t l y b yv i c t o rm i l l e ra n dm e a lk o b l i t z ，i nw h i c h t h ef i m i t ec y l i cg r o u pi sr e p l a c e db yt h e g r o u po f p o i n t so n a l le l l i p t i cc h i l ed e f i n e do v e raf i n i t ef i e l d t h em a i na t t r a c t i o no f e l l i p t i cc u r v ec r y p t o s y s t e mo v e r r s ai st h a tt h eb e s ta l g o r i t h mk n o w nf o rs o l v i n gt h e u n d e r l y i n g h a r dm a t h e m a t i c a l p r o b l e mi ne c c 限c d l p ) t a k e sf u l l ye x p o n e n t i a l t i m e t h i sm e a n st h a t s i g n i f i c a n t l ys m a l l e rp a r a m e t e r sc a nb eu s e di ne c ct h a ni n r s a ，b u tw i t he q u i v a l e n t1 e v e l so fs e c u r i t y b e s i d e s 血i s 、t h e r ea r en u m b e r l e s se l l i p t i c c u r v e st h a tc a nb eu s e dt oc o n s t r u c t 也eg r o u po f p o i n t so na ne l l i p t i cc n r v e s ot h e s e a d v a n t a g e s m a k e e l l i p t i c c u r v e c r y p t o s y s t e m b e c o m ear e s e a r c hf o c u so f c r y p t o g r a p h yi nr e c e n ty e a r s w em a i n l yd i s c u s s e s e l l i p t i c c u r v ec r y p t o s y s t e ma n dt h er e a t e da l g o r i t h m s , i n c l u d i n g ：也eb a s i ca r i t h m e t i co p e r a t i o n s n o to n l yo v e ro p t i m a le x t e n s i o nf i e l d sb u t a l s oo nt h ee l l i p t i cc u r v e t h em a i nc o n t e n ti s ：w a y so fe f f i c i e n t l yi m p l e m e n t i n g 也e b a s i c o p e r a t i o n o f a d d i n g a p o i n t t oi t s e l fa l a r g e n u m b e ro ft i m e s 0 0 i n t m u l t i p l i c a t i o n ) ：k n o w na t t a c k so ns y s t e m sb a s e do ne l l i f i t i c c u r v e s ad i s c u s so nt h e g e n e r a l i z a t i o no f s e l e c t i o no fs u i t a b l es e c u r ec i i i v c st oi m p l e m e n tc r y p t o s y s t e m t h i s p a d e ri sc o n s i s t e do f f i v ec h a p t e r s i nc h a p t e r1w e b r i e f l ys u i w c ys o m ei n t r o d u c t i v e m a t e r i a l s i n c l u d i n g t h em o t i v a t i o n sa n dt h e d e v e l o p m e n t so f 也ee l l i p t i c c u r v e c r y p t o s y s t e m s w eb e ：g i n i n c h a p t e r 2w i t ha ni n t r o d u c t i o nt o p u b l i c k e y c r y p t o g r a p h ya n dg i v e sas u m m a r yo f t h er e l e v a n tt h e o r yo f e l l i p t i cc u r v e so v e rf i n i t e f i e l d st h a tw es h a l ln e e d i nc h a p t e r3 ，t h ee l l i p t i cc u r v ed i s e r e t el o g a r i t h mp r o b l e m s a r ed i s c u s s e d w ed e m o n s t r a t eh o wt h el o g a r i t h m p r o b l e m i ns o m eg r o u p s ，i n c l u d i n g s i n g u l a re l l i p t i cc u l - v e s c a l lb ee f f i c i e n t l yr e d u c e d t ot h el o g a r i t h mp r o b l e mi naf i n i t e f i e l d i nc h a p t e r4 ，w eg i v et h ew a y so fe f f i c i e n t l yi m p l e m e n t i n gt h ee l l i p t i ct u l l e c r y p t o s y s t e m s ，i n c l u d i n g ：t h e d e f i n i t i o no f o r i r i t u a l e x t e n s i o n f i e l d s ( o e f ) ，t h e p o l y n o m i a lm a t h e m a t i c so v e ro e f ；w a y so fs e l e c t i n gg o o de i i i p t i cc u r v es u i t a b l et o i m p l e m e n tc r y p t o s y s t e m s ；p o i n ta d d i t i o na n dm u l t i p l i c a t i o n ；f r o b e n i u se x p a n s i o n ；a n d s o m ee l l i p t i cc u r v e c r y p t o s y s t c m i nc h a p t e r5 ，w eg i v e t h e s u m m a r ya n ds o m e s u g g e s t i o n k e yw o r d s ：e l l i p t i cc u r v e ，e l l i p t i c c u r v ec r y p t o s y s t e m ，e l l i p t i cc u r v ed i s c r e t e l o g a r i t h mp r o b l e m , o p t i m a le x t e n s i o nf i e l d s 上海交通大学卿j 士学位论文 第一章绪论 1 1椭圆曲线密码的研究背景和意义 密码学是一门研究信息安全且跟数学密切相关的学科它有古老和悠久的历史，早 在2 0 0 0 多年前，就出现了著名的恺撒密码，而公钥密码学则始于1 9 7 6 年d i 伍e 和h e l l m a n 于1 9 7 6 年发表了密码学新方向 1 】，开创了公钥密码学的新纪元；同时，r m e r k l e 于1 9 7 8 年也独立提出了公钥理论。公钥理论最大特点是采用两个密钥把加密密钥和解密密钥分 开。自公钥密码体制的思想问世以后，人们提出了大量公钥密码体制的实现方案。所有这 些方案的安全性都是基于求解某个数学难题( 或单向陷门函数) 。在这些方案中，绝大部 分要么被攻破，要么太复杂而难以实现，截止目前，具有一定安全性能又能比较容易实现 的体制按照所基于的数学难题分类，有如下三类： 1 基于太数分解问题的公钥密码体制，典型代表有r s a 体制。 2 基于有限域上离散对数问题的公钥密码体制，其中主要包括e i g a m a l 类加密体制 和签名方案，d i f f i e h e l l m a n 密钥交换方案等。 3 + 基于椭圆曲线离散对数问题的公钥密码体制。其中包括椭圆曲线型的 d i 衢e h e l l m a n 密钥交换方案，椭圆曲线型的m q v 密钥交换方案；椭圆曲线和数 字签名算法，椭圆曲线型的n y b e r g r u p p e l 签名方案等。 椭圆曲线是一种代数曲线，它从1 7 世纪以来就被许多数学家研究，1 9 8 5 年k o b l i t z 2 1 和m i l l e r 3 最早分别独立地提出了椭圆曲线密码体制基于椭圆曲线离散对数问题的公钥 密码体制：椭圆曲线密码体制( e c c - - - e l l i p t i c c u r v ec r y p t o s y s t e m ) 是利用有限域上的椭圆曲 线有限群代替基于离散对数问题密码体制中的有限循环群所得到的一类密码体制。 在椭圆曲线密码体制最初被提出后，有许多人开始致力于研究椭圆曲线密码体制的强 度及各种实现。1 9 9 0 年，m e n e z e s 利用个别特殊曲线来实现椭圆曲线密码体制，这种曲 线不仅其点数可直接算出而且实现起来非常快。但这一情况未持续多久。因为很快在1 9 9 1 年m e n e z e s ，o k a m o t o 和v a n s t o n e 4 发现了一种有效的攻击椭圆曲线离散对数问题的方法 ( 一般称为m o v 方法) ，这种方法能够把一类被称作是超奇异( s u p e r s i n g u l a r ) 的椭圆曲线在 多项式时间内约化到该椭圆曲线基域的某个次数较低的扩域上，进而可利用已有求解离散 对数问题的算法对其求解；但是很快地，m i y a j i 找到了使椭圆曲线不受m o v 方法攻击的 条件。1 9 9 1 年，k o y a m a ，m a u r e r ，o k a m o t o 和v a n s t o n e 提出了基于环z 。上椭圆曲线的类 r s a 密码体制及三个新的单向陷门函数：1 9 9 2 年，v a n s t o n e 提出了基于椭圆曲线的类d s a 签名机制，简称e c d s a ( e l l i p t i cc u r v ed i g i t a ls i g n a t u r ea l g o r i t h m ) ；1 9 9 3 年，d e m y t k o 提 出了一种新的基于环z 。上的椭圆曲线的类r s a 密码体制；同时，s c h o o t 5 于1 9 8 5 年提 出的计算椭圆蓝线有理点个数的算法，在1 9 8 9 年到1 9 9 2 年之间，a t i k i n 和e l k i e s 6 对其 作出了重大改进：而后又在c o u v e r g n e s ，m o r a i n ，l e r c i e r 等人的完善下，到1 9 9 5 年时人 上海交通大学硕士学位论文 们已能够较容易地计算出满足密码要求的任意椭圆曲线有理点的个数，椭圆曲线有限群阶 的计算，进而可以随机地选取椭圆盐线来实现椭圆曲线密码体制。】9 9 7 年，s m m 7 和 s a t o h ，a r a k i 分别提出了对一类“畸型”椭圆曲线( a n o m o l u sc u r v e ) 的多项式时间的攻 击算法；1 9 9 8 年，s e m a e v 8 对“畸型”椭圆曲线提出了另一种多项式时间的攻击算法。 这么多人研究椭圆曲线密码体制，那椭圆曲线密码体制到底有何优点呢，这主要体现 在如下两方面： 1 基于椭圆曲线有理点群的离散对数问题比有限域上的离散对数问题计算上更复 杂，至今还没有子指数时间( s u b e x p o n e n t i a l t i m e ) 的算法来解决椭圆曲线有理点群上 的离散对数问题： 2 椭圆曲线有理点群的结构使得密码体制的参数选择更加灵活，有限域上的椭圆曲 线提供了足够多的有理点群，并且这些有理点群能够较容易得计算出来。 而另一方面，随着数学与计算机科学的发展，人们对大数分解问题的能力、求解有限 域上离散对数问题的能力却在不断提高。这对于基于这两类数学困难问题的r s a 体制和 e l c a m a 体制是严重的威胁，为保持这些体制的安全性，迫使r s a 体制中使用的模数和 e l c a m a 中有限域的大小越来越大，对这两类体制，过去5 1 2 比特太小的密钥已足够安全， 但目前一般不得不使用1 0 2 4 比特或2 0 4 8 比特大小的密钥。因此，在同等安全的前提下， 椭圆曲线密码体制的密钥长度比r s a 体制、e l c a m a 体制下的密钥长度要小的多。一般的， 对椭圆曲线密码体制，1 6 0 比特长的密钥所具有的安全性和前两类体制中1 0 2 4 比特长的密 钥所具有的安全性相当，2 1 0 比特与2 0 4 8 比特相当等，这些特点使得椭圆曲线密码体制特 别适合那些计算能力及存储空间有限制的安全应用，如s m a r t 卡，无线设备。椭圆曲线密 码体制的优势逐渐地突现了出来。在这样一种背景和椭圆曲线密码理论逐渐走向成熟的隋 况下，近几年椭圆曲线密码已成了密码学中的又一个研究热点。 目前，关于椭圆曲线密码体制的标准化组织有a n s i x 9 6 2 ，a n s i x 9 6 3 ， i e e e p 1 3 6 3 9 】，s e c g 等，椭圆曲线密码体制的实现一般都集中在有限域g f ( 2 “) 及g f ( p ) ， 6 双) 上，并且在实现的时候都考虑到了种种对椭圆曲线密码的攻击算法，使之成为安全 的椭圆曲线。g h 2 n ) 上的椭圆曲线密码体制特别适用于硬件实现，因为子域g f ( 2 ) 的元素0 。 l 可用硬件简单实现，因此得到了广泛的深入的研究；而g f ( p ) 上的椭圆曲线密码体制一 般用特殊的p ，如m e r s e n n e 素数( 形如2 ”1 的素数) 来加快乘法中的取模运算( 取模运算 只需简单地用加法来是实现) ；g f ( p ”) 上的椭圆曲线密码体制则有b a i l e y ，p a a r 1 0 于1 9 9 8 年提出它是一种充分利用c p u 以字为单位做运算的高效特征的椭圆曲线密码体制。 椭圆曲线密码体制将会成为2 1 世纪最主要的公钥密码体制。这是由椭圆曲线密码体制 自身优越条件所决定( 如密钥短，计算速度快等) 。就目前以建立或正在建立的各种安全 信息传输和交换系统而言，它们的安全框架都是按照公钥密码学理论构筑的，离开了这一 理论，也就无从谈起它们的安全性。按当前的电子信息化程度，它的应用主要在银行结算， 电子商务和通信领域等。以后必将会扩展到人们社会生活和各个层面。因此，由椭圆曲线 密码理论所发展成的技术必将具有无限的商业价值。 2 上海交通大学硕士学位论文 1 2 本文章节安排 第二章主要介绍公钥密码体制的基本理论：先介绍了代数及数论问题的基本概念，如 离散对数问题，大整数分解问题，随后介绍一些密码术语，如单向函数，陷门单向函数等； 而且也简单地介绍了r s a 、e i g a m a l 公钥密码体制；并着重介绍了椭圆曲线公钥密码体制 的基本理论，包括椭圆曲线的定义及其上的运算，和椭圆曲线有关的一些定理和结论。 第三章中我们主要研究了椭圆曲线离散对数问题，我们首先给出了椭圆曲线离散对数 的定义，然后介绍了椭圆曲线离散对数的三种主要解法：1 ) 通用的离散对数方法p o l l a r d 口， 2 ) 针对超奇异曲线的m o v 演化算法，3 ) 针对“畸形”曲线的s e m a e v 方法。最后，我们 提出了安全椭圆曲线选取的准则，并比较了各种公钥密码体制的参数。 第四章研究了基于最优扩域的椭圆曲线密码算法的实现：首先我们给出了最优扩域的 定义，随后给出了最优扩域上的各种运算的算法以及椭圆曲线上的算法，然后介绍了最优 扩域的构造以及基于最优扩域的椭圆曲线的生成，并给出了试验结果，最后详细地介绍了 各种椭圆曲线密码体制。 第五章对全文作了总结和归纳，同时指出在椭圆曲线密码体制研究和实现中几个有待 深入的方向。 上海交通大学硕士学位论文 第二章公钥密码体制的基本理论 本章首先讨论代数、数论中的概念和其中一些计算难解的问题，并且阐述了它们在密 码学中的应用，然后论述构造复杂密码系统所需的基础算法和协议，并简单地介绍了r s a ， e i g a r n a l 公钥密码体制，最后着重介绍了椭圆曲线密码体制的基本理论。 2 1 代数和数论的基本概念 很长时间以来。数论被认为是无实际应用的纯理论科学。但是，现在它在密码学中有 相当重要的地位，很多公开密钥密码体制的安全性的基础是一些数论问题( 如大数分解) 的困难性。在本节中回顾密码学中重要的代数和数论结论，具体可参见【1 1 、【1 2 。 2 1 1 群 设s 是非空集合，是从s x s 到s 的二元运算a + b 表示将+ 作用于元素d ，b s 的结 果。如果对任意4 ，b s 都有a + 6 = b + 4 ，则是可交换的。如果对任意口，b s 都有 ( 口 b ) 十c = a ( b + c ) ，则是可结合的。如果元素e s 对任意a s 都有e + 口= a e = a ， 则e 是单位元。假设e 是单位元，如果元素口，b s 满足b + a = a + b = e ，则a 和b 互为逆元。 定义2 1 如果二元运算在集合g 上是可结合的，并且g 包含的单位元，g 中的每个 元素都有+ 下的逆元，则称g 关于构成了称为群的代数结构，记为( g ，) ( 简记为g ) 。 如果是可交换的，则这个群是阿贝尔群。如果i g i 是有限的则g 称为有限群。有限群的 元素个数称为群的阶。 群中的单位元是唯一的。如果+ 是加法运算，则单位元记作0 ，d 的逆元记作一a 。如 果是乘法运算，则单位元记作l ，a 的逆元记作l 。或a ，a “表示口自乘m 次，a ”表 示( v a ) “。 如果存在群g 的元素a ，使得对群中的任意元素b ，都存在x z ，使得b = 口，则称g 为循环群d 是g 的生成元，g = ( a ) 表示4 生成g 。元素6 的阶是满足矿= 1 的最小正整 数h ，记作o r d ( b ) 。有限群的任意元素的阶能够整除群的阶。如果a 是阶为m 的循环群g 的 生成元，则元素b = a i 的阶为m g c d ( m ，f ) ，特别地，6 是g 的生成元当且仅当g c d ( m ，f ) = 1 。 4 上海交通大学硕士学位论文 因此如果群的阶数为素数，则除了1 以外的任何元素都是g 的生成元。 群g 的子集g 是g 的子群当且仅当日关于其上的g 的运算形成了群。特别地，h 包含l ，并且如果口，b h n a b ，a 。h 。并且，1 日l 整除i g l 。由g 的元素口生成的一类 子群记为( 。) 。( 口) 的阶和a 的阶相同。因此，任意群元素的阶整除群的阶。 2 1 2 加群z 。和乘群z ： 模珑的整数集合z ，和模m 的加法运算构成了阶为m 的阿贝尔群。小于m 并与m 互素 的正整数集合和模m 的乘法运算构成了群z ：，其阶为欧拉函数值妒( m ) 。 定义2 2 欧拉舻函数是和正整数n 互素的小于月的正整数的数目，即 妒( h ) = l k 1 1 k n ，g c d ( k ，n ) = 1 ) l 。 kl 如果整数行= 兀，其中只是不同的素数，则妒o ) = 月兀( 1 - p 7 1 ) 。 i = j，= 】 对任意m 群z 。是循环群，群z ：是循环群当且仅当m 是素数时。 2 1 3 域 定义2 3 非空集合k 上的两个运算加法“+ ”和乘法“”如果满足以下三个条件，就 称k 是一个域： 1 ( k ，+ ) 是一个阿贝尔加法群； 2 ( k 0 ) ，x ) 是一个阿贝尔乘法群，其中0 是加法单位元： 3 对任意的口，b ，c k ，有a ( b + c ) = a b + a xc ，( a + b ) c = a xc + b c ( 分配律) 定义2 4 域k 的特征c h 呱k ) 是指：对所有的口k ，满足月口= 0 的最小正整数n ； 如果这样的正整数n 不存在，则c h a r ( k ) 为0 。 定义2 5 有限域e 是指有q 个元素的域。特别的，对于素数q ，2 占。 定义2 6 如果域k 包含域f ，则称k 是f 的扩域。 记号：k ：表示一个域；r ：实数域；q ：有理数域；c ：复数域：f ，有限域； 2 1 4 离散对数问题 离散对数问题的难解性保证了本文中提出的密码系统的安全性。下面将对这个问题进 行形式化的定义，并简单介绍解决这个问题的算法。 定义2 7 令g 是有限循环群，g 是g 的生成元。元素a g 的离散对数是一个整数x 上海交通大学硕士学位论文 ( 0 工i g l ) ，并满足口= g 。记为l o g g 口。 离散对数也称为口的指数。如果g 不是g 的生成元，那么若存在口对g 的离散对数，它 是满足口= g 。的最小整数石。 定义2 8 离散对数问题：给定有限循环群g ，生成元g 和一个元素口，找到整数z ， 0 蔓工曼i g i - l ，满足口= g 。 2 1 5 表示问题 定义2 9 令g 是阶为m 的有限循环群，g i 一，g 。g 是其不同的生成元。元素口g 的 一个表示是m 元组( 工，工。) ，对所有1 f m ，0 x f 竹一1 ，满足 n = 兀爵。 拉i 一个表示也称为一个指数元组。对任意元素4 g ，存在n ”个口对于( g i - ，g m ) 的m 元组 表示。 定义2 1 0 表示问题：给定有限循环群g 生成元组( 蜀，) 和元素口，找到整数组 成的m 元组( 而，j 。) ，对所有l i m ，0 t , f i t 一1 ，满足 盯= 丌驴。 扭【 表示问题是离散对数问题的推广。如果生成元g i ，一，g 。是随机选择的，则找到同一元素的 两个不同表示是和离散对数问题一样困难的。 2 1 6d j 怖e h e l l m a n 问题 定义2 1 1 d i f f i e h e l l m a n 问题：给定有限循环群g ，g 的生成元g ，两个元素矿和g ”， 找到元素g “。 定义2 1 2d i f f i e - h e l l m a n 确定问题：给定有限循环群g ，g 的生成元g ，三个元素g 。、 g 和g ，确定元素g 和g ”是否相等。 d i f f i e h e l l m a n 问题和离散对数问题的关系相当密切。如果离散对数问题可以在多项式 上海交通大学硕士学位论文 时间内解出，则首先计算“= l o g ，g “，然后计算( g ”) 。即可解出d i f f i e h e l l m a n 问题。在某 些群内，离散对数问题和d i f f i e h e l l m a n 问题是计算相当的。显然，如果能够解决 d i f f i e h e l l m a n 问题，d i f f i e - h e l l m a n 确定问题也能解决。一般，假设d i f f i e h e l l m a n 确定 问题是难解的。 2 1 7 大数分解问题 定义2 1 3 整数分解问题：给定正整数”，找到其因子分解，即确定不同的素数p ，和正 整数q ，使得月= p ：1 p - p p 。 分解整数 的算法有两种： 1 通用算法：运行时间只和h 的大小有关。如二次筛选法和数域筛选法。 2 专用算法：运行时间和n 的性质( 如最大素因子的大小) 有关。如试除法、p o l l a r d 的r h o 法、p o l l a r d 的p - i 法和椭圆曲线法。 2 2 公钥密码体制的问世及其相关术语 加密算法被分为两类：秘密密钥( 对称) 算法和公开密钥( 非对称) 算法。在对称算 法中，加密和解密的密钥相同，因此，需要用对称加密算法进行保密通信的双方必需事 先交换密钥。在公钥加密算法中，加密和解密的密钥不同。加密密钥( 即公钥) 是公开的， 解密的私钥是秘密保存的。所以，对称加密算法要求秘密传送密钥，而非对称加密算法只 需要鉴别公钥，它的安全性要求弱得多了。 2 - 2 - 1 对称密码体制 对称密码体制是用于两个通信者之间，为在公开信道上传输秘密消息的密码体制。这 种密码体制的使用使其他第三方无法读取截获的加密消息。对称密码体制描述如下： 记m 是所有可能的明文消息的集合，c 为所有可能密文消息的集合( 加密的消息) ，k 为所有可能密钥的集合。 一个对称密码系统包含下列元素： 加解密函数对d 。，e 。满足下列条件： b ( e k ( ) ) = m ，m m ，k k ， 两个通信实体a 和b 要进行加密通信，首先需要秘密协商秘密钥k k ( 可以通过物 理的方法或第三方可信中心) 。当a 要向b 发送消息m m 时，a 向b 发送密文c = e t ) ， b 收到密文后，利用解密函数d 及协商的秘密钥进行解密：m = d k ( c ) ，得到明文消息。 此密码体制要求a n 解密函数计算容易实现，且在没有密钥的情况下，由密文无法确定明文 7 上海交通大学硕士学位论文 和密钥。 对称密码体制的缺陷： 密钥分配问题通信双方要进行加密通信，需要通过秘密的安全信道协商加密密钥，而 这种安全信道可能很难实现或代价过高。 密钥管理问题在有多个用户的网络中，任何两个用户之间都需要有共享的秘密钥，当 网络中的用户一很大时，需要管理的密钥数目是非常大( n ( n 一1 ) 2 ) 。 没有签名功能当主体a 收到主体b 的电子文挡( 电子数据) 时，无法向第三方证明 此电子文档确实来源于b 。 2 2 2 公钥密码体制的问世 d i f f i e h e l l m a n 密钥交换 1 9 7 6 年，d i f f i ea n dh 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 】，论文描述了两个通信主体可以在公开信道上( 不安全信道) 通信并导出共享的秘密 信息，可以利用此秘密信息作为对称加密密钥。交换协议描述如下： 1 a 和b 公开选择一个有限群g 及一个群元素g g 。 2 a 生成一个随机整数口，在群g 中计算g 。，并把计算结果在公开信道上传给b 。 3 b 生成一个随机整数b ，在群g 中计算9 6 ，并把计算结果在公开信道上传给a 。 4 a 接收到9 6 ，并计算( 9 6 ) 。 5 b 接收到g 。，并计算( g 。) 6 。 此时，a 和b 已有了共享的群元素g “( 可作为共享密钥) 。( 此协议是没有认证的交 换协议，但可以通过第三方对交换的消息认证、签名) 2 2 3 公钥密码的一些术语 1 1 、 1 2 单向函数( o n e - w a yf u n c t i o n ) ：函数f ：m _ c 称为单向函数，如果，是满足下列条件 的可逆函数： 1 对任意m m ，计算f ( m ) 是“容易”的。 2 当c c 时， 计算，一( c ) 是”困难”的。 这里，计算是”容易”的，是指多项式时间可计算的；计算是困难的，是指计算需要指 数时间。 陷门单向函数( t r a p d o o ro u e w a yf u n c t i o n ) ：单向函数f ：m c ，若存在另外信息， 上晦交通大学硕士学位论文 使得f ：m - + c 的逆函数计算“容易”，则称，是陷门单向函数。 构造公钥密码体制，需要陷门单向函数( t o f ) 族 ：m 叶c ，k k ，此函数族应满 足对每个k k ，陷门f ( 七) 容易得到，即能够得到 逆运算的有效算法，但有效算法不能 够恢复k 。 利用陷门单向函数构造公钥密码体制 给定一陷门单向函数族，每个用户a 随机选取口k ，并公布计算兀的算法e 。l 称 为用户a 的公钥，陷门f ( 口) 称为a 的私钥。 公钥加密方法：当用户b 要向用户a 发送消息m 的密文时，利用a 的公钥e 。，计算 正( 肌) ，a 可以用自己的私钥恢复消息m 。 公钥签名方法： 当a 需要向b 发送一个经过签名的消息m 时，a 向b 发送消息m 及s ：f 2 1 ( m ) ，此 时，任何人可以利用a 的公钥e 。验证m = 厶( s ) 。 2 3 r s a 密码体制【13 】 r s a 是由r i v e s t 、s h a m i r 、a n da d l e m a n 在1 9 7 7 年提出，是d i f f i e h e l l m a u 抽象模型 的初次实现。 费马定理( f e r m a t ) ：n = p q ，p ，q 是不同的素数，则有对任意的整数a ( o a n ) ) 和任意 的正整数k ，有a 州小1 - a ( m o d n ) ，其中庐是欧拉函数，( h ) = ( p 一1 ) ( g 一1 ) 。 实现方法如下： 每个用户a 选取两个大素数p ，q ，并计算n = p q ，( n ) = ( p 一1 ) ( g 一1 ) ，任意选取 e ：1 e ( 竹) ，g c d ( e ，矿( h ) ) = 1 ，利用扩展的e u c l i d e a n 算法，计算d ，l d 妒( h ) ，其中d 满足d e ；1 ( m o d 妒0 ) ) a 的公钥为( n ，e ) 私钥为d ( p ，q 保密) 。 r s a 加密运算： 明文工，密文y = x 。m o d n 解密：明文x = y 4 9 上海交通大学硕士学位论文 2 4 e i g a m a l 密码体制【14 】 设g 是有限循环群，其阶为g ，g g 是g 的生成元，在g 中计算离散对数是困难的。 e i g a m a l 加密运算 j 初始阶段：每个用户可以选择一个随机数? ( 用户的私钥) ，计算g7 ( 公开密钥) 我们假设消息是g 中的元素，且用户a 要向用户b 发送消息m 。 2 a 随机生成整数k ，并计算g 。 3 a 查找b 的公钥9 6 ，并计算( 9 6 ) ，m g “。 4 a 向b 发送群元素对( g ，m g “) j b 计算( g ) 6 ，并由此可以恢复消息m 。 e i g a m a l 密码体制与d h 体制是等价的，基于离散对数的困难问题。为实施的安全性 及有效陛，群g 及元素g eg 的选取应满足下列条件： 1 群g 中的运算应“容易”， 2 为安全起见，群 中的离散对数应是“困难”的。 2 5 椭圆曲线密码体制 有限域k 上的椭圆曲线上的点形成一个阿贝尔群，该群上的加法运包括有限域上的算 术运算。椭圆曲线上的算法在软件和硬件实现方面都比较容易。1 9 8 5 年，n k o b l i t z 2 和 v m i l l e r 3 】首先提出了椭圆曲线密码体制。有限域上的椭圆曲线可以用于实现 d i f f i e h e u m a n 密钥交换方案，e l g a m a l 、s c h n o r r 1 5 、d s a 签名方案。下面主要介绍椭圆 曲线的基本理论。 2 5 1 椭圆曲线的定义 定义2 1 4设k 是一个数域，其特征不等于2 或3 ，设石3 + a x + b ( a ，b k ) 是没有重 根( 4 a3 + 2 7 b 2 0 ) 的三次多项式，一条椭睡曲线是指下列点的集合： e = ( 工，y ) ：y 2 = x 3 + a x + 6 ，o r ( x ，y ) = d ) 即一条椭圆曲线是满足方程 y 2 = x 3 + 础+ 6 ( 2 1 ) l o 上海交通大学硕士学位论文 的所有点的集合及一个无穷远点。 若域k 的特征是2 ，则k 上的椭圆曲线是满足方程 y 2 + x y = x 3 + a t t + 6 ( 2 2 ) 的点的集合及一个无穷远点，此时，不考虑右边的多项式是否有重根。 若域k 的特征是3 ，则k 上的椭圆曲线是满足方程y2 = x 3 + a x 2 + h + c 的点的集合及 一个无穷远点，此时，要求右边的多项式没有重根。 一般定义：任意域上的椭圆曲线方程的一般形式( w e i e r s t r a s s ) 是 y 2 + a l x y + 4 3 y = 工3 + a 2 x 2 + a4 x 十a 6( 2 3 ) 当k 的特征不等于2 时，上述方程可以变换为y 2 = x3 + 甜2 + 缸+ c ，当k 的特征大 于3 时上述方程可以变换为y 2 = x3 + b x + c 。当k 的特征为2 时，并不是所有的椭圆曲 线都能够写成( 2 ，2 ) 的形式，但在我们讨论的范围内，要求方程是( 2 2 ) 的形式。 非奇异性 设f ( x ，y ) = 0 表示上述各椭圆曲线方程的隐式方程，则椭圆曲线上的一点( x ，y ) 被 称为非奇异的，是指偏导数a f a f ，o f ，砂至少有一个在该点不为零。 2 5 2 实数域上的椭圆曲线 定义2 1 5 ：设e 是实数域上的一条曲线，p 、q 分别是e 上的两个点，我们根据下列 规则定义p 的负元和p + q ： 1 如果p 是无穷远点o ，则一p = o ，且p + q = q ，即无穷远点q 相当于加法群的单 位元：( 下列规则假设p 、q 都不是无穷远点) 。 2 设p 的坐标是( x ，y ) 即p = ( x ，y ) ，则一p 的坐标是( x ，一y ) ，即- p 与p 具有 相同的x 坐标，而y - 坐标互为相反数。有方程( 1 ) 可以得出：若( x ，y ) 在椭 圆曲线上，则( x ，- y ) 也在椭圆曲线上。 3 如果p 、q 有不同的x 坐标，则直线l = p q 与曲线正好有另一个交点r 1 ，若p q 是 p 点的切线，我们令交点r i _ p ；若p q 是q 点的切线，令交点r 1 = q ：p 与q 的 加法p + q 定义为r = - r ，其几何表示如下图2 1 ，图2 2 ： 4 若o p ，则定义p + q = o ( 无穷远点) 。 5 若p = q ，则令p q 是p 点的切线，设r f 是p q 与曲线的另一个交点，此时，定义 p + q = - r 。 上海交通大学硕士学位论文 图2 1 椭圆曲线点的加法 f i 9 2 - 1t h ea d d i t i o no ft w op o i n t so nt h ee l l i p t i cc u p c e p = e ，y ，) 。7) 广、 、 r = 屯，n ) 、 图2 2 椭圆曲线倍点运算 f i 9 2 - 2 t h ed o u b l eo p e r a t i o no fp o i n to nt h e e l l i p t i cc u f v - e 记无穷远点的坐标为( 0 ，0 ) ，即o = ( 0 ，o ) ； 1 设p = ( 西，y 1 ) o ，则一尸= 0 l ，- y 1 一a l x l 一a 3 ) ( 注p 与- p 是曲线e 上惟一有相同 x 坐标的点) ； 2 若q = 一p 贝0 p + q = ( 0 , 0 ) ； 3 设p = ( x l , y 1 ) 0 ( 0 ，0 ) ，q ：( x 2 ，y 2 ) 0 ( o ，0 ) ，q 一尸，尸+ q = ( x 3 ，n ) 则而= a 2 + 口1 一口2 而一工2 y 3 = 一( 丑+ 4 】) x 3 一y i + 血1 一口3 j 必 j p q 舯拈k 兰羔五苎 l2 y i + 口l x l + c t 一 椭圆曲线数乘运算 簧 谬 上海交通大学硕士学位论文 定义2 1 6 设m 是一整数，p 是椭圆曲线上的点，定义乘法m p 如下 一 z 一一 m p = p + p + - + p 判别式与j 不变量 定义2 1 7 设e 是方程( 2 3 ) 给出的椭圆曲线，定义如下变量： d 2 = 口? + 4 a2 d 4 22 a 4 + o 【4 3 d 6 = a ；+ 4 。6 d 8 = 0 1 2 06 + 4 口2 口6 一a 【3 a + 口2 d ；一d ： c l = 口；一2 4d a = 一d ；d8 8 d ? 一2 7d ：+ 9 d2 d 。d6 ( 2 4 ) j ( e ) ：。彳 ( 2 5 ) 称为椭圆曲线的判别式，当a 0 时，( e ) 称为椭圆曲线的j 一不变量。 定理2 1 ：椭圆曲线e ( 2 3 ) 是非奇异的，当且仅当a 0 。 定理2 2 ：设椭圆曲线e 的方程是( 2 1 ) ，则 a = 一1 6 ( 4 a 3 + 2 7 b 2 1 ，( ) = 一1 7 2 8 ( 4 a ) 3 a 2 5 3 有限域上的椭圆曲线 设e 是定义在特征为p 的有限域c 上的椭圆曲线，鼋= p ”，n 为一整数。 本节介绍椭圆曲线e 上的f r o b e n i u s 自同态及其重要特性。 有限域上椭圆曲线的阶数( 元素个数) 记为撑e ( c ) 定理2 3 ( h a s