（计算数学专业论文）schoof算法及其实现的一些策略.pdf

华中科技大善- - r 硕士学位论文 摘要 f 椭圆曲线密码e c c ( e l l i p t i cc u r v ec r y p t o g r a p h y ) t 1 互”，是由n e a l k o b l i t z 1 和 v i c t o r m i l l o r 分别独立地于1 9 8 5 年提出来的，从那以后大量的研究工作集中于它的 安全性和执行效率上，在最近几年中，e c c 已经被许多的国际标准化组织，例如 a n s i ( a m e r i c a n n a t i o ns t a n d a r d si n s t i t u t e ) 1 e e e ( 1 n s t i t u t eo fe l e c t r i c a la n de l e c t r o n i c s e n g i n e e r s ) 1 s o ( i n t e m a t i o n a ls t a n d a r d so r g a n i z a t i o n ) 授权可以应用于商业加密中。 在进行椭圆曲线密码加密之前，我们必须确定供加密用的有限域只上的椭圆曲 线e ，基于加密系统的安全性我们需要考虑域f ，上的椭圆曲线上的点的个数 # g f ( q 1 。在选取曲线参数时，有两种方案，一种是选取标准化组织推荐的曲线( 例 如按f i p s1 8 6 2 4 】中推荐的选取) ，另种方案是随机生成供加密的曲线。但是如 果随机生成的椭圆曲线在有限域只上的点的个数# g f ( q ) 不含大素数因子的话，则 容易被p o h i g h e l l m a n 方法攻击。所以要生成安全的椭圆曲线e ，必须满足在 域f ，上含有大的素数因子的条件。 s c h o o f 算法是由r e n es c h o o f i 6 1 提出来的，用来计算有限域e 上椭圆曲线上 ， 的点的个数? 本文首先介绍了椭圆曲线的相关知识，以及s c h o o f 算法，并给出了 s c h o o f 算法相关补充性的证明，得到了定理3 3 1 和定理3 3 2 ，并指出了参考文献 5 中公式推导的错误7 ，还构造了随机生成安全椭圆曲线的算法，此算法生成的椭圆 曲线的阶# g f ( q ) 含有大的素数因子，在此椭圆曲线上实现的加密系统可以抵抗 p o h l i g h e l l m a n 攻击。最后在实现策略部分给出了些算法的快速算法，并实现了 其中的一些关键算法。 关键词：椭圆曲线椭圆曲线密码 0 0 厂算法 安全的椭圆曲线 华中科技大学硕士学位论文 = ! ! ! ! ! ! = = ! = ! = ! = ! = ! ! ! ! = = ! = = ! = = = = = ! = = = ! = = ! ! = ! = ! ! ! = = a b s t r a c t e l l i p t i cc u r x 7 e c r ) p t o g r a p h 3 ，( e c c ) 、1 、a sp r o p o s e di n 19 8 5i n d e p e n d e n t l ) 吣 n e a lk o n i t z f i i a n dv i c t o rm i l l e rs i n c et h e n a 、a s ta m o u n to fr e s e a r c hh a sb e e nd o n e o ni t s s e c u r i t ) r a n di m p l e m e n t a t i o n i nr e c e n t j e a r s e c c h a sr e c e i ! 、e di n c l 。e a s i n g c o m m e r c i a la c c e p t a n c ea se 、i d e n c e db j i t si n c l u s i o ni ns t a n d a r do l g a n i z a t i o u ss u c ha s a n s i ( a m e r i c a n n a t i o ns t a n d a r d s i n s t i t u t e ) 1 e e e ( i n s t i t a t e o fe l e c t r i c a la n d e l e c t r o n i c se n g i n e e r s ) ，1 s o ( i n t e r n a t i o n a ls t a n d a r d so r g a n i z a t i o n ) ，a n dn i s t ( n a t i o n a l i n s t i t u t eo fs t a n d a r d sa n dt e c h n o l o g ) ) b e f o r ei m p l e m e n t i n ga ne c cs ) s t e m 、es h o u l dc h o o s et h ee l l i p t i cc u r , , ee o 、e r t h ef i n i t ef i e l df ，c o n s i d e r i n gt h ef a c t o ro ft h es e c u r i t yo ft h ec r y p t o s 5 s t e m s h o u l dc a l c u l a t e # g f ( q ) t h en u m b e ro ft h ep o i n t so ne l l i p t i cc u r v e so v e rf i n i t ef i e l d f f t h e r e a r et w os c h e m e st os o l ! ! ，et h ep r o b l e m t h ef i r s ti sc h o o s i n gef o l l o w i n g t h es u g g e s t i o n so fs t a n d a r d so r g a n i z a t i o n s ( s u c ha sn i s ti nf i p s18 6 2 ：t h es e c o n d i s c h o o s i n g e b 、r a n d o r n h o w e v e t ，t h ee l l i p t i c c u r , _ ，e c r y p t o s y s t e mi se a s i l y a t t a c k e db y p o h i g h e l l m a n a l g o r i t h m i ft h en u m b e ro ft h ep o i n t so ne l l i p t i cc u r ! ! e o 、7 e l f i n i t ef i e l d c d o e sn o t1 1 a 、，eh u g ep r i m ef a c t o es ow em u s ts a t i s f yt h ec o n d i t i o n # g f ( q 、s h o u l dh a sh u g ep r i l n ef a c t o ri no r d e r t og e n e r a t es e c u r ee l l i p t i cc u r ! ! e s c h o o fa l g o r i t h m 】p r o p o s e db y r e n es c h o o e w a su s e dt oc a l c u l a t et h e n u m b e ro ft h ep o i n t so l le l l i p t i cc u r v eo v e rf i n i t ef i e l d f r t h i sa r t i c l e 、f i r s ti n t r o d u c e s s o i t l ek n o u l e d g ea b o u te l l i p t i cc u r v e ，a n di h e nd e s c r i b e ss c h o o f sa l g o r i t h mi nd e t a i l e s p e c i a l l ) p r o x ，i d e ss o m es u p p l e m e n t a r yp r o v i n go f s c h o o f sa l g o r i t h m b a s e do nt h i s ， t h e o r e m s33 ，1a n d33 2a r ea c h i e v e d 、a n ds o m em i s t a k e sd u r i n gt h ed e d u c t i o ni nt h e l i 华中科技大学硕士学位论文 5 出p a p e rl i s t e d i nr e f e r e n c e sa r ep o i n t e d0 1 3 i a na l g o r i f l m ti sc o n c e i 、e dt og e n e r a l s e c u r ee l l i p t i c a lc u r e b ，r a n d o m ，t h el l u n l b e r o ft h e p o i n t s i nt h e e l l i p t i c c u r 、 g e n e r a t e dt h i s 、a 3 c o i _ l i a i a sh u g ep r i m ef a c t o r a n dt h e r e f o r e t h ec r ) p r o s ) s l e n lr e a l i z e i nt h i se l l i p t i cc u r x ec a l lg u a r da g a i n s tt h e p o h l i g - h e l l m a n a t t a c k a tl a s ts o l n eq u i c a l g o r i t h m s a r ep r o v i d e da n dr e a l i z e d k 姆w o r d s ：e l l i p t i cc u r e s c l l o o f a g o 州1 m e l l i p t i cc u i 、ec r ) p t o g r a p h y s e c u r ee l l i p t i cc u i 、e 华中科技大学硕士学位论文 1 1引言 1 绪论 近代密码学发展过程中有两件里程碑式的事件，一是1 9 7 7 年美国国家标准局 正式公布实施了美国数据加密标准d e s ，并公开它的加密算法，应用于商业加密 中：二是d 够p 和h e l l m a n 联合写的一篇“密码学的新方向”，提出了适应网 络上保密通信的公开密钥思想，掀起了公钥密码研究的序幕，“没有公钥密码的研 究就没有近代密码学”。 1 9 8 5 年，由n e a lk o b l i t z 和v i c t o rm i l l l 8 1 分别独立地提出了椭圆曲线密码 e c c ( e l l i p t i cc u r v ec r y p t o g r a p h y ) 后，大量的研究工作主要围绕在它的安全和执行 效率上，从1 9 9 7 年到现在椭圆曲线密码成了公钥密码体制中的研究热点。 1 2 椭圆曲线密码体制 椭圆曲线理论 9 , 1 0 , 1 1 , 12 1 是代数几何，数论等多个数学分支的一个交叉点。而椭 圆曲线密码体制，它是建立在椭圆曲线理论上的一种密码体制。根据椭圆曲线上 的点对于椭圆曲线上定义的加法构成a b e l 群这一性质，我们可以构造椭圆曲线 上的离散对数问题“3 。4 1 来构造椭圆曲线密码系统。 椭圆曲线上的离散对数问题，可以描述如下：给出一个有限域上的椭圆曲 线及曲线上的两点p ，q 求解方程q = k p 中的足是困难的，其中k 是整数， 为 椭圆曲线上点的数乘运算。 实际中有许多的椭圆曲线密码系统，如e l g a m a l 系统1 ，d i f f i e h e l l m a n 系 统【”，还有m a s s e ) ，一o m u r a 【3 1 系统等。 华中科技大学硕士学位论文 1 3 椭圆曲线密码体制的安全性 椭圆曲线密码体制的安全性取决于椭圆曲线离散对数问题的难解性。一般而 言，求解群g 上的离散对数问题的算法可分成两类：指数计算法与碰撞搜索法。 指数计算法具有亚指数时间复杂度，但要求在g 中“平滑性”概念，且g 中含有 足够多的平滑元素。目前最好的指数计算方法是线性筛法和数域筛法。碰撞搜索 法与前一种相比可以应用于一般群，该算法具有纯指数时间复杂度，目前最有效 的碰撞方法是p o l l a r d p 方法1 和p o h l i g h e l l m a n 方法。 假设g 是一个疗阶的a b e l 群，h = 是h g 生成的。阶循环子群。因为 在此群上应用p o l l a r d p 方法求解离散对数问题是一种随机算法，所以无法给出 运算时间的上界，而只能给出其期望运算次数，为d ( 帆) 。 而应用p o h l i g h e l l m a n 方法求解时，假设 n i = p 。 p | n 。 我们可以根据基于中国剩余定理构造同余方程组求解离散对数，该算法的时间复 杂度如下： ( 1 0 9 ( p m i n 。p ) 、e pm a x ( e a , p ) ) p l 从上面两种对椭圆曲线密码体制的攻击算法的时间复杂度来看，要想使攻击 方法是无效的，必须使椭圆曲线的阶即n 。含有大的素数因子，从目前实际应用情 况来看必须使此因子达到大概1 6 0 比特。 从安全角度考虑，怎样生成安全的椭圆曲线成为应用椭圆曲线密码体制首先 要考虑的问题。这涉及到怎样计算有限域兄上椭圆曲线上有理点的个数 # g ( ) 【2 5 2 6 1 。为了便于计算撑g ( ) ，一类被称为“超奇异椭圆曲线” s l 的特 殊椭圆曲线曾被建议应用于此密码体制，4 f f _ ；是m e n e z e s 等人于1 9 9 3 年证明了对于 华中科技大学硕士学位论文 建立在此类椭圆曲线上的离散对数问题可在概率多项式时间内归约为只的扩域 露上的离散对数问题，其中k 6 ，当p 3 时，ks 4 ，这样此类“超奇异椭 圆曲线” 就不能应用于加密。另外s e m a e v 发现对特征为q 的域兀上的椭圆曲线，假如 # g ( ) = q ，则e ( f q ) 中的离散对数问题可以在线性时间内归约于的加法群上 的离散对数问题，可以在线性时间内攻破。 1 4 s c h o o f 算法在椭圆曲线密码体制上的应用 从上述可知椭圆曲线的选择1 成了建立椭圆曲线密码体制首先要解决的问 提。由于现实中应用了不同的密码体制，椭圆曲线的选择也有两种方式。有些密 码体制如e l g a m a l 签名体制，d s s 签名体制需要知道椭圆曲线的阶撑g ( c ) 或 # g ( c ) 的一个大的素数因子：另外一些体制如d 猾e h e l l m a ni l s l 密码交换协议， e l g a m a l 加密体制虽然不需要知道 g ( c ) ，但是为了避免p o h l i g h e l l m a n 的攻 击，需保证拌g ( e ) 中有大的素数因子。 从上述情况来看椭圆曲线的选择可以有以下的两种途径。 一种是构造给定阶的椭圆曲线。a t k i n 和m o r a i n 在论文“e l l i p t i cc u r v e sa n d p r i m a l i t yp r o v i n g 忡1 中提到了这种方法。其思想是利用复乘构造素域c 上具有特 定阶的椭圆曲线。密码标准i e e e p l 3 6 3 2 0 1 也采用了该策略作为生成椭圆曲线的方 法之一。另一种是随机选取。即随机生成一条椭圆曲线，计算其阶拌g ( c ) 直到满 足含有大的素数因子条件为止。从安全角度来看，这是一种比较理想的方法。 s c h o o f 在刨驴t i cc u r v e so v e rf i n i t ef i e l d sa n d t h ec o m p u t a t i o no f s q u a r er o o t s r o o dp ”文中阐述了怎样利用中国剩余定理构造同余方程组并应用h a s s e 定理 华中科技大学硕士学位论文 来求得拌g ( c ) 的方法。 本文详细的介绍了s c h o o l 算法在椭圆曲线密码体制中的应用，并且给出了一 些补充性的证明，并对其关键的算法给出了实现。 1 5 椭圆曲线密码体制和其它公钥密码体制的比较 椭圆曲线密码体制的诱人之处在于与r s a 相比在安全性相当情况下，可以使 用较短的密钥。一般认为q 元域上的椭圆曲线密码体制，当q 的长度为1 6 0 比特时， 其安全性相当于r s a 使用1 0 2 4 比特模数，密钥短意味着小的带宽和存储要求， 这在某些应用中可能是决定性的因素。 椭圆曲线密码体制的另一个诱人之处在于：它是建立在一个不同于大整数分 解及素域乘法群离散对数的数学难题之上。自建立公钥密码体制以来，人们就基 于各种数学难题提出了大量的密码方案，但能够经受住时间考验且被广泛采用的 只有基于大整数分解以及离散对数问题的方案。因此它提供了一个新的加密平台。 椭圆曲线资源丰富，同一域上存在着大量的不同的椭圆曲线。这为安全性增 加了额外的保障。也为软硬件实现带来了方便。另外椭圆曲线上的一次群运算最 终化为其背景域上的不超过1 5 次的乘法运算，因此便于实现，在执行速度上，在 签名和解密方面较r s a 快，但是在签名的验证和加密上较r s a 慢。 1 6 椭圆曲线密码体制的现状、前景 正因为椭圆曲线密码体制和其它密码体制相比有着其独特的优点，从1 9 9 7 年 以来，椭圆曲线密码体制及其安全性的分析引起了密码学家及各界的极大的关注 和重视，现在已经成了研究热点。有关各界，包括学校( r o y a lh o l l o w a yc o l l e g e ) 商业组织( c e r f i e o m ) 及政府( 如美国国家安全局) 已从各个方面探索椭圆曲线密码技 术。这种密码体制也引起了“密码体制标准”研制者的极大兴趣。i e e e 标准 p 1 3 6 3 d s ( 1 9 9 8 年1 0 月版) 及p 1 3 6 3 d 9 ( 1 9 9 9 年2 月版) 对椭圆曲线密码体制做了重 点详尽的讨论。a n s i ( 美国国家标准局) 授权的金融业标准委员会x 9 制定了椭 圆曲线数字签名标准x 9 6 2 t 2 1 , 2 2 , 2 3 和密钥协商及传递标准x 9 6 3 。国际上著名的 r s a 实验室也开始制定了编号为p k c s # 1 3 的椭圆曲线密码标准将融合、平衡其他 华中科技大学硕士学位论文 标准，并与其他p k c s 标准有机的结合，对椭圆曲线密码体制的实现细节作出更 具体的规定。大多数密码学家对这种密码体制的强度及应用前景都越来越抱有乐 观态度。 华中科技大学硕士学位论文 2 1 椭圆曲线 2 椭圆曲线密码相关介绍 椭圆曲线【9 1 0 2 4 2 5 1 的研究来源于椭圆积分f 志出，其中厕为x 的三 或四次多项式。椭圆曲线是指由韦尔斯特拉斯( w e i e r s t r a s s ) 方程： y2 + a l x y + a 3 y = x 3 + q 2 x 2 + 口4 工+ 口5( 2 1 1 ) 所确定的平面曲线，通常用e 表示椭圆曲线。 若f 为一个域，口，f ，i = 1 , 2 ，5 ，满足( 2 1 1 ) 的数偶( x ，y ) 称为域f 上的椭 圆曲线上的点。，可以是有理数域，也可以是复数域，在本文中是指域 c = o ，l ，2 ，q 1 ) ，对应的椭圆曲线方程为： y 2 = x 3 + a x + 口( 2 1 2 ) 其中a ，b c ，且满足4 爿3 + 2 7 8 2 0 。 除了满足( 2 1 2 ) 所有的点外再加上一个特殊的点无穷远点d ，构成了椭圆曲线 上的所有的点。 2 2 椭圆曲线上点的运算 2 2 1椭圆曲线上点的加法 设p ( x ，y ) ，q ( x ：，_ ) ，；) 是椭圆曲线e 上的任意两点，l 为p q 的连线。假如p ，q 为同一点，则三为过点p 的切线。设上和椭圆曲线相交于点r7 ，是点r7 和无穷 远点p 的连线，也就是过点r 7 向x 轴所得的垂线，和椭圆曲线的相交于一点r ， 则r = p o q 。 对于方程( 2 2 ) 所对应的椭圆曲线，经过如此变换后可以得到相应的r 的坐标 是( x ，y ，) ，满足以下式子： 6 华中科技大学硕士学位论文 当p = q 时有 如图2 i 。32 五2 x l x 2 y 3 = 一) j 一兄( z 3 一x 1 ) 尸= 电，y ，) _ 。八 1 r | r = 电，小 。 图2 , 1 椭圆曲线上一点的2 倍：p + p = r 当p q 时( 2 2 1 ) ，( 2 2 2 ) 式相同但是a 如下： 我们可以用图2 2 j ：( y 2 一y 1 ) “ ( 屯一一) q = 屯，如) 。? l 。7，、 l ：二， f r p 2 电，) ，) 、 发= 电，y 3 ) 、 图2 2 椭圆曲线上的加法：p + q = r ( 2 2 1 ) ( 2 2 2 ) 五：塑 2 m ( 2 2 3 ) ( 2 2 4 ) 华中科技大学硕士学位论文 定理2 1 若p 和9 是椭圆曲线e 上任意的两点，j p q 连线上交e 于另点r ， 则有以下性质： ( 1 ) ( p o q ) o r = o ( 2 ) j d o o = p ( 3 ) p o q = q o p ( 4 ) e 上存在一点9 ，使得p o q = o ，这样的点q 以一p 表示 ( 5 ) 对于p 上的任意点p ，q ，r 有 ( p 0 9 ) o r = p o ( q o r ) 证明： ( 1 ) p o q 和r 作为曲线e 上两点，它们的连线平行于y 轴，交于无穷远点 o ，n o ) 式成立。 ( 2 ) 在曲线e 上取无穷远点o 作为q 点，尸q 的连线平行于y 轴，交e 于r 点， 此时r 点和p 点关于工轴对称，所以有和l 1 重合，所以有( 2 ) 式成立。 ( 3 ) 根据p o q 的定义，p o q = q o p 式成立。即椭圆曲线上的点关于。法 满足交换律。 ( 4 ) 可通过p 和q 的直线交曲线e 于r 点，根据性质( 1 ) 有：( p o q ) o r = 0 。 根据性质( 2 ) 有尸0 0 = p ，所以尸o r = 0 ，即有r = 一p ： ( 5 ) 可以通过各种情况对( 5 ) 进行验证，过程比较复杂，在此略去。 2 2 2 椭圆曲线上点的数乘运算 从定理2 1 可以看出，若将无穷远点o 作为。运算的零元素，性质( 3 ) 说明了 椭圆曲线上的点关于0 法满足交换律，性质( 5 ) 说明了椭圆曲线上的点关于。法满 足结合律。 华中科技大学硕士学位论文 我们可以定义如下数乘运算： m p 2 ! 土： ( 2 2 5 ) m 冼 从上面的分析可以看出椭圆曲线上的点关于运算。构成了a b e l 群。 2 3 相关概念和记号 c 域：表示以下有限域： = o ，l ，g l 其中口为素数，其上的加法和乘法运算分别是模g 的加法和 乘法。在其上满足+ 6 ) 9 = a ，+ b ，。 巧单位群：为_ 个循环群，可以表示为f i = f o ，它关于c 域上的乘法 形成一个阶为q 一1 的循环群。 e ( ) ：表示有限域上椭圆曲线上的点的集合可以表示为： e ( f q ) = ( x ，y ) i y 2 = x 3 + 4 工+ b 且有x ，y cw o 0 表示无穷远点。 拌g f ( g ) 表示有限域c 上点的个数，由a r t i n 提出猜测，h a s s e 证明了以下关 于估计椭圆曲线上点的个数定理”1 。 定理2 2 如果e 表示定义在有限域c 上的椭圆曲线，# g ，( g ) 表示椭圆曲线 上的点的个数，则 i 群g f ( g ) 一( g + 1 ) i 2 q( 2 2 6 ) 证明略。 f ，：表示有限域c 的扩域。 e ( c ) ：表示在f 。上的椭圆曲线上的点，可以描述为： e ( ) = ( x ，y ) 1 y 2 = x 3 + 爿x + 曰且讯，y 巧u o 华中科技大学硕士学位论文 ( 历上的点也有具有爿6 p ，群的结构。 椭圆曲线上的点的阶：设p 为椭圆曲线上的点，如果存在最小的正整数疗， 使得n p = 0 成立，其中0 为无穷远点，则称n 为p 点的阶。 2 4 椭圆曲线密码体制 椭圆曲线密码体制是根据椭圆曲线上的离散对数问题( e c d l p ) 构造的，椭圆 曲线上的离散对数问题可以具体描述为：已知p ，o 为椭圆曲线上的两点，要求解 方程p ：k o p 是困难的，其中足为整数，o 为椭圆曲线上点的数乘运算。 e c d l p 是比因子分解问题更难的问题，许多密码专家认为它是指数级的难度。 从目前已知的最好求解算法来看，1 6 0 比特的椭圆曲线密码算法的安全性相当于 1 0 2 4 比特的r s a 算法。 2 4 1 椭圆曲线密码体制系统 这里只介绍e l g m a l 密码系统。设给定的域为，g c ，且g 为非零的元 素。每一个用户随机的选择一个数a , o a q ，a 保密，将g 。公开，若b 要向a 发送 一个消息m ，可以随机产生一个整数k ，送给a 以下的一个数偶： ( g ，m g 。一) 由于有g 。一= ( g ) ，所以b 虽然不知道口。，也可以求得g ，a 收到了以上 的数偶以后，因为知道d 。，所以可以通过第一个数来d 次方来求得g ”，再通过 求此元素的逆和第二个元素相乘来获得原消息川。 将以上的加密通信方法应用到椭圆曲线上时，可以进行如下的改造： 假定明文m 编码嵌入到椭圆曲线上的一点只，选择一个点t e ，每一个用 户都选择一个数口，0 口 n ，n 为已知数，口保密，但是将a t 公开，假如用户b 想发送一个消息m 给用户a 的话，他可以向a 发送以下的数偶： ( j r ，匕+ k ( a 丁) ) 由于k ( a 。t ) = 口。( k t ) ，假如用户4 收到了此消息，可以将第一个数采用椭圆 曲线上的点的数乘运算进行口次数乘得到k ( a 丁) ，然后可以通过 1 0 华中科技大学硕士学位论文 巴+ k ( a _ t ) 一k ( a 。r ) = p _ 得到原消息的编码匕，然后经过译码得到埘。 其它的密码系统例如d 移p h e l l m a n 公钥系统，m a s s e y o m u r a 密码系统， 这里就不再多叙。 2 4 2 椭圆曲线加密方法与r s a 方法比较： ( 1 ) 安全性能更高 加密算法的安全性能一般通过该算法的抗攻击强度来反映。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 b i tr s a 、d s a 具有相同的安全 强度。 ( 2 ) 计算量小，处理速度快 虽然在r s a 中可以通过选取较小的公钥( 可以小到3 ) 的方法提高公钥处理 速度，即提高加密和签名验证的速度，使其在加密和签名验证速度上与e c c 有可 比性，但在私钥的处理速度上( 解密和签名) ，e c c 远比r s a 、d s a 快得多。因 此e c c 总的速度比r s a 、d s a 要快得多。 ( 3 ) 存储空间占用小 e c c 的密钥尺寸和系统参数与r s a 、d s a 相比要小得多，意味着它所占的存 贮空间要小得多。这对于加密算法在i c 卡上的应用具有特别重要的意义。 ( 4 ) 带宽要求低 当对长消息进行加解密时，三类密码系统有相同的带宽要求，但应用于短消 息时e c c 带宽要求却低得多。而公钥加密系统多用于短消息，例如用于数字签名 和用于对对称系统的会话密钥传递。带宽要求低使e c c 在无线网络领域具有广泛 的应用前景。 e c c 的这些特点使它必将取代r s a ，成为通用的公钥加密算法。比如s e t 协议 的制定者己把它作为下一代s e t 协议中缺省的公钥密码算法。 华中科技大学硕士学位论文 3 s c h o o f 算法相关性证明 为了将s c h o o f 算法的来龙去脉说明清楚，我们先引入以下的概念和记号。 3 1 概念和记号 b i , k f r o b e n i u s 映射m ：i 发p ( x ，j ，) ( c ) ，则映射。为满足( 3 1 1 ) 式： ，o o ，y ) _ 0 9 ，y 9 )( 3 1 1 ) e n d f , e ：为有限域c 上椭圆曲线e 上的点经过映射。作用以后形成的自同 态环。在西珂e 上映射。满足( 3 1 2 ) 式： 0 2 一f o + g = 0( 3 1 2 ) 其中，称为f r o b e n i u s 映射的迹。 根据r f 绷册”假设j a l t l 2 百，可以根据( 3 1 3 ) 式求出椭圆曲线上的点的个数 # g ( c ) ：榔9 # g ( c ) = q + 1 7( 3 i 3 ) 约化多项式序列甲。( z ，j ，) ：二元多项式序列l ( x ，y ) g ( x ，j ，) 对于 n z r n 一l 满足以下关系： 其中递推初值为： 甲2 。( j ，y ) = l ( + 2 、壬亲l 一一：吧，) 2 y 甲：。( z ，y ) = 叼甲。一一。峨+ 甲一，( x ，y ) = 一1 甲o ( x ，y ) = 0 ( 3 1 4 ) ( 3 1 5 ) 1 2 华中科技大学硕士学位论文 甲l ( x ，y ) = 1 v 2 ( y ) = 2 y 甲3 ( x ，】，) = 3 x + 6 a x 2 + 1 2 b x a 2 甲4 ( x ，y ) = 4 y ( x 6 + 5 a x 4 + 2 0 b x 3 5 a 2 x2 4 a b x 一8 8 2 一a 3 此多项式用来化简运算。 由以上的看来，多项式序列甲。，y ) 为有限域c 上的二元多项式，我们可以 利用椭圆曲线的方程： y 2 = x3 + a x + b 来将多项式( x ，n 消去y 2 项得到叫( ，y ) 。设多项式序列工( x ) c ( x ) ，通 过以下的变换( 3 1 6 ) ，( 3 1 7 ) ：i ( z ) = 甲。( x ，y )假如n 为奇数 ( z ) = 甲。( x ，r ) y假如 为偶数 可以将多项式序列l ( x ，y ) 化为c ( x ) 上的多项式序列工( x ) 。 3 2 引理 ( 3 1 6 ) ( 3 1 7 ) 引理1 设p = ( x ，y ) e ( f 目) ， z ；则有n p = 0 ( 无穷远点) 成立的充要条 件为正( x ) = 0 引理2 设p = ( x ，y ) e ( f ，) ，”z 。；且有印0 ( 无穷远点) ，则有 印= 一_ 。_ ，_ “v 二一l - 2 叼：) ( 3 2 1 ) 其中甲( x ) 为如( 3 1 4 ) 和( 3 1 5 ) 所示的多项式。 引理3 多项式序列 ( x ) 的次数d e g ( ) 满足( 3 2 2 ) 和( 3 2 3 ) 式： 华中科技大学硕士学位论文 d e g f = ( ”2 - 1 ) 当”为奇数时 d e g f = ( ”2 4 ) 当”为偶数时 此引理对多项式的规模做了定量的计算。 引理4 ( 中国剩余定理) 设，”2 。为两两互素的正整数 x ；b j m o d m i = 1 , 2 ，k 模【”l ，”2 ，“】有唯一的解。 假如令m = m 1 + m 2 h m i 设y 满足方程 ，2 m “2 ”1 ”2 “，一l ”2 + l ” m i y i ；l m o d m i j 1 , 2 - k ，则同余方程组的解为 证明略。 x = b l m i y l + b l m l y l + - + 6 女m 女y i 3 3 s c h o o f 算法相关性证明 ( 3 2 2 ) ( 3 ，2 3 ) 则同余方程组 定理3 3 1 经由变换( 3 1 6 ) ，( 3 i 7 ) 满足( 3 1 4 ) ，( 3 i 5 ) 的约化多项式序列 甲。( z ，y ) 可以写为( 3 3 1 ) ，( 3 3 2 ) ，( 3 3 3 ) 式中的正( x ) 序列。 厶。= 1 2 + l ( l + 2 + 辟l 一丘l + l 一2 )( 3 3 1 ) 五。二( z 3 + 删+ b ) 2 + + ：? 一工一。( 假如n 为偶数)( 3 3 2 ) = + 2 + 刀 4 i 即满足中国剩余定理的条件时求出同余方程组的解f ，从而求出 有限域上椭圆曲线上的点的个数。 所以由上面的分析看来s c h o o f 算法关键在于怎样在子群e l 】上构造，的同 余方程组( 3 4 1 ) 。设o 。为由在群e n d e l 小为数域g a t ( f q 厢) 上群研三，】 + g a l ( 厅f q l 上的点经。自同态映射形成的群) 上的映射，中。对所有点p ( x ，y ) e l ，】满足 ( o ：一f ，o + q ) p = 0 ( 3 4 3 ) 华中科技大学硕士学位论文 其中o 为椭圆曲线上的无穷远点，假如( 3 4 7 ) 对所有e ( x ，y ) e l ， 成立，l l j ( 3 4 1 ) 和( 3 4 3 ) 相减得到 ，i ，m o d l ， 为了求，。我们不需穷举，( 0 ， l 。) 是否对所有的点p 满足( 3 4 3 ) 式，可以通过计 算一系列多项式与 ( ) 最大公因式来求得。 设点a 1 为o ：p ，点a 2 为k _ p ( k ；q m o d l ；) 。当a 1 ，a 2 关于x 轴对称时满 足： o ：p = 一j ( 3 4 4 ) 而当a 1 ，a 2 为同一点时有： 中i p = 即( 3 4 5 ) 我们可以看到，无论是a 1 ，a 2 关于x 轴对称，还是为同一点他们的x 坐标都是 相等的，即满足： x - 2 = 工一_ 一z _ 必：( w ) 1k 我们可以将( 3 4 6 ) 中的( x ，_ y ) 换为多项式正( x ) 。 当k 为偶数时有： 当k 为奇数时有 ( 3 4 6 ) r 2 爿_ - 1 m “f 他删 ( 3 4 7 ) 一一九心m + l x 血+ ( 3 4 8 ) 对( 3 4 7 ) 式和( 3 4 8 ) 式去分母得到： 当k 为偶数时有： ( z - 2 一z ) ? ( x ) ( x 3 + 出+ 占) + 以一。( x ) + ，( x ) = 0( 3 4 9 ) 当k 为奇数时有： 华中科技大学硕士学位论文 ( x 。2 一工) ? ( j ) + ( x3 + 爿工+ b ) a 。( x ) + 。( 工) = 0( 3 4 1 0 ) 我们可以通过检测式( 3 4 1 1 ) 和式( 3 4 1 2 ) 来决定是否存在点p e l ， 上满足( 3 4 4 ) 或( 3 4 5 ) 式。 当k 为偶数时有： g c d ( ( x 。一j ) ? ( 曲 3 + 出+ 占) + 一，0 ) 五+ 。( 工) ，石0 ) )( 3 4 】1 ) 当女为奇数时有： g c d ( ( x ”一x ) ? ( z ) + ( 工3 + a x + b ) f k 一( j ) 丘+ 。( 工) ，f a x ) )( 3 4 1 2 ) 假如g o d 1 ，我们可以知道有一点p e l 存在满足( 3 4 4 ) 或( 3 4 5 ) 式， 假如g c d = 1 ，则通过和( 3 4 3 ) 比较可以知道，一定有： ，! 三0 假设有一点p e l ， 存在满足： o ：p 2 一妒( 3 4 1 3 ) 再由( 3 4 1 3 ) 和式( 3 4 3 ) 相减有： ri o m o d l ，( 3 4 1 4 ) 假如有一点p e l 。 存在满足： 中：尸2 妒( 3 4 1 5 ) 式( 3 4 1 5 ) 和式( 3 4 3 ) 相比较： 中j p t o p + q p = 2 q p - t o l p = 0 ( 无穷远点) 所以就有： 中p = 2 q t p( 3 4 1 6 ) 对( 3 4 1 6 ) 式两边都进行m ，变换有： 中：p = 4 q 2 t2 p 2 l 华中科技大学硕士学位论文 = q p 所以就有： t2 4 q m o d l ， ( 3 4 1 7 ) 式是一个平方剩余方程，令 w 25 q m o d l 若勒让德符号( g l 。) = 1 则此平方剩余方程有解 ，兰+ 2 1 r o o d l 其中0 w l ，又因为对点p e l 。 有： ( 中l 一圭r ) 2 p = d ( 无穷远点) 当( 3 4 2 0 ) 式 。p = ；，尸= 胛 成立，即对关于x 轴的坐标有： 当w 为偶数时， g c d ( ( x 。一x ) 十( x 3 + a x + b ) + 允( x ) ( 3 4 1 7 ) ( 3 4 1 8 ) ( 3 4 1 9 ) ( 3 4 2 0 ) + ：一。( ) 兀+ 。( x ) ， ( 工) )( 3 4 2 1 ) 当w 为奇数时， g c d ( ( x 9 一x ) + 允( x ) ) + 一i ( x ) + l + 1 ( x ) + ( x 3 + a x + b ) ，兀。( j )( 3 4 2 2 ) 假如( 3 4 2 1 ) 、( 3 4 2 2 ) 式的值为l 或勒让德符号( q l ，) = 一1 时表明a 1 ，a 2 关于x 轴对称，则有 f i 0 m o d l , 然而不能只通过( 3 4 2 1 ) 和( 3 4 2 2 ) 式来决定f ；- 2 w m o d l ，或f ；2 w m o d l ，因为 当两点关于x 轴对称的时候，他们的x 轴坐标是相等的，我们必须还要检验y 坐 华中科技大学硕士学位论文 标的正负号。 对于点p 满足( 3 4 2 0 ) 式，其对应的y 轴坐标满足以下方程： 产l 叼r _ t 掣： 对上式去分母化简得： 4 ) 州：y 9 一甲。2 _ ：一，+ 、壬，。一2 甲：+ 。= 0 将上式用：i ( 工) 表示得到( 3 4 2 3 ) ，( 3 4 2 4 ) ： 当w 为偶数时有： 4 y 4 f a y 9 一矾+ 2 足。十阢一2 丘，；o m o d 五( x )( 3 4 2 3 ) 当w 为奇数时有： 4 y ! f ? y 9 y f + 2 丘1 + 阢一2 允。= o m o d f l , ( x ) ( 3 4 2 4 ) 为了区分点p 是满足p = w p 还是满足p = 一w p ，我们分别对( 3 4 2 3 ) 和( 3 4 2 4 ) 用椭圆曲线方程化简然后检测( 3 4 2 5 ) 或( 3 4 2 6 ) 式： 当w 为偶数时有： g c d ( 4 ( x 3 + 爿x + b ) p 扎2 力 一 + 2 名，+ 一：丘。；o ，正( x ) )( 3 4 2 5 ) 当w 为奇数时有： g c d ( 4 ( x 3 + a x + b ) 州佗月3 一 + 2 一五l + l 一2 0 l - o ，兀( x ) )( 3 4 2 6 ) 当检测到( 3 4 2 5 ) 或( 3 4 2 6 ) 的值为1 ，则我们知道点p 满足中。p = 一w p ，则有 ，= 一2 w m o d l 。：否则就有p 满足p = w p ，且有，；2 w m o d l 至于w 的