（应用数学专业论文）rsa和椭圆曲线密码算法的研究.pdf

摘要 在公钥密码体制以前的整个密码学史中，所有的密码算法，包括原始手工计 算的、由机械设备实现的以及由计算机实现的，都是基于代换和置换这两个基本 工具。公钥密码体制则为密码学的发展提供了新的理论和技术基础，一方面公钥 密码算法的基本工具转换成数学函数；另一方面公钥密码算法是以非对称的形式 使用两个密钥，两个密钥的使用对保密性、密钥分配、认证等有深刻的意义。 r s a 算法是目前应用最广泛的一种公钥密码算法。本文简单介绍了r s a 公 钥密码体制，分析比较r s a 公钥密码中已有的模幂运算方法，将得到的最快软 件加速算法v l n w 滑动窗口法和硬件映射最快的m o n t g o m e r y 模乘算法综合， 得到改进后的m n e x p 算法能有效提高r s a 公钥密码的实现效率。 椭圆曲线密码系统被认为可以替代r s a 算法的一种公钥密码体制。本文阐 述了椭圆曲线及其相关知识，特别说明了建立在有限域c ( 其中p 是大于3 的 素数) 上的非奇异椭圆曲线e ，深入研究目前已有的各种标量乘法，由此提出了 椭圆曲线密码算法在混合坐标下改进的带符号滑动窗口算法，该算法兼容了n a f 方法的优点，拥有最少数目的非零窗口数，又避免了域元素上的大量求逆运算， 较成功地减少了标量乘法计算量。最后归纳得出一些有用的结论。 本文的创新点在于综合各种算法在不同方面的优势，从不同角度和不同层次 去改进模幂算法和标量乘算法，得到的新算法可供在实现r s a 和椭圆曲线密码 体制时参考，具有较大的实用价值。 关键词：r s a 公钥密码体制；椭圆曲线密码体制；滑动窗口算法；m o m 9 0 m e r y 模乘；模幂运算；标量乘法 n a b s t r a c t b e f o 他t h el l i s t o r yo f 印p e a i i n gp i l b l i c k e yc r y p t o g r a p h y ，a l l t h ee n c 珊p t i o na n d d e c r y 埘a l g o r i 也m si n c l u d i n g 吐圮砥g i 舱lm 锄i l a lc a l c u l a t i o n s ，i m p l e m 蛳t e db y m l l a 面c 砒e 叫p m e n to rc o m p u t t 1 1 e ya r cb a s e do n 也e s et v 阳b 酗i ct o o l s ： r e p l a c e m e n t 柚ds u b s t i t u t i o n p u b l i ck e yc r y p t o 斟a p h yl l a sp m v i d e dan e w 也e o f e t i c a l a 雌dt e c 眦c a lb a s i sf o rm ed e v e l o p m e mo fc r y p t o g r a p h y o nt h co n eh a n d ，t 量l eb a s i c t o o l so f p u b l i ck e ya l g 耐t h m 仃a i l s l a t ei n t om a 出e m a t i c a l 劬c t i o n ；o nt h eo t h e rh a l l d ， t i l ep u b l i ck e ya l g o r i t l l mu t w ok e y si l l 鹊y m m e t r i cf o m ，耐 l i c hh a sp r o f o 嘲d s i g m f i c 曲c ef b rc f i d e n t i a l i t y ，k e yd i s t r i b u t i o n ，弧m l 即吐c a 吐o n ，a n ds oo n a so n eo ft h ep u b l i ck e ya l g o 珊衄，r s aa l 删n l l i li sa p p l i e dm o s t 、城d e l y j r l l i s 砒i c l ep 州i d e sa _ b f i e fd e 刚砸o no fr s ap u b l i ck e yc f ) r p t o 舯p h y ，强煳l y s i s 黼d c 伽p 辩o fa l lk i n d so fp f e s e l l te x i s t e dm o d m 舡e x p o m i a t i o ni i lr s ap u b l i ck e y c r 腆g r a p h y ，ac o l l i g a t i o no ft l l e 胁t e 吼a c c e l 锄t i n gs o 如旧r ea l g 埘t 胁v l n w s l i d i n g w i n d o wm e t h o d sa n dh 甜d w a r e m a p p i n gf b tm o m g 啪e r ym o m l l a r 删n t i p l i c a l i o na l g o r i n 瑚t h a tc 鞠i l l l p r o v e 地i m p l c m e 哪e 髓c i c yo fr s a 舯b l i c k e yc r y p t o g 膪p h yf o ra c h i e v i n gt h en o v e la i g 碰t l l 】m m n e x pa l g 确m m e c ci sc o n s i d e r e dt ob ea i la l t e m 砒i v et or s a 1 1 1 i sa n i c l ep r o v i d e sa 蛹e f d e 咖t i o no fr s ap u b l i ck e yc 嘞p t o 脚h y 锄dt t l e a s s o c i 砷。dk 1 1 0 w l e d g e ，i i l p a m c l l l 盯砷r o d u c e sn o n s l l p c 陪抽g i l l a re l l i p t i cc u r v 船e 删c h i se s 诅b l i s i e do n 也e f m i t cf i e l de 、i 也p 3 ，i n d e p ms 伽i e sp r e s e me x i s t e ds c a l a rm u m p l i c a t i o n ， 缸廿埘p f o p o s e sa ni m p 州e ds i ”e ds l i d i r i g 谢n d o wa l g 嘶m mo ne c cu n d c ft h e m i x e dc o 伽d i n a t e s ，t h ei m p r o v e da l g o r i t i l n lc o m p 碰b l em ea d v 凸l l t a g eo f 也en a f ， h 勰t h cl 髓s tn 啪b c ro f z e r 0 、 ，i n d o wa n da v o i dal a r g en 啪b e ro f i n v e r s eo p 删i o n ， s u c c e s s f i l i l y r c d u c es c a 王a r m l t 碴l i c a t i o nc a l c l l l a t i o n f i n a l l y ，is u m m 撕z e 锄dd r a w s o m eu 向lc o n c l u s i o n s t h em a 主np 1 8 c eo fi o v a t i o no f 嘲i sp a p e ri st 0 铲a s pt l l ea d 、，a n t a g eo fd i 矗b r e m a l g 嘶t l l j m s ， 疳o md i 行e r e n t a 1 1 9 l e s a n dl c v e l s i m p r o v em o d u l a rc x p o n e n t i “o n a l g o r i t l l m 锄ds c a km u l t i p l i c a t i o na l g o 小胁，锄da c h i e v en e wa l g o r i t h i nw h i c hc a n p r o v i d e 坤f b r c e t ot l l e i m p l e m e n t a t i o no fr s a 觚de c c ，m e a n t i m et h en e w a l g o r i m mh a v eg r e a t e rp r a c t i c a lv a l u e 1 ( e yw o r d s ：r s ap u b l i c - k 锣c r y p t o s ”t e m s ；e m p t i c 如r v ec r y p t o s y s t e m s ； s i i m n gw i n d o wm e t h o d s ；m o t g o m e r y sm o d u l 盯m u i 蛀一i c 置h o n ； i 垤o d u l a re x p o n e n “h t i o no p e r a “o n ；s c a i a rm u l t i p h c a t i o n i 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研 究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文 不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研 究做出重要贡献的个人和集体，均己在文中以明确方式标明。本人完 全意识到本声明的法律后果由本人承担。 作者签名：声咿 日期：却年r 月 b 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权湖南大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在一年解密后适用本授权书。 2 不保密口。 ( 请在以上相应方框内打”) 、 一 作者签名：届妒二日期： 州年f 月 ，；日 导师签名：郧啊 日期：如6 年厂月，3 日 1 1 研究背景和意义 第1 章绪论 随着全球信息高速公路建设的兴起和通信网络的数字化、智能化、宽带化的 不断加快，特别是i n t e n | e t 的高速发展，给人们生活带来极大的方便。一方面， 电子政务、电子商务、电子邮件、电子自动转帐支付系统等已成为我们日常生活 中不可却少的一部分；另一方面，人们在高科技带来方便的同时对信息的安全存 储，安全处理和安全传输也提出了更高的要求，解决网络通信和电子商务系统的 信息安全问题成为了当务之急。密码学( c r y p t o 酽a p h y ) 便是解决这一问题的有效 手段。 公开密钥密码( 简称公钥密码，又称非对称公钥密码) 是现代密码学中最重要 的研究内容之一。密码学，其一般理解就是保护信息传递的机密性。但这仅仅是 密码学研究的一个方面。对信息发送人的身份的认证以及信息的完整性的检验是 密码学研究的另一个方面。公钥密码很好地解决了这两方面的问题，并正在产生 许多新的思想和方案。与公钥密码相对应的是传统密码( 又称对称密钥密码) 。在 传统密码中，用于加密的密钥与用于解密的密钥完全相同，因此，通常使用的加 密算法比较简便、高效，密钥简短。但是传送和保管密钥是一个严峻的问题。 公钥密码的观点是由遗菲( w d i 伍e ) 和赫尔曼( m e h e l l m a l l ) 于1 9 7 6 年在他们 的论文“密码学的新方向”一文中l l 】首次提出的，它使密码学发生了一场大的变 革。d i 茁e 和h e l l l i l 蛐为解决密钥管理问题，提出了一种峦钥交换协议，允许在 不安全的媒体上通信双方交换信息，安全地达成一致的密钥。在公钥密码中，加 密密钥不同予解密密钥，加密密钥公之于众，谁都可以使用。解密密钥只有解密 人自己知道，分别称为公开密钥( 简称公钥) 和秘密密钥( 简称私钥) 。公钥密码的 观点提出来之后，大量的公钥密码体制也陆陆续续涌现出来，比如r s a 公钥密 码、m e 削e - h e l l m 锄背包公钥密码、m c e l i e c e 公钥密码、e l g 绷a l 公钥密码和椭 圆曲线公钥密码c c ) 等，所有这些公钥密码的安全性都依赖于数学问题的难解 性。 公钥加密系统不存在对称加密系统中密钥的分配和保存问题，对于具有n 个 用户的网络，仅需要2 n 个密钥。公钥加密系统除了用于数据加密外，还可用于 数字签名。公钥加密系统可提供以下功能： ( 1 ) 机密性( c o 而d e n t i a l i t y ) ：保证非授权人员不能非法获取信息，通过数 据加密来实现。 ( 2 ) 认证( a u t b e m i c a t i o n ) ：保证对方属于所声称的实体，通过数字签名来实 现。 ( 3 ) 数据完整性( d a t ai n t e 鲥t y ) ：保证信息内容不被篡改，入侵者不可能用 假消息代替合法消息，通过数字签名来实现。 ( 4 ) 不可抵赖性( n o n r e p u d i a t i o n ) ：发送者不可能事后否认他发送过消息， 消息的接受者可以向中立的第三方证实所指的发送者确实发出了消息，通过数字 签名来实现。 目前己建立或正在建立的各种安全信息传输和交换系统的框架都是按照公 钥密码学理论来构筑的。当寻找公钥密码所基于的数学问题时，密码学家需要寻 找的是用最快算法所需要指数时间的问题。粗略地讲，它们的安全性都是基于复 杂的数学难题。对某种数学难题，如果利用通用的算法计算出密钥的时间越长， 那么基于这一数学难题的公钥加密系统就被认为越安全。2 0 多年来，许多曾经 提出的公钥密码已经被攻破了( 也即被证明是基于一个比原先所想像的要容易的 问题) ，也有很多被证明是不实用的，还有一些新的密码体制下在被研究，如基 于辫群的密码体制、n t r u 、量子密码体制等。迄今为止，比较流行的和被人们 认可的公钥密码体制主要有两类： ( 1 ) 基于大整数因子分解问题，其中最典型的代表是r s a 公钥密码。 r s a ( 蹦v e s t ，s l 啪i r a d l 锄姐) 是一种国际公认的理想公钥密码体制。它表达方 式简单，保密性强，没有密钥管理的麻烦，并且具有数字签名、认证和鉴别等多 种功能，特别适合于现代保密通信的需要。大整数幂剩余计算是r s a 公钥密码 学体制的核心运算之一，它可使得r s a 公钥密码计算速度非常缓慢，难以达到 实际运用的效果。为了提高r s a 公钥密码体制的运算速度，人们一直在寻找、 研究它的各种快速算法。由于目前国际上流行的其他凡种公钥密码体制的关键也 都是大整数幂剩余计算，因此，研究快速的大整数模幂算法具有十分重要的意义。 ( 2 ) 基于离散对数问题，比如e 1 g 锄a l 公钥密码和影响比较大的椭圆曲线公 钥密码( e c c ) 。椭圆曲线上的离散对数的计算要比有限域上的离散对数的计算更 困难，能设计出密钥更短的公钥密码，采用椭圆曲线构造的公钥系统已经体现出 比采用传统数论方法构造的r s a 公钥系统等具有更大的优势。与此同时随着各 种新算法的层出不穷、分布式计算能力的目益强大以及一些特定的场合( 如智能 卡等计算能力和存储能力非常有限的应用环境) ，这就迫使r s a 体制中使用的模 数和基于有限域上离散对数问题公钥密码体制中有限域的尺寸越来越大，同时需 要更长的密钥来保证信息的安全，因此造成了运算速度的降低。设计快速的r s a 和椭圆曲线密码算法成为公钥密码体制研究的热点，具有十分重要的理论意义和 实用价值，受到了国际上广泛关注。 1 2 国内外研究现状 r s a 公钥密码是于1 9 7 7 年提出的，算法研制的最初理念与目标是努力使互联 网安全可靠，旨在解决d e s 等对称算法的秘密密钥，在利用公开信道传输分发时 的难题。而实际结果不但很好地解决了这个难题，还可利用r s a 完成对电文的数 字签名以抗对电文的否认与抵赖，同时还可利用数字签名较容易地发现攻击者对 电文的非法篡改以保护数据信息的完艟性。r s a 是第一个成熟的、迄今为止最成 。1 2 ：；：j ：l ：一 功的公钥密码系统之一。它的安全性基础是数论和计算复杂性理论中的下述论 断：求两个大素数的乘积是计算上容易的，但要分解两个大素数的乘积求出它的 素因子是计算上困难的。有关r s a 体制的详细内容以及最新动态，可以从r s a 公 司的主页上p ：伽嗍 c h 嘴c 硼母_ c o m ，) 得到。模幂运算是r s a 公钥密码算法的关 键，也是最耗时的运算，因而引起了研究者的广泛注意。b o s 和c o s l 髓提出了有 效的加法链算法【2 】及其一系列的改进算法【3 一，b d c k c l l 等人提出的b o m w 算法1 5 】， f i n d l y 和j o h n s o n 于1 9 8 9 年提出的递归余数和算法嘲，d i m i t r o v 和c k l 州口】给出了 将指数表示成双基数形式的预处理方法，还有平方乘方法、m 进制法和滑动窗口 法i s 等，l o u 和c h a n g 驯给出了m 进制方法的改进方法，称为2 ”进制方法。目前在 用于硬件实现算法中，以m o n t g o m e r y 算法映射的方案速度较快。 椭圆曲线密码体制于1 9 8 5 年提出以来，由于它独特的优点f 如密钥长度小、 密钥单位比特安全强度高、计算速度快等) ，国际上许多国家、大公司甚至个人 都对它产生了浓厚的兴趣，并进行了大量研究。当前研究的热点主要有两方面： 一是随机曲线的选取问题，虽然现有的实现方案，都采用了非超奇异曲线或其他 特殊形式的曲线，如对于特征p 的椭圆曲线有s e a 算法【 】，对于特征2 的椭圆 曲线有s a t o h 类型的算法【l l ，1 2 l 等，但是要取得最佳的安全性必须采用随机曲线， 如何快速找到大量随机曲线仍是当前e c c 研究的热点；另一方面便是如何快速 实现e c c ，如对于定点p 的标量乘法的快速算法，对于随机点p 的标量乘法的 快速算法，以及基域的选择，域中元素的表示及运算的快速算法，坐标系的选择 等。尽管如此，国外还是有许多e c c 产品出现，如美国n e x tc o m d u t e r 公司己 开发出快速椭圆加密算法州，加拿大c e r t i c o m 公司开发了e c c 集成电路n 5 5 b “ 和1 2 0 0 0 个门器件) 等。在国内，虽有一些公司、学校及这方面的学者、专家作 了大量的研究，但是得到的e c c 的各类产品还是微乎其微。 1 3 本文的工作和论文的结构 我们在广泛参阅国内外相关公钥密码算法的文献和研究成果上，针对建立在 r s a 和椭圆曲线这两种密码体制上算法实现的困难性，对现有的一些常见的典 型算法进行分析、比较和综合，并在此基础上提出了自己的改进算法，改进后的 算法经分析都能有效地提高运算速度。论文中我们主要作了以下工作：第一，介 绍了r s a 和椭圆曲线两种公钥密码体制，并对两种公钥密码中现有的各种基本 算法作了综合分析；第二，对r s a 公钥密码体制中的模幂算法，我们采用变长 窗口技术的分割方法，不仅减少了非零窗口数目，而且减少了预计算量，同时选 取快速的模乘算法一m o n t g o m c r y 模乘算法，提出了改进的m n e x p 算法，从而有 利于r s a 密码算法的软硬件实现。第三，对有限域上椭圆曲线中点的标量乘法， 改进算法毛要从带符号的滑动窗口出发，综合利用不同坐标下异点加法和倍点运 算的快速性，设计出混合坐标下的改进算法，从而有利于椭圆曲线上点的数乘的 快速实现。 本文主要讨论了r s a 和椭圆曲线公钥密码体制及其上的密码算法，全文共 分四章。其中第一章简单介绍了本文的学术背景及理论与实际意义、国内外研究 现状，以及本文所做的工作及结构设计。第二章介绍了伴随公钥密码体制发展的 数学背景，包括数学在密码学史上的发展和密码体制中常常要涉及到的一些数论 知识和结论；第三章简单介绍了r s a 公钥密码体制及其具体应用，介绍了r s a 密码体制中已有的典型快速模幂运算方法，并给出了算法分析、比较，以及改进 的m o 嘲；0 m e r y 型模幂算法；第四章主要介绍了椭圆曲线公钥密码体制，给出了 计算椭圆曲线上标量乘法的各种方法，分析了不同坐标模式下的椭圆点加法公 式，由此提出了椭圆曲线密码算法在混合坐标下的改进算法。最后归纳得出一些 有用的结论。 第2 章数学背景 2 1 密码学中数学的发展史 保密通信具有悠久历史，在远古时期就有密写的碑文。中国十一世纪编纂的 武经总要一书中，详细记载了一个军用密码本。早期的密码学是门艺术， 人们常常是凭直觉和经验设计密码和破译，而不是用推理或证明。电报的发明和 无线电的诞生，引起通信技术的场革命。由于电子信息易被截取、伪造和篡改， 大大刺激了保密和破密的竞相发展，在这两方面同时开始使用更多的数学方法和 手段。第二次世界大战期间，美国聘请优秀数学家研究密码分析和破译，使用了 数论、群论和统计学知识，1 9 4 0 年就破译了日本的高级加密机“九七式欧文印字 机”( 美国人称为“紫密”) ，但日本人对此却长时间一无所知，创造了密码史上精彩 的一页。 二十世纪四十年代末，美国数学家商农( s h a l l l l o n ) 把信息论引入密码学，用 统计的观点对信源、密码源、接收密文进行数学描述和定量分析，将密码的编码 和破译都置于坚实的数学基础上，为私钥密码系统建立了数学理论基础，这时密 码学成为了一门科学( 仍保留其艺术的特点) 。但此时期密码学的研究工作进展不 大，公开的密码学文献也很少。 到六十年代微电子学和电子计算机的发展，使加密和破密都采用了快速的计 算手段和工具。特别是近年来数学计算机和数学型网络通信豹发展，保密通信不 仅用于传统的政治和军事领域，而且在经济、管理和备种公众事业中也显得日益 重要。由此还提出了许多新的课题，发展成更加广泛的信息安全领域，如计算机 数据保护、数学签名和身份认证、密钥管理与分配、电子仲裁等。传统密码要求 通信双方用的密钥应通过秘密信道私下约定，互联网上用户之多，如此庞大的密 钥如何管理? 它的定期更换也是十分复杂的工程。公钥密码的提出，不仅解决了 传统密码密钥分配的问题，而且还为签名和认证提供了手段，开创了公钥密码学 新纪元。 假设a 和b 是通信的双方，e 是窃听者，嘲络中的用户约定公钥密码体制， 每一用户有自己的公钥和私钥，并且在其他地方的数据库都是公开的，以下是a 使用公钥密码发送信息给b 的过程。 ( 1 ) a 从数据库中得到b 的公钥； a 用b 的公钥加密信息，然后传给b ； ( 3 ) b 用自己的私钥解密a 发送的信息。 在整个交换中一直在窃听的e ，虽有b 的公钥和用公钥加密的信息，但却恢复不 出b 的私钥或者是传送的信息。 公钥密码的原理就是基于单向陷门函数。单向函数是这样一个函数，计算起 来相对容易，但反过来，即求逆却很困难。单向蛹数不能用做加密，因为用这种 单向函数加密的信息毫无用处，无人能解开它。对加密，我们需要一种所谓的单 向陷门函数。单向陷门函数是有一个秘密陷门的一类特殊单向函数。它的一个方 向易于计算而反方向却难于计算，但是，如果你知道那个秘密陷门，就很容易反 方向计算这个函数。它设计得非常困难，以致于若没有秘密信息，使用最快的计 算机用几百万年的时间都不能解开加密信息。在随后的十年里，人们就围绕这个 关键，设计出了许多种单向函数，但是绝大多数都经不起考验。在设计出单向函 数之后不久，便有人找到求该单向函数逆运算的可实现算法。到目前为止，站得 住脚的只剩下两种方案。大数分解方案和离散对数方案，它们均来自于数论。近 年来人们采用代数数论与代数几何深刻的知识对数论中有限交换群研究了其上 的离散对数问题，取得了很好的应用效果。 在密码体制不断发展过程中，采用了愈来愈多的数论工具。数论成为了密码 学特别是公钥密码学的基本工具，本章下节较详细地介绍了论文中所要用到的一 些有用的数论事实。 2 2 相关数论知识 模运算： 定义l 给定一个整数开，如果用玎除两个整数口和6 所得的余数相同，则 称口和6 关于模疗同余，记为口；6 ( m o d 珂) 。 从o 到一1 的整数组成的集合构成了模丹的“完全剩余系”。这意味着，对每 一个整数口，它的模疗剩余是从o 到 1 这之间的某个整数。运算日m o d 埠表示d 被”除的剩余，称为模行运算。模算术同普通的算术一样，是可交换的、可结合 的和可分配的。而且，模运算的每一个中间结果，与先进行全部运算，再对最后 的结果模，其作用是一样的。 ( 口+ 6 ) m o d 甩= ( ( 口m o d 月) + ( 6 m o d ，1 ) ) m o d ” ( 口一6 ) m o d 斤= “口m o d 玎) 一( 6 m o d ，1 ) ) m o d 胛 口6 m o d = ( 口r n o d ，1 ) ( 6 i n o d ，崎m o d d ( 6 + c ) m o d h = ( ( 曲m o d 聍) + ( ( ￥c m o d 玎) ) m o d 胛 密码学中用了很多模月运算，因为像计算离散对数和模”平方根这样的问题 是困难的。模运算也很容易在计算机上实现，因为它将所有中间值和最后结果限 制在一个范围内。对一i 比特的模行，任何加、减或乘的中间结果都不会超过2 j | 比特长。因此我们可以用模算术做指数运算而又不会产生巨大的中间结果。 一些有用的结论： p 是素数，如果p 的因子只有l ，p 毛一模h 的同余类集合，即乙= o ，1 ， 一1 z 毛的乘法群：与n 互素的模n 的同余类，表示成z = 口乙l ( 口，九) = l “疗) 一万的欧拉函数：小于甩且与”互素的正整数的个数 欧拉( e u l e r ) 定理：如果掰和 互素，则口烈”，1 f m o d ”1 硕士学位论文 费尔玛( f e 肌a t ) 定理：p 是素数，口是正整数且满足g c d ( a ，p ) = l ，则有 窿”1z l ( m o d p ) ， 若 被分解成：n = p i 。岛。崩彬，则有妒( ”) = 兀( 钟一所。) ，特别当 g c d ( 历，1 ) = l ，有尹( 卅 ) = 尹( 研) 伊( 圩) ”1 若珂1 ，g c d ( d ，圩) = 1 ，则存在c 使得z 1 ( m o d h ) ，我们把c 称为是a 的模刀 的逆，记作口。( m o d ，1 ) 或a 有限域只中点p 的阶一阶数一是满足拄p = o 的最小整数。 ：兰：兰詈兰兰耋翌兰鎏曹2 ：一一 第3 章r s a 公钥密码体制 r s a 公钥密码体制之所以具有安全性，是基于数论中的一个事实：将两个 大的素数合成一个大数很容易，而相反过程则非常困难。由此可见，r s a 公钥 密码体制的安全性依赖于作为公钥的大整数 的位数长度。r s a 公钥密码体制是 1 9 7 7 年马萨诸塞理工学院里夫斯特很l r i v e s t ) 、沙米尔( a s h m i r l 、艾德勒曼 ( l a d l c m a n ) 三位教授研究出的一种基于素因子分解的困难性而设计的一种公钥 密码算法i l ”。他们的研究成果在1 9 7 7 年的4 月以“数字签名和公开密钥密码体制” 为题公开发表，并受到高度评价。现在国际标准组织，如i s o 、i t u 以及s w i f t 等均已接受r s a 公钥体制为标准，因此，r s a 可以被认为是现在民间和商业上 使用最为广泛的公开密钥密码体制和数字签名体制。 3 1 r s a 公钥密码体制 r s a 的基础是数论的欧拉定理，r s a 密码体制利用。中的计算，其中”是 嚼个不同奇素数p 和g 的乘积。对于这样一个整数月，注意到妒0 ) = ( p 一1 ) ( g 一1 ) 这个密码体制【1 5 的正式描述如下表3 1 所示。 表31r s 密码体制 设 = 朋r 其中p 和口都为素数。设a = f 吃：a 表示所有可能的明文组 成的有限集，f 表示所有可能的密文组成的有限集，且定义 世= ( n ，孽，e ，d ) ； = 朋，p d 兰lm o d 伊( n ) 对每一个足= ( ，n 吼p ，d ) ，定义加密和解密运算分别为 c = 埘。n l o d ”，卅= 一m o d h 其中k 代表密钥空间，是由所有可能的密钥组成的有限集。c ，m 互，是一 对明密文，p 为小于妒( n ) 且与它瓦素的正整数，n 和p 定义为公钥，p ，g 和d 都是秘钥( 私钥) 。 利用r s a 密码算法加密信息m ( 要求h 与m 互素，如果不互索，这是小概 率事件，忽略不计) ，首先将它分成小于月( 对二进制数据，选取小于n 的2 的最 大方幂) 的数据块 也就是说，如果p 和q 都为十进制1 0 0 位的素数，则n 刚好在 2 0 0 位以内，因此每个数据块，”，的长度也应在2 0 0 位以内。加密信息f 由类似划 分的同样长度的数据块组成。加密公式为 q = 硝m o d ” 要解密信息，取每个加密块f 并计算 m = c ? m o d h 由p d s l m o d 妒( n ) ，有耐= 1 由p d 善l m o d 妒( n ) ，有耐= 1 r p ( ”) ，其中，也为整数，因此 r p ( ”) ，其中，也为整数，因此 硕士学位论文 c ? 三f 聊； “耋肼j 一坤扣) 兰朋1 m p 叫l誊m ，m o d n = m i 这里利用了e u l e r 定理，由上述公式从密文中恢复出了明文，从而也证明了r s a 公钥密码的加密和解密算法的正确性。 r s a 密码体制的一个具体应用是，例如，有几家银行需要互相发送财政数 据，如果上千家银行，那么在每两家银行之间都有一个密钥来秘密通信是不可行 的。但可以用下述的这种方法，每一家银行事先选取两个整数玎和p ，然后将它 们出版在一本公开的书中。假设银行a 想传送数据或信息给银行b ，那么a 查 寻b 的月和p ，并用它们来传送信息。实际上，r s a 算法在传送大量数据或信息 时，并非足够快，因此r s a 算法经常被用来传送快速加密算法所用的密钥。 r s a 密码体制有很多方面可以讨论，包括实现细节、素性检测、加密和解 密的效率，以及安全问题。r s a 的加密和解密算法都是大数的模指数运算，在 实际应用中，这了安全，模数的长度一般大于等于1 0 2 4 比特。由于大数模幂运 算要用到大量的乘法和除法，面乘法和除法是十分耗时的运算，因此，r s a 运 算的强度很在大，速度很慢。为了加速r s a 算法，通常需要采用各种快速计算 算法。日前的主要软件加速算法包括求最大公约数、求模逆元、模幂运算【1 6 l ( 有 二元法、6 进制法、建表法等等) 、模乘运算【1 7 l ( 大数乘法算法、平方算法、f f t - b 豁e d 乘法算法、求余数算法、b l a l 【l e y 方法以及著名的m o 血g o 腓；r y 方法等) 和中国剩 余定理1 1 s j 等。特别地，计算大数的模指数运算的快速算法中以m o n t g o m e r y 算法 最突出。如何提出并实现一个有效的大整数模幂运算算法成为r s a 公钥密码算 法研究的热点，对r s a 公钥密码体制的实际应用具有重要的理论意义和实用价 值。 3 2 现有模幂算法综述 r s a 是一种国际公认的理想公钥密码体制。它表达方式简单、保密性强、 没有密钥管理的麻烦，并且具有数字签名、认证和鉴别等功能，特别适合于现代 保密通信的需要。但是大数模幂运算会使其计算速度非常缓慢，难以实际应用， 目前国际上流行的其他几种公钥密码体制的关键也都是大数模幂计算，因此，研 究快速的模幂算法具有十分重要的意义。本文先对有代表性的模幂运算的加速算 法进行简要的介绍，如基于软件加速的b r 算法【l “坤】( 反复平方和模乘法) 、6 进 制法( 求幂的固定窗口算法) 【1 9 1 、滑动窗口模幂算法【8 一卅和适于硬件实现的 m o m g o m e r y 型模幂算法等，通过分析和比较其上的算法速度，综合算法优势， 提出有效的改进算法。以下都是对正整数g 和p ，求m o d m 的模幂算法。 3 2 1 b r 算法( 反复平方和模乘法) 大多数的r s a 算法都是建立在反复平方和模乘算法【1 印的基础上，它是公钥 密码体制中的基本算法。先将指数p 表示二进制形式，即化为： p = ( 巳十，q ，p o ) 2 ，p ， o ，1 ， 则计算g m o d 聊即是计算( “( ( ( g 。- ) 2 ) ，旷) 2 ) 。g ) ，其中( ) 。表示括号中 的值取模。 从左到右的b r 算法： 输入：正整数聊，整数g ( g 肌) 及正整数p = ( 巳+ ，e 1 ，) ： 输出：譬m o d 删。 ( 1 ) s 卜1 ： ( 2 ) 对f 从一1 依次到o ，执行： 1 ) s 卜jsmod ，押： 2 ) 如果q = 1 ，则s 卜曙m o d 埘。 ( 3 ) 返回j 。 算法从p 的高位计算起，先平方模剩余再求模乘剩余，遇到为1 的位就用底 数去乘上一步的迭代结果；遇到为o 的位就直接对上一步的迭代结果求平方剩 余，其模乘次数一般需要拧+ _ l l ( p ) 一2 。在这里 是e 的二进制位数ll o g ；f + 1 ， ( e ) 是p 的二进制表示中1 的个数( 也就是p 的汉明重量) ，以上算法要做( 一1 ) 次平方和 ( p ) 一1 次模乘运算。如果p 是在区间上o p 脚随机选取的，p 中每一位出现o ，1 的概率相同，则约有2 位为1 ，故平均需要1 5 ”一2 次模乘。 从右到左的b r 算法： 输入：正整数m 、g ( g 肌) 及正整数p = ( i ，一，p i ，) 2 输出：g m o d 脚。 ( 1 ) j + _ 1 ： ( 2 ) 对i 从o 依次到月一1 ，执行： 1 ) 如果e = 1 ，则s + - 路m o d m ； g 卜g g m o d 聊。 ( 3 ) 返回j 。 以上两个算法执行同样次数的平方和乘法运算。但前者总是用固定的g 值做 乘法；后者第二步的平方与模乘运算是两个独立的过程，从硬件方面来说，它们 可被分开同时进行处理，这样可通过增大面积减少算法运行的时钟周期，从而提 高算法的运算速度。 3 2 2 6 进制法( 求幂的固定窗口算法) 6 进制法是二进制的一个推广，每次迭代执行超过l 位的幂次。因为b r 算 法中将指数p 二进制化以后，p 的比特序列长度变得很长( 往往大于1 0 2 4 位) ， 这样需进行多次迭代，不能提高计算效率。为了减少迭代次数，可以用缩短指数 比特位的方法来实现，将指数6 进制化，其中6 = 2 ，l o u 和c h a l l g 提出了6 进 制的模幂算法。其实质是将指数e 的二进制表示( e 。，p ；，) ：分成f 块，每块的 长度为t ，需要幻= ，如果t 不能整除n ，则至多填充t 一1 个0 ，这样指数e 被 1 0 i 1 分解成女位长的字e = ( 气+ ，。- 2 - p f ) = + ，2 ，f = o ，1 ，2 ，卜1 。此时求 ，= o 2 。m o d 卅的运算可通过下面的算法。 输入：正整数研，g ( 0 g 埘) 和8 输出：g 。m o d 聊。 ( 1 ) 预计算并存储g ”m o d m ，w = 2 ，3 ，4 ，2 1 1 ； ( 2 ) s _ g 岛一1 m o d 朋； ( 3 ) 对f _ 卜2 到0 ，执行： 1 ) s + - s 2 “”m o d 聊： 2 ) 如果e o ，那么j 卜踞5m o d m ； ( 4 ) 返回n 。 由o 互6 1 ，e = 置2 ，6 进制算法首先需要预计算g ”m o d m ，其中w 遍 历2 ，3 ，4 ，2 一l ，以备茬计算模幂时取用。m o d 聊在第( 1 ) 步预计算中需2 一2 次模乘运算，第( 3 ) 步中第一小步需七“一1 1 次( 即n 一 次) 模平方运算，由于 在2 中有2 一1 个e 的值是非零的，所以( 3 ) 中第二小步平均需o 一1 ) ( 1 2 4 ) 次 模乘运算，则平均所需模乘运算次数记为一2 + h 一女+ 0 一1 ) ( 1 2 一) 嘲。当 t = 1 时，可得到b r 算法( 反复平方和模乘法) 的平均运算次数。在不考虑e 的 值为o 的情况下，由极值理论得到七的最佳选取与e 的二迸制序列长度”必须满 足的关系式：n = 2 后2 l n 2 。在实际应用中，h 取值约为5 0 5 0 0 0 问，只须讨论当 t = 3 ，4 ，5 ，6 ，7 时的情形。由此得出七的取值范围【2 0 】应满足： 尼攀学，丛等丝) 且七 3 ，4 ，5 ，6 ，7 时，总的乘法运算次数能取到最小值。 3 2 3 滑动窗口模幂法 滑动窗i j 模幂法与6 进制法相比，6 进制方法就是窗口宽度为的一种固 定窗口计算方法，由于它的固定性限制，在某些方面不如滑动窗口算法处理来得 灵活。滑动窗口算法的灵活性。主要在于窗口分割的设计。在给出算法前，先了 解窗口分割的方法。定义七为窗口的宽度，r 是要分割的二进制序列，s 是一个 空序列一一进制序列中窗口的分割原则1 2 i j 如下： ( 1 ) 如果7 的长度大于或等于 ，执行： 1 ) 取为r 的最左边的位序列； 2 ) 取r 为，中除去后剩下的序列； 3 ) 取渺为中除去右边的o 后剩下的序列； 4 ) 取再为r 中除去左边的o 后剩下的序列： 5 ) s 卜旷，r 七- 盖： r s a 和椭圆曲线密码算法的研究 ( 2 ) 把丁的末尾不足 位的序列除去左边的o 后存到s 中； ( 3 ) 返回s 。 这样分割后窗口的宽度并不固定为长度，它不同于固定长度的非零窗口法 ( c l n w ) ，文献【8 】中把它定义为可变长度的非零窗口法( v l n w ) ，即上述分割 原则把指数e 分解成零窗口和非零窗口e ，窗口长度用三( e ) 表示，其中 f ：o 1 ，f 一1 ，实际窗口数r 不一定等于行，在这里七表示最长的窗口长度( 即 m a x ( 工( f ) ) ，其中f 遍历o ，l ，一1 ) 。例如：取七= 3 ，指数g = 3 7 4 5 = ( “1 0 1 0 1 0 0 0 0 1 ) 的二进制序列r 按固定长度的非零窗口算法( c u 4 w ) 有： e = l 卫0 丛0 0 业 这种固定长度的c l n w 方法的缺点在于增大了对非零窗口的计算量，可变长度 的非零窗口算法( v l ，n w ) 就避免了上述问题，那么利用上面分割原则分段后得 到的指数表示如下： p = l u o l 业0 0 0 0 l 同时根据窗口设计得到下面的模幂算法【1 9 1 。 输入：正整数m ，甙o g 如果e o ，那么5 卜蹭5 m o d 拼： ( 4 ) 返回s 。 算法中为计算g 。m o d 聊，需要预先计算m o d m ，其中f 遍历3 ，5 ，7 ，2 一l ， 以备在计算模幂时取用，其中需一次平方运算，2 “1 3 次模乘运算。第三步的 二小步的平均模乘次数主要跟分段后序列中非零窗口的个数相关，而v 1 n w 中 滑动窗口技术的平均非零窗口数为”( 女+ 2 ) 【2 2 1 ，这样使窗口宽度七的选取在算法 中显得更加重要。在指数p 的二进制长度确定时，可求得一个最佳的窗口宽度t ， 使总的模乘运算次数2 “一l + ”一t + 疗舢+ 2 ) 达到最少【2 3 】。 以上三种模幂算法都是基于软件加速算法，我们给出在不同位数的指数下算 法平均所需模乘次数，通过数据比较，可以知道v l n w 滑动窗口法所需计算量 是最少的，由此说明了v l n w 滑动窗口法在公钥密码中的可取性。 表3 2 各种不同模幂算法所需模乘运算次数 算法平均模乘次数 n b r 算法 7 6 6 l5 3 45 1 2 1 0 2 4 6 进制法( 后= 5 ) 6 3 6 1 2 4 75 1 2 1 0 2 4 c l n w 滑动窗口法 6 0 7 ( 七= 5 ) 1 1 9 5 ( 七z 6 ) 5 1 2 1 0 2 4 v l n w 滑动窗口法 5 9 5 ( 七= 5 ) 1 1 7 5 ( 七= 6 ) 5 1 2 1 0 2 4 3 3 m o n t g o m e u 型模幂算法 r s a 公钥密码体制中的加密和解密算法都用到大数的模指数运算，在实际应 用中，为了安全，模数的长度一般大于等于1 0 2 4 比特。这样大的数据量用软件处 理时速度很慢，而硬件实现无论从速度还是安全性的角度来考虑都比软件有优 势。因此，用硬件实现来达到比较高的速度是r s a 应用研究的一个目标。现有的 r s a 硬件实现算法的研究主要集中在基于m o n 蟾o m e r