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

四川理工学院毕业论文 rsa 密码体制的设计及 matlab 语言下的实现 学 生：xxx 学 号：06121020230 专 业：数学与应用数学 班 级：2006.2 指导教师：张金山 四川理工学院理学院 二 o 一 o 年六月 摘 要 rsa 算法是一个能同时用于加密和数字签名的算法，易于理解和操作，有较高的 安全性，因此有着广泛的运用。本文首先论述了 rsa 的基本运用途径，rsa 的数学原 理，其加密解密的具体算法，并给出了其在 matlab 应用软件上的实现，然后，对 rsa 的安全性进行了一定的分析，包括其可能存在的攻击和对参数的选择，以便对其 有更深的了解。 关键词：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 purpose, 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. keywords : 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 4.2 rsa 的参数选择 .15 结束语 16 参考文献 17 致 谢 18 四川理工学院毕业论文 1 前 言 随着计算机通信技术的迅速发展，在计算机网络和通信的众多领域中，信息的安 全性越来越受到人们的重视，于是，密码技术应运而生，目前计算机网络主要采用两 种密码体制，即公钥密码体制和私钥密码体制，作为公钥密码体制的重要技术的 rsa，主要用于数字加密和数字签名，由于其很好的安全性，可以保证网络中重要数 据的安全性，因此有广泛的应用。 rsa 于 1978 年由美国麻省理工大学的三位数学家提出，经过三十多年的发展，人 们对它的研究也逐渐广泛，它是第一个能用于数据加密和数字签名的算法，其安全性 依赖于大数的因子分解，因此，具有较高的安全性，有时也用于密钥的管理。 本文较为详细的介绍了密码体制的相关内容，包括 rsa 的主要应用及其在计算机 网络中的重要性。列举了 rsa 算法的数学基础，即数论知识。对其数学原理进行了简 单的说明，详细介绍了其具体算法。为了便于理解，笔者还举了一个简单的加密解密 实例，然后给出了其在 matlab 上的算法实现，最后，就其安全性进行了较为简单的 讨论。 由于时间关系，再加上笔者的能力有限，本文中尚有许多不足之处，敬请读者批 评指正。 第 1 章 rsa 简介 2 第 1 章 rsa 简介 1.1 密码体制简介 随着 internet 的广泛应用，电子商务和电子政务得到的迅速的发展，越来越多的个 人信息需要严格保密，因此，密码学成了必不可少的一门学科。密码技术是密码学的 重要内容，它是集数学，计算机科学，电子与通信等诸多学科于一身的的交叉学科， 它不仅能够保证机密信息的加密，而且能够实现数字签名，身份验证，系统安全等功 能。 目前计算机网络主要采用两种密码体制，对称密码体制和非对称密码体制。 对称密钥体制的加密密钥和解密密钥是相同的，只要知道加密密钥，就能推出解 密密钥，通信双方分别持有加密密钥和解密密钥，需要定期更新密钥。使用对称密码 体制进行保密通信时，通信双方要事先通过秘密的信道传递密钥，而秘密信道时不易 获得的。很久以来，密钥分发的问题一直困扰着密码专家，随着计算机网络的逐渐扩 大，密钥分配所造成的时间延迟和费用问题日益凸显出来。对称密码还有一个缺点， 就是密钥量太大，在有 个用户的通信网络中，系统的总密钥量将达到 ，这样大的n 2nc 密钥量在保存，传递，使用和销毁的各个环节中都会有不安全因素存在。此外，在一 些需要验证消息的真实性和消息发送方身份的场合，或在进行电子交易时，必须有手 写签名的数字形式即数字签名来确认身份，这是对称密码无法实现的。 非对称密钥体制不能从加密密钥推出解密密钥，加密和解密是采用一对不同的密 钥进行的，公钥（加密密钥）公开，私钥（解密密钥）保密。例如，甲将他的加密密 钥公开，任何想与甲通信的都可以采用这个加密密钥把要传送的信息（明文）加密成 密文发送给甲，只有甲知道解密密钥，能够将密文还原为明文，而任何第三方即使截 获到密文也不能知道密文所传递的信息。非对称密码体制最有影响的典型算法是 rsa，于 1978 年有美国麻省理工学院的三位数学家瑞弗斯特（rob rivest） ，沙米尔 （adi shamir）和阿德来门（ len adleeman）提出，rsa 算法既可用于数据加密，又可 用于数字签名，安全性良好，易于实现和理解。 1.2 rsa 的简介 rsa 是目前最为流行的公钥密码体制之一 ，其安全性是基于分解大素数的困难 四川理工学院毕业论文 3 性，由于其加密函数是一个单向函数，所以对第三方而言，试图在有效的时间内在计 算机上非法解密密文是不可能的。由于 rsa 能实现信息的加密，解密和数字签名，较 好的满足计算机网络应用的需求，因此得到了广泛的应用，主要用于保证以下几点： （1）数据的机密性：预防非法的信息存取和信息在传输过程中被非法窃取。 （2）数据完整性：保证通信中的信息不会被非法篡改，入侵者不能利用其他假消息 替换原始消息。 （3）身份认证：保证对方属于所称实体，是依靠数字签名实现的。 （4）不可抵赖性：发送者无法事后否认其发送过消息，消息的接收者可以像中立的 第三方 ca 证实所指的发送者确实发出了消息。 由于公钥密码体制中通信双方的公钥可以公开，以及其的较好的安全性，该种加 密方式及其相关系统在密钥管理，电子商务中都有着广泛的应用。 第 2 章 相关数论知识 4 第 2 章 相关数论知识 2.1 整除与互素 定义 2.1：设 为 是整数， ，如果存在 ，使得 ，则称 整除 ，ab0zcbcaa 记为 ，并且称 是 的一个因子，而 为 的倍数，若不存在 使得 ，则b| abzbc 称 不整除 ，记作 。| 定义 2.2：一个大于 1 的整数，如果它的正因数只有 1 和它本身，则该数称为素数， 否则叫做合数。 定理 2.1：（带余除法）设 ，则存在唯一确定的整数 和 ，使得：0,bza qr ，rq 定义 2.3：设 是不全为 的整数， 和 的最大公因数是指满足下述条件的整数ba, ，d （1） 为 和 的公因数，即 ，且 。ad|b| （2） 为 和 的所有公因数中最大的，即对 ，若 ，且 ，则 。abzca|bc|d 记作 ，如果 ，则称 和 互素。),(d1),(,z 定理 2.2：设任一大于 1 的整数 都能表示成素数的乘积，即a .tpa2 其中 是素数， ， （ ） ，并且，若不考虑 的排列顺序，则这种表示方法ip0iiip 是唯一的。 2.2 费马定理和欧拉定理 定理 2.3：（费马小定理）若 是素数， ，则 .pa|ppmod1 费马定理的等价形式： .apmod 定义 2.4：设 为正整数，欧拉函数 定义为满足条件： 且 的n)(nnb01),( 整数 的个数。b 具有如下性质：)(n （1）当 是素数时， ；1)(n （2）若 ， 为正整数，则 ；k12)(k 四川理工学院毕业论文 5 （3）若 ，且 ，则 ；pqn1),()1()(qpn （4）若 ， 为素数，则：t21 tipi .)1()()( 21121 tt pn 定理 3.4：（欧拉定理）对于任意整数 ，当 时，有 .na,nanmod( 证明： 设小于 且与 互素的正整数集合为 ，)(21nx 由于 ，故对 ， 仍与 互素。因此1),(),(nxai )(iix 构成 个与 互素的数，且两两不同余。这是因为，若有 ，使)(21x (n jix, 得 则由于 ，可以消去 ，从而,modji),aaxjiod 所以 与 在 的意义上是两个相同的集合，分别计,)(21nxa ,)(21nx mod 算两个集合中各元素的乘积，有 nxanod)(21)(21 由于 与 互素，故 .)(21,nx od)( 推论 3.1 amod1 2.3 中国剩余定理 中国剩余定理是解一次同余方程组最有效的算法。 首先，我们写出一次同余方程组的一般形式： kkmaxod2211 如果对任意 ，有 ，即 两两互素，则有以下固定jikji,11),(ji km,21 算法： （1） 计算 ，及 ；kmm21iim （2） 求出各 模 的逆，即求 ，满足 ；ii 1i iiod1 （3） 计算 ， 即为方程组的一个解.aaxkmod1 x 例 2.1：求相邻的四个整数，依次可被 整除.227,53 解： 设四个整数为 ，则有,x 第 2 章 相关数论知识 6 49mod2510x 计算 4925m ，1 2594,94,253 m0,7. 141312m 最终求得 410mod39x 四川理工学院毕业论文 7 第 3 章 rsa 的数学原理及其算法实现 3.1 rsa 的数学原理 rsa 算法基于下面的两个事实，保证 rsa 算法的安全有效性： 1）已有确定一个数是不是素数的快速算法； 2）尚未找到确定一个合数的质因子的快速算法： rsa 算法的工作原理 （1）任意选取两个不同的大质数 和 ，计算乘积 ，pqqpn ；)1()(qpn （2）任意选取一个大整数 ， 与 互素，整数 e 用做加密密钥， （注意：e)1( 的选取是很容易的，例如，所有大于 和 的质数都可用）e pq （3）确定解密密钥 ： ，根据 ， ， ，可以容易的计算d)(mod1pq 出 ；d （4）公开整数 和 ，将 保密；ne （5）将明文 （假设 是一个小于 的整数）加密为密文 ，计算方法为：pncpceod （6） 将密文 c 解密为明文 p，计算方法为： ndm 然而，只根据 和 （不是 和 ） ，要计算出 是不可能的，因此，任何人都可neq 以对明文进行加密，但只有授权用户（知道 ）才可以对密文进行解密。 例如：向用户 a 发送加密信息时，利用 a 的公开密钥 ， ,计算ane eecod)( 求出的整数 即为密文，c 当 a 受到 后，利用自己的解密密钥 ，计算a dncdmo)( 由欧拉定理，这里计算出的 恰好等于加密前的明文 .m 事实上，由于 )(o1aade .1|aden 设 ， ，当 时，有：)(antdezt)(, 第 3 章 rsa 的数学原理及其算法设计 8 amnod1)( 于是： atntdemcdaa)( )( 这时，对于每一个明文分组 ，要求其与模数 互素. 3.2 rsa 的算法设计 rsa 加密算法和解密算法的具体步骤： （1）rsa 算法的初始化，系统产生 2 个大素数 和 （保密）.计算 ，pqqpn （ 公开） ，n ，令随机选取整数 作为公钥（加密密钥） ，满足 （公开）和)1()(qpee 互质，计算私钥 （解密密钥） ，满足 .销毁 ， 及 .d )(mod1npq)(n （2）rsa 加密解密变换，首先将明文分块并数字化，然后将明文分成若干段，使每 个数字化的明文段的值小于 ，长度不大于 ，然后对每个明文块 依次进行加密，n2lgm 解密变换. 加密变换：分别使用公钥 和明文 ，得密文e neceod)( 解密变换：分别使用私钥 和密文 ，得明文dcdm 例 3.1：rsa 公钥密码加密解密算法实例 选 ， ， ， ，选择 ，计算出 .53p41q2173qpn208)(n31e671d 将 ， 公开， 保密，ned 设明文 为 ，对其加密，得到密文：m7 .2173mod4631c 解密时，计算 ，恢复出明文 .27od34671c rsa 的加密解密过程是一个模 的指数运算，计算 这个运算有一个快速nneod 实现的算法如下： 首先，将 表示为二进制形式：e ， ，12104raa log2e1,0ia 然后计算出： nmod21 4 nnrrr odod1221 其中， ， ，0ni i 四川理工学院毕业论文 9 由于： .110110 )()(222 rr aaaae mmm 而： ,)(22iiai 对于给定的 ，只需根据其二进制表示，取出 的 相乘即可，由于其中间e 1iai2 结果均为小于 的整数，从而使运算量大大减小.n 例 3.2：计算 2173mod34 作预计算： 809672 2173od543 128 m9076 由于 643 所以 2173od4637801521 例 3.3：一个简单的 rsa 加密解密算法 取 ， .则 ， .43p59q943n58)(ne 设明文段 2106m 则对于密文 .7od3c 做计算 84 251206 37mod60)3( 9824 251)(1068 37od)60(32 得密文为 现在将其恢复为明文：做计算 .其中 ，)(mod1ne13e2436)(n 即： ， ，使得： ， .即： 的值，因此，用|yx,1)(nyxe)(xd 辗转相除法： 1rqbabr10 212 . 第 3 章 rsa 的数学原理及其算法设计 10 nnrqr12 10nr 其中： ，得2110, kkqqnqx1)( 代入数据得： 937xd 则明文 25mo 又 68937 计算： 37d12 25o90)(2 834 37md641228 25o0)(6 5322 37d18164 5o904722 m356 237d18122537mod106)28(0946)(2937 得明文为： 06 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 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=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(miwen(i),d,n); end miwen mingwen 实验结果： 输入待加密的明文：2106 输入第一个大素数：43 四川理工学院毕业论文 13 输入第二个大素数：59 输入加密密钥：13 密文= 2321 明文= 2106 第 4 章 rsa 的安全性分析 14 第 4 章 rsa 的安全性分析 4.1 对 rsa 常见的攻击方法 rsa 的安全性依赖于对一种特殊形式的数 （ 为素数）进行分解的困难pqn, 行. 常见的攻击方法有： （1）分解 n 攻击 rsa 体制最直接的方式就是试图分解模数 ，得到 ，求出 ，从而由nqp,)(n 和 求出解密密钥 ，今天对大整数进行分解最有效的三种算法是二次筛法，椭e)(d 圆曲线分解算法和数域筛法；目前 1024bit 以上的 rsa 被认为是符合安全性要求的. （2）对 的值直接猜测d 实践证明这是一种穷搜索法 （3）直接猜测 )(n 事实上，这并不比分解 容易，因为若能猜出 ，则由)(n pq1 很容易求出 的分解，但已证明这种算法等价于分解 .n （4）小指数攻击 当加密指数 较小时，可以加快运算速度，但易受攻击如果采用不同的模数 及相e n 同的 值，对 个线性相关的消息加密，则存在一种攻击方法，如果消息相同，e2/)1( 则用 个消息就够了. 如：三个用户的加密密钥 均为 3，而有不同的模数 ，这里要求e 321,n 两两互素，若要同时向这三个用户发送广播消息 ，先对 分别进行加密，321,n m 计算 33232131 od,mod,odncncnmc 这里 ，密码分析者截获到这三个密文后，由于 两两互素，可2,in 321,n 用中国剩余定理，求出 3213 由于 ，故 ，因此有 ，得到明文 ，321,i n3cm 防止这种攻击的方法，对于短的消息，可用独立的随机值填充，使其足够长，即消息 满足 ，这样就可以防止小指数攻击.m3213n 四川理工学院毕业论文 15 （5）定时攻击 定时攻击通过观察解密所需时间来确定解密密钥，但如果 的二进制表示中 1 的d 数目较多时，则解密需要的运算时间也较长。 4.2 rsa 的参数选择 1. 的确定：n 的确定可以归结为如何选定 ，对于 ，有以下一些要求：qp, （1） 要足够大qp, 一般选取 位十进制数，并要判定其位素数20 （2） 之差要大, 若 之差较小，不妨设 ，则 也较小，由qpqp2/)( 44/)(22n 当 很小时， 接近 ，从而 接近 可以逐个检验大于/)(n/)(qpn 的整数 ，直到找到一个 ，使得 是一个平方数， ，则由：xx2 22yx 推出yqp2/)(yqp 为避免这种情况，在 rsa 算法中，通常选择 为强素数.q, （） 与 的最大公约数要小1 2. 和 的选择ed 首先， 要满足