（计算机软件与理论专业论文）GF（2ltmgt）域上椭圆曲线密码系统的关键算法研究与实现.pdf

g f ( 2 ) 域上椭圆曲线密码系统的关键算法研究与实现 摘要 随着i n t r e n e t 的迅速发展，信息安全问题显得日益重要。但由于计算机 的计算能力逐步强大，因此必须有更安全、更有效率的加密算法才能保证数据 安全。椭圆曲线加密系统与其他公钥加密系统相比，以其密钥长度短，安全强 度高等许多优点，迅速受到国内外安全专家的极大关注。本文对g f ( 2 “) 域上 的椭圆曲线密码系统做了理论研究和实现工作。 文章首先介绍了网络安全基本问题、常见的网络安全技术、密码学的基本 概念和和几个著名的公钥算法：参考i e e ep 1 3 6 3 草案对相关数学理论和基本算 法进行了全面深入的研究，主要有有限域g f ( 2 ) 上的基本运算，安全椭圆曲线 和基点的选取等。特别地，在深入研究了现有的典型的点积运算以后，提出了 有效n a f 的概念，并认为对基点和随机点的点积运算应采用不同的方法才能获 得较高的效率，在此基础上构造了基于有效n a f 的新算法，理论分析和实验表 明这些算法是合理有效的；文章还设计了一个新的椭圆曲线加密解密方案，该 方案的优点是无须明文嵌入。最后在有限域g f ( 2 ”。) 上就k o b l i t z 曲线实现了 该椭圆曲线密码系统，实验说明该系统具有较好的时间性能。 关键字：椭圆曲线密码系统有限域g f ( 2 ”)算法多项式基有效n a f r e s e a r c ho na n d i m p l e m e n t a t i o n o f k e ya l g o r i t h m s o n e l l i p t i cc u r v e c r y p t o s y s t e m o v e r g f ( 2 “) 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 s i n c r e a s i n g l yi m p o r t a n t b u tn o w , c o m p u t e rh a sh i g h e rc o m p u t ea b i l i t y ，s o i t m u s th a v es a f e ra n dh i g h e re f f i c i e n te n c r y p t i o na l g o r i t h m 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 ，e l l i p t i c c u r v e c r y p t o s y s t e m ( e c c ) h a sm a n y m e r i t s ，f o re x a m p l e ，s h o r t e rs e c r e tk e y ，h i g h e rs e c u r i t ya n ds oo n ，s ot h e i n f i n i t e a t t e n t i o ni sp a i dt oi 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 i nt h i sa r t i c l e ，t h e r e s e a r c ho nt h e t h e o r y a b o u te l l i p t i cc u r v e c r y p t o s y s t e mo v e rg f ( 2 ”) a n dt h e i m p l e m e n t a t i o no f i ta r ed o n e a t f i r s t ，t h e b a s i c p r o b l e m o fn e t w o r k s e c u r i t y ，s o m e n e t w o r ks e c u r e t e c h n o l o g y , c r y p t o l o g ya n ds o m ef a m o u sp u b l i ck e ya l g o r i t h m sa r ed i s c u s s e di nt h e t h e s i s r e f e rt oi e e ep13 6 3d r a f t ，m a t ht h e o r ya n db a s i ca l g o r i t h mi np o i n ti sa l s o f u l l s t u d i e d ，t h e ya r e ：t h eb a s i co p e r a t i o no v e ro f ( 2 ”) ，f i n d i n gs e c u r ee l l i p t i cc u r v e a n db a s i sp o i n to v e rg f ( 2 ”) e s p e c i a l l y ，a r e rs t u d y i n gs o m e p u b l i s h e df a s ta l g o r i t h m s f o rt h ep o i n tm u l t i p l i c a t i o no ne l l i p t i cc u r v e s ，t h ep s 3 c rp r e s e n t s an e w c o n c e p t o fe f f e c t i v e n a f i no r d e rt oi m p r o v et h er a t eo fp o i n tm u l t i p l i c a t i o na l g o r i t h m ，b a s ep o i n ta n dr a n d o m p o i n tm u s ta d o p td i f f e r e n tm e t h o d s ，t h e nt w on e w m e t h o d sb a s e do ne f f e c t i v en a fa r e p r e s e n t e d t h e o r ya n a l y s i sa n dt h ee x p e r i m e n tp r o v et h a t ：t h e s en e wp o i n tm u l t i p l i c a t i o n a l g o r i t h m sh a v eh i g h e re f f i c i e n c y m o r e o v e r ，an e we n c r y p t i o na n dd e c r y p t i o ns c h e m e s o ft h ee c ca r ed e s i g n e d ，i t sm e r i ti sn op l a i n t e x t i n s e r t i nt h ee n d ，e c cb yk o b l i t z c u r v e so v e rg f ( 2 ”3 ) a r ei m p l e m e n t e d ，t h en e ws c h e m eh a sb e t t e rt i m ep e r f o r m a n c e t h r o u g he x p e r m e n t s 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 s y s t e m ，o v e rg f ( 2 4 ) ，a l g o r i t h m ，p o l y n o m i a lb a s i s e f f e c t i v en 陋 合肥工业大学 本论文经答辩委员会全体委员审查，确认符合合肥工业大学硕士论文质量 要求。 主席： 委员： 导师： 答辩委员会签名： 瓣冲回似孓袱 用阴种 勘以 1 互虬 j 劳1 级投 i 独创性声明 本人声明所呈交的学位论文是奉人在导师指导下进行豹研究工作及取得的研究成 果。据我所知除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果也不包含为获得盘罡王业太堂或其他教育机构的学位或证书而 使用过的材料。与我一同工作的同忠对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 学位论文作者签名： 1 厅戒j 签字日期：j 吖年月圹日 学位论文版权使用授权书 本学位论文作者完全了解盒胆些鑫璺 有关保留、使用学位论文的规定有权保 留井向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阏。本人授 权佥匿工些盘堂可以将学位论文的垒部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存，汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者娩、石蠢l 签字日期：年月日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名 j 惕孔一 签字日期：) 卅年月f p 自 电话 邮编： 致谢 值此论文完成之际，谨向我的导师侯整风副教授表示最真挚的感谢! 论文 是在侯老师悉，心指导下完成的。在论文的撰写过程中，侯老师提出了很多指导 性的意见，并多次对文稿进行了悉心的审阅。更感谢侯老师三年来对我无微不 至的关怀与孜孜不倦的教诲! 侯老师严谨的治学态度、渊博的专业知识、敏锐 的学术洞察力将对我以后的工作、学习产生深远的影响。古语云，一日为师， 终生为师，侯老师是我终生的老师。 我还要感谢计算机学院的王浩教授和胡学钢教授，在这三年的学习期间他 们给了我大量的指导和帮助，在这里我向王老师和胡老师表示深深地感谢。 此外，在课题的研究过程中还得到了我的同学杨帆，胡忠辉，刘洋宇，吴 燕萍等的帮助，在此一并对他们表示感谢。 在这里还要特别感谢我的爱人刘伟，感谢这几年来她在生活上无微不至的 关心，工作上全力以赴的支持，在我学习期间，她勇敢地挑起家庭重担，抚养 教育年幼的女儿。在论文顺利完成之际，希望能与我的家人分享其中的快乐。 最后，再次诚挚的感谢所有关心和帮助我的老师，领导，同学和亲人! 作者：符茂胜 2 0 0 5 年5 月2 0 1 1 计算机网络与信息安全 第一章序言 随着计算机和通讯技术的迅猛发展，特别是i n t e r r l e t i n t r a n e t 的迅速普 及和广泛使用，近年来网络上兴起各种新的业务，例如电子商务、电子政务等， 使得大量的敏感信息常常通过公共通讯设施或计算机网络等开放系统进行频繁 交换，计算机网络和人们的日常生活密不可分，对于社会，经济的影响也越来 越大。 然而，不幸的是，这个开放的信息系统存在着众多的安全隐患或漏洞，网 络上的传输信息随时都有可能被非法存取、窃听、篡改或破坏。网络犯罪对国 家安全，企业安全和个人安全所造成的损失也同益严重，计算机网络安全已经 成为一个社会问题。 一般情况下，对计算机网络的攻击可分为主动攻击和被动攻击。 被动攻击一般不会导致被侵入系统中所含信息的任何变动，而且系统的操 作和状态也不会改变。被动攻击主要是从传输中获得信息，威胁信息的保密性。 例如：对通讯线路中传输的信号进行搭线监听：从通讯设备工作过程中所产生 的电磁泄露中截获有用信息；通过对系统进行长期监视，利用统计分析方法对 诸如通信频度、通信的信息流向、通信总量的变化等参数进行研究，从而发现 有价值的信息和规律等。 主动攻击则是有意篡改系统中所含信息，或者改变系统的状态和操作。因此， 主动攻击主要威胁信息的完整性、可用性和真实性。例如：通过欺骗通信系统或用户 达到非法用户成为合法用户，或者特权小的用户冒充成为特权大的用户的目的；改变 信息内容，删除其中的部分内容，用假消息代替原始消息，或者将某些额外消 息插入其中：否认自己曾经发布过的某条信息，伪造一份对方来信，或者修改 来信等。 再比如：非法登录，非授权访问，破坏通讯规程和协议，拒绝合法服务， 设置陷阱，重发攻击等其他各种各样的网络攻击。 要保证网络信息安全就必须想办法尽量克服以上的种种威胁。当然，无论 采取何种防范措施，都不可能保证通信系统的绝对安全，安全永远只是相对的。 国际上网络信息安全的研究起步早。力度大，积累多，应用相对较广。2 0 世纪8 0 年代，美国国防部基于军事计算机系统的保密需要，在以前的基础理论 研究成果的基础上，制定了“可信计算机系统安全评价准则”( t c s e c ) ，其后 又制定了关于网络系统、数据库等方面的系列安全解释，形成了安全系统结构 的晟早原则。在2 0 世纪9 0 年代，英、法、德、荷四国针对t c s e c 准则的局 限性，联合提出了包括保密性、完整性、可用性概念的“信息技术安全评价准 则”( t i s f c ) 。近年六国七方( 美国国家安全局和国家技术标准研究所、加、英、 法、德、荷) 共同提出了“信息技术安全评价通用准则”( c of o ri ts e c ) 。c c 综合了国际上已有的评审准则和技术标准的精华，给出了框架和原则要求。 我国的信息安全研究经历了通信保密、计算机数据保护两个发展阶段，并 已经进入了网络信息安全的研究阶段。但由于系统内核受控于人，基于具体产 品的增强安全功能的成果，难以保证没有漏洞，难以得到很好的推广应用。 1 2 常见网络安全技术 网络安全技术的研究非常热门，涌现了各种网络安全技术。下面是几种常 见的网络安全技术。 ( 1 ) 防火墙技术 防火墙技术就是指设置在不同网络( 如可信任的企业内部网和不可信任 的公共网) 或网络安全域之间的一系列部件的组合。在逻辑上它是一个限制器， 同时也是一个分析器，能有效的监控内部网和i n t e m e t 之间的活动，保证内部 网络的安全。 ( 2 ) 数据加密技术 数据加密是保障网络信息安全的最基本、最核心的技术措施和理论基础。 与防火墙配合使用，是提高信息系统及数据安全性和保密性，防止秘密数据被 外部破坏所采取的主要技术手段之一。本文所要研究的椭圆曲线密码系统就是 一种数据加密技术。 ( 3 ) 安全内核技术 在操作系统的层次上考虑安全，尝试把系统内核中可能产生安全性问题的 部分从内核中剔除出去，从而使系统更安全。 ( 4 ) 数字签名技术 数字签名与日常生活中的手写签名效果一样。它不但能使消息接收者确认 消息是否来自合法方，而且可以为仲裁者提供发送消息者对消息签名的证据。 ( 5 ) 审计技术 它使信息系统自动记录下网络中机器的使用时间，敏感操作和违纪操作等。 ( 6 ) 访问控制技术 它允许用户对其常用的信息库进行适当权利的访问，限制他随意删除，修 改或拷贝信息文件。访问控制技术还可以使系统管理员跟踪用户在网络中的活 动，及时发现并拒绝黑客入侵。 ( 7 ) 身份认证技术 2 身份认证技术是计算机中较早应用的安全技术。它是互联网上信息安全的 一道重要屏障，应用广泛，也是目前网络安全技术中研究的重要课题之一。 1 3 课题背景 由于计算机运算速度的提高和网络分布式计算能力的逐步强大，这给目前 的加密解密体制带来了严重的安全问题，因此必须有更高强度的加密和认证体 制才能保证数据安全。 1 9 8 5 年，n k o b l i t z 和v m i l l e r 相互独立地提出了在密码学中应用椭圆曲 线( e l l i p t i c a lc u r v e ) 的思想1 7 “l ，使其成为构造公开密钥密码体制的一个有力的 工具。 椭圆曲线密码系统( e c c ) 与其他公钥加密系统相比，以其密钥长度短，安全 强度高等许多优点，迅速受到国内外安全专家的极大关注，基于椭圆曲线的公 开密钥密码体制获得了极大的发展，积累了大量的研究成果和文献。 椭圆曲线密码也引起了工业界的广泛关注。例如：电子商务协议s e t ( s e c u r e e l e c t r o n i ct r a n s a c t i o n s ) 的制定者已把它作为下一代s e t 协议中缺省的公钥密码算法。 许多标准化组织也制定了关于椭圆曲线公开密钥密码体制的相关标准，例如：i e e e 组织制定的公钥密码标准p 1 3 6 3 ，美国国家标准协会( a n s i ) 带i 定的椭圆曲线数字签名 算法( e c d s a ) 标准a n s i x 9 6 2 。 但是，在e c c 的研究领域中尚存在一些难题，成为制约其发展和应用的瓶颈， 如明文的嵌入算法、曲线阶和基点阶的计算、安全曲线的选取算法、椭圆曲线上的点 积运算等，而椭圆曲线上的点积运算，即计算n p 则是椭圆曲线研究的一个核心问题 和热点问题。本文对g f ( 2 ”) 域上的椭圆曲线密码系统的关键算法做了理论研究 和实现工作。本文的创新点有：( 1 ) ，在对有限域g f ( 2 m ) 上的椭圆曲线的点积运算 作了较为深入的研究后，提出了有效n a f 的概念，并认为对基点g 和随机点p 的点 积运算应采用不同的方法才能获得较高的效率，因此，利用大整数1 1 的有效n a f 表 示，提出了相应的点积算法( 详见4 5 节) 。( 2 ) ，现有的椭圆曲线加密解密系统基 本上都需要明文嵌入，而目前的明文嵌入方法都可能出现部分明文不能嵌入到 椭圆曲线上情形，因此，在5 1 2 节设计了一个无须明文嵌入的加密解密方案， 实验表明，该方案是合理可行的。 1 4 本文组织 本文以下部分的组织结构和主要内容如下： 第二章现代密码学简介。主要介绍了对称密码学和公开密钥密码学，重点 介绍了几个著名的公开密钥算法：r s a ，d i f f i e - h e l l m a n ，e i g a m a l ，最后也提及了 椭圆曲线密码体制( e c c ) 。 第三章椭圆曲线密码学。对涉及到的数学知识进行了较为深入的研究，然 后对椭圆曲线密码体制的形成，发展以及基本原理和应用作了详细的归纳和介 绍。在3 2 3 节着重介绍了有限域上的椭圆曲线及其基本运算。 第四章g f ( 2 “) 域上椭圆曲线密码系统的关键算法研究。首先对有限域 g f ( 2 “) 上的基本算法做了归纳和总结。对基于有限域f i f ( 2 “) 上的椭圆曲线密码 系统中的几个关键算法和问题做了全面深入的研究，主要包括：安全椭圆曲线 的选取及其阶的计算基点的选取和基点阶的计算，点积算法等。本文提出了 有效n a f 的概念，并就此设计了针对基点和随机点的点积算法，5 3 节对比实 验的结果表明，新的算法具有较高的效率。 第五章椭圆曲线密码系统的实现。设计了一个g f ( 2 “1 域上椭圆曲线加密 解密系统，该系统的一个重要特点是无须明文嵌入。对系统实现中的一些细节 做了介绍，模拟实现了本系统，并分析了实验结果。 第六章结束语。对本文进行总结和归纳，指出其不完善的地方和以后工作 的方向。 1 5 本章小结 本章主要介绍了网络与信息安全的一些基本问题，指出密码技术是网络和 信息安全的基本和核心技术。最后对课题背景和本文的结构组织做了交代。 4 第二章现代密码学简介 随着知识经济的到来，互联网的兴起，人们可以很方便地获得许多的免费 资源，但同时信息在传输过程中容易受到攻击。对于这些网络攻击，除了制定 相应的法律外，更需要从技术层面上采取保护措施，密码技术就是一种很有效 的方法。它能够有效地应用于信息鉴别、数字签名等，从而防止电子欺骗，这 对信息系统的安全起到极其重要的作用。 2 1 密码学介绍 密码的历史极为久远，其起源可以追溯到远古时代，人类有记载的通信密 码始于公元前4 0 0 年。密码学( c r y p t o g r a p h y ) - - 词来源于古希腊的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 ) ，意思为密写。虽然密码是一门古老的技术， 但是自密码诞生直至第二次世界大战结束，对于公众而言，密码充满了神秘感， 似乎密码只与军事，间谍等紧密联系在一起。随着计算机的发明和广泛使用， 特别是i n t e r n e t 的迅猛发展，使得密码学终于揭开了神秘的面纱走进公众的 曰常生活。 2 1 1 密码学的发晨过程 密码学的发展大致可分为三个阶段w 1 ：古代加密方法，古典加密和近代加 密。 古希腊墓碑的铭文志，隐写术，以及黑帮行话等都可以看作古代的加密方 法。这种加密方法实际上包含了密码学的若干要素，但是只能限制在一定范围 内使用。 古典密码一般采用手工或机械变换的方式实现，它比古代加密方法更复杂， 但是密钥的变化量较小。古典密码时期的密码系统已经初步呈现当代密码系统 的雏形。古典密码的代表密码体制主要有：单表代替密码，多表代替密码和转 轮密码。c a e s a r 密码是一种典型的单表代替加密，多表代替密码有v i g e n e r e 密码，h i l l 密码，著名的e n g i m a 密码【2 l 是第二次世界大战中使用的转轮密码。 1 9 4 9 年c l a u d es h a n n o n 发表了保密系统的信息理论。1 9 7 6 年w d i f f i e 和m h e l l m a n 发表了密码学的新方向，这两篇重要的论文和1 9 7 7 年美国实 施的数据加密标准( d e s ) ，标志着密码学的理论和技术的划时代的革命性变 革，宣告了近代密码学的开始。在这一阶段，密码理论蓬勃发展，密码算法设 计与分析互相促进，出现了大量的密码算法和各种攻击方法。同时，密码使用 的范围不断扩大，也出现了许多通用的加密标准，促进了网络和技术的发展。 例如：a e s ，r s a ，e 1 g a m a l 等都是著名的密码技术，本文所要研究的椭圆曲线密 码体制由于其安全性高，计算速度快，资源要求小等优点，迅速成为公开密钥 加密系统的研究热点。 随着其他技术的发展，一些具有潜在密码应用价值的技术也逐渐得到了密 码学家的重视，出现了一些新的密码技术，例如：混沌密码，量子密码等，这 些新的密码技术获得了极大的重视，并在逐步地走向实用化。 2 1 2 密码学的基本概念 密码学是以认识密码变换的本质、研究密码保密与破译的基本规律为对象 的学科，它包括两个分支：密码编码学( c r y p t o g r a p h y ) 和密码分析学 ( c r y p t a n a y s is ) 。密码编码学主要研究对信息进行交换，以保护信息在信道的 传输过程中不被攻击者窃取、解读和利用的方法，而密码分析学则与密码编码 学相反，它主要研究如何分析和破译密码。这两者之间既相互对立又相互促进。 现代密码学除了包括密码编码学和密码分析学两个主要学科外，还包括近几年 才形成的新分支一密码密钥学，它是以密码的核心部分一密钥作为研究对象的 学科。密钥管理是一种规程，它包括密钥的产生、分配、存贮、保护、销毁等 环节，在保密系统中至关重要。上述三个分支学科构成现代密码学的主要学科 体系。 一个密码系统或称为密码体制由以下五个部分组成： 1 明文空间尸：全体明文集合； 2 密文空间c ：全体密文集合： 3 密钥空间k ：全体密钥集合，k = ( k 。，k 。) ，k 。表示加密密钥，k 。表示解密 密钥； 4 加密算法e 明文和密文之间的变换规则； 5 解密算法d ，密文和明文之间的变换规则； 加密变换：c = e ( p ，k ) ； 解密变换：p = d ( c ，k 。) = d ( e ( p ，k 。) ，k 一) ； 在整个密码系统中，还有非授权者，或称之为攻击者( h t t a c k e r ) ，他们 通过前面提及的各种方法来窃听和干扰信息。如果非授权者借助窃听到的密文 以及其他一些信息通过各种方法推断原来的明文甚至密钥，这一过程称为密码 分析或密码攻击。从事这一工作的人称为密码分析者或密码分析员 ( c r y p t a n a ly s t ) 。 一个完整的密码系统可以表示成图2 1 所示的模型。 6 图2 - 1 完整的密码系统示意图 2 1 3 密码系统的分类 密码体制的分类方法【4 】 艮多，其中常见的分类方法有： ( 1 ) 根据加密算法与解密算法所使用的密钥是否相同，或是否能简单地由 加密密钥求的解密密钥，可以将密码体制分成对称密钥密码体制( 或称之为单 钥密码体制，秘密密钥密码体制，对称密码体制等) 和非对称密钥密码体制( 或 称为双钥密码体制，公开密钥密码体制等) 。这是我们经常使用的一种分类方法。 如果一个密码系统的加密密钥和解密密钥相同，或者虽然不相同，但可以 由其中的任意一个容易地得到另外一个，所采用的就是对称密钥密码体制。例 如：著名的d e s ，a e s 等都是对称密钥密码体制。 如果一个密码系统把加密和解密分开，加密和解密分别用两个不同的密钥 实现，并且由加密密钥推导出解密密钥在计算上不可行的，则该系统就是采用 的非对称密钥密码系统。采用非对称密钥密码系统的每个用户都有一对选定的 密钥，其中一个是可以公开的，叫做公钥，另一个由用户自己秘密保存，称为 私钥。公开密码体制的典型代表有：r s a ，e i g a m a l ，以及本文研究的椭圆曲线 密码体制( e c c ) 等。 ( 2 ) 根据密码算法对明文信息的加密方式，可分为流密码和分组密码。 流密码逐位地加密明文消息字符，例如：a 5 ，s e a l 等都是流密码算法。 分组密码将明文消息分组，每个分组含有多个字符，逐组地进行加密，例如： d e s ，r c 5 ，a e s 等都是分组密码算法。 ( 3 ) 按照是否能进行可逆的加密交换，又可分为单向函数密码体制和双向 交换密码体制。单向函数最重要的特点是很容易地把明文转换成密文，但是再 把密文转换成原来的明文却是困难的，有时甚至是不可能的。典型的单向函数 有：m d 4 。m d 5 ，s h a 1 等。 2 2 对称密码体制 1 9 7 3 年美国国家标准局n g s ( n a t i o n a lb u r e a uo fs 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 ya g e n c y ) 研 究发现这是唯一满足各项要求的方案，并于1 9 7 7 年宣布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 g i a ld a t ae n c r y p t i o n a 1 9 0 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 d e 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 ih 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 c e de n c r y p t i o ns t a n d a r d ) 的活动， 并专门成立了a e s 工作组，目的是确定一个美国政府2 l 世纪应用的数据加密标 准，参加竞选的有l5 个加密算法，最后由r i j n d a e l 算法胜出哺1 。 在对称密码体制( s k c ) 中，任意一对通信实体共享一对密钥，其中一个 称为加密密钥，一个称为解密密钥，加密密钥和解密密钥相同或者彼此之间容 易相互确定。因此加密密钥和解密密钥都必须保密，它的加解密模型如图2 2 所示。 2 3 公开密钥体制 确文l ：瓣! 加謦。+ 。臻。脯： 图2 - 2s k c 加解密模型 1 9 7 6 年，d i f f i e 和h e l l m a g i 首次提出公钥加密体制的设想1 6 1 。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 公钥密码系统1 6 j ；d i g i t a ls i g n a t u r e a 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 ) ；1 9 8 5 年，n e a lk o b l i t z i ( 美国华盛顿大学) 和v i c t o r m i l l e r l 7 1 ( i b m 公司) 相互独立地提出了在密码学中应用椭圆曲线的思想。 我国学者提出的基于布尔代数的公开密钥体制和陶仁骥、陈世华教授提出 的基于有限自动机理论的公开密钥密码体制【9 1 。这是世界上第一个时序公开密 钥密码。它容易实现，密钥量适中，加解密速度快，已受到国际上的广泛关注。 在公开密钥体制( p k c ) 中，任何一个通信实体都有一对密钥，其中一个称 为公钥，一个称为私钥，公钥和私钥不同在不知道陷门信息的情况下，由公 钥推出私钥在计算上是不可行的，公钥总是用于加密和验证，私钥总是用于解 密和签名。p k c 的加解密模型如图2 3 所示。它的加解密算法和加密密钥可以 公开，但解密密钥必须保密。其安全性取决于其所依赖的数学问题的难解性。 常用的非对称密码体制有基于大整数分解问题困难性的r s a 体制、基于离散对 数问题困难性的d s a 体制、以及基于椭圆曲线离散对数问题( e c d l p ) 困难 性的e c c 体制l2 1 。 塌篁；密冀 明文 盘= ：毒： 簟i 薷 【一： 竹枣矗= = 墨， 闰2 - 3p k c 加解密模型 下面简单介绍几个典型的公开密钥密码体制： 一、r s a 算法 r s a 加密算法的过程是： 取两个素数p 和口( 保密) 计算疗= p q ( 公开) ，伊( 哟= ( p - 1 ) ( q - 1 ) ( 保密) 随机选取整数e ，满足g e d ( e ，p ( 疗) ) = l ( 公开) 计算d ，满足d e s lr o o d 烈疗) ( 保密) 利用r s a 加密第一步需将明文数字化，对明文信息按小于l o g ： 位分块，一个 明文信息块对应一个数字。 加密算法c = m 。( r o o d n ) 解密算法 9 1 = c 4 ( r o o d n ) 其中，m 为明文，c 为密文。 二、d i f f i e h e l l m a a 密钥交换协议 设p 为5 1 2 比特以上大素数，g p ，p 、g 公开，以下是a ，b 通过不安全 信道交换会话密钥的d i 炳e h e l l m a n 协议： ( 1 ) a 随机选择x p ，发送g 。( r o o d p ) 给b ： ( 2 ) b 随机选择y p ，发送g ( m o d p ) 给a ； ( 3 ) a 通过自己的x 秘密计算( ) 1 ( r o o d p ) = 9 9 ( r o o d p ) ： ( 4 ) b 通过自己的y 秘密计算( g 。) ( r o o d p ) = g ”( r o o d p ) ； 现在a 与b 拥有相同的秘密值g w ( r o o d p l 作为共同的秘密密钥或由此派生 出秘密密钥，利用该密钥就可以通过s k c 进行保密通信了。该协议的安全性基 于有限a b e l 群上的离散对数问题的难解性。和r s a 类似，要求p 为安全素数。 三、e l g a r e a l 算法 e i g a m a l 算法可用于数据加密，也能用于数字签名和身份认证1 1 3 1 ，其安全 性依赖于计算有限域上离散对数这难题。 ( 1 ) 产生密钥对。首先选择一个素数p ，两个随机数，g 和x ，g ，x p ，计 算： y = g x ( m o dp ) ，则其公钥为y ，g 和p 。私钥是x 。g 和p 可由一组用户 共享。 ( 2 ) e 1 g a m a l 用于数字签名。被签信息为m ，首先选择一个随机数k ，k 与 p 1 互质，计算：a = g k ( m o dp ) 再用扩展e u c l i d e a n 算法对下面方程求解b ： m = x a + k b ( m o dp 1 ) 签名就是( a ，b ) 。随机数k 须丢弃。 验证时要验证下式： y “a + a b ( m o dp ) = g “m ( m o dp ) 同时一定要检验是否满足1 = a p 。否则签名容易伪造。 ( 3 ) e i g a m a l 用于加密。被加密信息为m ，首先选择个随机数k ，k 与p 1 互质，计算： a2g “k ( m o d p ) b 2 y “k m ( m o dp ) ( a ，b ) 为密文，是明文的两倍长。 解密时计算：m ；b a a x ( r o o dp ) 四、椭圆曲线密码系统( e c c ) 基于有限域g 以口) 上的椭圆曲线，可以建立椭圆曲线密码系统( e c c ) 。这 里口为一大素数或素数的幂( p ”，通常为2 ”) 的形式。 在椭圆曲线e 上的点关于“十”法构成a b e l 群。、卵，q e ，有p + q = r ，r 是椭圆曲线上的点，而k p = p + p + p ( 累加女1 次) ，对于给定的有限域上的 椭圆曲线，选取基点( b a s ep o i n t ) g ，用户私下产生随机数k 作为自己的私钥， 再计算g 所产生的椭圆曲线上的点作为公钥，发送方利用接受方的公钥加密， 而接受方则利用自己的私钥解密。由于e c c 是本文讨论的课题，详细的讨论见 后面的章节。 e c c 、r s a 和e l g a m a l 都可用于数字签名，身份认证【4 5 和密钥交换， d i f i l e h e l l m a n 仅适用于密钥交换。 2 4 对称密锅体制和公开密锈体制比较 s k c 的优点是加密解密速度快，保密强度高。其缺点( 1 ) 密钥必须另外 1 0 通过一个安全信道传送，密钥分发困难。( 2 ) 不能提供严格的认证功能。发送 方不能使接收方相信信息确实是由意定的发送方发过来的：p k c 的优点是( 1 ) 彻底解决了密钥分发问题。由于加密密钥是公开的，解密密钥由通信实体自己 保存，p k c 中实际上不存在密钥分发问题。( 2 ) 具有数字签名功能。数字签名 可以提供三种安全服务：身份鉴别，数据完整性和抗抵赖。p k c 的缺点是算法 复杂，加密解密速度一般要比s k c 慢1 0 0 0 倍 2 1 。正是基于s k c 与p k c 的这 些特点，在加密系统设计过程中，通常是用非对称加密算法加密会话密钥，而 用对称加密算法加密所需传送的明文。 2 5 本章小结 本章主要介绍了密码学的基本知识，并列举了几个著名的公开密钥算法。最后 对公开密钥体制和对称密钥体制的优缺点作了分析，指出：在加密系统设计过程中， 一般用非对称加密算法加密会话密钥，而用对称加密算法加密所需传送的明文。 3 1 有关数学背景 第三章椭圆曲线密码学 定义3 1 ：群是一个代数系统，它是由一个非空集合g 组成，在集合g 定 义了一个二元运算满足： ( 1 ) 封闭性，即：对任意的a , b g ，有a o b g ； ( 2 ) 结合性，即：对任意a , b ，c g ，有a b c = ( a b ) c 妄a ( b c ) ； ( 3 ) 单位元，即：存在一个元素1 g ，( 称1 为单位元) ，对任意元素a g ，有：a o i = i o a = a ； ( 4 ) 逆元，即：对任意a g ，存在一个元素a “g ，( 称a _ 为逆元) ， 使得：a - a q = a _ o a = 1 ； 我们把满足上面性质的代数系统称为群，记为 。 如果群 满足交换律，即对任何a , b g ，有a e b = b o a ，则称g 为交换 群，或者阿贝尔群。 任意群 ，a g ，元素a 的乘幂定义为 a n = a a a a ，( n 个a 相乘) 。其中n 为正整数。 并规定：a 0 = 1 ( 单位元) 。显然有a m e a “= a ”“ 定义3 2 ：如果集合g 中只含有有限多个元素，则我们称 为有限群， 并把集合g 中的元索个数称为有限群g 的阶。 群具有以下性质： ( 1 ) 群中的单位元是难一的； ( 2 ) 消去律成立，即对任意的a , b ，c g ，如果a b = a t c ，则b = e ；如果 b a = c a ，则b = c ： ( 3 ) 群中的每一个元素其逆元是唯一的。 定义3 3 ：设 是一个群，如果群g 中存在个元素q ，使得对群g 任 意元素b 都存在一个整数i 使得b = d i p 则我们称g 是一个循环群，称元素。 为群g 的个生成元。 有限循环群的生成元具有以下性质： 定理3 i ：循环群 ，n 为群g 的一个生成元，l 为群g 的单位元，g 的阶为n ，则：a “= 1 3 1 2 有限域 一域的概念 满足以下三个条件的代数系统( f + ，) 称为域。 ( 1 ) f 关于运算+ 成a b e l 群，其单位元记为0 。 ( 2 ) f o ) 关于运算构成a b e l 群，其单位元记为l 。 ( 3 ) v a ，b ，c f ，分配律成立。即 ( a + 6 ) + c = d + c + b + c c + + b ) = c + a + c + b f ( o ) 表示集合f 除去元素( o ) 后的元素。 二伽罗瓦域g f ( p ”) 定义3 4 ：域f 中元素个数称为域的阶( o r d e r ) ，记为o r d f 。若域f 阶为 一有限数p ，则称之为有限域或g a l o i s 域【”1 ，记为g f ( p ) 。 定义3 5 ：一个多项式在，域上，若不能表示为两个低次幂的多项式之积 则称该多项式是f 域上的不可化约多项式。 多项式p ( x ) = a o + a l x + + 吼矿，q f ，f - 0 ，l ，k 如果f 的元素个数为p ，则不同的多项式p 0 ) 个数为矿“，即p ( x ) 和k + l 位p 进制数u k a k 。口2 口l 口。一一对应其中a i e f i = o ，1 ，2 ，t 。 例3 1 ：当弘g h 2 ) = 0 ，l 时，设 p o o o ( x 1 = 0 ； p 1 0 0 0 ) = 工2 ； p o o l 扛净1 o p 1 0 i ( 工) = ，+ l ： p o l o ) = x ： p l l o o ) = x 2 + x ； p 0 1 1 0 ) 2 x + 1 o p l li ( x ) = x 2 + x + l 很显然，p ，( 工) 与二进制数i 一对应。这些多项式的乘积可得幂超过2 的 多项式。若引进在g 尺2 ) 上的不可化约多项式m o ) 3 竹+ l 作为模约多项式，则 容易验证这些多项式关于加法“+ ”和乘法“，j 构成有限域。更确切地说：在 g 以2 ) 域上，m o dm ( 工) 构成有限域，可表示成g f ( 2 ，矿+ x + 1 ) 。 定理3 2 ：设p ( x ) 是系数在g f ( p ) 域的m 次不可化约多项式，则次方m 1 ， 系数在g f ( p ) 上的所有多项式关于r o o d p ( x ) 构成一阶为p “的o a l o i s 域c f ( p “) 。 g f ( p ”) 的元素可表示为元素在有限域g f ( p ) 的m 维向量，也可以看成是系 数在g f ( p ) 的多项式类r o o d p ( x ) 的同余类。 并且域中存在最大的线性无关元素，设为= 1 , a 。，口：，域中除去零 元素外的每一个元素都可以表示成如下形式： a o 口o + 口l 口l + + d _ 一i 口_ 一ia ，g f ( p ) ，i = 1 , 2 ，m 因此，上例中的g f ( 2 ，一+ x + 1 ) 又可以记为g f ( 2 3 ) ，将p o o l ) 、p o , o ( x ) 、p l o o 缸) 写成三维向量的形式，分别为：e o = o ，0 ，1 ) ；q = 0 ，l ，0 ) ；e 2 = l ，0 ，0 ) ，很显然， g f ( 2 3 ) 上的每个元素都可以由向量组e o 、e l 、e 2 唯一线性表示，因此 e o ，e l ， e 2 还是域的一组基因此此例的域g f ( 2 3 ) 还是多项式基的有限域。 三本原元素 令f 是，非零元素的集合。即，= f o 。 ，是阶为r = p m 1 关于乘法的循环群。若该群含有有限元素： 口，口2 ，o f ，口= l 则口称为域f 的本原元素。 在上例中，选取口= p o l o ( x ) = x ，则m o d m ( x ) ( i = l ，2 ，7 ) 依次如下 x ，x 2 ，x + l ，x 2 + x ，x 2 + z + l ，工2 + 1 ，1 。 x 即为域g f ( 2 3 1 的本原元素。 3 1 3 算法复杂性