（计算机应用技术专业论文）安全椭圆曲线系统的研究和实现.pdf

安全椭圆曲线系统的研究和实现 摘要 随着互联网的快速发展，信息安全闯题显得日益重要。相关网络安全协议 应运而生，而它们的基础都是安全高效的加密算法，椭圆曲线加密系统与其他 公钥加密系统相比有许多优点，受到国内外安全专家的极大关注。可是椭圆曲 线加密系统( e c c ) 并无公开的标准源代码，还处于“百花齐放，百家争鸣”的 局面，文章对于安全的椭圆曲线加密系统做了理论研究和实现工作。 文章首先讨论了网络安全基本问题、网络安全协议和密码学；对相关数学 理论进行了研究，特别是给出了一种新的求解g 尺2 ”) 上二次方程的矩阵法，而 它是选取椭圆曲线上的随机点的关键步骤，和i e e e p 1 3 6 3 的方法相比，它有易 于软件实现、效率高等优点，在国内外相关文献上还未见到更好的求解方法： 接着讨论了椭圆曲线的基本运算，进而给出了在g f ( 2 ”) 上选取安全曲线及基点 的步骤；文章还设计了椭圆曲线加密系统的加解密方案，讨论了椭圆曲线系统 的安全性问题。最后文章就k o b l i t z 曲线加密系统进行了软件实现。 关键词：有限域椭圆曲线密码系统算法 r e s e a r c ho na n di m p l e m e n t a t i o no fs e c u r ee l l i p t i cc u r v e c r y p t o s y s t e m a b s t r a c t w i t ht h ef a s td e v e l o p m e n to fi n t e r n e t ，t h ep r o b l e mo fi n f o r m a t i o ns e c u r i t y l o o k si n c r e a s i n g l yi m p o r t a n t 。t h e no nt h eb a s i so fs a f ea n dh i g he f f i c i e n te n c r y p t i o n a l g o r i t h m ，s o m er e l a t e dn e t w o r kp r o t o c o l sa r ep r o d u c e d c o m p a r e dw i t hs o m e o t h e r p u b l i ck e yc r y p t o s y s t e m s ，e l l i p t i cc u r v ee r y p t o s y s t e m ( e c c ) h a sm a n ym e r i t s ，s ot h e s p e c i a la t t e n t i o ni sp a i dt o i tb yt h en e t w o r ks a f e t ys p e c i a l i s ti nt h ew o r l d e c ci s w i d e l ya r g u e db e c a u s eo f n os t a n d a r ds o u r c ec o d e i nt h i sa r t i c l e ，t h er e s e a r c hi so n t h ee c c t h e o r ya n d t h ei m p l e m e n t a t i o no fi ti sa l s od o n e i nt h i st h e s i s ，t h eb a s i cp r o b l e mo fn e t w o r ks e c u r i t y ，s o m ec o r r e l a t i v ep r o t o c o l s a n dc r y p t o l o g ya r ed i s c u s s e da tf i r s t ，m a t ht h e o r yi np o i n ti sa l s os t u d i e d e s p e c i a l l y ， as o r to fn e wm a t r i xm e t h o do fs o l v i n g q u a d r a t i ce q u a t i o n o v e r g 以2 ”) i s g i v e n ，w h i c h i st h ek e yo fs e l e c t i n gr a n d o mp o i n to v e re l l i p t i cc u r v e s n ob e t t e r s o l u t i o nh a sb e e nf o u n di nr e l a t e d1 i t e r a t u r ei nt h e w o r l d c o m p a r e dw i t hi e e e p13 6 3 s m e t h o d ，i t i s e a s y t o i m p l e m e n t t h es o f t w a r ea n do b t a i n h i g h e f f i c i e n c y ，e t c t h e nt h eb a s i co p e r a t i o no fe l l i p t i cc u r v ei sd e b a t e da n dt h es t e p so f f i n d i n g s e c u r ec u r v ea n db a s i s p o i n to v e r6 f ( 2 “) a r ep r e s e n t e d m o r e o v e r , t h e e n c r y p t i o n a n dd e c r y p t i o ns c h e m e so ft h ee c ca r e d e s i g n e da n dt h es e c u r i t y p r o b l e m o fe c ci sa l s oc o n s i d e r e d i nt h e e n d ，e c cb y k o b l i t zc u r v e s a r e i m p l e m e n t e d k e y w o r d s ：f i n i t ef i e l d ，e l l i p t i cc a r v ec r y p t o s y s t e m ，a l g o r i t h m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据 我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得金月b 王业太堂或其他教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论 签字日期：力驴睁多月缈日 学位论文版权使用授权书 本学位论文作者完全了解金目b 王些盔堂有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权金 b 兰些盍堂可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 致谢 值此论文完成之际，谨向我的导师叶震副研究员表示最真挚的感谢! 论文 是在叶老师的指导下完成的。在论文的撰写过程中，叶老师提出了很多指导性 的意见，并多次对文稿进行了悉心的审阅。研一时叶老师就指导我进行椭圆曲 线相关问题的研究，三年来不论是在学习上还是在生活上叶老师都给了我极大 的关心和帮助。叶老师严谨的治学态度、广博的知识、敏锐的学术思想更是给 了我很深的影响。 许多老师特别是周国祥老师和胡学钢老师给予我学习上很大帮助和鼓励， 非常感谢你们：师兄高柯俊、燕辉、和郑利平都给过我学习上的指导，真的很 高兴认识你们；郑利平、周兵斌还有我三个人曾经有一年多的时间学习吃饭都 泡在一起，这真是我以后最美好的回忆。 感谢我的父母，感谢他们对我的养育之恩：感谢我的哥哥，没有他的帮助， 我不可能有今天的成绩。 作者：张庆胜 2 0 0 4 年5 月2 5 曰 前言 随着i n t e r n e t 的迅猛发展，网络安全问题显得越来越重要，相关网络安全 协议应运而生，而这些协议又是以高效安全的加密算法为前提的。 加密算法分为对称加密算法和非对称加密算法。在网络上进行数据传输肘， 通常使用对称加密算法加密所要传输的数据，而用非对称加密算法加密密钥。 就非对称加密算法来说，目前r s a 应用最为普及，但e c c 和r s a 相比有 许多优点，诸如安全性高、密钥量小、灵活性好等等，自1 9 9 7 年以来，e c c 的研究和应用工作已受到普遍关注。 e c c 的研究和应用工作还处于“百家齐放，百家争鸣”的状况，国际上e c c 的理论和应用工作都取得了许多卓有成效的成果。已有e c c 的许多标准问世， 如i e e ep 1 3 6 3 、a n s ix 9 6 2 等；也有一些公司致力于e c c 的应用工作，如 c e r t i c o m 公司等。国内e c c 相关文献较少，理论研究的成果相对其他方面的研 究成果来说要少得多；就应用方面来说，可用的资源也很少。 文章较为系统地讨论了e c c 的相关问题，总结前人的工作内容主要有：网 络安全简介( 第一章) ，密码学简介( 第二章) ，数学理论( 第三章部分节) ，椭 圆曲线基本运算( 第四章部分节) ，椭圆曲线加密系统安全性分析( 第四章第七 节) ：创造性的工作主要有：给出了一种新的g f ( 2 ”) 上二次方程的求解方法( 第 三章最后一节) ，在此基础上结合前人的理论成果提出了安全e c c 参数的选取 步骤( 第四章第四节) ，设计了椭圆曲线加密系统方案( 第四章第六节) ，快速 实现了k o b l i t z 曲线加密系统并对实验结果进行了数据分析( 第五章) 。 第一章网络安全简介 随着计算机网络的发展，社会对网络安全的要求也越来越高。计算机网络 安全是指利用网络管理控制和技术措施，保证在一个网络环境里，数据传输的 安全性。 1 1 网络安全威胁 安全威胁是指某人、物、事件或概念对某一资源的保密性、完整性、可用 性或合法使用所造成的威胁。某种攻击就是某种威胁的具体实现。 安全威胁有时可以被分类成故意的( 如黑客攻击) 和偶然的( 如信息被发往 错误的地方) ，故意的威胁又可以被进一步分类成被动的和主动的。被动威胁包 括只对信息进行监听，而不对其进行修改；主动威胁则对其进行故意的篡改【2 5 】。 典型的网络安全威胁主要有： ( 1 ) 授权侵犯：一个被授权使用系统的人，却将此系统用做其他非授权的目的。 ( 2 ) 旁路控制：攻击者发掘系统的安全缺陷或安全脆弱性。 ( 3 ) 业务拒绝：对信息或其他资源的合法访问被无条件拒绝。 ( 4 ) 窃听：信息从被监视的通信过程中泄露出去。 ( 5 ) 电磁射频截获：信息从电子或机电设备所发出的无线频率或其他辐射中 被提取出来。 ( 6 ) 非法使用：资源被某个非授权的人或者以非授权的方式使用。 ( 7 ) 人员不慎：一个授权的人为了钱或利益，或由于粗心，将信息泄露给一个 非授权的人。 ( 8 ) 信息泄露：信息被泄露或暴露给某个非授权的人或实体。 ( 9 ) 完整性侵犯：数据的一致性通过对数据进行非授权的增生、修改或破坏丽 受到损害。 ( 1 0 ) 截获修改：某一通信数据在传输的过程中被改变、删除或替代。 ( 1 1 ) 假冒；一个实体( 人或系统) 假装成另一个不同的实体。 ( 1 2 ) 媒体废弃：信息被从废弃的磁介质或打印过的媒体中获得。 ( 1 3 ) 物理侵入：一个侵入者绕过物理控制而获得对系统的访问。 ( 1 4 ) 重放：所截获的某次合法通信数据拷贝，出于非法的目的而被重新发送。 ( 15 ) 业务否认：参与某次通信交换的一方，事后错误否认曾经发生过此次交 换。 ( 1 6 ) 资源耗尽：某一资源被故意超负荷的使用。导致对其他用户的服务中断。 ( 1 7 ) 业务欺骗：某一伪系统或系统部件欺骗合法的用户或系统自愿放弃敏感 信息。 2 ( 1 8 ) 窃取：某一安全攸关的物品被偷盗。 ( 1 9 ) 业务流分析：通过对通信业务流模式进行观察，而非法截获非授权的信 息。 ( 2 0 ) 陷阱门：将某一“特征”设立于某个系统或系统部件中，使得在提供特定 的输入数据时，允许安全策略被违反。 ( 2 1 ) 特洛伊木马：含有一个察觉不出的或无害的程序段软件，当它被运行时 会损害用户的安全。 1 2 数据传输的安全需求 网络环境下，数据传输必须满足以下四大基本需求【1 1 ： ( 1 ) 机密性( c o n f i d e n t i a l i t y ) 指系统应使未授权者无法理解所窃听到的信息。 可以通过加密来保证机密性。 ( 2 ) 真实性( a u t h e n t i c i t y ) 指接收方所接收到的数据是发送方所发送的数据， 而不是别的数据。 ( 3 ) 数据完整性( d a t ai n t e g r i t y ) 指系统不应使信息被未经授权的用户篡改。 数据摘要和数字签名可以保证数据的完整性，但它们实现起来比较复杂，系统 开销比较大，一般只用于完整性要求较高的领域，特别是商业、金融业等领域。 ( 4 ) 不可抵赖性( n o nr e p u d i a t i o n ) 发送者事后不能否认他所发送的信息。可 以通过数字签名来实现身份鉴别。 在安全的开放环境中，用户可以获得各种安全服务。安全服务是一种活动， 它用于增强一个信息系统的信息传输的安全性。在一个分层通信体系结构中， 安全服务几乎可以出现在任何一层。安全服务包括访问控制服务、数据完整性 服务、数据机密性服务、身份认证服务和抗抵赖服务等五种安全服务。 1 3 相关网络安全协议 传统的网络服务程序，如：f t p 、p o p 和t e l n e t 在本质上都是不安全的，因为 它们在网络上用明文传送口令和数据，别有用心的人非常容易就可以截获这些 口令和数据。而且，这些服务程序的安全验证方式也是有其弱点的，就是很容 易受到“中间人”( m a n i n - t h e - m i d d l e ) 这种方式的攻击。所谓“中间人”的攻击方 式，就是“中间人”冒充真正的服务器接收你的传给服务器的数据，然后再冒充 你把数据传给真正的服务器【2 7 】。服务器和你之间的数据传送被“中间人”一转手 做了手脚之后，就会出现很严重的问题，因此数据在网络上的传输需要安全的 通信协议。 1 3 1s s h ( s e c u r es h e l l ) 最初s s h 是由芬兰的一家公司开发的1 2 8 1 。但是因为受版权和加密算法的限 制，现在很多人都转而使用o p e n s s h 。o p e n s s h 是s s h 的替代软件，而且是免 费的，预计将来会有越来越多的人使用它而不是s s h 。s s h 是由客户端和服务 端的软件组成的，有两个不兼容的版本1 x 和2 x ，用s s h2 x 的客户程序是不能 连接到s s h1 x 的服务程序上去的，o p e n s s h2 x 同时支持s s h1 x 和2 x 。 通过使用s s h ，你可以把所有传输的数据进行加密，这样“中间人”这种攻 击方式就不可能实现了，而且也能够防止d n s 和i p 欺骗。还有一个额外的好处 就是传输的数据是经过压缩的，所以可以加快传输的速度。s s h 有很多功能， 它既可以代替t e l n e t ，又可以为f t p 和p o p 甚至p p p 提供一个安全的“通道”。 从客户端来看，s s h 提供两种级别的安全验证。第一种级别是基于口令的 安全验证，只要你知道自己帐号和口令，就可以登录到远程主机。所有传输的 数据都会被加密，但是不能保证你正在连接的服务器就是你想连接的服务器。 可能会有别的服务器在冒充真正的服务器，也就是受到“中间人”这种方式的攻 击：第二种级别是基于密钥的安全验证，需要依赖于密钥，也就是你必须为自 己创建一对密钥，并把公用密钥放在需要访问的服务器上，如果你要连接n s s h 服务器上，客户端软件就会向服务器发出请求，请求用你的密钥进行安全验证， 服务器收到请求之后，先在该服务器的目录下寻找你的公用密钥，然后把它和 你发送过来的密钥进行比较。如果两个密钥一致，服务器就用公用密钥加密“质 询”( c h a l l e n g e ) 并把它发送给客户端软件。客户端软件收到“质询”之后就可以 用你的私人密钥解密再把它发送给服务器。用这种方式，你必须知道自己密钥 的口令。但是，与第一种级别相比，第二种级别不需要在网络上传送口令。第 二种级别不仅加密所有传送的数据，而且“中间人”这种攻击方式也是不可能的， 因为他没有你的私人密钥，但是整个登录的过程可能需要1 0 秒。 1 3 2s s l ( s e c u r es o c k e tl a y e r ) 网景公司1 29 】( n e t s c a p e ) 提出的安全套接层协议( s s l ) 是基于w e b 应用 的安全协议，它包括服务器认证、客户认证( 可选) 、s s l 链路上的数据完整性 和s s l 链路上的数据保密性。对于电子商务应用来说，s s l 使用公开密钥体制 和x 5 0 9 数字证书技术保护信息传输的机密性和完整性，主要适用于点对点之 间的信息传输。但由于s s l 不对应用层的消息进行数字签名，因此不能提供交 易的不可否认性，这是s s l 在电子商务中使用的最大不足。鉴于此，网景公司 在从c o m m u n i c a t o r4 0 4 版开始的所有浏览器中引入了一种被称作“表单签名 ( f o r ms i g n i n g ) ”的功能，在电子商务中，可利用这一功能来对包含购买者的 订购信息和付款指令的表单进行数字签名，从而保证交易信息的不可否认性。 综上所述，在电子商务中采用单一的s s l 协议来保证交易的安全性是不够的， 但采用“s s l + 表单签名”模式能够为电子商务提供较好的安全性保证【9 】。 当一个应用程序( 客户机) 想和另一个应用程序( 服务器) 通信时，客户 机打开一个与服务器相连接的套接字连接。然后客户机和服务器对安全连接进 行协商，作为协商的一部分，服务器向客户机作自我认证：客户机可以向服务 器选择作或不作自我认证。一旦完成了认证并且建立了安全连接，则两个应用 程序就可以安全地进行通信。按照惯例，把发起该通信的对等机看作客户机， 另一个对等机则看作服务器。图1 中名为a 和b 的两台对等机想安全地进行通 信，在简单的p 2 p 应用程序的环境中，对等机a 想查询对等机b 上的一个资 源。每个对等机都有包含其专用密钥的一个数据库( 名为k e y s t o r e ) 和包含其 公用密钥的证书。密码保护数据库的内容。该数据库还包含一个或多个来自被 信任的对等机的自签名证书。对等机a 发起这项事务，每台对等机相互认证， 两台对等机协商采用的密码及其长度并建立一个安全通道。 图1s s l 安全通信模型 1 - 3 3p k i ( p u b l i ck e yi n f r o s t r u c t u r e ) 公钥基础设施( p k i ) 是一种新的安全技术，它由公开密钥密码技术、数字证 书、证书发放机构( c a ) 和关于公开密钥的安全策略等基本成分共同组成的。 p k i 密钥交换和身份验证的安全性依赖于p k i 使用的公开密钥算法、对称加密算 法和摘要算法，而这些算法的载体就是p k i 的核心一c a ( c e r t i f i c a t i o n a u t h o r i t y ) ，即认证机构。c a 是通信双方相互信赖的第三方肚1 。一个机构通过 采用p k i 框架管理密钥和证书可以建立一个安全的网络环境，这个框架主要包 括x 5 0 9 格式的证书及证书废除列表( c r l ) 、c a r a 操作协议、c a 管理协议和 c a 政策制定。 由于p k i 体系结构是目前比较成熟、完善的i n t e r n e t 网络安全解决方案，国 外一些大的网络安全公司纷纷推出一系列的基于p k i 的网络安全产品，如美国 的v e r i s i g n ，i b m ，e n t r u s t 等安全产品供应商为用户提供了一系列的客户端和服 务器端的安全产品，为电子商务的发展提供了安全保证，为电子商务、政府办 公网和e d i 等提供了完整的网络安全解决方案。 1 3 4s 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 ) 电子商务在提供机遇和便利的同时，也面i 临着一个最大的挑战，即交易的 安全问题。在网上购物的环境中，持卡人希望在交易中保密自己的帐户信息， 使之不被人盗用；商家则希望客户的定单不可抵赖，并且在交易过程中，交易 各方都希望验明其他方的身份，以防止被欺骗。针对这种情况，美国v i s a 和 m a s t c r c a r d 两大信用卡组织联合国际上多家科技机构，共同制定了应用于 i n t c r n c t 上的以银行卡为基础进行在线交易的安全标准，这就是安全电子交易 ( s e t ) 。它采用公钥密码体制和x 5 0 9 数字证书标准1 。 由于s e t 提供了消费者、商家和银行之间的认证，确保了交易数据的安 全性、完整可靠性和交易的不可否认性，特别是保证不将消费者银行卡号暴露 给商家等优点，因此它成为了目前公认的信用卡借记卡的网上交易的国际安全 标准。 s e t 安全电子交易协议主要应用于bt oc 模式中保障支付信息的安全性。 s e t 协议本身比较复杂，设计比较严格，安全性高，它能保证信息传输的机密 性、真实性、完整性和不可否认性。s e t 协议是p k i 框架下的一个典型实现， 同时也在不断升级和完善，如s e t2 0 支持借记卡电子交易。 综上所述，这几个网络安全协议的安全性依赖于所采用的加密算法的安全 性，近年来高效快捷的加密算法越来越受到人们的关注，本论文讨论的重点是 椭圆曲线加密算法的理论研究与实现工作，这属于密码学的范畴，下面先简要 介绍一下现代密码学。 第二章现代密码学简介 随着知识经济的到来，互联网的兴起，人们可以获得更多的免费资源，可 是信息在传输过程中却可能受到被动攻击和主动攻击。其中从传输信道截获密 文或明文进行分析的攻击方法称为被动攻击；非法入侵者采用删除、修改、增 添、重放、伪造等手段向系统注入假信息则被称为主动攻击f 3 】。对于这些网络 安全隐患问题除了制定法律外，还需要有合适的保护措施，密码技术就是一种 有效的方法，其能够有效地应用于信息鉴别、数字签名等，从而防止电子欺骗， 这对信息系统的安全起到极其重要的作用。 2 1 密码学及密码体制的构成与分类 2 1 1 经典密码学与现代密码学 早在公元前4 0 0 多年密码学就已经产生，正如破译者一书中所说的“人 类使用密码的历史几乎与使用文字的时间一样长”。密码学( c r y p t o g r a p h y ) 一 6 词来源于古希腊的k r u p t o s ( h i d d e n ) 和g r a p h e i n ( t ow r i t e ) ，意思为密写。它 是以认识密码变换的本质、研究密码保密与破译的基本规律为对象的学科。经 典密码学主要包括两个既对立又统一的分支即密码编码学和密码分析学。研究 密码变化的规律并用之于编制密码以保护秘密信息的科学，称为密码编码学。 研究密码变化的规律并用之于密码以获取信息情报的科学，称为密码分析学， 也叫密码破译学。前者是实现对信息保密的，后者是实现对信息反保密的，密 码编码学与密码分析学相辅相成，共处于密码学的统一体中。现代密码学除了 包括密码编码学和密码破译学两个主要学科外，还包括近几年才形成的新分支 一密码密钥学，它是以密码的核心部分一密钥作为研究对象的学科。密钥管理 是一种规程，它包括密钥的产生、分配、存贮、保护、销毁等环节，在保密系 统中至关重要。上述三个分支学科构成现代密码学的主要学科体系f 4 】。 2 1 2 密码体制的构成 一个密码体制由以下五个部分组成川： 1 明文空间p ： 2 密文空间c ； 3 加密密钥空间疋； 4 解密密钥空间肠； 5 加密变换e ：p x i c e 专c ； 6 解密变换d ：c 心- - ) p ； 用m 表示明文，用c 表示密文。加密变换e ( k ，肌) 又记为e k ( m ) ，解密变换 d ( k ，c ) 3 l 记为d k ( c ) 。如果v m p ，e 。e 。( m ) = m 成立，称该密码体制具有保 密性。如果v 埘p ，e l 。4 。( m ) = m 成立，并且解密密钥只为唯一一个通信实 体所知晓，称该密码体制具有认证性。 当我们强调一个密码体制的保密功能时，又称该密码体制为加密体制；强 调一个密码体制的认证功能时，又称该密码体制为签名体制：强调一个密码体 制的密钥交换功能时，又称该密码体制为密钥交换体制。 2 1 3 密码体制的分类 如果以加密形式进行分类，密码可分为分组密码和序列密码f 6 】。所谓分组 密码即对固定长度的一组明文进行加密的一种加密算法( 如d e s 、a e s ) ；1 9 1 8 年，g i l l b e r tv e r n a m 提出了序列密码的概念，所加密的明文长度不固定，密钥 与明文一样长，采用一次一密的方式，加密密钥和解密密钥相同，即k e = k a = k ， 加密为c = mk ，解密为m = c o 七。 如果按密钥个数为标准进行分类密码可分为无密钥密码、单密钥( o r l e k e y ) 密码和双密钥( t w o - - k e y ) 密码。单密钥密码体制又称私钥( p r i v a t ek e y ) 或古典( c l a s s i c a l ) 密码或对称密码( s y m m e t r i ck e yc r y p t o s y s t e m ) 体制；双密 钥密码体制又称公钥( p u b l i ck e y ) 密码体制或非对称密码体制( a s y m m e t r i ck e y c r y p t o s y s t e m ) 。我们约定用s k c 表示对称密码体制，用p k c 表示公钥密码体 制。 2 2 对称密码体制 1 9 7 3 年美国国家标准局n b s ( n a t i o n a lb u r e a uo f s t a n d a r d ) 正式向社会公开 征集加密算法。1 9 7 4 年i b m 正式向n b s 提交了应征方案d e s ( d a t ae n c r y p t i o n s t a n d a r d ) ，n b s 会同美国国家保密局n s a ( n a t i o n a ls e c u r i t y a g e n c y ) 研究发 现这是唯一满足各项要求的方案，1 9 7 7 年，美国国家标准局( a n s i ) 宣布d e s 作为国家标准用于非国家保密机关，开创了公开全部密码算法的先例；r c 5 是 由r i v e s t 于1 9 9 4 设计的一种新型的分组密码算法；i d e a ( i n t e r n a t i o n a ld a t a e n c r y p t i o na l g o r i t h m ) 于1 9 9 0 年由j m a s s e y 和x l a i 提出，当时的名称是 p e s ( p r o p o s e de n c r y p t i o ns t a n d a r d ) ，其产生的背景是作为d e s 的更耨换代产品 的候选方案，1 9 9 1 年，e b i h a m 和a s h a m i r 提出了差分分析方法，为抵抗这 种新的攻击方法，p e s 的新版本出现了，并于1 9 9 2 年改名为i d e a ：1 9 9 7 年4 月1 5 日，美国国家标准技术研究所( n i s t ) 发起征集先进加密标准 a e s ( a d v a n e e de n c r y p t i o ns t a n d a r d ) 的活动，并专门成立了a e s 工作组，目的 是确定一个美国政府2 1 世纪应用的数据加密标准，参加竞选的有l5 个加密算 法，最后由r i j n d a e l 算法胜出口】。 在s k c 中，任意一对通信实体共享一对密钥，其中一个称为加密密钥，一 个称为解密密钥，加密密钥和解密密钥相同或者彼此之间容易相互确定。因此 加密密钥和解密密钥都必须保密它的加解密模型如图2 所示。 图2s k c 加解密模型 d e s 算法的基本设计思想是通过多次迭代，将简单的基本运算( 例如左移、 右移、模2 加等) 和变换( 选择函数、置换函数) 构造成数据流的非线性变换。 d e s 中加密与解密的密钥和流程是完全相同的，区别仅仅是加密与解密操作中 子密钥序列的施加顺序刚好相反”。d e s 已经获得广泛应用，但由于已证明d e s 不能成为群碍j ，d e s 改进成多重d e s ，特别是3 d e s 应用比较普遍。 本文讨论的椭圆曲线加密算法属于p k c ，因此2 3 节对p k c 做了重点介绍， 目的也就是做个很好的比较。 8 2 3 公开密钥体制 1 9 7 6 年，d i f f i e 和h e l l m a n 首次提出公钥加密体制的设想。1 9 7 8 年r i v e s t 、 s h a m i r 和a d l e m a n 联合提出了r s a 公钥密码系统；d i g i t a ls i g n a t u r ea l g o r i t h m ( d s a ) 是s c h n o r r 和e 1 g a m a l 签名算法的变种，被美国n i s t 作为数字签名标准 ( d s s ) i ”】：1 9 8 5 年，n e a l k o b l i t z t 2 2 1 ( 美国华盛顿大学) 和v i c t o r m i l l e r l 2 3 j ( i b m 公司) 相互独立地提出了在密码学中应用椭圆曲线的思想。 我国学者提出的基于布尔代数的公开密钥体制和陶仁骥、陈世华教授提出 的基于有限自动机理论的公开密钥密码体制。这是世界上第一个时序公开密钥 密码。它容易实现，密钥量适中，加解密速度快，已受到国际上的广泛关注。 如果通过对此研究和改进能使之成为一种安全、适用的有限自动机的公开密钥 密码，那么这一成果将无疑属于中国1 4 0 1 。 在p k c 中，任何一个通信实体都有一对密钥，其中一个称为公钥，一个称 为私钥，公钥和私钥不同，在不知道陷门信息的情况下，由公钥推出私钥在计 算上是不可行的，公钥总是用于加密和验证，私钥总是用于解密和签名。p k c 的加解密模型如图3 所示。它的加解密算法和加密密钥可以公开，但解密密钥 必须保密。其安全性取决于其所依赖的数学问题的难解性，p k c 的安全性所基 于的数学难题就是指如何找到一个计算上可行的算法对其所使用的单向函数进 行逆向计算。常用的非对称密码体制有基于大整数分解问题困难性的r s a 体 制、基于离散对数问题困难性的d s a 体制、以及基于椭圆曲线离散对数问题 ( e c d l p ) 困难性的e c c 体制1 9 j 。 2 _ 3 1r s a 图3p k c 加解密模型 r s a 自n 密算法的过程是： ( 1 ) 取两个素数p 和q ( 保密) ( 2 ) 计算 l ；p q ( 公开) ，妒( 月) = ( p 一1 ) ( q 一1 ) ( 保密) 9 ( 3 ) 随机选取整数p ，满足g c d ( e ，妒( 砌= 1 ( 公开) ( 4 ) 计算d ，满足d e ；1m o d 妒( n ) ( 保密) 利用r s a 加密第一步需将明文数字化，对明文信息按小于l o g ：n 位分块，一 个明文信息块对应一个数字。 加密算法c = m 。( m o d n ) 解密算法f q = c “( m o d n ) 其中m 为明文，c 为密文。 2 _ 3 2d i f n e h e l l m a n 设p 为5 1 2 比特以上太素数，g p ，p 、g 公开，以下是a ，1 3 通过不安全 信道交换会话密钥的d i f i l e h e l l m a n 协议： ( 1 ) a 随机选择x p ，发送g m o d p ，给b ： ( 2 ) b 随机选择y p ，发送g y ( r o o d p ) 给a ； ( 3 ) a 通过自己的x 秘密计算( 9 7 ) 。( r o o d p ) = 9 9 ( r o o d 力； ( 4 ) b 通过自己的y 秘密计算( 9 5 ) ( m o d p ) 。9 9 ( m o d p ) ； 现在a 与b 拥有相同的秘密值g ”( m o d p ) 作为共同的秘密密钥或由此派生 出秘密密钥，利用该密钥就可以通过s k c 进行保密通信了。该协议的安全性基 于有限a b e l 群上的离散对数问题的难解性。和r s a 类似，要求p 为安全素数。 2 3 r 3 d s a d s a t l 中各通信实体共用的参数：索数p ，满足2 卜1 p 2 0 ，并且5 1 2 s ， 1 0 2 4 ，6 4 | ，：素数q 。满足2 5 9 孽2 1 6 0 ，酬p 一1 ：整数g ，1 g p 1 ，g q = 1 ( r o o d p ) 。 各通信实体密钥对的产生：通信实体随机选取整数x ，0 c x q ，计算y = 矿 r o o d p ，x 作为该实体的私钥，y 作为该实体的公钥。 验证者在对签名消息进行验证之前，应当以可靠的方式获得共用参数p 、q 、 g 并且知道签名方的身份和公钥， 、签名过程 a 产生对消息m 的签名，执行如下操作： ( 1 ) 随机选择七，k 9 ； ( 2 ) 计算，= ( g k r o o d p ) r o o d g 5 ；r k “( h ( m ) + x r ) ) m o dq 其中日为安全h a s h 算法1 ”1 ( s h a ) 。则( r ，0 就是a 对消息m 的签名。 二、验证过程 设b 收到( 肼， j ) 后，为验证( ，j ) 就是a 对信息胛的签名，执行如下操作： ( 1 ) 检验有0 r g 和0 2 ，p 、q z + ，k 0 o u t p u t ：“m o d ，z 1 v o 2 ，v i p ，q o 1 ，q l l 2 k2 ( k , k ，_ i 七】t 。) 2 ，k 。= 1 3 f o rif r o m ，d o w n t o0d o 3 1 g o g oq lm o d - 3 2 i f k ，= 1t h e n g i g o q m o d 以 v o v ov i 一尸q o m o d 聆 v l 2t ob et e s t e d ，f o rt h en u m b e ro f t r i a l s o u t p u t ：t h em e s s a g e “p r i m e ”o r “c o m p o s i t e ” 1 c o m p u t eva n do d d ws u c h t h a tn 一1 = 2 v w 2 f o r j f r o m1 t o fd o 2 1c h o o s er a n d o m 口i n t h e i n t e r v a l0 口 r t 2 2b ( - - a ”r o o dn 2 3i fb = 1o r ”一1g o t os t e p2 6 2 4f o r f f r o m1t ov 一1d 0 2 4 1b ( - - b 2 m o d 2 4 2i f b = 行一1g ot os t e p2 6 2 4 3i fb = 1 o u t p u t “c o m p o s i t e ”a n ds t o p 2 4 4 n e x t j 2 5 o u t p u t c o m p o s i t e ”a n ds t o p 2 6n e x t j 3 o u t p u t “p r i m e 设h 有k 位，则经过a l g o r i t h m2 测试若n 为素数，然而它为合数的概率 为 p k , , - - 2 + 4 k ( 2 撕) 仁( 巩硷8 8 ) 为了将发生错误的概率减小到小于2 。1 ”。a l g o r i t h m2 中的参数，应根据表l 取值。 krk，kf 1 6 03 42 0 2 2 0 82 33 3 5 3 6 01 2 1 6 1 1 6 33 32 0 9 2 l52 23 6 1 3 9 21 1 1 6 4 1 6 63 22 1 6 2 2 22 13 9 3 4 3 01 0 1 6 7 1 6 93 l2 2 3 2 3 12 04 3 1 4 7 99 1 7 0 1 7 33 02 3 2 2 4 i1 94 8 0 5 4 28 1 7 4 1 7 72 92 4 2 2 5 2l85 4 3 6 2 67 1 7 8 18 12 82 5 3 2 6 41 76 2 7 二7 4 66 1 8 2 18 52 72 6 5 2 7 81 67 4 7 9 2 65 l8 6 1 9 02 62 7 9 2 9 41 5 9 2 7 1 2 3 24 1 9 1 1 9 52 52 9 5 3 1 31 41 2 3 3 1 8 5 33 1 9 6 。2 0 l2 43 1 4 3 3 41 3 1 8 5 3 - u p 2 表1 概率判定太数素数性参数f 的取值表 3 3 2 有限域 3 2 1 域的概念 满足以下三个条件的代数系统( f ，+ ，+ ) 称为域。 ( 1 ) f 关于运算+ 成a b e l 群，其单位元记为0 。 ( 2 ) f 、 0 关于运算+ 构成a b e l 群，其单位元记为1 。 ( 3 ) v 口，b ，c f ，分配律成立。即 ( d + 6 ) + c = 口+ c + 6 + c c + ( a + 6 ) = c + 口+ c + b f o ) 表示集合f 除去元素 0 ) 后的元素。 3 2 2 伽罗瓦域g f ( p ”) 定义域f 中元素个数称为域的阶( o r d e r ) ，记为o r df 。若域f 阶为一有 限数p ，则称之为有限域或g a l o i s 域，记为g f ( p ) 。 定义一个多项式在，域上，若不能表示为两个低次幂的多项式之积，则 称该多项式是f 域上的不可化约多项式。 多项式p ( x ) = 口o + a i x + - + 口 x ，a f f ，f = 0 , 1 ，k 如果f 的元素个数为p ，则不同的多项式p g ) 个数为，h 1 ，即p 0 ) 和肛l 位p 进制数a k a a 2 a l a o 一一对应，其中o i e f i = o ，l ，2 ，七。 例1 当f = g f ( 2 ) = o ，1 时，设 p o 0 0 0 ) 20 ；p o o l ( x ) 2 1 ；p o l o ( x ) = x ；p o l l ( 石) = x + 1 ： p l o o ( x ) = x z lp , o t ( x ) = x 2 + 1 ：p l i o ( x ) = x 2 乜；p ) 爿2 乜+ 1 很显然，p ，( x ) 与二进制数i 一一对应。这些多项式的乘积可得幂超过2 的 多项式。若引进在g f ( 2 ) 上的不可化约多项式肌0 ) 黾3 + z + 1 作为模约多项式，则 容易验证这些多项式关于加法“+ ”和乘法“，”构成有限域。更确切地说：在g f ( 2 ) 域上，m o dm ( x ) 构成有限域，可表示成g f ( 2 ，x 3 + x + 1 ) ，有的也表示成 f 2 x ( x 3 + x + n 。 3 2 3 有限域基本理论 定理1 设p ( x ) 是系数在g f ( p ) 域的肌次不可化约多项式，则次方州1 ，系 数在g f ( p ) 上的所有多项式关于r o o d p ( x ) 构成一阶为p “的g a l o i s 域g f ( p m ) 。 g f ( p “) 的元素可表示为元素在有限域g f ( p ) 的m 维向量，也可以看成是系 数在g f ( p ) 的多项式类r o o d p ) 的同余类。 并且域中存在最大的线性无关元素，设为口。= 1 , a ，口：，口。，域中除去零 元素外的每一个元素都