（微电子学与固体电子学专业论文）双域椭圆曲线密码处理器设计.pdf

a bs t r a c t c r y p t 0 1 0 9 yc a nb ed i v i d e di n t ot h r e et y p e s ：s t r e a mc i p h e r ，s y m m e t r i c a lc i p h e r ( b l o c k c i p h e na n da s y m m e t r i c a lc i p h e r ( p u b l i c k e yc i p h e r ) a n d i ti st h ek e yt e c h n o l o g yo f i n f o 肿a t i o ns e c u r i t y a m o n gt h e s et e c h n o l o g i e s ，t h ep u b l i c - k e yc i p h e r i st h em o s t i m p o r t a n to n e c u r r e n t l y ，t h et w om a i nc r y p t os y s t e m sa r er s a ( b a s e d o ni fp r o b l e m ) a n de c c ( b a s e do ne l l i p t i cc u r v ed i s c r e t ep r o b l e m ) a l t h o u g hr s a c r y p t o s y s t e mi ss t i l l t h eb e s tk n o w na n dm o s tw i d e l yu s e dp u b l i c k e yc r y p t o s y s t e m ，e c cb e c o m e s m o r ea n d m o r ep o p u l a ri nr e c e n ts e v e r a ly e a r sa n dp l a ym o r ea n dm o r ei m p o r t a n tr o l ei nm o d e m i n f o 哪a t i o ns y s t e m ss i n c ei th a sh i g h e rs i n g l eb i ts e c u r i t ys t r e n g t h ，h i g h e ro p e r a t i o ns p e e d a n ds o m eo t h e ra d v a n t a g e sw h e nc o m p a r e dt or s a t h i st h e s i sf o c u s e so nt h ev l s id e s i g no fav e r s a t i l ee 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 ) p r o c c s s o r ah i g h s p e e d 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 mw i t ht h ef e a t u r eo f a n t i - a t t a c ki s p r o p o s e d ，w h i c he s p e c i a l l y b e n e f i t sd i g i t a lv e r i f i c a t i o no p e r a t i o n ；a c o m d l e t ei n s t r u c t i o ns e ti sp r e s e n t e d ，w h i c hc a ns u p p o r ta l lt h ef i n i t e f i e l da r i t h m e t i c i n c l u d i n gd u a l f i e l dm u l t i p l i c a t i o na n d d i v i s i o n ；m o n t g o m e r ym u l t i p l i c a t i o na n d d 1 v 1 s l o n o p e r a t i o n sa r eu n i f i e da ta l g o r i t h ml e v e lt oi m p r o v e t h ea r e ae f f i c i e n c y ；b yi n t e g r a t e dt h e d a t a p a t ho fm o n t g o m e r ym u l t i p l i c a t i o na n d m o d u l a rd i v i s i o n ，t h ep r o p o s e dp r o c e s s o 。c a n s u p p o r tt h ee ca l g o r i t h m sb a s e d o nb o t hg f ( p ) a n dg f ( 2 n ) t h ei m p l e m e n t a t i o nr e s u l tb a s e do ns m i c0 2 5 u r nc m o st e c h n o l o g y s h o w st h e a d v a n t a g e so fo u rc h i p i na s p e c t ss u c ha sa g i l i t y ，a n t i - a t t a c ka b i l i t ya n ds p e e dw h e n c o m p a r e dt ot h eo t h e r s t h ep r o p o s e dp r o c e s s o rc a n b ee a s i l yi n t e g r a t e di n t oa r m b a s e d e m b e d d e ds y s t e m st os u p p o r th i g h - p e r f o r m a n c ei n f o r m a t i o ns e c u r i t ys e r v i c e s k e yw o r d s ：e c c ，g a l o i sf i e l d ，f i n i t ef i e l d ，m o n t g o m e r y m u l t i p l i c a t i o n 聱 0 ； j 步 ， 囊 目录 i i i i i i 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 t 1 1 1 1 1 t 1 1 1 1 1 1 1 y 18 117 3 1 摘要2 a b s t r a c t ：； 第一章引言6 1 1公钥密码学及椭圆曲线密码学简史。6 1 1 1概念的形成_ 6 1 1 2公钥密码协议7 1 1 3椭圆曲线密码学的诞生7 1 1 4椭圆曲线密码系统的现状与未来8 1 2椭圆曲线密码算法的实现方案9 1 3论文主要工作及特点9 1 4论文内容安排1 0 【第一章参考文献】1 0 第二章椭圆曲线密码系统1 l 2 1椭圆曲线密码学的来源1 l 2 2椭圆曲线数学基础1 1 2 2 1 有限域理论1 l 2 2 2 椭圆曲线群运算1 3 2 3椭圆曲线密码协议2 0 2 4椭圆曲线点乘调度2 3 2 4 1二进制方法2 3 2 4 2固定点点乘算法2 4 2 4 3 m o n t g o m e r y 点乘方法2 4 2 5功耗分析技术2 6 【第二章参考文献】一2 6 第三章e c c 处理器数据通路实现算法2 7 3 1 g f ( p ) 域乘法运算2 7 3 1 1约减运算2 7 3 1 2针对特殊素数域的约减方法2 7 3 1 3b a r r e t t 方法2 8 3 1 4 m o n t g o m e r y 约减方法3 0 3 1 5g f ( p ) 域模乘实现方法小结与比较3 4 3 2g f ( 2 m ) 域模乘运算3 5 3 2 1 基于标准基的g f ( 2 m ) 域乘法器的设计3 5 3 2 2 基于标准基的d i g i t s e r i a l 有限域乘法器3 8 3 3求逆运算4 2 3 3 1基于费马小定理的求逆方法4 2 3 3 2基于扩展欧几里德算法的求逆方法4 3 【第三章参考文献】4 4 第四章m o n t g o m e r y 模乘器设计透视4 5 4 1m o n t g o m e r y 模乘方法4 5 4 2 m o n t g o m e r y 模乘算法4 6 4 4 2 1算法的时间和空间要求4 6 4 2 2 m o n t g o m e r y 模乘算法的分类4 7 4 2 3分离的操作数扫描算法( s o s ) 4 7 4 2 4粗粒度集成的操作数扫描算法( c i o s ) 。4 9 4 2 5细粒度集成的操作数扫描算法( f i o s ) 。5 0 4 2 6细粒度集成的积扫描算法( f i p s ) 51 4 2 7几种算法的比较5 2 4 3 m o n t g o m e r y 模乘器硬件实现。5 3 4 3 1 m o n t g o m e r y 模乘硬件算法5 3 4 3 2算法并行性分析5 4 4 3 3s c a l a b l em o n t g o m e r y 乘法器结构5 5 4 3 4两种改进方法5 6 【第四章参考文献】一5 8 第五章椭圆曲线密码处理器设计5 9 5 1点乘调度5 9 5 1 1转换算法5 9 5 1 2 k p 到h p + i q 的转换以及h p + i q 计算方法6 1 5 2椭圆曲线群运算6 2 5 3抗攻击性能6 4 5 4指令集定义6 4 5 5双域椭圆曲线处理器设计6 6 5 5 1双域椭圆曲线处理器结构6 6 5 ! ；2o j w k e ys h i f t e r 6 6 5 5 3译码器6 7 5 5 4 双域运算单元( d u a l f i e l da l 6 7 5 5 5多周期指令控制器6 8 【第五章参考文献】。7 2 第六章椭圆曲线密码处理器实现7 3 6 1 s o c 平台7 3 6 2f p g a 验证7 3 6 2 1 g f ( p ) 域点乘功能验证7 4 6 2 2 g f ( 2 m ) 域点乘功能验证7 5 6 3a s i c 实现结果7 6 6 4性能比较7 7 6 5 结论7 8 【第六章参考文献】。7 8 硕士学习期间学术论文及专利列表。7 9 致谢8 0 t 一 i 第一章引言 第一章引言 【摘要】本章介绍论文的研究背景和选题意义，交代论文的主要工作和贡献，给 出论文的章节安排。 1 1 公钥密码学及椭圆曲线密码学简史 椭圆曲线密码算法是一种高性能的公钥制密码算法，本节概要地介绍公钥密 码学和椭圆曲线密码学的发展历史及现状，使读者对本论文的背景有所了解。 1 1 1概念的形成 在公钥密码学的发展历史上，最有突破意义的是公钥密码系统概念的形成。 在2 0 世纪7 0 年代之前，密码算法只存在对称密码一种类型，通信双方必须事先 确定一个共享密钥，然后才能用来加密通信数据或者鉴别彼此身份。 2 0 世纪7 0 年代初r a l p hm e r k l e 等人提出了一种进行保密通信的新想法，现 在m e r k l e 博士是g e o r g i a 工业大学信息安全中心的一名知名教授，1 9 7 4 年的时 候他还是一个正在寻找季度作业课题的本科生，当时他偶然决定从密码学中寻找 合适的题目。正如他后来所说的：“让一个对密码学完全不懂的人来研究密码学 的问题，有利也有弊，优势就是不会局限于已有的框架，而困难则在于一开始很 难向别人表达清楚自己的想法。 m e r k l e 在思考如何为一个不安全的系统建立安全机制的问题时，开发了一 种所谓的“难题方法”，这是一种利用难题来建立难度可以控制的问题的方法。 在他给出的例子当中，a 随机想出一些难题发送给b ，b 也想出一些难题，收到 a 的难题之后，把两者进行比较，看是不是会出现相同的。如果有相同的，b 则 把它发回给a 。由于这个难题由a 、b 共同想出，因此他们俩能够找到解答( 在 m e r k l e 的描述中，答案是一个4 0 位的数) ，这个答案就可以用作他们的共享密 钥。 a 、b 可能要提出2 2 0 个难题才能找到一个碰撞，而窃听者要尝试2 4 u 种可能 才能解决这一难题得到a 、b 的密钥。也就是说窃听者需要付出更多的代价来得 到相同的结论。这一方法中有着公钥密码学思想的萌芽：虽然可以公布难题( 公 6 第一章引言 钥) ，但是其他人得不到答案( 私钥) ，与之相关的信息交换是安全的。 新的想法很少能够一下子变得很完美的，m e r k l e 自己也承认这一点，否则 他一定会很快受到别人的赞赏。在开始阶段，他并没有为自己的想法找到什么支 持，也没有能够把它实际应用到密码学中。幸运的是，他不是唯一有这种想法的 人，有一天有人告诉他：“你知道吗，b e r k e l e y 的几个小伙子有跟你类似的想法! 其实他们就是w h i td i f f i e 和m a r t i nh e l l m a n ，很快m e r k l e 跟他们成为合作者。 后来也就有d i f f i e 和h e l l m a n l 9 7 6 发表的那篇著名论文：“n e wd i r e c t i o n si n c r y p t o g r a p h y 1 1 2公钥密码协议 2 0 世纪7 0 年代出现了两种基本的公钥密码协议：19 7 5 年提出的 d i f f i e h e l l m a n 密钥交换方案；r i v e r s 、s h a m i r 以及a d e l m a n ( r s a ) 1 9 7 7 年提 出的数字签名方案。d i f f i e h e l l m a n 密钥交换方案安全性建立在离散对数难题基 础之上。r s a 则倚赖于大整数分解难题。 然而到了8 0 年代，研究者们意识到尽管这些难题本身确实非常难于求解， 要想获得足够得安全功能，还必须借助于精心设计得密码协议，需要一种精确定 义安全目标的方法，以及给出所设计的协议能够满足这些目标的证明。 在制定密码协议得时候，必须假设窃听者可能非常强大，而且他们的着手点 是密码协议中最为薄弱的关键环节。可能的最为强大的对手都不能攻破一个密码 协议中最为薄弱的关键环节，那么这个密码协议才是安全的。这一模型最终催生 了需要利用特定的计算假设来证明所设计的协议满足安全定义要求的“可坯织安 全”这一概念。 尽管直到上世纪9 0 年代中期，才产生了能够实用的可证明安全的密码协议。 在这之前已经取得了其它一些进展，最为显著的就是1 9 8 4 年产生的e l g a m a l 公钥加密和签名方案，作为r s a 的竞选方案，它的安全性建立在离散对数难题 基础之上而不是整数分解，同样1 9 8 5 年出现的椭圆曲线密码学( e c c ) 也是如 此。 1 1 3 椭圆曲线密码学的诞生 e c c 由v i c t o rm i l l e r 博士( 目前任职于普林斯顿通信研究中心) 和n e a l k o b l i t z 博士( 目前是华盛顿大学数学教授) 于上世纪8 0 年代提出。据他们两人 回忆，在他们发明e c c ，椭圆曲线一直是纯数学学科的一个非常神秘的领域， 7 一 i 3 9 第一章引言 很少有人考虑过它会有什么实际应用。 首先是椭圆曲线理论可以用来攻击密码系统这一思想开始流传，其催化剂便 是1 9 8 4 年关于整数分解问题的l e n s t r a 手稿。k o b l i t z 和m i l l e r 两人都开始考虑 椭圆曲线是否作为将来密码系统的基础。 这一考虑有很好的数学支持。在有限域中，对于一个给定的素数，有且只有 一个乘法群。同时，对于给定不同大小的素数，存在很多条椭圆曲线。p o h l i g 和 h e l l m a n 的研究工作证明了这一点很重要：离散对数难题的难度由群中最大的素 数决定。也就是说，椭圆曲线可以提供充足的曲线来满足极高的难度。最为重要 的是用来攻击其它公钥密码系统的“平方根边界 方法对椭圆曲线并不适用。 1 1 4 椭圆曲线密码系统的现状与未来 关于椭圆曲线密码系统的众多标准在上世纪9 0 年代纷纷诞生，它们包括： p k c s 、s s l 、n i s t 、i s o 、i e e e 、a n s i 以及其它。这一时期也出现了用来管 理公钥密码系统中大量验证工作的公钥密码基础设施( p k i ) 。 2 1 世纪以来，密码学出现了几项重大的进展。高级加密标准( a e s ) ，被用 来满足不同强度要求的安全需求。美国国家技术标准委员会( n i s t ) 坚持要求 在公钥密码领域必须采用与系统中a e s 安全强度一致、灵活性相当的算法，以 此作为选择依据，所有的公钥密码算法中e c c 最为合适。 在对带宽、功耗、占用资源受限的无线通信环境下，e c c 更是体现出了其 特有的适用性。由于e c c 的这些优势，美国国家安全局选择e c c 了作为密码 系统现代化计划所要求的新的、更强大的公钥密码算法。特别值得一提的是n s a 选择e c c 来实现密码交换协议、数字签名和加密等功能以保护机密的国家安全 信息。 同时研究者们一直在努力寻求现有公钥密码系统的替代品。然而到目前为 止，这些努力都没有成功：新发明的公钥密码系统或者在安全性上不如e c c ， 或者其运行速度太慢。许多研究者把研究方向转向了超椭圆曲线，超椭圆曲线是 更广义的椭圆曲线，椭圆曲线是超椭圆曲线的第一类。目前为止，第二类超椭圆 曲线被证明跟椭圆曲线安全强度相当，其他类的超椭圆曲线安全性则较弱，而第 二类超椭圆曲线的速度较慢，因此较e c c 并没有什么优势。 从诞生到现在这段比较短的时间跨度里，e c c 已经从纯数学数论发展成为 主流的密码学系统。同时正如n e a lk o b l i t z 博士所观察到的，在过去的3 0 年里， 密码学本身也在发生大的转变：从几乎是军事领域特有的技术变成现代商业和日 常生活中不可或缺的因素。现在e c c 已经迎来了它的黄金时期。 推荐的一种曲线参 数进行优化设计，以提高除了通用性以外的性能指标，也可以兼顾数种曲线参数 运算需求，设计成较为通用的硬件：可以只实现一种有限域( 素数域或者多项式 域) 上的椭圆曲线算法，以降低硬件开销，也可以设计成双域椭圆曲线芯片以增 大曲线参数的选择空间；可以采用硬连线的方式来实现以提高实现效率，也可以 从通用性角度出发，采用更加灵活的电路形式如f p g a 、可配置硬件、处理器等， 以获得很好的兼容性。 设计者必须对椭圆曲线算法有充足的了解，同时具备一定的v l s i 设计知识， 才能根据不同的要求在不同的性能指标中作出好的t r a d e o f f , 设计出满足要求的 硬件。 1 3 论文主要工作及特点 已有很多关于e c c 算法实现的设计方案，比较典型的是 1 】， 2 ， 3 】， 4 】。尽 管在椭圆曲线数字签名算法中必须用到求逆运算，目前为止仍没有具备双域求逆 功能的处理器设计报道。同时，考虑到快速求逆运算指令的引入也可以加速椭圆 曲线点乘运算，因此提出一种新型的e c c 处理器，在不增加很多硬件成本的前 提下引入双域求逆功能，显得非常必要。近些年来，旁道攻击技术给信息安全芯 片带来了很大的威胁，其攻击效率远远高于对算法本身的攻击。与之相应的，目 前也有不少防御攻击的方法相继被提出 5 】【6 】，但它们都是以牺牲较多处理器 速度和面积为代价，限制了处理器的性能。 本文对高性能通用椭圆曲线密码处理器设计进行了研究，在不同的层次均进 行了优化设计：采用0 j w ( 最优联合权重) 点乘调度算法加速点乘运算，提出了 具有抗攻击性能的高速点乘调度算法，该算法对签名运算的加速效果尤为明显； 设计了完备的指令集，可以支持双域乘法、除法等所有运算；在算法级统一模乘、 模除算法，以最大程度地复用硬件；通过引入双域求逆与m o n t g o m e r y 模乘相统 一的算法和数据通路，处理器能进行任意g f ( p ) 和g f ( 2 n ) 域上的有限域运算。 同时，采用处理器的形式来实现e c c 以增强通用性，在椭圆曲线在优化硬件 9 g - 一一 第一章引言 耗攻击能力的同时，达到了接近软件实现才具有的面积、速度以及增强芯片抗功 灵活性。 1 4 论文内容安排 本论文的核心内容为椭圆曲线密码芯片设计，全文共分为5 章： 1 ) 第一章为引论，介绍一些背景知识，交代论文的主要内容及安排； 2 ) 第二章为椭圆曲线密码系统综述，从最根本的数学原理、密码算法以及实现 上对e c c 做综合介绍； 3 ) 第三章围绕椭圆曲线密码处理器数据通路设计，对模乘、模逆等有限域运算 算法进行了详细介绍，椭圆曲线密码算法的运算都是定义在有限域上，有限 域运算能力直接影响到系统性能； 4 ) 第四章对m o n t g o m e r y 乘法进行单独介绍，模乘运算是目前公钥密码算法的 核心运算，m o m g o m e 巧模乘器的设计是整个密码芯片设计中的难点，直接 决定芯片的面积、速度和功耗等性能，这方面的内容非常丰富，因此单独介 绍。 5 ) 第五章系统地介绍一种双域e c c 处理器设计方案。 6 ) 最后给出芯片的f p g a 以及基于s m i c0 2 5 u r nc m o s 工艺的实现结果，芯 片目前处于封装阶段。 【第一章参考文献】 11j g o o d m a na n da c h a n d r a k a s a n a ne n e r g ye f f i c i e n tr e c o n f i g u r a b l e p u b l i c k e yc r y p t o g r a p h yp r o c e s s o r i e e ej o u r n a lo fs o l i d s t a l t e c i r c u i t s 2 0 0 1 ，v o l3 6 ( 11 ) ：18 0 8 18 2 0 f 2 1a k a s h is a t o ha n dk o h ji 亿出a n o as c a l a b l ed u a l f i e l de l l i p t i cc u r v e c r y p t o g r a p h i cp r o c e s s o r i e e et ra n s a c t i o no nc o m p u t e r s ，2 0 0 3 ，v 0 1 5 2 ( 4 ) ：4 4 9 4 6 0 f 31 a k d a n e s h b e ha n dm a h a s a a , a r e ae 伍c i e n th i g ls p e e de l l i p t i cc u r v e c r y p t o p r o c e s s o rf o rr a n d o mc u r v e s i t c c ，2 0 0 4 4 5 6 4 6 2 4 】p h i l i ph w l e o n g ，a n di v a nk h l e u n g am i c r o c o d e de l l i p t i cc u r v e p r o c e s s o ru s i n gf p g at e c h n o l o g y i e e et r a n s a c t i o n so nv e r yl a r g e s c a l ei n t e g 町i o n ( v l s i ) s y s t e m s ，2 0 0 2 ，v o l l 0 ( 5 ) ：6 1 7 7 1 2 【5 】h m a m i y a ，e f f i c i e n tc o u n t e r m e a s u r e sa g a i n s t 砒) a ，d p a ，a n ds p a p r o c c r y p t o g r a p h i ch a r d w a r ea n de m b e d d e ds y s t e m s ( c r i e s ) ，l n c s ，2 0 0 4 3 4 3 3 5 6 6 】m a r cj o y e t h em o m g o m e 巧p o w e r i n gl a d d e r p r o c c r y p t o g r a p h i ch a r d w a r e a n de m b e d d e ds y s t e m s ( c h e s ) ，l n c s 2 0 0 2 2 91 3 0 2 1 0 第二章椭圆曲线密码系统 第二章椭圆曲线密码系统 【摘要】本章从数学原理、算法、协议、差分功耗分析以及椭圆曲线算法的抗攻 击技术等方面完整地介绍椭圆曲线密码系统。 2 1 椭圆曲线密码学的来源 椭圆曲线的研究来源于求椭圆积分f 1 丽d x ，其中e ( x ) 是x 的三次或四次 多项式。这样的积分不能用初等函数来描述，由此引入椭圆函数的概念，继而引 ， 出了椭圆曲线。1 9 世纪上半叶，数学家们正致力于采用代数的方法来研究几何 学中的曲线问题，作为代数几何研究对象，椭圆曲线受到广泛的研究，产生了丰 富而又深奥的理论。在研究过程中，人们发现椭圆曲线具有非常神奇的特性，也 就是椭圆曲线上的任意两点相加所得第三点仍位于同一条曲线上。更重要的是， 椭圆曲线具有加密运算所必备的特性：椭圆曲线上点乘的逆运算是相当复杂的， 选取适当参数，其复杂度将为指数级，因此可以保证加密算法的安全性。 然而直n 1 9 8 5 年椭圆曲线系统才被用到密码学，由n e a lk o b l i t z ( 目前是华 盛顿大学的数学教授) 1 和v i c t o rm i l l e r ( 当时在i b m ，现在就职于普林斯顿通 信研究中心) 2 两人分别提出，之后逐渐成为公钥制加密算法领域的研究热点。 2 2 椭圆曲线数学基础 大多密码系统都需要用到代数群的概念，椭圆曲线可以用来形成椭圆曲线 群，所谓群就是一个相互之间满足特定算术运算规则的元素组成的集合。对于椭 圆曲线群，这种运算规则是在几何学上定义的。椭圆曲线可以定义在任何的域上， 密码学上采用的椭圆曲线都是定义在有限域( g a l o i sf i e l d ) 上的，下面分两小节 介绍椭圆曲线密码系统的数学基础知识。 2 2 1 有限域理论 定义1 ( 群) ：+ ”是非空集合g 上的二元运算，并且满足 1 ) + 是封闭的： 一 & ， 2 ) + 是可结合的： 3 ) 存在单位元e ； 4 ) 对集合g 内的任意元素x ，存在逆元x ，使得x + x 一= e ； 那么称代数系统 为群( g r o u p ) 比如( z ，0 ，+ ) 是群，( n ，0 ， + ) 不是群。如果集合g 为有限集，则称 是有限群，并把元素个数n 称为有限群g 的阶数。如果群 满足交换律，即a + b = b + a ，则称为阿贝 尔群( a b e l i a ng r o u p ) ，或者称为交换群 定义2 ( 域) ：“+ ”和“幸，是非空集合f 上的二元运算，并且满足 1 ) 为阿贝尔群，并且以0 作为+ ”运算的单位元； 2 ) f 中所有的非零元素在“ 运算上构成阿贝尔群，“ 运算的单位元为1 ； 3 ) “ 运算对“+ ”运算满足分配率：a 宰( 1 什c ) = a + a 宰c ，a , b ，c 为f 的任意元素 那么称代数系统 为域( f i e l d ) 比如q 、r 、c 都是域，z 、 实数系数多项式都不是域。 域是对常见数系( 比如有理数q 、实数r 和复数c ) 及其基本特征的抽象， 它由集合f 和两种运算加法( 用+ 表示) 和乘法( 用，一c 表示) 共同组成。如果集 合f 为有限集合，则称 是有限域。 有限域的元素个数称为有限域的阶。存在一个q 阶有限域f ，当且仅当q 是 一个素数的幂，即q = p r n ，其中p 是一个素数，称为有限域f 的特征，m 是一 个正整数。若m - - 1 ，则f 称为素域。若m l 则f 称为扩域。对于任意一个阶q ， 实质上只存在一个q 阶有限域，也就是说任意两个q 阶有限域是同构的，我们用 f q 表示他们。 设p 是一个素数，则模p 的全体余数的集合 0 ，1 ，2 ，p 一1 ) 关于模p 的加法和 乘法构成一个p 阶有限域，记为f p ，称p 为f p 的模。对于任意的整数a ，ar o o d p 表示用p 除a 所得到的余数r ，0 r p 1 ，这种运算称为求模p 的剩余。 阶为2 m 的域称为二进制域或特征为2 的有限域，记为f 2 m 。构成f 2 m 的一 种方法就是采用多项式基表示法。在这种表示方法中，域f 2 m 的元素次数最多为 m 1 次的二进制多项式。跟素域中的模p 对应，二进制域中存在一个1 1 1 次既约 多项式( 既约的概念是指该多项式不能被分解成次数低于m 的二进制域上多项 式的乘积) ，对于任意的m ，这样的多项式一定存在，并且能够有效产生。域中 元素之间的运算需要对该既约多项式取模约。 定义3 ( 二进制有限域的多项式表示) ：f 为一任意二进制域，f 上的多项式表示 1 2 - 一 簟 o 【j ， 第二章椭圆曲线密码系统 程式e 倪：y 2 = x 3 + a x + b 定义的实数域上的椭圆曲线，椭圆曲线的形状由a 、b 决定， 可以参见图l 、图2 * t l 图3 中的曲线形状。 y ， ! z 厂、 l li l 一 t o 峪 l 一7 l 弋 土 l 喜 尹= p 一缸+ 6 p 年玲= o 图1点p 的逆元 如果判别式4 a 3 十2 7 b 2 不为0 ，则椭圆曲线e r ：y 2 = x 3 + a x + b 可以用来形成一 个群。椭圆曲线群是加法群，其元素为椭圆曲线上的实数点和无穷远点，基本运 算为加法，曲线上两个点的加法在几何上由“t a n g e n t c h o r d ”也就是“弦与切线” 法则定义。 如图1 所示，椭圆曲线上的点p ( x ，y ) 逆元就是p 关于x 轴对称的点一e ( x ，- y ) ， 而且椭圆曲线上的每一个点都存在其逆点。 如图2 所示p 、q 为曲线上的两个不同点，而且p 不是一q ，求点p 与q 相加 后的点r 几何学上的方法就是，连接p q 两点的连线为l ，设l 和曲线e 相交 于另一点一r ，是点一r 和无穷远点0 的连线，和益线e 交于一点，该点 就是r 。 1 4 第二章椭圆曲线密码系统 一 乖 d + 坳 ” - ” ： ， - ￥ 。气屈 ，毪 芦= x a 7 x ，( - 2 3 5 ，- 1 8 6 ) q ( - o 1 ，0 8 3 6 ) - r 够8 9 ，5 6 2 ) 置岱8 9 ，- 5 6 2 ) 户+ q = 震= 侈8 9 ，- 5 6 2 ) 图2 点加的几何求解 倍点也就是一个点与它自己相加的方法如图3 所示，类似与点加，区别是 连线l 为点p 的切线，注意到p 点位于x 轴的情形，这种情况下倍点的结 无穷远点o ，如图4 所示。 y ， ； 一 t 。 ，iii f l _ 一 。，j ，i 夏 嵇，2 6 5 ) _ 震1 1 1 ，一2 6 4 ) 露1 1 l ，2 6 4 ) 2 o = 震拳( - 1 1 1 ，2 , 6 4 ) 户- x a 缸+ 5 图3倍点的几何学求解 一 一 图4倍点的特殊情况 尽管这种几何方法用来求椭圆曲线上的点之间的运算非常直观，但是在执行 算术运算的时候显得不是很实际，相比之下采用代数公式的方法能够更有效的计 算椭圆曲线几何算术，下面给出点加和倍点的计算公式。 若两个不同的点p = ( x p ，y p ) g 艮q - - ( x q ，y q ) 不互逆，r = ( x r ，y r ) 为两者相加之后 的点，则x r = s 2 一x p x q ，y r = 一y p + s ( x p x r ) ，其中s = ( y p y q ) ( x p x q ) ，注意 到s 是经过p 、q 两点连线的斜率。 若r = ( x r ，y r ) 是点p = ( x p ，) ，p ) 的倍点，y p 不为0 ，则x r = s 2 2 x p ，y r = y p + s ( x p x r ) ，其中s = ( 3 x p 2 + a ) ( 2 y p ) ，s 是点p 的切线斜率。 实数域运算需要采用浮点运算，非常费时，而且由于舍入误差的原因，也不 可能达到很到的精度。密码学上的运算要求快速、精确，因此实际采用的椭圆曲 线群是定义在有限域上的，也就是椭圆曲线群内的点是有限的。 f p 上的椭圆曲线可以通过选择椭圆曲线方程中的变量a 、b 属于f p 域而得 到，此时的椭圆曲线包含所有满足椭圆曲线方程式模p 的点。跟实数域一样，a 、 b 的取值必须满足判别式不为0 ，以得到椭圆曲线群。域f p 上的椭圆曲线公式 在定义椭圆曲线时已经给出。 1 6 第二章椭圆曲线密码系统 下面举一个例子来说明，考虑域f 2 3 上的椭圆曲线，令a - - 1 ，b = o ，椭圆 曲线方程式为y 2 = x 3 + x 。该椭圆曲线上有2 3 个点，分别是： ( 0 ，o ) ( 1 ，5 ) ( 1 ，1 8 ) ( 9 ，5 ) ( 9 ，1 8 ) ( 1 1 ，1 0 ) ( 1 1 ，1 3 ) ( 1 3 ，5 ) ( 1 3 ，1 8 ) ( 1 5 ，3 ) ( 1 5 ，2 0 ) ( 1 6 ，8 ) ( 1 6 ，1 5 ) ( 1 7 ，l o ) ( 1 7 ，1 3 ) ( 1 8 ，1 0 ) ( 1 8 ，1 3 ) ( 1 9 ，1 ) ( 1 9 ，2 2 ) ( 2 0 ，4 ) ( 2 0 ，1 9 ) ( 2 1 ，6 ) ( 2 1 ，1 7 ) 该椭圆曲线的图形如图5 所示。 g l l i p 6 x 硼稃ee 孵械麟户= + 嚣盯盱 图5域f ( 2 3 ) 上的椭圆曲线 x 注意到每一个x 值均对应着两个点。即使如此图形看起来是随机的，它仍然 关于y = 1 1 5 对称。在前面提到实数域椭圆曲线上每个点都有其逆点，两者关 于x 轴对称。在域f 2 3 上，y 坐标为负的点需要对2 3 取模，因此对称轴变成了 y = 1 1 s 。0 1 7 i 3 囊 定义在f p 域的椭圆曲线上的点之间的算术不再具备几何上的求解方法，其 代数计算公式，跟定义在实数域上的类似，唯一的区别就是所有的计算公式都是 模p 运算，因此在这里不再给出。 有限域f 2 m 的元素为m 比特字符串，可以通过多项式基表示或者最优标 准基来表示，不同的表示方法有不同的算术运算规则。定义在该域上的椭圆曲线 通过选择a 、b 属于f 2 m 域来得到( 唯一的条件就是判别式b 不为0 ) 。由于 该域的特征值为2 ，椭圆曲线方程式( 定义椭圆曲线处给出) 跟实数域和f p 域 有所不同。 下面举例说明f 2 m 域上的椭圆曲线，考虑有限域g f ( 2 4 ) ，域上元素采 用多项式基表示，不可约多项式为坟x ) = x 4 + x + 1 。该域的生成元为g = ( 0 0 1 0 ) ， g 的幂分别是： g o = ( 0 0 0 1 ) 9 1 = ( 0 0 1 0 ) 9 2 = ( 0 1 0 0 ) 9 3 = ( 1 0 0 0 ) 9 4 = ( 0 0 1 1 ) g s = ( 0 1 1 0 ) 9 6 = ( i i 0 0 ) 9 7 = ( i 0 1 1 ) 9 8 = ( 0 1 0 1 ) 9 9 = ( 1 0 1 0 ) 9 1 0 = ( 0 1 1 1 ) 9 1 1i ( 1 1 1 0 ) 9 1 2 = ( 1 1 1 1 ) 9 1 3 = ( 1 1 0 1 ) 9 1 4 = ( 1 0 0 1 ) 9 1 5i i ( 0 0 0 1 ) 在实际的密码学应用中，参数m 必须足够大，否则采用遍历法就可以攻破 密码系统，在现在的实际应用中，m 取1 6 0 以上比较合适。 考虑椭圆曲线y 2 + x y = x 3 + 9 4 x 2 + 1 ，这里a = 9 4 ，b = g o = 1 。满足该式 的点有1 5 个，假设点( 9 5 ，矿) 就是其中之一，则有( 9 3 ) 2 + 9 5 9 3 = ( 9 5 ) 3 + 矿9 1 0 + 1 ， 即9 6 + 9 8 = 9 1 5 + 9 1 4 + l ，由于( 11 0 0 ) + ( 0 1 0 1 ) = ( 0 0 0 1 ) + ( 1 0 0 1 ) + ( 0 0 0 1 ) = ( 1 0 0 1 ) ， 所以假设成立。下面列出所有满足上面椭圆曲线方程的点i ( 1 ，9 1 3 ) ( 9 3 ，9 1 3 ) ( 9 5 ，g l1 ) ( 9 6 ，9 1 4 ) ( 9 9 ，9 1 3 ) ( g l o ，g s ) ( 9 1 2 ，9 1 2 ) ( 1 ，9 6 ) ( 9 3 ，g s ) ( 9 5 ，9 3 ) ( 9 6 ，g s ) ( 9 9 ，9 1 0 ) ( g 加，g ) ( 9 1 2 ，o ) ( o ，1 ) ，o f ( 2 4 ) 上的椭圆曲线y 2 + x y