（信号与信息处理专业论文）椭圆曲线加密算法的研究与实现.pdf

摘要 安全问题在现今通信与计算机网络中扮演了非常重要的角色。随着i n t e m e t 越来越被 大众所接受与使用，各种商业和社会业务开始转化为电子形式在网上进行。使用各种各 样的加密算法，可以保证这些活动的安全性。椭圆曲线密码体制是一种公钥密码体制， 最早由m i l l e r 矛t l k o b l i t z 分别独立地提出。相对于以往基于有限域上离散对数问题或大整数 分解问题的传统公钥算法，椭圆曲线密码算法具有安全性高、速度快、密钥短、实现时 所需占用资源少的特点。自从椭圆曲线密码提出后，广大科研工作者对椭圆昀线密码理 论进行了大量的研究，目前对于椭圆曲线密码理论的研究特别是对椭圆曲线密码体制的 实现技术的研究是密码学界和产业界的一个热点。 本文首先研究了现代密码学相关的基本理论与密码系统的数学模型，介绍了现存的 三种公钥加密算法，特别是椭圆曲线加密算法。然后介绍了与椭圆曲线加密密切相关的 有限域、有限群等理论。接着详细阐述了椭圆曲线的结构，基于二进制有限域上的模乘、 模平方、模逆运算和基于有限群上的点加、点乘、倍点运算。对于各种运算按照层次化、 模块化的设计思想，采用硬件描述语言v e r i l o g 作为设计输入进行椭圆曲线加密算法的设 计，在每个设计层次和每个模块都进行了仿真综合验证，得以保证底层设计的正确性。 在确保每个模块的设计f 确后，完成对电路的顶层设计，进行总体的仿真综合，并用 m a t l a b 验证所实现的算法的正确性。在实现二进制有限域上的模乘运算时，采用了一 种基于查找表的模乘方法，该方法在消耗了一定硬件资源的基础上，提高了模乘的计算 速度，从而加快了整个椭圆曲线加解密的速度。 关键字：公钥加密算法；椭圆曲线加密：点乘；模乘：查找表 r e s e a r c ha n d i m p l e m e n t a t i o n o f e l l i p t i cc u r v ec r y p t o g r a p h ya l g o r i t h m a b s t r a c t s e c u f i t yi s s u e sa r ep l a y i n ga r ti m p o r t a n tr o l ei nt h em o d e mc o m m u n i c a t i o na n dc o m p u t e r n e t w o r k s a st h ei n t e m e tb e c o m e sm o r ea n dm o r ea c c e s s i b l ef o rt h ep u b l i ct ou n d e r s t a n da n d e m p l o y , m a n yk i n d so f c o r r m a e r c i a la n ds o c i a lt r a n s a c t i o n sc a nb ep e r f o r m e de l e c t r o n i cf o r i l li n t h en e t w o r k u s i n ga l lk i n d so f c r y p t o g r a p h i ca l g o r i t h m sc a r li n s u r es e c u r i t yo f t h e s ea c t i v i t i e s e l l i p t i c c u r v ec r y p t o g r a p h y ( e c c ) s y s t e m s ，w h i c ha r eas e r i e so fp u b l i c - k e ys y s t e m s ，a r e p r e s e n t e df i r s tb ym i l l e ra n d k o b l i t zi n d e p e n d e n t l y e l l i p t i ce u l w e sc r y p t o 静a p h ya l g o r i t h mh a s ah i g h s a f e t yp r o p e r t y a n df a s t e r s p e e d ，a l l o w sf o r s h o r t e rk e y l e n g t h s ，r e q u i r e sf e w e r c o m p u t a t i o n a lr e s o u r c e sf o ri m p l e m e n t a t i o nt h a no t h e rt r a d i t i o n a lp u b l i c k e ya l g o r i t h m sb a s e d o nt h ed i s c r e t el o g a r i t h mi nf i n i t ef i e l d sa n dt h ei n t e g e rf a c t o r i z a t i o np r o b l e m t h et h e o r yo f e c ci s b e i n gs t u d i e dal o ta n di t i st h ef o c u so ft h ec r y p t o g r a p h ya n dt h ei n d u s t r i a le s t a t e ， e s p e c i a l l yt h et e c h n i q u eo f t h ei m p l e m e n t a t i o n o f e c c t h ef u n d a m e n t a lt h e o r yo ft h em o d e m c r y p t o l o g yi sf i r s t l yr e s e a r c h e d ，t h r e es o r t so f e x i s t e d p u b l i c k e ya l g o r i t h m sa n de l l i p t i cc u r v e sc r y p t o g r a p h ya l g o r i t h ma l ei n t r o d u c e dt o o s e c o n d l y ， g a l o i sf i e l dt h e o r ya n df i n i t eg r o u p t h e o r yr e l a t e dw i t he l l i p t i cc u r v ec r y p t o g r a p h y a r ed i s c u s s e d f h e nt h es t r u c t u r eo fe c ci s e x p a t i a t e di nd e t a i l ，t h ea l g o r i t h m so fm o d u l a rm u l t i p l i c a t i o n ， m o d u l a rs q u a r i n g ，m o d u l a ri n v e r s i o nb a s e do ng a l o i sf i e l da n d p o i n ta d d i t i o n ，p o i n t m u l t i p l i c a t i o n ，d o u b l ep o i n tb a s e do nf i n i t eg r o u pa r ef o c u so nt o o ，t h i st e s i sa s c e r t a i nt h e i m p l e m e n t a t i o n o f e l l i p t i cc h i v e sc r y p t o g r a p h ya l g o r i t h mf o rh a r d w a r ep r o j e c t ：a c c o r d i n gt ot h e d e s i g n i d e ao fh i b e r a r c h ya n dm o d u l a r i z a t i o n ，w ea d o p tv e r y h i g hs p e e di ch a r d w a r e d e s c r i p t i o nl a n g u a g e ( v e r i l o g ) a sd e s i g ni n p u t ，s i m u l a t i o na n ds y n t h e s i st h ed e s i g ni ne v e r y j e v e la n de v e r ym o d e lf o rt h ec o r r e c t i o no ft h ef u n d a m e n t a ld e s i g n a t i e rt h a t f i n i s ht h et o p d e s i g n u s i n gm a t l a bv e r i f i e s a l lo ft h e s e d e s i g n s w h e ni m p l e m e n t a t i o nm o d u l a r m u l t i p l i c a t i o nb a s e d o ng a l o i sf i e l d ，ak i n do f m o d u l a r m u l t i p l i c a t i o nb a s e do nl o o k u pt a b l ei s p r e s e n t e d o nt h ec a s eo fc o n s u m p t i o ns o m eh a r d w a r er e s o u r c e ，c a l c u l a t i n gs p e e do fm o d u l a r m u l t i p l i c a t i o ni si n c r e a s e d ，t h ee f f i c i e n c yo f e l l i p t i cc u r v e sc r y p t o g r a p h yi si n c r e a s e dt o o k e yw o r d s ：p u b ii c k e y p o i n tm u i t c r y p t o g r a p h ya i g o r i t h m ： e p ii c a t i o l 3 ：m o d u i a rm u i t i p ip tiec u r v e s c r y p t o g r a p h y c a t i o f t ：l o o k u dt a b i e 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究丁作 及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理工大学 或其他单位的学位或证书所使用过的材料。与我一同工作的同志对本研究所 做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：乇瀣鹾日期：塑堕! i ： 椭圆曲线加密算往的研究与实现 0 前言 密码学是一门研究信息安全且跟数学密切相关的学科，它有古老和悠久的历史，早 在2 0 0 0 多年前，就出现了著名的凯撒密码。1 9 7 6 年，d i f f i e s f d h e l l m a n 提出的密码学的新 方向一文导致了密码学上的一场革命。他们首次证明了在发送端和接收端无密钥传输 的保密信息是可能的，从而开创了公钥密码学的新纪元。此后，大量的公开密钥密码体 制被陆续提出柬，所有这些体制的安全性依赖于数学问题的难解性。几十年来，许多曾 经被提出的公丌密钥密码体制已经被攻破了，也有许多被证明是不实用的。迄今只有三 类体制被证明是安全的和有效的，这些体制根据它们所依据的数学问题，可分类为：大 整数因子分解问题( r s a ，由其发明人r o n a l d l r i v e s t ，a d is h a m i 和l e o n a r dm a d l e m a n 的 姓名而得来的密码体制，是己知的最好例子) ，离散对数问题( 例如：e l g a m a l 体制) 以及椭 圆曲线上的离散对数问题。 椭圆曲线密码体制( e c c ，e l l i p t i c c u r v e c r y p t o g r a p h y ) 是由n e a lk o b l i t z 和v i c t o r m i l l e r 在1 9 8 5 年分别独立提出的1 2 】，它所基于的数学问题的困难性被公认是目前已知的公 钥密码体制当中每b i t 提供加密强度最高的一种，数学问题越难，意味着越小的密钥尺寸 能产生等价的安全性。 e c c 作为公开密钥密码体制中的一种，在丰富的理论基础上可以实现高度的安全性， 它具有存储效率、通信带宽的节约以及计算效率等多方面的优越性，是一种非常有前途 的密码体制。德国、日本、法国、美国、加拿大等国的很多密码学研究小组及一些公司 实现了椭圆曲线密码体制，我国也有一些密码学者做了这方面的工作。近年来，e c c 被 广泛应用于商用密码领域，这可由e c c 被许多著名的国际标准组织所采纳佐证，屯i i i e e e 、 n i s t ( 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 d t e c h n o l o g y ) 、i s o 、a n s i ( a m e r i c a nn a t i o n a ls t a n d a r d si n s t i t u t e ) ，包括： 卜i e e ep 1 3 6 3 加密、签名、密钥协商机制 卜a n s ix 9 椭圆曲线数字签名算法、椭圆曲线密钥协商和传输协议 - i s o i e c 椭圆曲线e 1 g a m a l 体制签名 卜i e t f 椭圆曲线d h 密钥交换协议 卜a t m f o r u m 异步传输安全机制 卜f i p sl8 6 2 美国政府用于保证其电子商务活动中的机密性和完整性 目前，国外有大量的厂商已经使用或是计划使用椭圆曲线密码体制。加拿大的 c e r t i c o m 把公司的整个赌注都投在椭圆曲线密码上，专门生产e c c 产品，给其它公司提供 服务，现已授权3 0 0 耋；家企业使用e c c 密码技术，包括c i s c o 系统有限公司、摩托罗拉等： s e t ( s e c u r ee l e c t r o n i ct r a n s a c t i o n ) 的发展商g l o b e s e t 公司则计划将e c c 用于付费应用当 中。s e t 协议的创立者s a 牙t l m a s t e r c a r d 组织对e c c 也给予了相当的关注。e c c 对r s a 己经 形成强劲的挑战，对于椭圆曲线密码的研究也是方兴未艾。目前国内只有少数单位投入 力量开发e c c ，但e c c 具有许多r s a 无法比拟的优点，所以e c c 必将取代r s a ，成为下一 代公钥加密算法的代表。 本课题来源于加密网卡的一部分，为了既保证加解密的速度，又保证加解密的安全 性，在加密网# 中对于明文的加密采用d e s ，t d e s ，a e s 等对称加密算法，丽用r s a 、 e c c 这两种公钥加密算法加密d e s ，t d e s ，a e s 等对称加密算法的密钥。这样既可以保 椭圆曲线加密算法的研究与实现 证明文的加解密速度，又可以保证加解密的安全性。 这篇文章共分五部分。 第一章主要介绍了密码学的基本知识及其分类，着重介绍r 公钥加密算法的理论基 础，并对现今流行的三类公钥密码体制所依赖的数学难题加以比较，总结了e c c 算法的 优点。 第二章对于椭圆曲线加密系统中用到的各种参数作了介绍，在分析比较了各种参数 的特点之后，选取了适合于本文使用的各种参数，在选定参数的基础上划分出椭圆曲线 加解密系统的层次，制定出该算法的体系结构。 第三章介绍t - - 进制有限域上的各种运算，给出二进制有限域上的模加、模乘、模 平方和模逆运算的理论基础，把各种算法设计成单独的模块，根据算法写v e r i l o g 程序， 用m o d e l s i m 进行仿真，用s y n p l i f y 进行综合，分析了仿真与综合的结果，用m a t l a b 加以 验证。特别是对于模乘运算，提出了一种基于查找表的模乘算法，在消耗了一定的硬件 资源的日口提下，加快了模乘的计算速度。 第四章介绍了基于椭圆曲线上的点构成的a b e l 群上的各种运算，给出点乘、点加、 和倍点运算的理论基础，在用v e f i l o g 语言实现这四种运算的时候，分别设计了满足于这 三种算法的有限状态机，为了便于上层控制模块的调用，也把这三种算法设计成单独的 模块，同样用m o d e l s i m 进行仿真，用s y n p l i f y 进行综合，分析了仿真与综合的结果，用 m a t l a b 验证了算法的正确性。 第五章对于椭圆曲线加密算法进行了总结与展望。 椭圆曲线加密算法的研究与实现 1 密码理论 本章将主要介绍密码学的一些基本概念。在给出了密码学基本概念及其分类的基础 i ，特别详细介绍了公钥加密算法和现存的三种公钥加密算法所依赖的数学难题以及各 自的特点，给出椭圆曲线加密算法的优点。 1 1 密码学基本概念 密码的历史极为久远，早在四千多年前，古埃及人就开始使用密码来保密传递的消 息。虽然密码是一门古老的技术，但自密码诞生直至第二次世界大战结束，它始终与军 事、机要、间谍等工作联系在一起，只有少数人掌握和控制，对于公众而言，密码始终 处于一种未知的黑暗当中。 信息技术的发展迅速改变了这一切。随着计算机和通信技术的迅猛发展，大量的敏 感信息常常通过公共通信设施或计算机网络进行交换，特别是i n t e r n e t 的广泛应用、电子 商务和电子政务的迅速发展，越来越多的个人信息需要严格保密，如：银行账号、个人 隐私等。正是这种对信息的秘密性与真实性的需求，密码学才逐渐揭去了神秘的面纱， 走进公众的日常生活当中。 密码的基本思想是对机密信息进行伪装。一个密码系统完成如下伪装：某用户( 加 密者) 对需要进行伪装的机密信息( 明文) 进行变换( 加密变换) ，得到另外一种看起来 似乎与原有信息不相关的表示( 密文) ，如果合法的用户( 接收者) 获得了伪装的信息， 那么他可以从这些信息中还原得到原来的机密信息( 解密变换) ，而如果不合法的用户试 图从这种伪装后的信息中分析得到原有的机密信息( 密码分析者) ，那么，要么这种分析 过程根本是不可能的，要么代价过于巨大，以至于无法进行。 窃听密码分析者 - t - i 尤 图1 】密码系统示意图 f i g 1 1c r y p t o s y s t e ms k e t c hm a p 文 准确地说，一个密码系统由明文空间、密文空间、密码方案和密钥空间组成口】。 ( 1 ) 加密的信息称为明文。明文的全体称为明文空间。一般情况下，明文用m ( 或 m ，即消息，m e s s a g e ) 或p ( 或p ，即明文，p i a i n t e x t ) 表示。明文是信源编码符号，可 能是文本文件、位图、数字化存储的语音流或数字化的视频图像的比特流。可以简单地 认为明文是有意义的字符流或比特流。 ( 2 ) 密文是经过伪装后的明文，全体可能出现的密文的集合称为密文空间。一搬情 况下，密文用c ( 或c ，即c i 【p h e r ，密码) 表示，它也可以被认为是字符流或比特串。 ( 3 ) 密码方案确切地描述了加密变换与解密变换的具体规则。这种描述一般包括对 明文进行加密时所使用的一组规则，称为加密算法：使用加密算法对明文实旌的变换过 椭圆曲线加密算法的研究与实现 程称为加密变换，简称为加密：以及对密文进行还原时所使用的一组规则，称为解密算 法；使用解密算法对密文实施的变换过程称为解密变换，简称为解密。 ( 4 ) 加密和解密算法的操作通常在称为密钥的元素( 分别称为加密密钥与解密密钥) 控制下进行。密钥的全体称为密钥空间。一般情况下，密钥用k ( 或k ，即k e y ，密钥) 表示。密码设计中，各密钥符争一般是独立、等概出现的，也就是说，密钥一般是随机 序列。 一个保密系统可以完整地表示为如图1 1 所示的模型p 1 。 1 2 密码体制的分类 根据加密算法与解密算法所使用的密钥是否相同，或是否能简单地由加解密密钥求 得解力密密钥，可以将密码体制分成私钥密码体制( 也叫单钥密码体制、对称密钥密码 体制) 和公钥密码体制( 也叫作双钏密码体制、非对称密钥密码体制) f 4 】。 1 2 1 私钥密码体制 如果一个保密系统的加密密钥和解密密钥相同，或者虽然不相同、但由其中的任意 一个可以很容易地得知另外一个，这种保密系统就称为私钥密码体制_ 1 。例如：d e s ( d a t a e n c r y p t i o ns t a n d a r d ) 、t d e s ( t r i p l e d a t a e n c r y p t i o ns t a n d a r d ) 、i d e a ( i n t e m a t i o n a i d a t a e n c r y p t i o n a l g o r i t h m ，i d e a ) 、r c 5 ( r c = r o n s c o d e r o n = r o n r i v e s t o f r s a f a m e ) 、a e s ( a d v a n c e de n c r y p t i o ns t a n d a r d ) 等都是私钥密码体制的一些例子。使用私钥密码体制时， 如果有能力加密( 或解密) 就意味着必然也有能力解密( 或加密) 。 使用私钥密码体制进行秘密通信时，为了保证通信的安全性，任意不同的用户之间 都应该使用互不相同的密钥，这样，如果一个网络中有n 个用户，他们之间彼此可能需要 进行秘密通信，这时网络中将共需要n ( n 1 ) 2 个密钥( 其中，每个用户都需要保存 一1 个密钥) ，这样巨大的密钥量给密钥分配和管理带来了极大的困难。另外，随着计算机网 络，特别是i n t e m e t 的发展，网络上互不相识的用户可能需要进行保密的会话( 例如，如 果用户在进行电子商务活动时，需要保密的连接，这时的客户对象可能根本不是固定的 对象) 这个时候不可能提前约定使用的密钥。随着计算机处理能力的进一步增强，这些 私钥密码系统的安全性受到了进一步的威胁，所以私钥密码体制的应用受到了一定的限 制。 1 2 2 公钥密码体制 如果一个保密系统能够把加密过程和解密过程分开，并且加密和解密分别使用两个 不同的密钥实现，并且由加密密钥推导出解密密钥在计算上是不可行的，则该系统所采 用的就是公钥密码体制( 非对称密钥密码体制) 1 4 1 。采用公钥密码体制的每个用户都有 一对选定的密钥其中一个是可以公开的，一个由用户自己秘密保存。例如：r s a 、 e 1 g a m a l 、椭圆曲线密码等都足公钥密码体制的典型代表。 2 0 多年来，公开密钥密码系统获得了巨大的发展，在理论研究方向，为数众多的密 码研究人员，甚至包括其他领域的。些研究人员对公开密钥密码投入了巨大的精力与热 情，发表了大量的研究文献，获得了一整套系统的研究成果；在实践应用当中，公开密 钥密码成功地解决了计算机网络安全的身份认证、数字签名等i x 题，推动了包括电子商 椭圆曲线加密算法的研究与实现 务在内的大批网络应用的不断深入、发展。图1 2 1 4 是一般公开密钥密码的示意图。 其中，图中e ( e 。，m ) 表示使用用户b 的公开密钥e 。对明文脚进行加密，d ( d 。，c ) 表 示用户b 使用自己保存的秘密密钥d 。对密文c 进行解密( 有时也使用e 。表示给用户b 发送秘密消息时所使用的加密变换，即e 。= e ( e ) ，使用d 。表示用户b 的解密变换， 即d b = d ( d h ，- ) ) 。 图1 2 公开密钥密码体制 f i g1 2 p u b l i ck e yc r y p t o s y s t e m 公开密钥密码的加密变换e ( e 。，研) 与解密变换d ( a 。，c ) 应满足下列要求： ( 1 ) d ( d 。，c ) 是e ( e 。，m ) 的逆变换，即对于任意明文b l ，均有 d ( d 8 ，c ) = d ( d b ，e ( e 8 ，m ) ) = m ； ( 2 ) 在已知加密密钥e 8 时，e ( e 口，m ) 的计算不难；在己知解密密钥d 自时，d ( d b ，c ) 计算也不难； ( 3 ) 如果不知道d 。，那么即使知道p 。，具体的加密与解密算法过程以及密文c ，确 定明文的计算是不可行的。 上述要求指出：在公开密钥密码中，对任意明文进行加密变换是容易计算的( 注意： 加密密钥可以为所有用户得到) ；如果知道解密密钥，那么，对密文进行解密也将是容易 计算的，但是，如果不知道解密密钥，对密文进行逆变换以得到正确的明文在计算上将 是不可行的。 表1 1 私钥密码体制与公钥密码体制的比较 t a b l ei i c o m p a r i s o no f p r i v a t e k e ya n dp u b l i c k e yc r y p t o s y s t e m 1 川同个算法进行加密和解密，而密钥有 公钥 对，其中一个用于加密，另一个用于解密 密码 2 发送方和接收方每个拥有一对相互匹配的 体制 密钥c - p 的一个( 不是同一个) 1 两个密钥中的一个必须保密 2 如果不掌握其他信息要想解密报文是不可 能的或者至少是不现实的 3 知道所用的算法加上一个密钥加上密文的 样本必须不足以确定另一个密钥 5 椭圆曲线加密算法的研究与实现 在了解了公钥密码体制与私钥密码体制各自的特点之后，把公钥密码体制与私钥密 码体制的运行条件与安全条件加以比较，如表1 - 1 f 3 1 1 4 惭示。， 1 3 公钥密码系统依赖的数学难题 目前的公钥密码系统主要依赖于下列三种数学难题一j ： ( 1 ) 大整数因子分解问题 ( 2 ) 离散对数问题 ( 3 ) 椭圆曲线上的离散对数问题 第一类公钥系统为r s a 系统，它的安全性是基于大整数因子分解的困难性，而大整 数因子分解问题是数学上的著名难题，因而可以确保r s a 算法的安全性。r s a 系统是公 钥系统的最具有典型意义的方法，自提出以来就一直是人们研究的焦点。对于密码破译 者来况，在这种系统中，已知密文而想得出明文就必须进行大整数的因子分解。 r s a 方法的优点主要在于原理简单，易于使用。但是，随着分解大整数方法的进步 及完善、计算机速度的提高以及计算机网络的发展( 可以使用成千上万台机器同时进行 大整数分解) ，作为r s a 加解密安全保障的大整数要求越来越大。为了保证r s a 使用的 安全性，其密钥的位数一直在增加，比如，目前一般认为r s a 需要1 0 2 4 位以上的字长， 显然，密钥长度的增加导致了其加解密的速度大为降低，硬件实现也变得越来越难以忍 受，这对使用r s a 的应用带来了很重的负担，对进行大量安全交易的电子商务更是如此， 从而使得其应用范围越来越受到制约p j 。 第一类公钥系统的安全性依赖于离散对数的计算困难性1 5 j 。设g 为一个有限a b e l 加法群，假定g 为g 的某个元，a 为任意的整数，如果已知g 及a * g ，如何求出整数a 来 的问题在数学上称为离散对数问题。一般说来，当群g 选择得当，且整数d 充分大时， 求解此类问题是非常困难的。离散对数问题又可细分为两类，一类为某个有限域上的离 散对数问题。一类为椭圆曲线上的离散对数问题。两者比较，后一类问题求解更为困难 些。基于这一判断，人们通过对群g 作出不同的选择时，构造了各种不同的公钥系统， 比如，m a s s e y o m u r a 公钥系统，e 1 g a m a l 公钥系统，d s a ( d i g i t a ls i g n a t u r e a l g o r i t h m ) 公钥系统等等。 第三类公钥系统是建立在椭圆曲线离散对数问题上的密码系统，称为椭圆曲线密码 系统。定义在某种有限域上的椭圆曲线上的点在定义了零元素和加法后，构成一个有限 阶的a b e l 群。设g f ( p ) 为一有限域，则g f ( p ) 上的一条椭圆曲线e 上的点在定义了零元 素和加法后构成了一个有限群助，这个有限群的阶可经由某些特别方法计算出来，设已 知属于印的点g 和a * g ，从g 和a * g 求出a 来是非常困难的，此种问题称为椭圆曲线离 散对数问题，它较通常的离散对数问题更为困难。椭圆曲线加密算法自从诞生之日起， 它的安全性和实现效率就被众多的数学家和密码学家所广泛研究。所得的结果表明，较 之r s a 算法，e c c 具有密钥长度短，加解密速度快，对计算环境要求低，在需要通讯时， 对带宽要求低等特点。 表l 一2 3 1 比较t e c c ，r s a ，d s a 在等价安全强度下所需的密钥尺寸，假定已知解整 数分解问题，离散对数问题和椭圆曲线离散对数问题的最好算法，考虑需要基于某m i p s 椭网曲线加密算法的研究与实现 ( 每秒运算1 0 0 万条指令) 年破解一个密钥这样的等价强度下的密钥尺寸。 表1 2e c c ，r s a ，d s a 算法的性能比较 t a b l e1 2p e r f o r m a n c ec o m p a r i s o no f e c c ，r s aa n dd s a 椭圆曲线加密算法e c c 与r s a 方法相比有着很多技术优点： ( 1 ) 安全性能更高： 加密算法的安全性能一般通过该算法的抗攻击强度来反映。e c c 和其他几种公钥 系统相比，其抗攻击性具有绝对的优势。椭圆曲线的离散对数计算困难性( e c d l p ) 在计算复杂度上目前是完全指数级，而r s a 是亚指数级的。这体现e c c 比r s a 的每 b i t 安全性能更高。 ( 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 要快得多。同时e c c 系统的密钥生 成速度比r s a 快百倍以上。因此在相同条件下，e c c 有更高的加密性能。 ( 3 ) 存储空间占用小： e c c 的密钥尺寸和系统参数与r s a 、d s a 相比要小得多。1 6 0 位e c c 与1 0 2 4 位 r s a 、d s a 具有相同的安全强度，2 2 0 位e c c 则与2 0 4 8 位r s a 、d s a 具有相同的安 全强度。意味着它所占的存贮空间要小得多。这对于加密算法在资源受限环境上( 如智 能卡等) 的应用具有特别重要的意义。 ( 4 ) 带宽要求低： 当对长消息进行加解密时，三类密码系统有相同的带宽要求，但应用于短消息时 e c c 带宽要求却低得多。而公钥加密系统多用于短消息，例如用于数字签名和用于对 称系统的会话密钥传递。带宽要求低使e c c 在无线网络领域具有广泛的应用前景。 椭圆曲线加密算法的研究与实现 2 椭圆曲线密码系统理论基础 椭圆曲线加密系统要实现的本质是椭圆曲线上的点构成的a b e l 群上的点乘运算，而 a b e l 群是一个加法群，根据加法群的运算特点，椭圆曲线上的点乘运算又需要转化成椭 圆曲线上的点加运算来实现，当两个加数相同的时候，点加运算又变成了倍点运算，所 以椭圆曲线上的点乘运算需要转化成椭圆曲线上的点加和倍点运算实现。点加和倍点运 算都需要转化成二进制有限域上的模乘、模加、模平方和模逆运算来实现。本章介绍了 e c c 加密系统的数学基础：有限群和有限域；选择适合于椭圆曲线加密系统所使用的有 限域、基、椭圆曲线、基点及其相应的阶数、加密密钥；给出e c c 加解密的步骤以及层 次结构。 2 1 有限群： 定义1 ：假定g 是具有有限个或无限个元素的集合，在g 的元素间给出了一个代数运算4 ( a n 、乘或其它运算) ，使得 ( 1 ) 封闭性，即：对任意的口，b g ，有口 b g ； ( 2 ) 结合律，即：对任何a ，b ，c g ，有a b s c = ( a + b ) 4c = a $ ( b4 c ) ： ( 3 ) 单位元，即：存在一个元素口g ( 称为单位元) ，对任意元素a g ，有 a e = e a 嚣a ( 4 ) 逆元，即：对任意d g ，存在一个元素a g ( 称为逆元) ，使得 日十口= 疗1 $ a = e 把满足上面性质的代数系统称为群，记作( g ，。) 。 定义2 ：如果群( g ，t ) 满足交换律，即对任何以b g ，有口+ b = b + a ，则称g 为交换群 ( 或a b e l 群、加法群等) 。 群具有以下性质【6 j ： ( i ) 群中的单位元是惟一的： ( 2 ) 消去律成立，即对任意的e l , b ，c g ，如果曲= a c ，则b = c ，如果b a = c a ，则b = c ； ( 3 ) 群中的每一元素其逆元是惟一的。 定义3 ：群的阶，用i g l 来表示，表示群中元素的个数。元素个数为无限的叫做无限群， 元素个数为有限的叫做有限群。 群的一些例子【6 】【7 】： ( 1 )所有正有理数集对于乘法形成一个群。 ( 2 ) 所有整数集对于加法形成一个a b e l 群。 ( 3 ) 整数系z 对加法构成群，它是无限群。 ( 4 ) 有理数系q 对加法构成群，它是无限群。 ( 5 ) 实数系r 对加法构成群，它是无限群。 f 6 ) 复数系g 对加法构成群，它是无限群。 ( 7 ) 正有理数集o + 对乘法构成群，它是无限群。 ( 8 ) 正实数集r 十对乘法构成群，它是无限群。 定义4 ：对于任意一个元素g g ，满足g 7 = p 的最小的正整数，称为元素g 的阶，用j g 表示。 椭圆曲线加密算法的研究与实现 定义5 ：元素g g ，当且仅当群g 中的任何一个元素都可以表示成g 的形式且f 为整数 时，元素g 被称为群g 的产生元；并且吲= l g f 。 例子：设群为g = z ；= 1 , 2 ，3 ，4 ) ，对乘法形成一个群，群的阶j gj = 4 。 因为 2 0 m o d 5 ：1 2 1 m o d 5 = 2 22 m o d 5 = 4 2 3 m o d 5 = 3 2 4 m o d 5 = 1 所以元素2 的阶是4 。 又因为 4 0 m o d 5 = l 4 1 m o d 5 ：4 42 m o d 5 ：1 4 3 r o o d 5 ：4 4 4 m o d 5 ：1 所以元素4 的阶是2 。 元素2 是群的产生元，因为群中的任何一个元素都可以通过2 的某次方得到，元素4 却不是。因为通过元素4 得不到这个群中的全部元素。 2 2 素数有限域与二进制有限域： 定义1 ：域是一个代数系统，它由一个( 至少包含两个元素的) 非空集合，组成，在集合 f 上定义有两个二元运算：加法( 用符号+ 表示) 与乘法( 用符号，表示，有时 可以将日+ b 简写为a b ) ，并满足下面条件： ( 1 ) f 的元素关于加法“+ ”成交换群，记其单位元为0 ( 称为域的零元) ； ( 2 ) f 0 ) 关于乘法“”成交换群，记其单位元为“1 ”( 仍然称其为域的单位元，或么元) ； ( 3 ) 乘法在加法上满足分配律，即：对任意的口，b c f ， a ( b + c ) = a b + a 4 c ( 口+ b ) + c = a + c + b + c 把满足上面性质的代数系统称为域，并记为 。 域的几个例子同： ( 1 ) 定义了普通的加法与乘法运算的复数集合。 ( 2 ) 定义了普通的加法与乘法运算的实数集合。 ( 3 ) 定义了普通的加法与乘法运算的有理数集合。 定义2 ：如果集合f 只包含有有限个元素，则称这时的域f 为有限域，也称为伽罗华域 或g a l o i s 域。 定义3 ：域f 的阶就是域f 中的元素个数。 椭圆f h 线加密算法的研究与实现 定义4 ：有限域f 的非零产生元素称为域，的产生元。 定义5 ：有限域的特征值用c h a r ( f ) 来表示，它是一个最小的正整数j ，使得 ! ! ：! 三o j “n l c j 例子：考虑有限域g f ( 7 ) ，包含元素为 o ，1 ，2 ，3 ，4 ，5 ，6 ) 。域的阶为7 ，特征值也是7 ，因为 ! ! ! ! ! ! ! zo ( m o d 7 ) 7 f t h i e f 因为： 3o = l m o d 7 3 1 = 3 m o d 7 32 = 2 r o o d 7 3 3 ：6 m o d 7 34 = 4 m o d 7 35 ：5 m o d 7 3 6 ：1 m o d 7 所以元素3 是域g f ( 7 ) 的产生元。 定义6 ：任何阶为素数的整数次方的有限域都是唯一存在的。这些域可以用g f ( p ) 来表 示，这里p 是一个素数，m 为正整数。 在加密系统，通常采用两种类型的有限域，它们是素数有限域和二进制有限域，下 面分别介绍这两种有限域。 一、素数有限域 当：l ，p 是一个 3 的素数时，称有限域为素数有限域【7 1 。 有限域的特征值可以用c h a r ( f ) = p 3 来表示。 ，j = 0 ，1 ，2 ，( p 一1 ) ，在素数有限域上的加法运算和乘法运算都是对p 取模的。加 密时所采用的素数p 应该足够的大，使得在有限域c 上，e c d l p ( e l l i p t i c c u r v e d i s c r e t e l o g a r i t h mp r o b l e m ，椭圆曲线离散对数问题) 是不可能解决的。随着对e c d l p 攻击的新 理论和方法的产生，p 值只能变得越来越大【8 l 。 二、：二进制有限域 当p ：2 ，m 为正整数时，称有限域为二进制有限域叽 二进制有限域f ( 2 ”) 或g f ( 2 ”) 的特征值可以用c h a r ( g f ( 2 ”) ) = 2 来表示。可以把二 进制有限域f ( 2 ”) 当成是在e 上的m 维向量空间。 二进制有限域上的元素需要通过某种基来表示。 2 3 基： 二进制有限域g f ( 2 ) 包含2 “个元素 基是一系列在f ( 2 ) 上的元素 ，。l - ，r 。， 一的公式来表示 o 每一个元素都是通过某种基来表示的。 ) ，则每一个元素a g f ( 2 ”) 都可以用 椭圆曲线加密算法的研究与实现 d = c l i x i ( 2 1 ) i = 0 这里q e ，f e ，a ，= 0 0 r 1 最常用的两种基是多项式基和正交基【9 】，分别介绍这两种基。 2 - 3 1 正交基 在e 上的g f ( 2 ”) 的正交基是一个形如 ，2 ，”，7 ，p 2 ”。) 的基，g f ( 2 ”) ， 这样的。个基总是存在的。 a = ( ，a l j ，a m _ 1 ) 代表元素口= a o p + a i 卢2 十a 2 r + + a m - i 2 肿。 零元素表示为0 = ( 0 , 0 ，0 ) ，乘法单位元表示为1 = ( 1 ，1 ，1 ) 。 正交基最大的优点是域元素的平方操作非常简单，在硬件实现时只是简单的循环左 移。给出一个用正交基表示的元素a = ( a 。，a 。，口。) ，可以得到： 口2 = ( q 2 7 ) 2 = a , p 2 ”= ( 口m - i ，口。胡。) ( 2 2 ) i = 0= 0 对于任何整数s ，1 s m l ，a 的2 5 次方可以通过循环左移5 位得到，即： a 2 = ( a m _ sa 。一1 ，a o a l ，a 。一1 ) ( 2 3 ) 还可以证明a ”。= 口。与此类似，a 的平方根可以通过循环右移1 位得到，即： a “2 = ( a l ，a 2 ，口卅- l ，a 0 )( 2 4 ) 虽然基于正交基的平方运算在硬件实现上比较简单，但是基于正交基的乘法运算相 对来说却是比较麻烦的，所以在实际的应用中常采用种称为高斯正交基的正交基【l0 1 。 高斯正交基只在有限域g f ( 2 ”) 上的m 值为某一些特定值时才存在。高斯正交基有各种不 同的类型，它的类型代表了乘法运算的复杂性，用t 来表示。一般认为，类型越小，乘 法运算越有效j 。对于一组给定的m 与t ，至多存在一种类型为t 的高斯正交基。在所 有的高斯正交基中，类型i 与类型i i 高斯正交基有最有效的乘法运算法则，所以类型i 与类型i i 高斯正交基也称为最优化正交基i 与最优化正交基i i 。 理论：( m u l l i n ，o n y s z c h u k ，v a n s t o n e & w i l s o n ) ( 1 ) 有限域g f ( 2