（计算机软件与理论专业论文）rsa公钥密码体制.pdf

山东大学硕士学位论文 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外。本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：盗! ：茔 日期：竺! ：! ：， 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：谜i 生堑导师签名：鸯叁生日 山东太学硕士学位论文 摘要 r s a 公钥密码体制 研究生：张小萍 指导老师：周大水教授 r s a 公钥密码体制是1 9 7 7 年由r i v e s t 、s h a m i r 和a d l e m a n 三人提 出的，这是公开密钥密码体制中最优秀的加密算法。r s a 算法是建立 在大数分解和素数检测的理论基础上的，两个大素数相乘在计算机上 是容易实现的，但将该乘积分解的计算量却相当大，大到甚至不能实现。 r s a 公钥密码体制的优点是其原理简单，其加密和认证都使用公开密 钥，用户在开始通信前不需要事先约定一个秘密密钥。r s a 的安全性 依赖于大数的因子分解，但并没有从理论上证明破译r s a 的难度与大 数分解难度等价，即r s a 的重大缺陷是无法从理论上把握它的保密性 能如何，而且密码学界多数人士倾向于因子分解不是n p c 问题。现在已 经有结i 仓：r s a ( p + q ，e ) 的安全性跟p , q ，e 的选取有很大的关系。密钥越 长，安全性越高，在今天，商业加密推荐使用1 0 2 4 b i t 的密钥，2 0 4 8 b i t 将提供更高的安全性，实际上当前7 6 9 b i t 被认为是不易分解的。 d s p 芯片，又称数字信号处理器是近年来新起的一种专用于数字信 号处理的芯片。加密算法如果单纯用软件实现，升级比较容易，但安 全性和速度都与经过特殊设计的硬件无法相比。因此采用d s p 芯片制 作p c 安全卡，即利用专用的汇编语言实现算法并装载到卡上，再在专 用芯片上运行，不失为一种性能高且成本低的解决方案。t i 公司新推 出的t m s 3 2 0 c 5 4 x 系列具有性能适中，价格低廉，产品成熟等特点，并 且其乘法指令执行快，并行性高，比较适合加密运算使用，因此采用 t m s 3 2 0 c 5 4 xd s p 作为加密卡的主c p u 。要设计一个适合5 4 x 系列的r s a 算法，便其速度高，就要关注5 q x 系列指令系统的特点。本文介绍一 种在5 4 x 系列中的r s a 模幂算法，是在尝试了许多种算法后认为是最 好的。 山东人学碗上学位论文 本文的主要内容如下： 1 ) 介绍关于r s a 的一些基本数学和公钥密码体制知识。 这一部分将介绍论文中使用的数学符号极其意义。由于r s a 是公 钥密码体制当中的一种，而且是在“公钥密码体制”的概念提出之后 出现的第一个经受各种攻击尝试被证明是安全的密码体制，因此这一 章先开始介绍公钥密码体制，讨论关于公钥密码体制的安全性。 2 ) 对r s a 密码体制的详细描述。 这章主要描述r s a 密码体制实现的详细过程，同时为了表明r s a 密码体制是安全的，这里列出了几种攻击方法，其中时间攻击法是通 过测试加密的时间来猜测加密的私钥，但这种方法并不能从根本上攻 破r s a ，通过这几种攻击方法，这一章同时也列出了在实现r s a 过程 中要注意的一些问题。在参考文献 7 中提出了一种破译r s a 的能力 的零知识证明s c h n e i e r 方案，该方案在零知识证明破译r s a 的能力时， 证明过程有些问题，并且它也不能确认是谁破译了r s a 。这一章还介 绍了一种方案针对上述问题对s c h n e i e r 方案进行了一些改动；它不但给 出了种破译r s a 的能力的零知识证明，并且通过数字签名让验证 者确认是谁破译了r s a 。 3 ) 对模幂运算和解密些快速实现。 在公钥密码体制中，不仅是r s a ，还有e l g a m a l 体制，椭圆曲 线体制都要用到模幂运算，模幂运算更是r s a 的核心，因此在实现 r s a 的过程当中，要实现快速实现加解密首先就是要使模幂运算得到 快速实现。这一章主要介绍了3 种快速实现模幂运算的算法，这三种 算法各有优缺点，要根据编程环境选择。另外，该章还介绍了一种使 用中国剩余定l 里( c r t ) 来加快解密运算的方法。 4 ) r s a 数字签名系统。 随着r s a 在数字签名当中的应用，数字签名在实际应用中面i 临各种 不同的情况第四章在给出用r s a 用于数字签名的一种最简单的形式 外，还给出一种适用于有序签名方案，其中有序签名是指组成员的按 序签名。组内由i 2 个用户组成，任何组签名由n 个成员互相生成，组签名 2 山东大学坝j 一学位论文 的大小等于单个签名的大小，组成员对信息的签名不存在盲签名，外界 用户可以认证组签名，签名认证过程简单，只需要一个组对外的公开密 钥，组对签名消息负责。方案中组的公开密钥由所有成员的密钥决定， 组内不需要设立收集者，通信耗费少。 5 ) r s a 在d s p 加密卡中的实现 r s a 是当前最广泛应用的公钥密码体制，在p k i 协议，s e t 协议中都 是一个不可缺少的重要部分。第五章中介绍了一种r s a 的应用，r s a 在t m s 3 2 0 c 5 4 x 系列d s p 当中的实现。笔者在实现r s a 算法的过程中尝 试了许多种算法，这一种是所有在d s p 中实现最快的，尽管也遇到了 一些问题，例如d s p 中的模乘累加指令m a c 并不支持无符号数的操作， 但是经过一些变换，我们实现了用m a c 指令的无符号的操作，该算法 在d s p 中实现时基本上达到了加密卡要求的速度。 论文关键词：r s a ，公钥密码体制，模幂运算，d s p 山东大学碰! 士学位论文 r s ap u b l i ck e yc r y p t o g r a p h y g r a d u a t es t u d e n t ：z h a n gx i a o p i n g t u t o r ：p r o f z h o ud a s h u i a b s t r a c t r s ap u bl ick e yc r y p t o g r a p h yw a sc r e a t e db yr i v e s t ，s h a m i ra n d a d l e m a ni n1 9 7 7 ，i ti st h eb e s ti np u b l i ck e yc r y p t o g r a p h ys y s t e m r s aa r i t h m e t i cb a s eo n t h e o r y o f p r i m e t e s t a n d i n t e g e r f a e t o r i z a t i o n l o g a r i t h mp r o b l e m ，i t i s e a s y i n c o m p u t e r t o m u l t i p l yo n ep r i m ea n da n o t h e r ，b u ti ti sd i f f i c u l tt of a c t o r i z e t h ep r o d u c t ，t h et i m eo fc o m p u t i n gi st o ol o n gt or e a l i z e t h e s t r o n gp o i n to fr s ap u b l i ck e yc r y p t o g r a p h yi st h a ti t st h e o r y i sv e r ye a s yt ou n d e r s t a n d ，u s e rd o n tn e e dt a l ka b o u tap r i v a t e k e y b e f o r e c o m m u n i c a t i o n ， b e c a u s et h e c r y p t o g r a p h y a n d a u t h e n t i c a t i o no fr s a o n l yu s ep u b l i ck e y t h es e c u r i t yo fr s a p u b l i cc r y p t o g r a p h y b a s eo na b i gi n t e g e r f a c t o r i z a t i o n o g a r i t h mp r o b l e m ，b u ti tc a n tp r o v ei nt h et h e o r yt h a tt h e d i f f i c u l t yt os e t t l er s ap u b l i cp r o b l e ma n dt of a c t o r i z eab i g i n t e g e ri se q u i v a l e n t ，t h a ti st os a yt h a tas h o r t c o m i n go fr s a p u b l i cc r y p t o g a p h y i e si nt h a tw ec a n tk n o wjt ss e e u r i t yi n t h e o r y i t i s m a j o ro fc r y p t o g r a p h i s t sc o n s i d e rt h a ti n t e g e r f a c t o r i z a t i o np r o b l e mi s n tn p cp r o b l e m n o ww ec a n g e t t h e c o n c l u s i o n：t h e s e c u r i t y o fr s a ( p * q ，e ) h a s c o n s a n g u i n e o u s r e l a t i o nw i t ht h es e l e c t i o no fp ，q ，e t h e k e yi sm o r el o n g ，t h e s e c u r i t yi sb e t t e r 。i nn o wd a y s ，t h ec r y p t o g r a p h yf o rc o m m e r c e c o m m e n d su s i n g1 0 2 4 一b i tk e y ，b u tt h e2 0 4 8 一b i tk e yo f f e r sh i g h e r s e c u r i t y ，i nf a c t t h e7 6 8 一b i tk e yi sd jf f i c u l tt of a c t o r iz ein t h ed a y s d s pc h i p ，w h i c hi sa l s on a m e d d i g i ts i g n a lp r o c e s s o r ，i s 4 山东大学硕士学位论文 j _ _ _ - _ _ _ _ _ _ _ - _ _ _ _ l - _ _ _ _ _ _ - _ _ l - l ii i _ l - - _ _ _ _ - i _ _ - - _ _ _ - s p e c i a l l ya n du n i v e r s i l yu s e d f o rd i g i ts i g n a lp r o c e s s i n gi n r e c e n ty e a r s i ft h ec i p h e r i n ga r i t h m e t i cisa p p l i e db ys o f t w a r e ， t h e ni ti se a s yt ou p g r a d e ，b u ti t ss e c u r i t ya n dr a p i d i t yc a n t e x c e e dt h eo n et h a ti sa p p l l e db yh a r d w a r ew h i c his s p e c i a l ly d e s i g n e d s oi ti sah i g hc a p a b i l i t ya n dl o wc o s ts o l u t i o nt h a t w eu s ed s p c h i p t om a k ep c s e c u r i t y c a r dw h i c h i m p l e m e n t a r i t h m e t i cu s e ds p e c i a la s s e m b l el a n g u a g ea n dl o a dt oc a r d ，t h e n r u ni nt h ep a r t i c u l a rc h i p t h et m s 3 2 0 c 5 4 xs e r i e sw h i c hw a sn e w c r e a t e db yt 1c o m p a n yh a st h ec h a r a c t e r so fg o o df u n c t i o na n d 1 0 wc o s t ，m a t u r ep r o d u c t s ，p l u s ，t h er a p i dm u l t i p l i c a t i o n i n s t r u c t i o nc a nb e h i g hj u x t a p o s e dw h i c h i ss u i tt o c i p h e r a p p l i c a t i o n ，s o w ec h o o s et m s 3 2 0 c 5 4 x d s pa sm a i n c p uo f c r y p t o g r a p h yc a r d i fw ew a n t t od e s i g nar a p i dr s aa r i t h m e t i c f i t t i n gw i t h5 4 xs e r i e s ，w em u s tp a ya t t e n t jo nt ot h ec h a r a c t e r s o fi n s t r u c t i o n s y s t e m t h i sp a p e r i n t r o d u c ear s am o d u l a r e x p o n e n t i a t i o na r i t h m e t i c ，i ti s t h eb e s ti na 1 1t h a tit e s t h e r ea r et h em a i nc o n t e n t so ft h ep a p e r ： 1 ) i n t r o d u c et h eb a s i cm a t hk n o w l e d g eo fr s aa n dk n o w l e d g eo f p u b l i ck e yc r y p t o g r a p h y t h i sc a p t u r ew i l li n t r o d u c et h em a t hs y m b o lu s e di nt h ep a p e r ， a n di t sm e a n i n g a sr s ai so n eo fp u b l i ck e yc r y p t o g r a p h y ，a n d i tw a st h ef i r s to n ew h i c hw a sp r o v e ds e c u r i t y b e i n gs e r i e s a t t a c kt e s t sa f t e r “p u b l i ck e yc r y p t o g r a p h y ”c o n c e p t i o n b r o u g h to u t ，s ot h i ss e c t i o nw ew i l if i r s ti n t r o d u c ep u b l i ck e y c r y p t o g r a p h y ，a n d t a l ka b o u tt h e s e c u r i t y o f p u b l i ck e y c r y p t o g r a p h y 2 ) d e s c r ih et h er s ap u b li ck e yc r y p t o g r a p h y t h iss e c t i o nw i i ld e s c r i b pt h ep a r t jc e l a r p r o c e s so fr s a p u h l i ck e yc r y p t o g r a p h y ，i no r d e rt os h o wt h es e c u r i t yo fr s a 5 山东入学坝士学位沦义 p u b l i ck e yc r y p t o g r a p h y ，h e r ew e1 i s ts e v e r a la t t a c k i n g m e t h o d s a tt h es a m et m ew ea l s ol i s ts o m ep o i n t sw es h o u l dp a ya t t e n t i o n t o s c h n e i e r p u t s f o r w a r da z e r o k n o w e d g ep r o o f w h c hc a n d e c o d er s a b u th e r ei ss o m e t h i n gw r o n gw i t ht h ep r o v i n gp r o c e s s w h e nt h ez e r o k n o w l e d g ep r o v e st h ec a p a b i 】i t yo fd e c o d i n gr s a m e a n w h i l ei tc a nn o tm a k ec l e a rw h od e c o d e sr s a t h i ss o u t i o n m a k e ss o m ec h a n g e st ot h es c h n e r i e rs o l u t i o na c c o r d n gt ot h e a b o v e _ m e n t i o n e dp r o b l e m s ，n o to n l yo f f e r sz e r o k n o w l e d g ep r o o f w h i c hc a nd e c o d er s a ，b u ta l s os h o w st h ev a l i d a t e rw h od e c o d e s r s at h r o u g hd i g t a l s i g n a t u r e 3 ) h i g h s p e e di m p l e m e n t a t i o na b o u tm o d u l a re x p o n e n t a t i o na n d d e c i p h e r n o to n l yr s a ，b u ta l s oe l g a m a la n de 1 i p t i cc u r v ep u b i ck e y c r y p t o g r a p h y i nt h e p u b l i ck e yc r y p t o g r a p h y u s em o d u l a r e x p o n e n t i a t i o na r i t h m e t i c ，f u r t h e r m o r em o d u l a re x p o n e n t i a t i o n i st h ec o r eo fr s a ，s oi nt h e i m p l e m e n t i n gp r o c e s so fr s a ，i n o r d e rt oa c c e l e r a t et h er s ac i p h e r i n ga n dd e c i p h e r i n gp r o c e s s w em u s ta tf i r s ta c c e l e r a t et h em o d u l a re x p o n e n t i a t i o np r o c e s s t h is c h a p t e rm a i n l yi n t r o d u c e s3s o r t so fh i g h s p e e dm o d u l a r e x p o n e n t i a t i o na r i t h m e t i c ，t h e s ea r i t h m e t i ch a v et h e i ro w n s h o r t c o m i n g sa n dv i r t u e s ，w es h o u l dc h o o s et h eb e s to n ei nt h e t h r e eo n e s a c c o r d i n g t o p r o g r a m m i n g e n v i r o n m e n t w ea l s o i n t r o d u c eaf a s td e c i p h e r i n ga r i t h m e t i cu s e dc h i n e s er e m a i n d e r t h e o r e m ( c r t ) 4 ) d i g i t a ls i g n a t u r es y s t e mo fr s a w i t ht h er s a a p p l i e d i nt h e d i g i t a ls i g n a l ，u r e ，d i g i t a l s g n a l ，u r e l f a c e sa l1s o r t so fp r a t i c a l i n s t a n c ( s t h ef o u r t h c a p t u r en o to n yb r i n go u tas i m p l e s tr s ad i g t a sjg n a t u r eb u t a ls o g i v eo u tas c h e m ew h i c hi sf i tt oo r d i n a ls i g n a t u r ea n d 6 山东大学硕：匕学位论义 b r o a d c a s t i n gs i g n a t u r e ，o r d i n a ls i g n a t u r em e a n s t h em e m b e ro f at e a ms i g n a t u r ei nt h eo r d e ro n et oo n e ，t h eg r o u pi sm a d eu p o fnm e m b e r s ，e v e r ys i g n a t u r ei sm a d eb ynm e m b e r s ，i te q u a l s t os i n g es i g n a t u r e t h e r ei sn ob l i n d i n g s i g n a t u r eh e r e ，a n y o n e o u t s i d eg r o u pc a nc e r t i f i c a t et h es i g n a t u r e t h ep u b l i ck e yw a s d e o i d e db yt h ek e y so fa 1 1m e m b e r s ，a n dt h es c h e m ed o n tn e e d c o l l e c t o r ，a n di t sc o m m u n i c a t i o nc o s t sv e r yf e w 5 ) r s ai m p e m e n t a t io ni nt h ed s pc r p t o g r a p h i n gc a r d r s ai st h em o s tu n i v e r s e a p p l i c a t i o n i nt h e p u b l i ck e y c r y p t o g r a p h y ，a n di ti sai n d i s p e n s a b l es e c t i o no fp k ip r o t o c o l a n ds e tp r o t o c 0 1 t h ef i f t hc a p t u r ew i l li n t r o d u c eaa p p l i c a t i o n o fr s aw h i c hd e s c r i b er s ai m p l e m e n t a t i o ni nt h et m s 3 2 0 c 5 4 x s e r i e sd s p it r ys e v e r a la r i t h m e t i ci nt h er s ai m p l e m e n t a t i o n ， a n dt h i so n ei st h ef a s t e s ti nt h ed s p a l t h o u g ht h ea r i t h m e t i c i m p l e m e n t i n gf a c e ss o m ed i f f i c u l t yi nt h ed s p ，f o re x a m p l e ，t h e m o d u l a rm u l t i p l i c a t i o ni n s t r u c t i o nm a cc a n ts u i tf o ru n s i g n i n t e g e r ，b u tb ys o m ec h a n g e ，w ec a nu s et h ei n s t r u c t i o nm a ci n t h eu n s i g ni n t e g e r ，t h i sa r i t h m e t i ca r r i v et ot h es p e e dr e q u e s t o ft h ee n c r p y t i o nc a r d k e yw o r d s ： r s a ，p u b l i c _ k e yc r y p t o g r a p h y ，m o d u l a r e x p o n e n t i a t i o na r i t h m e t i c ，d s p 7 山东大学坝l j 学位论文 绪论 近年来，随着计算机及网络在全社会的逐步推广应用，尤其是国 际互联网i n t e m e t 在中国的引入，使得社会的信息化进程进一步加快， 给人们带来了巨大的经济效益和社会效益。如利用数据通信网进行数 据传输的( 电子数据交换) 系统，一改过去那种缓慢的手工作业方式， 使各种业务数据都通过计算机网络在各相关部门迅速地传输，节约了 时间、纸张，减少了库存，提高了买方、卖方、海关、银行等组织部 门的工作效率，带来了极大的利益。但同时也应看到：随着这种金融 电子化和无纸贸易的兴起，人们的许多非常机密的数据都需要在网络 上传输，从而使得数据在网络中传输的安全性也日益突出地显现出来， 现在赖以传输数据的计算机网络系统是一个不安全的数据传输系统， 它们可以被以下方式入侵： 1 ) 搭线窃听采用硬线搭接方法来截取在某些通信线路上以明码形 式传输着的数据。 2 ) 电磁窃听通过接收空中的无线电传输的电磁信号而窃取数据。 3 ) 联机入侵利用现有数据传输网络系统的安全方面的缺陷，通过 网络冒充合法的用户非法闯入对方的计算机系统，窃取有用信息或破 坏其系统。 病毒、黑客的猖獗使身处今日网络社会的人们感觉到谈网色变， 无所适从。但我们必需清楚地认识到，这一切一切的安全问题我们不 可一下全部找到解决方案，况且有的是根本无法找到彻底的解决方案， 如病毒程序，因为任何反病毒程序都只能在新病毒发现之后才能开发 出来，目前还没有哪能一家反病毒软件开发商敢承诺他们的软件能查 杀所有已知的和未知的病毒，所以我们不能有等网络安全了再上网的 念头因为或许网络不能有这么一日，就象“矛”与“盾”，网络与病毒、 黑客永远是一对共存体。 现代的电脑加密技术就是适应了网络安全的需要而应运产生的， 山东大学碗士学位论文 它为我们进行一般的电子商务活动提供了安全保障，如在网络中进行 文件传输、电子邮件往来和进行合同文本的签署等。数据加密的基本 过程就是对原来为明文的文件或数据按某种算法进行处理，使其成为 不可读的一段代码，通常称为“密文”，使其只能在输入相应的密钥之 后才能显示出本来内容，通过这样的途径来达到保护数据不被非法人 窃取、阅读的目的。该过程的逆过程为解密，即将该编码信息转化为 其原来数据的过程。 当今网络社会选择加密已是我们别无选择，其一是我们知道在互 联网上进行文件传输、电子邮件商务往来存在许多不安全因素，特别 是对于一些大公司和一些机密文件在网络上传输。而且这种不安全性 是互联网存在基础t c p i p 协议所i 重有的，包括一些基于t c p i p 的服务；另一方面，互联网给众多的商家带来了无限的商机，互联网 把全世界连在了一起，走向互联网就意味着走向了世界，这对于无数 商家无疑是梦寐以求的好事，特别是对于中小企业。为了解决这一对 矛盾、为了能在安全的基础上大开这通向世界之门，我们只好选择了 数据加密和基于加密技术的数字签名，r s a 就是加密技术中优秀的一 种。 山东人学颧 。学位论史 第一章r s a 的基本数学知识 1 1 基本的数论知识 在描述r s a 如何工作之前，我们先介绍一些数论知识，这些知识是 实现r s a 的理论基础： 若a x = - 1 ( m o dn ) e o ，x 有解，则x 是a 的逆，解模的逆元问题很困 难，一般来说，如果a 和n 是互素的，那么a - 1 5 x ( r o o dm ) 有唯一的解。 使用扩展的欧几里德算法可以出a 模n 的逆元。 扩展的欧几里德算法描述如下： o n o - - - n 1 a 0 = a 2 x o = o 3 x = l 4 q = l n o ，b o j 5 i = n _ q + a 0 6 w h i l er 0d o 7 t e m p = x o q 4 x 8 i f t e m p 一0t h e nt e m p - - t e m pm o d 1 3 9 i f t e m p 1 ) 。 如果n 是素数，那么中( n ) 一n 一1 ，如果n = p + q ，且p 和q 都是素数， 那么巾( 1 1 ) = ( p - 1 ) + ( q 一1 ) ，这些结论将在我们谈到的r s a 公钥密码体 制中一再出现，r s a 公钥密码体制来源于此。 欧拉函数也可用来计算模1 2 的逆元，但不是在任何情况下都能使 用： 根据费尔马小定理的欧拉推广，如果g c d ( a ，n ) = 1 ，那么： r ( “) m o d n = 1 现在计算a 模n 的逆元很容易： x = a 。( “) 。lm o dn 通常，欧几里德算法在计算逆元方面比欧拉推广更快，特别是对于 5 0 0 位范围内的数 1 1 3 素数 素数是这样一一种数：比1 大，其因子只有1 和它本身，没有其他的 数可以整除它，素数是无限的。密码学，特别是公钥密码学常用大的 素数( 5 1 2 位，甚至更长) 。对尺寸为n 的数，一个随机数是素数的概 率接近于i nn 分之一。那么小于n 的素数的总数为n 0 nn 1 。问题“n 是素数吗? ”是比问题“n 的因子是什么? ”更容易回答的问题。如果你 产生随机候选数，然后试着分解它们，从而找出素数，这种方法是错 误的。正确的方法是对产生的随机数先进行测试是否是素数。产生素 数的一般方法可以分为两类，既确定性素数产生方法和概率性素数产 生方法。 1 ) 确定性素数产生方法： 山东犬学硕士学位论文 确定性素数产生方法产生的数必然是素数，然而其产生的素数却 带有一定的限制，假若算法设计不佳，便容易构造出带有规律的素数， 使密码分析者能够分析出素数的变化，进而可以猜出该系统中使用的 素数。 此类方法主要有两类，即基于l u c a s 定理和基于p o c k l i n g t o n 定理的 确定性素数产生方法，本文仅介绍基于l u c a s 定理的确定性素数产生 方法。此方法需要求得素数n 1 的全部素因子。 l u c a s 定理：设n e n ，存在一个正整数a ，1 a o 且z = l ，那么p 不是素数。 ( 5 ) 设j 弓+ 1 。如果j b 且z p 一1 ，设乎z 2 m o d p 然后回到第 ( 4 ) 步。如果z 印一1 ，那么p 通过测试，可能是素数。 ( 6 ) 如果j = b 且z p l ，那么p 不是素数。 般来说，我们在实际中先让p 试除2 0 0 0 以内的素数，若都不能 整除，再进行5 次r a b i n m i l l e r 测试。 山东_ ： _ = 学j i ! i | 士学位论义 1 2 公开密钥算法 1 2 1 背景 公开密钥的密码学的概念是由w h i t e f i e l dd i f f i e 和m a t i n h e l l m a n 发明的，r a l p h m a k l e 也独立推出了此概念。它在密码学上的 贡献在于使用一对密钥加密密钥和解密密钥且从加密密钥推 出解密密钥是不可行的。1 9 7 6 年，d i m e 和h e l l m a n 在美国国家计算 机会议上首先公布了这个概念，几个月后，出版了这篇开创性的论文 n e wd i r e c t i o n si nc r y p t o g a r p h y ( 密码学的新方向) 。 1 9 7 6 年后，提出了多种公开密钥算法，其中许多是不安全的。而 那些被视为安全的算法，有许多却不实用，要么是密钥太大，要么密 文远大于明文。 只有少数几个算法既安全又实用。在这些既安全又实用的算法中， 一些仅适用于密钥分配，一些适用与加密( 且扩展作为密钥分配) ，还 有一些只适用与数字签名。只有3 种算法可很好地用于加密和数字签 名，r s a 算法就是其中之一。 i 2 2 公开密钥算法的安全性 因为密码分析者能获取公开密钥，它们总可以选择任意消息来加 密。这意味着，给定了c = e k ( p ) 的密码分析者能够猜测p 的值并很 容易验证他们的猜想。如果可能的明文的数目少到足以进行穷尽搜索， 这将是一个严重的问题，但这能够通过用随机数填充消息的方法来解 决。这使相同的明文加密得到不同的密文。 用公开密钥算法来加密会话密钥，这一点尤其重要。e v e 能够产生 一个由b o b 的公开密钥加密的所有可能的会话密钥的数据库。当然， 这需要很多时间和大容量存储，但对4 0 位出口密钥或5 6 位d e s 密钥 而言。，这比攻击b o b 的公开密钥算法所用的时间和存储空问要少得多。 一旦e v e 获得该数据库后，她就可以任意的读取b o b 的邮件。 公开密钥算法能抵抗选择明文攻击，他们的安全性依赖于由公开密 乐人学埘j 学位论艾 钥恢复出私人密钥的难度，以及由密文恢复出明文的难度。通过大多 数公开密钥算法特别容易受到选择密文的攻击。 数字签名是加密的逆过程，除非在加密和签名过程中采用了不同的 密钥，否则攻击是不可避免的。 总而言之，重要的是从整体上研究一个系统，而不应局限于系统的 一部分。好的公开密钥协议应设计成任何一方都不能解密其他方产生 的任意消息。对等证明协议就是一个很好的例子。比较著名且安全的 公钥密码体制有：r s a 体制，e l g a m a l 体制和椭圆曲线体制等，下 面我们着重要介绍r s a 公钥密码体制。 山东大学删= b 学位论义 第二章密码系统的描述 2 1r s a 加解密的基本描述 2 1 1 r s a 的基本过程 r s a 使用了指数表达式。明文以分组为单位加密，其中每个分组 是小于某个数n 的二进制值。也就是说，分组大小必须小于或者等于 l o g ( n ) 2 ；实践中分组大小是k 比特，其中2 k n 2 k + l 。对于某个明文分 组m 和密文分组c ，加密及解密的形式如下： c = m 。m o dnm = c om o d n _ ( m 。) om o dn = m 州m o dn 发送方和 接收方都必须知道1 3 的值。发送方知道e 的值，而只有接收方知道d 的 值。因此，这是一种公开密钥为k u = e ，n ) ，且私有密钥为k r = d ，n ) 的公 开密钥加密算法。要使这个算法能够满足公开密钥加密的要求，必须符 合如下条件： 1 、有可能找到e 。d x n 的值，使得对所有m n 有m e a = mm o dn 。 2 、对于所有r r l r l 的值，要计算m 。和c o 相对来说是简单的。 3 、在给定e 和n 时，判断出d 是不可行的。 那么如何找到m 印m o dn 的关系呢? 假定：给定两个素数p 和q ，以及 两个整数n 和m ，使得n = p q 而且0 m n ，并且对于任意整数k ，下列关系 成? r ：m k 寸) f n ) + l = m k ( p 1 ) ( q 一1 ) + l5 m m o d d 其中d ) ( n ) 是欧拉t o t i e n t 系 数，也就是不超过r l 且与n 互素的整数个数。因而可以得到需要的关系， 如果：d e = k 中( n ) + l 等价于e d i i r o o d 由( n ) d 5 e 。m o d 审( n ) 也就是说d 和e 是以巾( n ) 为模的乘法逆元。注意根据模运算规则，它的必要条件是d ( 并 有e ) 与巾( n ) 是互素的。等价地，( g o d 巾( n ) ，d ) = 1 。 现在可以给出r s a 方法。它的成分有：p q 两个素数( 私有，选 择) n _ p q ( 公开，计算出) e ，其中g c d ( 巾( n ) ，e ) = e 中( n ) ( 公开，选择) d ； e - i m o d 中( n ) ( 私有，计算出)私有密钥由 d ，n 组成，而公开密钥由 e , n ) 组成。假设用户a 公布了它的公开密钥，而用户b 希望向a 发送一个 报文m ，那么b 计算出c = m 。( m o d n ) 并传输c 。在收到这个密文时，用户 山东大学硕士学位论文 a 通过计算m = c 4 ( m o d n ) 进行解密。下面用图l 来归纳r s a 算法。 密钥的产生 选择两个素数p , q 计算n = p q 计算中( n ) = ( p 一1 ) ( q - 1 ) 选择一个数e g c d ( 巾( n ) ，e ) = 11 e 中( n ) 计算d 公开密钥e n 私有密钥d , p ，q 2 1 2 模幂运算的实现 从上面的算法的基本实现我们可以看出，不论是r s a 的公钥加密 运算还是私钥解密运算都是一个模幂运算我们先从就指数方面如何 计算模幂运算： 1 ) b r 法 传统的计算方法b r ( b i n a r yr e p r e s e n t a t i o n ) 算法是将指数e 二 i - 1 进制化来实现的即将指数x 表示成二进制形式：e = ( e ，4 2 ) 之后再进 行一系列迭代运算 这里e i = o 或1 ，o i 1 0 e 】+ 1l = 1 0 9 2 e + l ，算法如下 1 z = l 2 f o ri = 1 1d o w n t o0d o 山东大学坝卜学位论文 3 z = z 2r o o d l l 4 i f e i = lt h e nz = z + xm o d 1 1 本算法从e 的二进制的高位计算起，遇到为1 的位就用a 去乘上一步 的迭代结果，先求乘同余再求平方剩余；遇到为0 的位就直接对上一步 的迭代结果求平方剩余其时间复杂度为t ( n