（计算机应用技术专业论文）快速产生安全椭圆曲线的研究.pdf

电子科技大学硕士论文：快速产生安全椭圆曲线的研究 摘要 椭圆曲线密码体制( e c c ) 建立在椭圆曲线群上离散对数( e c d l p ) 的难 解性这一数学难题。由于e c d l p 没有皿指数时间复杂度算法，e c c 在同等安 全强度下可以使用长度小得多的密钥长度。e c c 的“短密钥，高强度”使e c c 特别适台于像智能卡这样的资源受限环境。 快速产生安全的椭圆曲线是e c c 理论研究和实际应用的前提和基础。一种 方法是先产生伪随机椭圆曲线，再计算椭圆曲线的阶，判断是否满足素性或近素 性以及其它条件。但此方法的一个重大缺陷就是计算椭圆曲线的阶的困难性。 另一种方法就是构造给定阶的椭圆曲线，也就是所谓的复乘( c m ) 方法。为 了避免在加密或签名中信息泄漏，最好给定素数阶的椭圆曲线。 本文对构造素数域上特定的素数阶非超奇异椭圆曲线的c m 方法进行了详 细的分析，使用f l i n t c ( 用于大整数和数论函数) 软件包进行了具体实现，同 时为了提高产生安全椭圆曲线的速度，基于b l p i 并行实现了上述算法。 关键词：椭圆曲线密码体* o ( e c c ) ，椭圆蓝线，复乘方法，消息传递接口( m p i ) 电子科技大学硕士论文t 快速产生安全椭圆曲线的研究 a b s t r a c t i ti s g e n e r a l l y b e l i e v e dt h a tt h ed i s c r e t e l o g a r i t h mp r o b l e m i na n o n s u p e r s i n g u l a re l l i p t i c c u r v e 肜ki sm u c hm o r ed i f f i c u rt h a nt h ed i s c r e t e l o g a r i t h mp r o b l e mi n a6 n i t ef i e l do ft h es a m es i z ea s 丘s ot h ee l l i p t i cc u r v e c r y p t o s y s t e m sc a np r o v i d ee q u i v a l e n ts e c u r i t ya st h ee x i s t i n gp u b l i ck e ys c h e m e s u s i n gm u c hs h o r t e r s e c t e l k e y s s oe c ch a st h ea d v a n t a g eo fl o wr e s o l l r c e r e q u i r e m e n tf s u c ha ss m a r tc a r d ) a n di ti sv e r yf a s t f a s tg e n e r a t i o no fs e c u r ee l l i p t i cc u r v e si sp r e c o n d i t i o ni nt h ee c c sr e s e a r c h a n d a p p l i c a t i o n t h e r ea r ea n u m b e r o f w a y s t og e n e r a t ee l l i p t i cc u r v ep a r a m e t e r s s e l e c ta l la p p r o p r i a t ef i n i t ef i e l d t h e ns e l e c ta l le l l i p t i cc u r v eo v e rt h ef i e l da t r a n d o m ，c o u n tt h en u m b e ro fp o i n t so nt h ec u r v eu s i n gs c h o o l sa l g o r i t h m ，c h e c k w h e t h e rt h en u m b e ro fp o i n t si s n e a r l yp r i m e ，a n dr e p e a t u n t i l a p p r o p r i a t e p a r a m e t e r sa r ef o u n d h o w e v e re x i s t i n gi m p l e m e n t a t i o n s o fs c h o o f sa l g o r i t h ma r e 1 e s se m c i e n t s e l e c ta l - a p p r o p r i a t ef i e l d ，t h e ns e l e c ta i la p p r o p r i a t ec u r v eo r d e r ，a n dg e n e r a t e ac n v eo v e rt h ef i e l d 、 ，i mt h i sn u m b e ro fp o i n t s u s i n gt e c h n i q u e s b a s e do n c o m p l e xm u l t i p l i c a t i o n i f t h ec u r v eo r d e ri sp r i m e ，t h el e a k a g eo fi n f o r m a t i o ni s p r e v e n t e d i nt h ep a p e r , as c h e m eo fc o n s t r u c t i n ge l l i p t i cc u r v e so v e rt h ep r i m ef i e l di s a n a l y z e d a m e t h o dt oi m p l e m e n tt h es c h e m ei sd e s i g n e d ai l e wp a r a l l e l e ds c h e m e b a s e do nm p i c hi si m p l e m e n t e dt oi m p r o v et h ee f f i c i e n c yo f t h ec o m p u t a t i o n k e y w o r d s ：e l l i p t i cc u r v ec r y p t o g r a p h y ( e c c ) ，e c ，c o m p l e xm u l t i p l i c a t i o n ( c m ) ， m e s s a g ep a s s i n gi n t e r f a c e ( m p i ) i i 电子科技大学硕士论文：快速产生安全椭圆曲线的研究 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也 不包含为获得电子科技大学或其它教育机构的学位或证书而使用 过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示谢意。 签名：拉鲞盘日期：劲噼年0 4 月2 8 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论 文的规定，有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：盘巫盥导师签名：塑 日期：沙垆年f 月z 萝日 电子科技大学硕士论文：快速产生安全椭圆曲线的研究 a n s i c m d e s d s a e c e c c e c d h e c d l p e c d s a e c i e s e c m q v f l i n t f s m l f s t c g n b i e e e i s 0 m p i m p i c h m q v m r n i s t o n b p l ( i p k 缩略语 a m e r i e a nn a t i o n a ls t a n d a r di n s t i t u t e c o m p l e xm u l t i ，l i c a t i o n d a t ae n c r y p t i o ns t a n d a r d d i g i t a ls i g n a t u r ea l g o r i t h m e l l i p t i cc u r v e e l l i p t i cc u r v ec r y p t o g r a p h y e l l i p t i cc u r v e d i f f i c - h e l i m a n e l l i p t i cc u r v e d i s c r e t el o g a r i t h mp r o b l e m 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 e l f i p t i cc u r v ei n t e g m t e de n c r y p t i o n s c h e m e e l l i p t i cc u r v em e n e z e s - q u - v a u s t o n e f u n c t i o nf o rl a r g ei n t e g e ri nn u m b e rt h e o r ya n dc r y p t o g r a p h y f i n a n c i a ls e r v i c e sm a r k u pl a n g u a g e f i n a n c i a ls e r v i c e st e c h n o l o g yc o n s o r t i u m g a u s sn o r m a lb a s e i n s t i t u t eo f e l e c t r i c a la n de l e c t r o n i c se n g i n e e r s i n t e r n a t i o n a lo r g a n i z a t i o nf o rs t a n d a r d i z a t i o n m e s s a g ep a s s i n g i n t e r f a c e m e s s a g ep a s s i n g i n t e r f a c ec h m e n e z e s - q u - v a n s t u n e m i l l e r - r a b i n ( u s ) n a t i o n a li n s t i t u t eo f s t a n d a r d sa n dt e c h n o l o g y o p t i m a l n o r m a lb a s e p u b l i ck e yi n f r a s t r u c t u r e p u b l i ck e yi n f r a s t r u c t u r ef o r t h ei n t e r n e t i 电子科技大学硕士论文：快速产生安全椭圆曲线的研究 r s h r s a s e a s h a 1 s s l t l s w a p w t l s r e m o t es h e u r i v e s t s h a m i r - a d l e m a np u b l i c k e yc r y p t o g r a p h y s c h o o f - e l k i e s - a t k i na l g o r i t h m s e c u r eh a s ha l g o r i t h mr e v i s i o no n e s e c u r es o c k e t s l a y e r t r a n s p o r tl a y e rs e c u r i t y w i r e l e s sa p p l i c a t i o np r o t o c 0 1 w i r e l e s st r a n s p o r tl a y e r s e c u r i t y 电子科技大学硕士论文：快速产生安全椭圆曲线的研究 ，a 、 l j d e ( c ) ( e ( 兀) ，+ ) ( e ) ，( e ) g c d ( b ，m ) p i 聊 一d h d ( x ) 办( 一d ) 符号 有q 个元素的有限域 a 对b 的j a c o b i 或l e g e n d r e 符号 以e 为基域的椭圆曲线群的阶 以c 为基域的椭圆曲线群 椭圆曲线群e 的判别式， 椭圆曲线群e 的一不变量 b 和m 的最大公约数 p 整除m 负奇基本判别式 h i l b e r t 多项式 一d 的类数 电子科技大学硕士论文：快速产生安全椭圆曲线的研究 1 1e c c 及其标准 第一章引言 每种公钥密码体制都依赖于一个难解的数学难题。根据数学难题，已公认的 安全实用公钥体制可分为以下三类：( 1 ) 整数因式分解体制( w p ) ，基于大整 数因式分解计算的困难性，如r s a ；( 2 ) 离散对数体制( d l p ) ，基于有限域 离散对数计算的困难性，如d s a 、e i g a m a l ；( 3 ) 椭圆曲线离散对数体锘r ( e c d l p ) ， 基于有限域上椭圆曲线离散对数计算的困难性，如e c c 。 1 1 1e c c 简介 椭圆曲线密码体制在同等安全强度下可以使用长度小得多的密钥长度。例 如，1 6 0 位长的e c c 密钥具有的安全强度相当于1 0 2 4 位长的r s a 密钥。e c c 是目前提供每比特最高安全强度的公钥体制( 表1 1 。1 9 9 9 年8 月2 2 日r s a 一5 1 2 被攻破，密钥不得不被加长，密钥长度的增长，对本来计算速度缓慢的r s a 来洗， 更是不堪重负。e c c 的“短密钥，高强度”使e c c 可用较小的开销( 所需的计 算量存储量带宽软件和硬件实现的规模等) 和时延( 加密和签字速度高) 实现较高 的安全性特别适用于计算能力和集成电路空间受限( 如i c 卡) 带宽受限( 如无线 通信和某些计算机网络) 要求高速实现的情况。 表1 ：可比的密钥长度 s e c a t n y l w ，醴 l3 y n m a n m l c 薯髓锄e f x x ；- b m m t l 崔蝴e圳a f l t 强a f i nb i t s lin s i z e i nb i m l 舶i t 臻o f 霹缸b i t t l 。 “n o 酗岫暑妇i n b i t 曲 5 65 61 1 2 翻：2 , g o昱dl 鞠椭料 l j 2 l 】22 2 4猢 1 2 暑 2 矗2 5 6粥霭 1 9 21 9 23 j 8 47 枷 2 5 62 5 65 1 21 5 3 ；6 0 椭圆曲线密码体制的另一优点是椭圆曲线资源极丰富，由群论中的拉格朗日 定理 1 】可知，有限域只仅有有限的几个乘法子群。但是有数量级为q 的椭圆曲 线的同构类【2 1 。 定理设是有限域，则定义在上的椭圆曲线同构类的数目为： 吣) - 2 m + ( 争+ 2 9 ( 1 ) 电子科技大学硕士论文：快速产生安全椭圆曲线的研究 其中( 一) 是l e g e n d r e 符号 1 1 2e c c 标准 e c c 比较核心的标准 3 包括a n s ix 9 6 2 ，a n s ix 9 6 3 ，f i p s1 8 6 2 ，i e e e p 1 3 6 3 ，i e e ep 1 3 6 3 a ，i p s e c ，i s o1 4 8 8 8 3 ，i s 01 5 9 4 6 。 a n s ix 9 6 2 标准的e c d s a 用于财政金融行业，要求h a s h 使用s h a 1 ，椭 圆曲线参数n 2 ”o ，并且使用a n s i 所认可的伪随机数发生器等。 a n s ix 9 6 3 草案的密钥协商和密钥分发方案也用于财政金融行业，特别的， 它列出了基于e c i e s 、e c d h 、和e c m q v 的各种密码方案。像a n s ix 9 6 2 ， 它也要求h a s h 使用s h a 1 ，椭圆曲线参数n 2 ”o ，并且使用a n s i 所认可的伪 随机数发生器等。 f i p s1 8 6 2 标准中的三个签名方案用于美国政府，a n s ix 9 6 2 的e c d s a 也 是其中之一。 i e e ep 1 3 6 3 标准的密码方案有慕于大整数因子分解问题的，有基于传统离 散对数问题的，也有基于e c d l p 。基于e c c 的e c d s a 、e c d h 、和e c m q v 在i e e ep 1 3 6 3 分别称为e c s s a 、e c k a s d h l 、e c k a s m q v 。 i e e ep 1 3 6 3 a 草案作为i e e ep 1 3 6 3 的补充，包括e c i e s 。 i p s e c 标准支持e c d h 的变型，i p s e c 的椭圆曲线参数中，f 2 m ( m 为合数) 为默认值，并且基点的阶不为素数。 i s o1 4 8 8 8 3 标准的签名方案被确定为i s o 数字签名标准。 i s o1 5 9 4 6 草案采用基于e c c 的密码技术。i s o1 5 9 4 6 2 指定了签名方案， 包括e c d s a ：i s o1 5 9 4 6 3 指定了密钥建立方案，包括e c d h 、e c m q v 。 另外，f s t cf s m l 标准、p k i x 标准、s ，m i m e 标准、s s 坍l s 标准、w a p w t l s 标准、和w a p w m l s c r i p t c r y p t oa p i 标准广泛使用上述核心e c c 标准中 的密码方案。 值得一提的是s e c g 组织，s e c g ( t h es t a n d a r df o re f f i c i e n tc r y p t o g r a p h y g r o u p ) 是由加拿大c e r t c o m 公司( r s a 一5 1 2 破解的发起者) 发起的，包括v e f i s i g n 、 m o t o r o l a 、s u n 等，致力于提供可互操作的安全解决方案的联盟。s e c1 和s e c2 是s e c g 开发的e c c 标准，和绝大多数核心的e c c 标准兼容( 表2 ) 。 表2 ：s e c 中和核心的e c c 标准兼容的密码方案 电子科技大学硕士论文：快速产生安全椭圆曲线的研究 1 2 安全椭圆曲线的快速产生及其意义 所谓e c c 中椭圆曲线的产生，就是要确定椭圆曲线参数。 e c c 的安全性在于有限域上椭圆曲线离散对数的难解性这个数学难题。针 对e c d l p 有各种各样的攻击，所谓安全椭圆曲线，就是它能抵御目前的所有攻 击，我们通过选择椭圆曲线的参数和密钥来达到目的。 安全椭圆曲线是e c c 理论研究和实际应用的前提和基础，如果椭圆曲线不 安全，其后的各种快速算法的研究、密码体制的研究以及在实践中的应用成了空 中楼阁。 e c c 常用于智能卡和无线设备等计算资源或存储资源有限的环境，则对产 生安全椭圆曲线的快速算法的研究有重要的实践价值。比如，由于计算的复杂性， r s a 的密钥不会在智能卡中产生，而是预产生再装入智能卡，而e c c 可直接在 智能卡中产生参数和密钥。本论文通过选择合适的产生椭圆曲线的方法并对之并 行化的处理来达到快速性要求。 1 3 安全椭圆曲线的快速产生的研究现状 1 3 1 安全椭圆曲线快速产生的通用方法 安全椭圆曲线的快速产生通常有四种方法。 1 先产生伪随机椭圆曲线，再计算# 五( 疋) ，判断是否满足素性或近素性以 及其它条件。这种方法由于其参数的伪随机性，因此参数中不存在陷门， 且能抵御针对e c d l p 特定目的的攻击，安全性较高。因此s e c 、a n s i x 9 6 2 等e c c 标准所推荐的椭圆曲线参数都是由这种方法产生。但此方 法的一个重大缺陷就是计算拌e ( 瓦) 的困难性，虽然有s c h o o f 算法，该 算法的时间复杂度为o ( 1 0 9 9p ) ，可在多项式时间算出# e ( e ) ，并且还 电子科技大学硕士论文：快速产生安全椭圆曲线的研究 法。 有对该算法的各种改进方案，如s e a ，但这些算法在实践中还不够有效。 2 构造给定阶的椭圆曲线，这就是所谓的复乘( c m ) 方法。为了避免在 加密或签名中信息泄漏，最好给定素数阶的椭圆蓝线。 3 选择特殊的椭圆曲线，比如k o b l i t z 曲线的阶就容易计算，计算# e l ：e ) ， 判断是否满足素性或近索性以及其它条件。2 、3 产生椭圆曲线参数的效 率都比1 高，3 所选择的椭圆曲线，其特殊性导致标量乘法的效率很高。 但2 、3 的参数没有伪随机性，易遭受特定目的攻击。 4 直接选用s e c 、a n s i x 9 6 2 等e c c 标准所推荐的安全椭圆曲线。但这 些曲线的数量很少，比如s e c 2 仅推荐了3 条1 6 0 位椭圆曲线， a n s i x 9 6 2 则没有推荐，k o b l i t z 曲线的数量也不多，不能满足理论研究 和实践应用对安全椭圆曲线的需求。 综上所述，2 是目前比较可行产生椭圆曲线的方法。也是本论文所采用的方 1 3 2 研究现状 使用复乘( c m ) 方法产生安全的椭圆曲线，s e c l 、f i p s 、i e e e 等标准对如何 选择安全椭圆曲线的参数做了指导，但没有给出具体的算法和实现。 国内周长缨、何大可、徐秋亮等人基于国外学者研究成果做了进一步研究。 l a mky ，l i n gs ，l u c a sc kh u i 提出了效率更高的c m 方法 4 】： 拌e ( c ) = m ，m 原来要求具有一个形式为2 p + 1 的大素数因子( p 是一个素 数且q 2 1 ( m o d m ) ) ，在不损害安全性的情况下放宽到形式为2 咖+ 1 的素数( f 是 一个小整数) 。这样，适用于e c c 的安全椭圆曲线的数目显著增加，产生的椭圆 曲线也比原来的方案快得多。周长缨等人具体实现了该方法 5 。 徐秋亮等人提出的c m 方法 6 】构造出的椭圆曲线，其阶无平滑阶因子或者含 有多个大素数因子。在这类椭圆曲线上建立的公钥密码体制，消除了离散对数型 加密或数字签名方案信息泄漏的隐患。 a t k i n a ，m o r a i nf 等提出的c m 方法【7 】需要多次求解形如p = d ( t r ) 的模 方程，何大可等人提出的方法【8 直接搜索形如m 2 + d n 2 的整数并做素性检测得到 p ，效率得到了提高。 何大可等人提出的方法简洁明晰，效率较高，本论文以该方法为基础进行了 实现。 4 电子科技大学硕士论文：快速产生安全椭圆曲线的研究 1 4 论文的主要工作 1 对产生安全椭圆曲线进行了研究 2 对何大可等人提出的“构造素数域上特定的素数阶非超奇异椭圆曲线” 的c m 方法给出了具体实现 3 该方法的基于m p i 的并行实现 1 5 论文的章节安排 第二章对e c c 和产生椭圆曲线产生的一些基本概念和技术进行了全面的分 析和介绍，并对实现所用到的工具包f l i n t c 进行了大致的介绍。本章所涉及 的概念和技术将作为论文后续工作的基础。 第三章是论文的重点，论文的主要工作在此展开。包括何大可等人提出的算 法的描述，单机实现，基于m p i 的多机实现以及对实验结果的分析。 第四章是全文的总结，以及在本文基础上可进一步开展的研究工作。 电子科技大学硕士论文： 快速产生安全椭圆曲线的研究 第二章e c c 和f l i n t c 软件包 2 1e c c 本论文的选择的椭圆曲线是基域为奇素数特征有限域的椭圆曲线。 2 1 1 椭圆曲线 设基域e 为有q 个元素的有限域，射影平面砰上的齐次表达式： 】，2z + 口1 秽z + 口3y z 3 轷+ 口2 x 2z + 口4 您2 + 口6 2 3 ，称为w e i r s t r a s s 等式，其 中口l ，03 ，2 ，d4 ，口6 。 令蹦- r , z ) = y 2 z + a 1 x y z + a3 y z 3 - x 3 一口2 x 2 z - a 4 x z 2 一a6 2 3 ，则f ( x ，y ，z ) 称为w e i r s t r a s s 多项式。 当f ( x ，y ，z ) ( 嚣，等，篆) ( o ，0 ，o ) 时，由w e i r s t r a s s 等式所确定的曲线即为 椭圆曲线。 由于砰模型是由仿射平面鬈添加一条虚直线( 其上的点为虚点) 而成，故砰 上的椭圆曲线有其a ；上的等价形式，这只要在w e i r s t r a s s 等式中 设z 0 ，萨剧z ，y = y z ，则可将w e i r s t r a s s 等式以仿射坐标的形式改写为 y2 + 口1 工y + d3 芦3 + 口2 x2 + 口4 工+ 口6 如果椭圆曲线的特征值c h a r ( ) 2 ，3 ，那么可将椭圆曲线变换为 y2 鼍3 + 鼎怕一a , b ee 6 ( 3 ) 电子科技大学硕士论文：快速产生安全椭圆曲线的研究 2 1 2 椭圆曲线离散对数 给定点g e ( f q ) ，寻找一个整数女，使昭e ( ) 。其中，就是e ( ) 上 以g 为基k g 的离散对数，k g 表示与g 自身相加k 次，称为标量乘法或点积。在 e c c 中，k 为私钥，k g 为公钥。该离散对数的求解是很困难的。e c c 就是基于 有限域上椭圆曲线离散对数计算的困难性的。 2 1 3 椭圆曲线基域选择的考虑 椭圆曲线密码体制所关注的基域有两种类型：二元域。，它的特征为2 ，包 含了2 ”个元素，n 为大于1 的整数：素数域c ，特征为p ，包含了p 个元素，p 为奇素数。e c d l p 的计算复杂度日前已知仅仅和点群的阶有关，和有限域乘法 群不同，这里有限域代数结构不起作用，对于域尺寸近似相等的域e 。和， e c d lp 问题一样困难。 基域c 元素可用两种有效的方式来表示：正规基表示和多项式基表示。针 对只。，正规基能提高效率，因为正规基下有限域元素的平方是循环移位。在实 现k o b l i t z 椭圆曲线密码时，选择具有高斯优化正规基( g n b ) i 构基域。对c ，当 大素数p 是厂义梅森数时，对模p 的归约运算是非常有效的。例如取p = 2 2 2 4 2 9 6 + 1 ，令r n = l 0 9 2 p ，t = m 3 2 = 7 ，可用7 个3 2 位字存储一个域元素，大素数域中 的元素运算实质变成了多字运算。这时，对模p 的归约运算效率较高。 只在国外研究很多，大多数研究聚焦在通过f p g a 、d s p 、v i s l 等来设计 e c c 的处理器。只。中的元素选用恰当的表示方法，比如优化正规基( o n b ) ， 运算效率较高，比如它的模乘方运算可以通过移位来实现。的模加、模乘、 模乘方、模逆等很适合硬件实现。 本论文的实验条件为：p c 机或p c 集群，c 更加利于实验和实现，因此本 论文研究基于奇素数特征的有限域e 上的椭圆曲线的产生。 电子科技大学硕士论文： 快速产生安全椭圆曲线的研究 2 1 4 奇素数特征有限域上的椭圆曲线 有限域e ，p 3 ，p 为奇素数，其上的椭圆曲线方程为 y 2 三x 3 + 甜+ 6 ( m o d p ) ，a ，b c e ( ) = ( x ，y ) ly 2 ；x 3 + 鼎+ 6 ( m o d p ) ) u 0 1 ，o 为无穷远点 在e ( 只) 定义点加运算，记为“+ ” v p e ( 只) ，o + p = p + o 一0 = 0 ： v 尸e ( e ) ，p = ( _ ，y 1 ) 0 ，贝0 一p = ( _ ，一y 1 ) 如果q = - p ，则p + q = d ； 如果p 0 ，q 0 ，q - p ，p = ( ，y 1 ) ，q = ( x 2 ，y 2 ) ，则p + q = r = ( x 3y 3 ) 丛丛，工l x 2 工2 一葺 3x12+a，五：而2y l 1 x 3 = a 2 一x 1 一心 儿= a ( x l 一而) 一y ( e ( ) ，+ ) 构成a b e l 群，e ( 匕) 的元素称为e 的“巴一有理点”，e ( ) 相 应称作e 的“一有理点集”。e c c 就是建立在群e ( 0 ) 的密码体制。 记( e ) = 一1 6 ( 4 a3 + 2 7 b 2 ) ，j ( e ) = 一1 7 2 8 ( 4 a ) 3 a ( e ) ， a ( e ) 称为e 的判别式，j ( e ) 称为e 的，一不变量 在通过复乘( c m ) 方法构造椭圆曲线时，会用到h a s s e 定理。 定理( h a s s e 定理)令f e ( c ) = g + 1 一t ，贝1 l t l 2 i 电子科技大学硕士论文：快速产生安全椭圆曲线的研究 2 2 奇素数特征的有限域椭圆曲线的参数及其产生步骤 2 2 1 椭圆曲线参数 奇素数特征的有限域瓦上的椭圆曲线的参数是六元组 t = ( p ，a ，b ，g ，n ，h ) 其中， p ：的特征，也是c 的大小 d ，b ：a ，b c 决定椭圆曲线方程 e ( f p ) ：歹2m x 3 + 麟+ 6 ( m o d p ) g ：e c c 的基点 ：素数，g 的阶 h ：余因子，h = # e l ：c ) h 椭圆曲线参数指定了一条椭圆曲线和基点，这是建立e c c 的基础。 2 2 2 产生步骤 输入：建立e c c 所要求的安全级别，用t 来衡量 f 5 6 ，6 4 ，8 0 ，9 6 ，11 2 ，1 2 8 ，1 9 2 ，2 5 6 输出：上椭圆曲线参数t = ( p ，a ，b ，g ，z ，h ) 步骤： 1 选择奇素数p 3 来确定有限域 l 0 9 2 p = 2 t ，2 5 6 l 0 9 2 p = 5 2 1 f = 2 5 6 2 选择o ，b 确定椭圆曲线方程 y 2e x 3 十甜十6 ( m o d p ) 口b e e ( f v ) 9 电子科技大学硕士论文：快速产生安全椭圆曲线的研究 3 选择基点g ，g 的阶 ，余因子h g ( ，) e ( e ) ： 2 x g 3 + + 6 ( m o d p ) i 是素数，且n g = 0 0 ，可得出，存在唯一因子分解 z = d v 2 ，其中d 是正的非平方数。因此， 4 p = “2 + d v 2( 5 ) 些整数“满足 m = p + 1 “f 6 1 d 称为c m 对素数p 的判别式。c m 方法用j d 决定j 一不变量和构造阶为p + l 一“ 或p + 1 + “的椭圆曲线。 使用这个方法，首先找到素数p ，再找到满足( 6 ) 的“、和满足( 5 ) 的最 小d 。然后检测珑= p + l 一“或脚= p + l + “是否满足安全条件。反复此过程直到 这样的7 找到a 找到合适的脾之后，基于d 构造h i l b e r t 多项式，并求出该多项 式的根。h i l b e r t 多项式的一个根就是_ ，一不变量。由，一不变量构造椭圆曲线e 和 电子科技大学硕士论文：快速产生安全椭圆曲线的研究 e ，这两条椭圆曲线只有一条的阶满足要求。随机选取e 上的点p ，和e 的点 p ，若m p 0 ，则e 的阶为m ，反之，若m p o ，则e 的阶为m 。 c m 方法的关键点是构造高精度浮点和复数算术的h i l b e r t 多项式，所需计 算成本较高。 为了克服这个问题，c m 的一个变型被提出【9 。它输入c m 判别式d ( d ；3 ( m o d 4 ) ) ，计算p 和m ，要求研是一个素数，通过随机选择u 和v ，再检 测p = 2 + v 2 ) 4 ，而得到一定长度的素数p 。这种变型h i l b e r t 多项式的计算只 依赖于d ( 和p 无关) ，因此d 和- ，一不变量可以预计算。何大可等人提出的复 乘( c m ) 方法基本上与这种变型相同。 c m 的另外一个变型 1 0 】与上面的变型类似，不同之处在于它用w e b e r 多项 式代替h i l b e r t 多项式。首先随机选择素数p ，再用c o m a c c h i a 算法计算“和v ， 最后判断m 是否满足安全条件。这里删要求近素性，m = n q ，n 是一个小整数， q 2 且玎是素数。其步骤如下： 预计算阶段： 1 选择判别式d ；o 或3 ( m o d 4 ) 并且d 3 ( m o d 8 ) 2 用d 构造w e b e r 多项式 主阶段： 3 随机选择素数p ，用c o m a c c h i a 算法计算出( 6 ) 的解u 和v ，若无解， 重新选择素数p 。直到合适的素数p 找到，p 就是基域e 的特征p 。 4 椭圆曲线的阶是m = p + 1 一u 或研= p + 1 + u ，检测m 是否满足安全条件， 若不是，回到3 5 计算w e b e r 多项式的根，转换w e b e r 多项式的根为h i l b e r t 多项式的根。 6 h i l b e r t 多项式的根代表了，一不变量，以此构造椭圆曲线e 和e 。 7 随机选取e 上的点p ，和e 的点p ，若聊p 0 ，则e 。的阶为朋，反之， 若m p o ，则e 的阶为m 。 2 4f l i n t i c 软件包 f l i n t c 软件包是德国的密码学专家m i c h a e l w e l s c h e n b a c h 编写的用于大数 运算和数论函数运算的函数库【1 1 ，f l i n t c 这个名字是f u n c t i o nf o rl a r g e i n t e g e r si nn u m b e rt h e o r y a n d c r y p t o g r a p h y ( 用于数论和密码学的大整数的函数) 电于科技大学硕士论文；快速产生安全椭圆曲线的研究 的缩写，有c 和c + + 两个版本。本论文采用的是c 版本。 1 大整数的表示 在公钥密码体制中，参加运算的是长达几百位的大整数。f l i n t c 软件包定 义了特殊的数据结构表示大整数。 ( 1 ) 出于内存管理会消耗计算时间的考虑，所有的大整数都是静态存储的。 ( 2 ) 出于效率原因，要使大整数的运算直接化为c p u 寄存器的运算，因此， 大整数的分量采用标准数据类型。f l i n t c 选择了u n s i g n e ds h o r t i n t ( 下 面称为u s h o r t ) 。 ( 3 ) 一个大整数在内存中表示格式为 n = ( 啊慢伟) b0 n j 1 的m i l l e r - r a b i n 概率素性检验 1 确定q 和r ，使得n 一1 = 2 q ，q 为奇数。 2 随机选择一整数a ，l a n 。置e 卜0 ，b 卜a 9 m o d n 。若b = 1 ，输出 “n 可能是素数”，并终止算法。 3 旦b 1 m o d n ，并且e t 一1 ，置b x ) + i n f i n i t e ) = 1 u ；( +