毕业论文-RSA密码体制的设计及MATLAB语言下的实现28627.doc

《毕业论文-RSA密码体制的设计及MATLAB语言下的实现28627.doc》由会员分享，可在线阅读，更多相关《毕业论文-RSA密码体制的设计及MATLAB语言下的实现28627.doc（22页珍藏版）》请在三一文库上搜索。

1、 四川理工学院毕业论文四川理工学院毕业论文 RSARSA 密码体制的设计及密码体制的设计及 MATLABMATLAB 语言下的实现语言下的实现 学 生：XXX 学 号：06121020230 专 业：数学与应用数学 班 级：2006.2 指导教师：张金山 四川理工学院理学院 二 O 一 O 年六月 摘摘 要要 RSA 算法是一个能同时用于加密和数字签名的算法，易于理解和操作，有较高的 安全性，因此有着广泛的运用。本文首先论述了 RSA 的基本运用途径，RSA 的数学原 理，其加密解密的具体算法，并给出了其在 MATLAB 应用软件上的实现，然后，对 RSA 的安全性进行了一定的分析，包括其可能

2、存在的攻击和对参数的选择，以便对其 有更深的了解。 关键词：RSA 公钥密码体制 加密 解密 MATLAB 安全性 ABSTRACT RSA is an algorithm which can be used for both encryption and digital signature. It is easy to understand as well as to operate, and has an upper security which makes it popular. This paper firstly delivers information on the basic p

3、urpose, the mathematic principle and the specific arithmetic of RSA. Then it presents an implementation of RSA on the application software MATLAB. After that, this article also analyzes the security of RSA, including its potential leaks, parameter options, which helps us to know further of RSA. Keyw

4、ords : RSA public key cryptography encryption decrypt MATLAB security 目 录 前 言1 第 1 章 RSA 简介 .2 1.1 密码体制简介 .2 1.2 RSA 的简介 .2 第 2 章 相关数论知识4 2.1 整除与互素4 2.2 费马定理和欧拉定理 .4 2.3 中国剩余定理 .5 第 3 章 RSA 的数学原理及其算法实现 .7 3.1 RSA 的数学原理.7 3.2 RSA 的算法设计.8 3.3 RSA 的 MATLAB 实现10 第 4 章 RSA 的安全性分析 .14 4.1 对 RSA 常见的攻击方法14

5、4.2 RSA 的参数选择.15 结束语16 参考文献17 致 谢18 四川理工学院毕业论文 1 前前 言言 随着计算机通信技术的迅速发展，在计算机网络和通信的众多领域中，信息的安 全性越来越受到人们的重视，于是，密码技术应运而生，目前计算机网络主要采用两 种密码体制，即公钥密码体制和私钥密码体制，作为公钥密码体制的重要技术的 RSA，主要用于数字加密和数字签名，由于其很好的安全性，可以保证网络中重要数 据的安全性，因此有广泛的应用。 RSA 于 1978 年由美国麻省理工大学的三位数学家提出，经过三十多年的发展，人 们对它的研究也逐渐广泛，它是第一个能用于数据加密和数字签名的算法，其安全性

6、依赖于大数的因子分解，因此，具有较高的安全性，有时也用于密钥的管理。 本文较为详细的介绍了密码体制的相关内容，包括 RSA 的主要应用及其在计算机 网络中的重要性。列举了 RSA 算法的数学基础，即数论知识。对其数学原理进行了简 单的说明，详细介绍了其具体算法。为了便于理解，笔者还举了一个简单的加密解密 实例，然后给出了其在 MATLAB 上的算法实现，最后，就其安全性进行了较为简单的 讨论。 由于时间关系，再加上笔者的能力有限，本文中尚有许多不足之处，敬请读者批 评指正。 第 1 章 RSA 简介 2 第 1 章 RSA 简介 1.1 密码体制简介密码体制简介 随着 Internet 的广泛

7、应用，电子商务和电子政务得到的迅速的发展，越来越多的个 人信息需要严格保密，因此，密码学成了必不可少的一门学科。密码技术是密码学的 重要内容，它是集数学，计算机科学，电子与通信等诸多学科于一身的的交叉学科， 它不仅能够保证机密信息的加密，而且能够实现数字签名，身份验证，系统安全等功 能。 目前计算机网络主要采用两种密码体制，对称密码体制和非对称密码体制。 对称密钥体制的加密密钥和解密密钥是相同的，只要知道加密密钥，就能推出解 密密钥，通信双方分别持有加密密钥和解密密钥，需要定期更新密钥。使用对称密码 体制进行保密通信时，通信双方要事先通过秘密的信道传递密钥，而秘密信道时不易 获得的。很久以来，

8、密钥分发的问题一直困扰着密码专家，随着计算机网络的逐渐扩 大，密钥分配所造成的时间延迟和费用问题日益凸显出来。对称密码还有一个缺点， 就是密钥量太大，在有个用户的通信网络中，系统的总密钥量将达到，这样大的n 2 n C 密钥量在保存，传递，使用和销毁的各个环节中都会有不安全因素存在。此外，在一 些需要验证消息的真实性和消息发送方身份的场合，或在进行电子交易时，必须有手 写签名的数字形式即数字签名来确认身份，这是对称密码无法实现的。 非对称密钥体制不能从加密密钥推出解密密钥，加密和解密是采用一对不同的密 钥进行的，公钥（加密密钥）公开，私钥（解密密钥）保密。例如，甲将他的加密密 钥公开，任何想与

9、甲通信的都可以采用这个加密密钥把要传送的信息（明文）加密成 密文发送给甲，只有甲知道解密密钥，能够将密文还原为明文，而任何第三方即使截 获到密文也不能知道密文所传递的信息。非对称密码体制最有影响的典型算法是 RSA，于 1978 年有美国麻省理工学院的三位数学家瑞弗斯特（Rob Rivest） ，沙米尔 （Adi Shamir）和阿德来门（Len Adleeman）提出，RSA 算法既可用于数据加密，又可 用于数字签名，安全性良好，易于实现和理解。 1.2 RSA 的简介的简介 RSA 是目前最为流行的公钥密码体制之一 ，其安全性是基于分解大素数的困难 四川理工学院毕业论文 3 性，由于其加密

10、函数是一个单向函数，所以对第三方而言，试图在有效的时间内在计 算机上非法解密密文是不可能的。由于 RSA 能实现信息的加密，解密和数字签名，较 好的满足计算机网络应用的需求，因此得到了广泛的应用，主要用于保证以下几点： （1）数据的机密性：预防非法的信息存取和信息在传输过程中被非法窃取。 （2）数据完整性：保证通信中的信息不会被非法篡改，入侵者不能利用其他假消息 替换原始消息。 （3）身份认证：保证对方属于所称实体，是依靠数字签名实现的。 （4）不可抵赖性：发送者无法事后否认其发送过消息，消息的接收者可以像中立的 第三方 CA 证实所指的发送者确实发出了消息。 由于公钥密码体制中通信双方的公钥

11、可以公开，以及其的较好的安全性，该种加 密方式及其相关系统在密钥管理，电子商务中都有着广泛的应用。 第 2 章 相关数论知识 4 第第 2 章章 相关数论知识相关数论知识 2.1 整除与互素整除与互素 定义定义 2.1：设为是整数，如果存在，使得，则称整除，ab0bZcbca ba 记为，并且称是的一个因子，而为的倍数，若不存在使得，则ab |baabZcbca 称不整除，记作。baa b | 定义定义 2.2：一个大于 1 的整数，如果它的正因数只有 1 和它本身，则该数称为素数， 否则叫做合数。 定理定理 2.1：（带余除法）设，则存在唯一确定的整数和 ，使得：0,bZbaqr ，rqba

12、br 0 定义定义 2.3：设是不全为的整数，和的最大公因数是指满足下述条件的整数ba,0ab ，d （1）为和的公因数，即，且。dabad |bd | （2）为和的所有公因数中最大的，即对，若，且，则。dabZcac |bc |dc 记作 ，如果，则称和互素。),(bad 1),( ,baZbaab 定理定理 2.2：设任一大于 1 的整数都能表示成素数的乘积，即a . t t pppa 21 21 其中是素数， （） ，并且，若不考虑的排列顺序，则这种表示方法 i p0 i ti 1 i p 是唯一的。 2.2 费马定理和欧拉定理费马定理和欧拉定理 定理定理 2.3：（费马小定理）若是素数

13、，则.pa p | pa p mod1 1 费马定理的等价形式：.paa p mod 定义定义 2.4：设为正整数，欧拉函数定义为满足条件：且的n)(nnb 01),(nb 整数的个数。b 具有如下性质：)(n （1）当是素数时，；n1)( nn （2）若，为正整数，则； k n2k 1 2)( k n 四川理工学院毕业论文 5 （3）若，且，则；pqn 1),(qp) 1)(1()(qpn （4）若，为素数，则： t t pppn 21 21 )1 (tipi .) 1() 1)(1()( 21 11 2 1 1 21 tt ppppppn t 定理定理 3.4：（欧拉定理）对于任意整数，当

14、时，有.na,1),(nana n mod1 )( 证明：证明： 设小于且与互素的正整数集合为，nn, )(21n xxx 由于，故对，仍与互素。因此1),( , 1),(nxna i )(1ni i axn 构成个与互素的数，且两两不同余。这是因为，若有，使 )(21 , n axaxax )(nn ji xx , 得则由于，可以消去，从而,modnaxax ji 1),(naanxx ji mod 所以与在的意义上是两个相同的集合，分别计, )(21n axaxax , )(21n xxx nmod 算两个集合中各元素的乘积，有 nxxxaxaxax nn mod )(21)(21 由于与

15、互素，故. )(21 , n xxx n)(mod1 )( na n 推论推论 3.1 naa n mod 1)( 2.3 中国剩余定理中国剩余定理 中国剩余定理是解一次同余方程组最有效的算法。 首先，我们写出一次同余方程组的一般形式： kk max max max mod mod mod 22 11 如果对任意，有，即两两互素，则有以下固定jikji,11),( ji mm k mmm, 21 算法： （1） 计算，及； k mmmM 21 i i m M M （2） 求出各模的逆，即求，满足； i M i m 1 i M iii mMMmod1 1 （3） 计算，即为方程组的一个解.MaM

16、MaMMx kkk mod 1 1 1 11 x 例例 2.12.1：求相邻的四个整数，依次可被整除. 2222 7 , 5 ,3 ,2 解解： 设四个整数为，则有2, 1, 1xxxx 第 2 章 相关数论知识 6 49mod2 25mod1 9mod0 4mod1 x x x x 计算 492594M ，49259 1 M2594,4994,49254 432 MMM 30, 9 , 7 . 1 1 4 1 3 1 2 1 1 MMMM 最终求得 44100mod29349x 四川理工学院毕业论文 7 第 3 章 RSA 的数学原理及其算法实现 3.1 RSA 的数学原理的数学原理 RSA

17、 算法基于下面的两个事实，保证 RSA 算法的安全有效性： 1）已有确定一个数是不是素数的快速算法； 2）尚未找到确定一个合数的质因子的快速算法： RSA 算法的工作原理 （1）任意选取两个不同的大质数和，计算乘积，pqqpn ；) 1() 1()(qpn （2）任意选取一个大整数 ， 与互素，整数 e 用做加密密钥， （注意：ee) 1() 1(qp 的选取是很容易的，例如，所有大于和的质数都可用）epq （3）确定解密密钥：，根据 ，可以容易的计算d) 1)(1mod(1qpedepq 出；d （4）公开整数和 ，将保密；ned （5）将明文（假设是一个小于的整数）加密为密文 ，计算方法为

18、：ppnc npc e mod （6） 将密文 c 解密为明文 p，计算方法为： ncp d mod 然而，只根据和 （不是和） ，要计算出是不可能的，因此，任何人都可nepqd 以对明文进行加密，但只有授权用户（知道）才可以对密文进行解密。d 例如：向用户 A 发送加密信息时，利用 A 的公开密钥，,计算 A n A e A e nmmEc A mod)( 求出的整数 即为密文，c 当 A 受到 后，利用自己的解密密钥，计算c A d A d nccDm A mod)( 由欧拉定理，这里计算出的恰好等于加密前的明文.)(cDm 事实上，由于)(mod1 AAA nde .1| )( AAA

19、den 设，当 时，有：1)( AAA ntdeZt 1)(,( A nm 第 3 章 RSA 的数学原理及其算法设计 8 A m nmmod1 )( 于是： A tnnTde nmmmmmcD AAAA mod)()( )(1)( 这时，对于每一个明文分组，要求其与模数互素.mn 3.2 RSA 的算法设计的算法设计 RSA 加密算法和解密算法的具体步骤： （1）RSA 算法的初始化，系统产生 2 个大素数和（保密）.计算，pqqpn （公开） ，n ，令随机选取整数 作为公钥（加密密钥） ，满足 （公开）和) 1() 1()(qpnee 互质，计算私钥（解密密钥） ，满足.销毁，及.)(n

20、d)(mod1ndepq)(n （2）RSA 加密解密变换，首先将明文分块并数字化，然后将明文分成若干段，使每 个数字化的明文段的值小于，长度不大于，然后对每个明文块依次进行加密，nn 2 logm 解密变换. 加密变换：分别使用公钥 和明文，得密文emnmmEc e mod)( 解密变换：分别使用私钥和密文 ，得明文dcnccDm d mod)( 例例 3.1：RSA 公钥密码加密解密算法实例 选，选择，计算出.53p41q2173qpn2080)(n31e671d 将， 公开，保密，ned 设明文为，对其加密，得到密文：m374 .2173mod446 31 mc 解密时，计算 ，恢复出明

21、文.2173mod374 671 c374 RSA 的加密解密过程是一个模的指数运算，计算这个运算有一个快速nnmemod 实现的算法如下： 首先，将 表示为二进制形式：e ， 1 1 210 242 r r aaaaelog2er 1 , 0 i a 然后计算出：nmmmod 2 1 nmnmmmodmod 4 2 12 nmnmm r rr modmod 1 2 2 21 其中，10nmi11ri 四川理工学院毕业论文 9 由于：. 1 1 101 1 10 )()( 2222 r r r r aaaaaae mmmmm 而： 1, 0, 1 )( 2 2 i i a am a m i i

22、 i 对于给定的 ，只需根据其二进制表示，取出的相乘即可，由于其中间e1 i a i m2 结果均为小于的整数，从而使运算量大大减小.n 例例 3.2：计算2173mod37431 作预计算： 2173mod8041398763742 2173mod1035804374 24 2173mod21091035374 28 2173mod19232109374 216 由于 16842131 所以 2173mod44637480410352109192337431 例例 3.3：一个简单的 RSA 加密解密算法 取，.则 ，.43p59q25375943n24365842)(n13e 设明文段 2

23、106m 则对于密文.2537mod210613c 做计算 84113 2537mod4312106 2537mod560)431(2106 22 2537mod9885602106 24 2537mod601)988(2106 28 2537mod2321)601()988()431(210613 得密文为2321 现在将其恢复为明文：做计算 .其中，)(mod1ned13e2436)(n 即：，使得：，.即：的值，因此，用1| )(ednyx,1)(nyxe)(xd x 辗转相除法： 11 rqbabr 1 0 221 rqrb 12 0rr . 第 3 章 RSA 的数学原理及其算法设计

24、 10 nnnn rqrr 121 0 nn rr 11 nnn qrr 其中：，得 2110 , 1, 0 kkkk QQqQQQ n n Qx 1 ) 1( 代入数据得：937 xd 则明文2537mod2321937m 又5122561283281937 计算：2537mod2162321 2537mod990)216(2321 22 2537mod8189902321 24 2537mod6448182321 28 2537mod1205)644(2321 216 2537mod86112052321 232 2537mod5178612321 264 2537mod904517232

25、1 2128 2537mod3029042321 2256 2537mod1283022321 2512 2537mod2106)128(302904861)644()216(2321937 得明文为：2106 3.3 RSA 的的 MATLAB 实现实现 1. 模求逆函数n function d=moni(u,n) n1=n; n2=u; b1=0; b2=1; for i=0:1000 q=floor(n1/n2); r=n1-q*n2; i=i+1; 四川理工学院毕业论文 11 if r=0 n1=n2; n2=r; t=b2; b2=b1+q*b2; b1=t; else break

26、end end if n2=1 warning(所求的模逆不存在)； end if n2= =1 if 0= =mod(i,2) b2=-b2; else b2=b2; end d=mod(b2,n); %return; end 2.求模 n 的大数幂乘函数 function dashuchenmi=dashuchenmi(x,r,n); a=x; b=r; c=1; for i=1:1000 if b= =0 dashuchenmi=c; end 第 3 章 RSA 的数学原理及其算法设计 12 if mod(b,2)=0 b=b-1; c=mod(c*a,n); else b=b/2; a

27、=mod(a*a,n); end end dashuchenmi=c; 3.主函数 clc clear fid=input（输入待加密的明文： ， s ） ； f=abs(fid); p=input(输入第一个大素数：)； q=input(输入第二个大素数：)； e=input(输入加密密钥：)； n=p*q; fain=(p-1)*(q-1); d=moni(e,fain); for i=1:length(f) miwen(i)=setstr(dashuchenmi(f(i),e,n); end for i=1:length(f) mingwen(i)=setstr(dashuchenmi(

28、miwen(i),d,n); end miwen mingwen 实验结果： 输入待加密的明文：2106 输入第一个大素数：43 四川理工学院毕业论文 13 输入第二个大素数：59 输入加密密钥：13 密文= 2321 明文= 2106 第 4 章 RSA 的安全性分析 14 第 4 章 RSA 的安全性分析 4.1 对对 RSA 常见的攻击方法常见的攻击方法 RSA 的安全性依赖于对一种特殊形式的数（为素数）进行分解的困难pqn qp, 行. 常见的攻击方法有： （1）分解n 攻击 RSA 体制最直接的方式就是试图分解模数，得到，求出，从而由nqp,)(n 和求出解密密钥，今天对大整数进行分

29、解最有效的三种算法是二次筛法，椭e)(nd 圆曲线分解算法和数域筛法；目前 1024bit 以上的 RSA 被认为是符合安全性要求的. （2）对的值直接猜测d 实践证明这是一种穷搜索法 （3）直接猜测)(n 事实上，这并不比分解容易，因为若能猜出，则由n)(n pqn qppqn1)( 很容易求出的分解，但已证明这种算法等价于分解.nn （4）小指数攻击 当加密指数 较小时，可以加快运算速度，但易受攻击如果采用不同的模数及相en 同的 值，对个线性相关的消息加密，则存在一种攻击方法，如果消息相同，e2/ ) 1( ee 则用 个消息就够了.e 如：三个用户的加密密钥 均为 3，而有不同的模数，

30、这里要求e 321 ,nnn 两两互素，若要同时向这三个用户发送广播消息，先对分别进行加密， 321 ,nnnmm 计算 3 3 32 3 21 3 1 mod,mod,modnmcnmcnmc 这里，密码分析者截获到这三个密文后，由于两两互素，可 321 ,minnnnm 321 ,nnn 用中国剩余定理，求出 321 3 modnnnmc 由于，故，因此有，得到明文， 321 ,minnnnm 321 3 nnnm 3 cm m 防止这种攻击的方法，对于短的消息，可用独立的随机值填充，使其足够长，即消息 满足，这样就可以防止小指数攻击.m 321 3 nnnm 四川理工学院毕业论文 15

31、（5）定时攻击 定时攻击通过观察解密所需时间来确定解密密钥，但如果的二进制表示中 1 的d 数目较多时，则解密需要的运算时间也较长。 4.2 RSA 的参数选择的参数选择 1. 的确定：n 的确定可以归结为如何选定，对于，有以下一些要求：nqp,qp, （1）要足够大qp, 一般选取位十进制数，并要判定其位素数200100 （2）之差要大qp, 若之差较小，不妨设，则也较小，由qp,qp 2/ )(qp 4/)(4/)( 22 qpqppqn 当很小时，接近，从而接近可以逐个检验大于2/ )(qp 4/)( 2 qp n2/ )(qp n 的整数，直到找到一个，使得是一个平方数，则由：nxxn

32、x 222 ynx 推出 yqp xqp 2/ )( 2/ )( yxq yxp 为避免这种情况，在 RSA 算法中，通常选择为强素数.qp, （）与的最大公约数要小1p1q 2. 和的选择ed 首先， 要满足，同时，为了减少计算量，可令 的二进制表示中 的e1)(,(nee1 数目尽量小，同时，用 求出的也不能太小，否则易受攻击.ed 四川理工学院毕业论文 16 结束语结束语 由于 RSA 在计算机网络，尤其是电子商务中有着广泛的应用，因此，RSA 成为了 研究得最为广泛的公钥算法，从提出到现在，经历了各种各样的考验，逐渐被人们接 受，普遍被认为是目前最为优秀的公钥方案之一。 本文对 RSA

33、 做出了简单的介绍，包括其产生背景，主要应用，数学原理，具体算 法，安全性分析，并给出了其在 MATLAB 软件上的实现。 RSA 涉及的知识极为广泛，不但要求有深厚的专业知识，还有很多其它内容，比 如对当代网络背景的了解，对计算机基础知识的掌握，对 MATLAB 软件的熟练运用等。 同时，也注重专业知识的应用，强调学以致用。 由于自己的能力有限，无法对这方面内容进行深入的研究，再加上对专业知识掌 握的深度不够，因此，在完成该论文时遇到了很多困难。比如，在给出程序代码时， 由于对 MATLAB 软件不太熟悉，很难进行编程。所以，本文难免有很多不足之处，但 我坚信， “一份耕耘，一份收获” 。困

34、难能让我们学到更多，更好的锻炼自己。 参考文献 17 参考文献参考文献 1杨晓元，魏立线.计算机密码学M.西安，西安交通大学出版社 2朱文余，孙琦.计算机密码应用基础M.北京，科学出版社 3闵嗣鹤，严士健.初等数论M.北京，高等教育出版社 4 李海涛，邓樱，MATLAB6.1 基础及应用技巧M.北京，国防工业出版社 5李晓辉.公钥密码体制与 RSA 算法J.福建电脑.2009 6刘栋梁，陈艳萍.RSA 密码体制在电子商务中的安全应用J.大众科技.2005 7段晓萍，李燕华.非对称密码体制 RSA 的原理与实现J.内蒙古大学学报.2009 致谢 18 致致 谢谢 大家都知道写论文是一件很繁琐的事情，在这一次写论文的过程中，遇到了很多 问题，比如理论知识的进一步学习，MATLAB 软件知识的进一步学习，论文的安排， 文献的查找等，所以完成比较困难，但在张金山老师的指导下，在同学的帮助和鼓励 下，顺利完成了毕业论文。在此，对张金山老师和同学们表示衷心的感谢！