公开密钥加密算法RSA的Matlab实现本科毕业论文

1、公开密钥加密算法rsa的matlab实现 摘要rsa算法是基于数论的公开密钥加密算法，它已经成为现在最流行的公钥加密算法和数字签名算法之一。其算法的安全性基于数论中大素数分解的困难性，所以rsa公钥密码体制算法的关键是如何产生大素数和进行大指数模幂运算。本文首先介绍了rsa 公开密钥加密算法的数学原理，并介绍了几种流行的产生大素数的算法。然后用matlab具体实现公钥加密算法rsa的加密和解密，从而实现了数据的安全传输。关键词 rsa算法；加密；素数the realization of rsa algorithm for public key encryption based on matla

2、b(grade 07,class 3,major electronics and information engineering ，communication engineering dept.，shaanxi university of technology, hanzhong 723003, shaanxi) tutor: abstract :the algorithm is based on the theory of rsa public key encryption algorithm, it has become the most popular public key encryp

3、tion algorithm and digital signature algorithm of one. the safety of the algorithm based on number theory cuhk the difficulty of prime decomposition, so the rsa public key cryptography algorithms is key to how to produce large prime numbers dazhi and transmit power operation. this paper first introd

4、uced the rsa public key encr -yption algorithm of mathematical theory, and introduces several popular produce large prime numbers of the algorithm. then use matlab rsa public key encryption algorithm re -alization of encryption and decryption is realized, and the safety of the data trans -mission.ke

5、y words: rsa algorithm; encryption; prime number 毕业设计（论文）原创性声明和使用授权说明原创性声明本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得 及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。作 者 签 名： 日 期： 指导教师签名： 日期： 使用授权说明本人完全了解 大学关于收集、保存、使用毕业设计（论文）的规定，

6、即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。作者签名： 日 期： 学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名： 日期： 年 月 日学位论文版权使用授

7、权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权 大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名：日期： 年 月 日导师签名： 日期： 年 月 日目录引言11数据加密概述21.1基本概念21.2 数据加密分类32 matlab工具介绍62.1 matlab语言的主要特点62.2 matlab的程序设计622.1 脚本文件和函数文件622.2 函数调用和参数传递822.3 matlab的程序结构

8、和控制流程83 rsa公钥密码体制103.1 算法简介103.2算法的数学基础103.3 rsa公钥密码算法10 3.3.1 算法步骤103.3.2 参数分析113.3.3 安全性分析123.4 公钥密码体制中安全大素数的生成133.4.1 素数筛选133.4.2 素数检测143.5 rsa的matlab实现163.5.1算法原理163.5.2 运行过程203.5.3结论分析224 基于rsa的数字签名234.1 数字签名概述234.2 基于rsa的数字签名244.3 rsa数字签名方案的不足245 rsa算法的实际应用和发展255.1 算法的应用255.2算法的改进26结论27致谢28参考文

9、献29附录30附录a：英文资料及翻译30附录b：源程序40引言随着internet用户的激增，世界正步入网络经济的新时代。如网上购物、网上银行、网上证券等。然而，有一些人利用利用他们所掌握的技术非法侵入他人的计算机系统，窃取、篡改、破坏一些重要的数据，给社会造成巨大的损失。密码技术的发展与应用，对解决信息交换的安全问题，保障数据信息的安全，起着不可忽视的作用。所谓密码技术，就是针对信息进行重新编码，从而达到隐藏信息的内容，使非法用户无法获取信息真实内容的一种手段。目前在网络中，一般采用两种密码体制：对称密钥体制和非对称密钥体制。对称密钥体制中的加密密钥和解秘密钥是相同的，所以又称密秘密钥密码体

10、制。对称密钥算法运算效率高、使用方便、加密效率高，在处理大量数据时被广泛使用，但其关键是要保证密钥的安全，为安全起见，密钥要定期改变，所以，对称密钥就存在一个如何安全管理密钥的问题。与对称密钥体制相对应的非对称密钥体制又称为公开密钥密码体制，它是在1976 年由diffe 和hellman 发表的密码学的新方向一文中提出的，从此打破了长期使用单密钥体制的束缚。自此提出公约密码思想以后，涌现出很多的公约密钥算法体系，经过20多年的实践检验，公约系统的应用技术日趋完善，应用领域日趋广泛。公开密钥密码体制，加密密钥和解秘密钥是分开采用一对不同的密钥进行的，分别存在一个公钥和私钥，公钥公开，私钥保密，

11、并且知道其中一个时并不能从中推出另一个。其典型的算法有背包密码、rsa等。 其中rsa公约算法系统因为其可靠安全性，易于实现性，更是受大家的认可和欢迎。rsa加密算法的最大优点就是不需要对密钥通信进行保密，所需传输的只有公开密钥，这样就省去了一条开销很大的密钥传输信道。其保密性强，密钥管理方便，并且具有数字签名、认证和签别等多种功能，特别适合于现代保密通信的需要。大多数使用公钥密码进行加密和数字签名的产品和标准使用的都是rsa算法。rsa的安全性是基于大数因子分解的困难性。目前一般认为rsa需要1024位以上的字长才有安全保障。由于rsa所采用的模幂运算耗时太多，因此它通常只能用于加密少量数据

12、或者加密密钥。需要注意的是，rsa的安全性只是一种计算安全性，绝对不是无条件的安全性，这是由它的理论基础决定的。所以，在实现rsa算法的过程中，每一步都应该尽量从安全性方面考虑。本文就rsa算法以及如何用matlab语言实现给于了详细的分析。1 数据加密概述 密码学是一门古老而深奥的学科，它对一般人来说是陌生的，因为长期以来，它只在很少的范围内，如军事、外交、情报等部门使用。计算机密码学是研究计算机信息加密、解密及其变换的科学，是数学和计算机的交叉学科，也是一门新兴的学科。随着计算机网络和计算机通讯技术的发展，计算机密码学得到前所未有的重视并迅速普及和发展起来。在国外，它已成为计算机安全主要的

13、研究方向，也是计算机安全课程教学中的主要内容。密码是实现秘密通讯的主要手段，是隐蔽语言、文字、图象的特种符号。凡是用特种符号按照通讯双方约定的方法把电文的原形隐蔽起来，不为第三者所识别的通讯方式称为密码通讯。在计算机通讯中，采用密码技术将信息隐蔽起来，再将隐蔽后的信息传输出去，使信息在传输过程中即使被窃取或载获，窃取者也不能了解信息的内容，从而保证信息传输的安全。 任何一个加密系统至少包括下面四个组成部分： （1）未加密的报文，也称明文。 （2）加密后的报文，也称密文。 （3）加密解密设备或算法。 （4）加密解密的密钥。 发送方用加密密钥，通过加密设备或算法，将信息加密后发送出去。接收方在收到

14、密文后，用解密密钥将密文解密，恢复为明文。如果传输中有人窃取，他只能得到无法理解的密文，从而对信息起到保密作用。1.1 基本概念数据加密技术就是指将一个信息或明文经过加密钥匙及加密函数转换，变成无意义的密文，而接收方则将此密文经过解密函数.解密钥匙还原成明文。加密技术是网络安全技术的基石。明文，即加密前的真实的数据或信息，它是可以被外界所识别，它指代的含义比较广泛，比如用户a要将一份文件发送给用户b，那么我们就将用户a手里所拿的那份文件称之为明文。密文，就是对信息经过一定的处理，使它变成无意义的乱码，非指定用户无法对它进行识别，例如a使用密钥k加密消息并将其发送给b，b收到加密的消息后，使用密

15、钥k对其解密以恢复原始消息，那么在这一过程当中a在途中发送给b的东西我们就叫它密文，因为这个文件除b外，其他人得到它也没有任何意义，这就保证了信息传送的保密性。完成加密和解密的算法成为为密码体制。人们一方面要把自己的信号隐蔽起来，另一方面则想把别人的隐蔽信息挖掘出来，于是就产生了密码分析的逆科学密码分析。密码分析研究的问题是如何把密文转换成明文。把密文转换成明文的过程称为破译。破译也是进行函数变换，变换过程中使用的参数也叫密钥。 一般地，如果求解一个问题需要一定量的计算，但环境所能提供的实际资源却无法实现，则这种问题是计算上不可能的。如果一个密码体制的破译是计算上不可能的。则称该密码体制是计算

16、上安全的。密码体制必须满足三个基本要求：（1）对所有的密钥、加密和解密都必须迅速有效；（2）体制必须容易使用；（3）体制的安全性必须只依赖于密钥的保密性。密码体制要实现的功能可分为保密性和真实性两种。保密性要求密码分析员无法从截获的密文中求出明文。一般情况下一个密码体制的保密性包括两项要求：（1）即使截获了一段密文c，甚至知道了与它对应的明文m，密码分析要从系统中求出解密变换，仍然是计算上不可行的。（2）密码分析员要由截获的密文c中系统的求出明文m是计算上不可能的。数据的真实性要求密码分析员无法用虚假的密文代替真是密文而不被察觉，它也包括两个要求：（1）对于给定的c，即使密码分析员知道了对应于

17、它的明文m，要系统的求出加密变换仍然是计算上不可能的。（2）密码分析员要系统地找到密文，使其是明文空间上有意义的明文，这在计算上是不可能的。1.2 数据加密分类专用密钥：又称为对称密钥或单密钥，加密和解密时使用同一个密钥，即同一个算法。如des和mit的kerberos算法。单密钥是最简单方式，通信双方必须交换彼此密钥，当需给对方发信息时，用自己的加密密钥进行加密，而在接收方收到数据后，用对方所给的密钥进行解密。当一个文本要加密传送时，该文本用密钥加密构成密文，密文在信道上传送，收到密文后用同一个密钥将密文解出来，形成普通文体供阅读。在对称密钥中，密钥的管理极为重要，一旦密钥丢失，密文将无密可

18、保。这种方式在与多方通信时因为需要保存很多密钥而变得很复杂，而且密钥本身的安全就是一个问题。公开密钥：又称非对称密钥，加密和解密时使用不同的密钥，即不同的算法，虽然两者之间存在一定的关系，但不可能轻易地从一个推导出另一个。有一把公用的加密密钥，有多把解密密钥，如rsa算法。 非对称密钥由于两个密钥（加密密钥和解密密钥）各不相同，因而可以将一个密钥公开，而将另一个密钥保密，同样可以起到加密的作用。 在这种编码过程中，一个密码用来加密消息，而另一个密码用来解密消息。在两个密钥中有一种关系，通常是数学关系。公钥和私钥都是一组十分长的、数字上相关的素数（是另一个大数字的因数）。有一个密钥不足以翻译出消

19、息，因为用一个密钥加密的消息只能用另一个密钥才能解密。每个用户可以得到唯一的一对密钥，一个是公开的，另一个是保密的。公共密钥保存在公共区域，可在用户中传递，甚至可印在报纸上面。而私钥必须存放在安全保密的地方。任何人都可以有你的公钥，但是只有你一个人能有你的私钥。它的工作过程是：“你要我听你的吗？除非你用我的公钥加密该消息，我就可以听你的，因为我知道没有别人在偷听。只有我的私钥（其他人没有）才能解密该消息，所以我知道没有人能读到这个消息。我不必担心大家都有我的公钥，因为它不能用来解密该消息。” 公钥加密体制具有以下优点:（1） 密钥分配简单。（2） 密钥的保存量少。（3） 可以满足互不相识的人之

20、间进行私人谈话时的保密性要求。（4） 可以完成数字签名和数字鉴别。密码分析用户b解密加密用户a 明文m 密文c=e（m，） m=d（c，） 私钥空间公钥空间 （密钥本) 图1.1 公钥密码体制示意图对称密钥：对称密钥是最古老的，一般说“密电码”采用的就是对称密钥。由于对称密钥运算量小、速度快、安全强度高，因而目前仍广泛被采用。 des是一种数据分组的加密算法，它将数据分成长度为64位的数据块，其中8位用作奇偶校验，剩余的56位作为密码的长度。第一步将原文进行置换，得到64位的杂乱无章的数据组；第二步将其分成均等两段；第三步用加密函数进行变换，并在给定的密钥参数条件下，进行多次迭代而得到加密密文

21、。 非对称加密技术：数字签名一般采用非对称加密技术（如rsa），通过对整个明文进行某种变换，得到一个值，作为核实签名。接收者使用发送者的公开密钥对签名进行解密运算，如其结果为明文，则签名有效，证明对方的身份是真实的。当然，签名也可以采用多种方式，例如，将签名附在明文之后。数字签名普遍用于银行、电子贸易等。 数字签名：数字签名不同于手写签字，数字签名随文本的变化而变化，手写签字反映某个人个性特征，是不变的；数字签名与文本信息是不可分割的，而手写签字是附加在文本之后的，与文本信息是分离的。 值得注意的是，能否切实有效地发挥加密机制的作用，关键的问题在于密钥的管理，包括密钥的生存、分发、安装、保管、

22、使用以及作废全过程。2 matlab工具介绍 2.1 matlab语言的主要特点（1）具有丰富的数学功能。 包括矩阵各种运算。如：正交变换、三角分解、特征值、常见的特殊矩阵等。 包括各种特殊函数。如：贝塞尔函数、勒让德函数、伽码函数、贝塔函数、椭圆函数等。 包括各种数学运算功能。如：数值微分、数值积分、插值、求极值、方程求根、fft 、常微分方程的数值解等。（2）具有很好的图视系统。 可方便地画出两维和三维图形。 高级图形处理。如：色彩控制、句柄图形、动画等。 图形用户界面gui制作工具，可以制作用户菜单和控件。使用者可以根据自己的需求编写出满意的图形界面。（3）可以直接处理声言和图形文件。

23、声言文件。如： wav文件（例：wavread，sound等）。 图形文件。如： bmp 、gif 、 pcx 、tif 、jpeg等文件。（4）. 具有若干功能强大的应用工具箱。如：simulink、comm、dsp、 signal等16种工具箱。（5）. 使用方便，具有很好的扩张功能。 使用matlab语言编写的程序可以直接运行，无需编译。 可以m文件转变为独立于平台的exe可执行文件。 matlab的应用接口程序api是matlab提供的十分重要的组件 ，由 一系列接口指令组成 。用户就可在fortran或c中 ， 把matlab当作计算引擎使用 。 （6）. 具有很好的帮助功能 提供十

24、分详细的帮助文件（pdf 、html 、demo文件）。 联机查询指令：help指令（例：help elfun，help exp，help simulink），lookfor关键词（例： lookfor fourier ）。2.2 matlab的程序设计 2.2.1 脚本文件和函数文件m文件有两种形式 ：脚本文件（script file）和函数文件（function file ）。这两种文件的扩展名，均为“ . m” 。（1）m脚本文件: 对于一些比较简单的问题 ，在指令窗中直接输入指令计算 。 对于复杂计算，采用脚本文件（script file）最为合适 。 matlab只是按文件所写的指令

25、执行 。 m脚本文件的特点是： 脚本文件的构成比较简单，只是一串按用户意图排列而成的（包括控制流向指令在内的）matlab指令集合。 脚本文件运行后 ，所产生的所有变量都驻留在 matlab基本工作空间（base workspace）中。只要用户不使用清除指令（clear）， matlab指令窗不关闭，这些变量将一直保存在基本工作空间中。（2）m函数文件: 与脚本文件不同 ，函数文件犹如一个“黑箱”，把一些数据送进并经加工处理，再把结果送出来。 matlab提供的函数指令大部分都是由函数文件定义的。 m函数文件的特点是： 从形式上看，与脚本文件不同 ，函数文件的笫一行总是以 “function

26、”引导的“函数申明行”。 从运行上看 ，与脚本文件运行不同 ，每当函数文件运行， matlab就会专门为它开辟一个临时工作空间，称为函数工作空间（ function workspace） 。当执行文件最后一条指令时 ，就结束该函数文件的运行，同时该临时函数空间及其所有的中间变量就立即被清除。 matlab允许使用比 “标称数目 ”较少的输入输出宗量，实现对函数的调用 。（3）m文件的一般结构: 由于从结构上看 ，脚本文件只是比函数文件少一个“函数申明行”，所以只须描述清楚函数文件的结构 。 典型m函数文件的结构如下 ： 函数申明行：位于函数文件的首行，以关键functio开头，函数名以及函数的

27、输入输出宗量都在这一行被定义。 笫一注释行：紧随函数申明行之后以%开头笫一注释行。该行供lookfor关键词查询和 help在线帮助使用 。 在线帮助文本区：笫一注释行及其之后的连续以%开头的所有注释行构成整个在线帮助文本。 编写和修改记录：与在线帮助文本区相隔一个“空”行，也以%开头，标志编写及修改该m文件的作者和日期等 。 函数体：为清晰起见，它与前面的注释以“空”行相隔。2.2.2 函数调用和参数传递（1）局部变量和全局变量: 局部（local）变量：它存在于函数空间内部的中间变量，产生于该函数的运行过程中，其影响范围也仅限于该函数本身 。 全局（global）变量：通过 global

28、指令，matlab也允许几个不同的函数空间以及基本工作空间共享同一个变量，这种被共享的变量称为全局变量。（2）函数调用: 在matlab中，调用函数的常用形式是：输出参数1,输出参数2, = 函数名(输入参数1,输入参数2, ) 函数调用可以嵌套，一个函数可以调用别的函数，甚至调用它自己 （递归调用）。（3）参数传递: matlab在函数调用上有一个与众不同之处 ：函数所传递的参数具有可调性 。 传递参数数目的可调性来源于如下两个matlab永久变量： 函数体内的 nargin 给出调用该函数时的输入参数数目。 函数体内的 nargout 给出调用该函数时的输出参数数目。 只要在函数文件中包括

29、这两个变量，就可以知道该函数文件调用时的输入参数和输出参数数目。 值得注意：nargin、 nargout 本身都是函数，不是变量，所以用户不能赋值，也不能显示。 “变长度”输入输出宗量：varargin 、 varrgout。具有接受 “任意多输入” 、返回“任意多输出”的能力 。 跨空间变量传递：evalin。2.2.3 m文件的调试（1）编写 m文件时，错误（bug）在所难免。错误有两种：语法（syntax）错误和运行（run-time）错误。（2）语法错误是指变量名、函数名的误写，标点符号的缺、漏等。对于这类错误，通常能在运行时发现，终止执行，并给出相应的错误原因以及所在行号。（3）运

30、行错误是算法本身引起的，发生在运行过程中。相对语法错误而言，运行错误较难处理 。尤其是m函数文件，它一旦运行停止，其中间变量被删除一空，错误很难查找。（4）有两种调试方法：直接调试法和工具调试法。（5）直接调试法：可以用下面方法发现某些运行错误。（6）在m文件中，将某些语句后面的分号去掉， 迫使m文件输出一些中间计算结果，以便发现可能的错误。（7）在适当的位置，添加显示某些关键变量值的语句（包括使用 disp 在内）。（8）利用 echo 指令，使运行时在屏幕上逐行显示文件内容。echo on 能显示m脚本文件；echo funnsme on 能显示名为funnsme 的m函数文件。（9）在原

31、m脚本或函数文件的适当位置，增添指令 keyboard 。 keyboard 语句可以设置程序的断点 。（10）通过将原m函数文件的函数申明行注释掉，可使一个中间变量难于观察的m函数文件变为一个所有变量都保留在基本工作空间中的m脚本文件。 3 rsa公钥密码体制3.1 算法简介公钥加密算法的典型代表是rsa (rivest , shamir , adelman)算法 ，它是公共密钥机制中的一种比较成熟的算法。它是建立在“大数分解和素数据检测”的理论基础上的，两个大素数相乘在计算机上是容易实现的, 但将该乘积分解成两个素数因子的计算量却相当巨大, 大到甚至在计算机上不可能实现，所以就确保了rsa

32、算法的安全性。rsa算法是第一个既能用于数据加密又能用于数字签名的算法， 它为公用网络上信息的加密和鉴别提供了一种基本的方法，因此对它的开发和研究对我们进行知识总结和积累并将所学与实际相结合都有重大的实际意义。3.2 算法的数学基础基于rsa算法的数学定理：定义：设m 是正整数，1，2，3，m 中与m 互素的数的个数记作，称为欧拉函数。定理1（欧拉定理） 若整数a和m 互素，即gcd(a,m)=1,则 特别当p为素数时，对任意的a,有定理2 若m1, gcd(a,m)=1,则存在c，使得 ca1(modm)，称c 为a 的模m 的逆，记作(modm)定理3 若, , ,则有 定理4 （中国剩余

33、定理） 设: 是两两互素的正整数，则对任意的整数一次同余方程组: (i=1,2,k)对模: 有惟一解， 是满足 的一个整数，即对模的逆。3.3 rsa公钥密码算法3.3.1 算法步骤 首先，产生密钥(1)随机选取两个大素数p与q；(2)计算n=p*q（公开），（n）=（p-1）*（q-1）（保密）；(3)随机选取正整数e,使之满足gcd(e,(n)=1,且1e(n);(4)利用欧几里得算法计算d,使之满足ed1(mod(n)，d为保密的解密密钥;(5)用e=作为公钥,用d=作为私钥。其次，加密和解密，用rsa公钥密码体制加密时,先将明文数字化,然后进行分组,每组的长度不超过log(n),再每组

34、单独加密和解密。加密过程如下:假设要加密的明文组为m(0mn),加密过程就是c=e(m)=(mod n),c为密文;解密过程是:m=d(c)=(mod n);m就为恢复出的明文，它应该与前面输入的待加密的明文内容一致。rsa算法整体思路如上所示，在本文中我们就此算法过程用对应matlab语言实现。3.3.2 参数分析rsa 算法的安全性等价于分解n 的困难性，但是在实际的应用中，很多时候是因为算法实现的细节漏洞导致被攻击，所以在rsa算法构造密码系统时,为了保证系统的安全性需要仔细地选择使用的参数。rsa 算法主要的参数有3 个:模数n 、加密密钥e和解密密钥d 。（1）算法模n的确定：rsa

35、模数n =p*q是rsa算法安全性的核心，如果模数n被分解，则rsa公钥密码体制将立刻被攻破，所以选择合适的n是实现rsa 算法的重要环节。一般来讲，模数n的选择可以遵守以下4个原则： n=p*q , 要求p 和q 为强素数（strong prime）；强素数定义如下:存在两个大素数使得；存在4 个大素数，使得；称为三级素数，为二级素数。 p 和q 之差要大，相差几位以上； p 1 与q 1 的最大公因子要小； p 和q 要足够大。这是应用r s a 算法要遵守的最基本原则，如果rsa算法是安全的，则n=p*q 必须足够大，使得因式分解模数n 在计算上是不可行的，下面给出的是一般性使用原则：

36、临时性（casual）384bit，经过努力可以破译； 商用性（commercial）512bit，可由专业组织破译； 军用性（military）1024b it，专家预测十年内不可破译。随着计算机能力的不断提高和分布式运算的发展，没有人敢断言具体的安全密钥长度。（2）算法e 与d 的选取原则：在rsa算法中的条件是很容易满足的，这是因为任意两个随机数互素的概率为，如果e ,d 比较小，加、解密的速度快，也便于存储，但这必然导致安全性问题，一般的e,d 的选取原则如下： e不可过小。经验上e 选16位的素数，这样既可以有效地防止攻击，又有较快的加、解密速度。 最好选e 为的阶数，即存在i ,使

37、得，i 达到，可以有效地抗击攻击。 d 要大于。选定e 后可使用欧几里德算法在多项式时间内计算出d。3.3.3 安全性分析 如果说rsa体制的安全性等价于因子分解，那就是说，作为公钥选择的（e,n）参数，n是不能轻易被因子分解的，否则构造单向函数的t=（n）=(p-1)(q-1)就没有秘密可言了。原因很简单，rsa的安全性依赖于因子分解的困难性，目前因子分解速度最快方法的时间复杂度为：t=o(exp(sqrt(ln(n)ln ln(n)=o()，且n因子被分解，就意味着rsa系统被攻破。反过来，能攻破rsa系统，表明可以分解n的因子，不过这不是绝对的。所以出于安全性考虑，在设计rsa系统时，对

38、n的选择是很重要的。在rsa算法中,若n =p*q 被因数分解,则rsa便被攻破。因为若p,q 已知,则(n)=(p- 1)*(q - 1)便可以计算出,解密密钥d 便可利用欧几里得算法求出。因此rsa的安全性是依赖于因数分解的困难性。在上一节的参数分析中我们重点讲了对各参数选取原则，这里不再重复。在许多实际应用中，人们总希望使用位数较短的密钥d，一是可降低解出或签名的时间，二是能够满足计算能力低于主机的硬件芯片的需求，比如ic卡中的cpu处理。现在我们就分析几个rsa体制的安全性问题。（1）弱密钥情形类似其他密码体制一样，rsa体制也存在弱密钥现象。若已知明文组=123,=183,=72,=

39、30,假定n=pq=17x11=187，取e=7时，可以发现，明文m经过rsa连续变换后，就能恢复原文。比如:根据=rsa（）=（mod n），则有： =183（mod187） =72（mod187） =30（mod187） =123（mod187）这时=，对加密系统来说是不可靠的，必须加以克服。（2）同模攻击的可能性假定两个用户，共享一个模为n的rsa算法，加密密钥分别为，并且gcd(，)=1，如果用户a想加密同一个明文m，分别从，加密得到密文：= mod n和=mod n，分别将送给，送给。而攻击者截获两个密文后，可以通过使用扩展欧几里得算法得到r,s,使得r. +s. =1.然后按下列计

40、算： . mod n=()()mod n= m其中，=为同一明文，表明即使rsa密码系统很安全，但攻击者破获a发送的明文也是可能的。所以实际中建议不同用户不可使用公共的模n。除此之外，不同用户选用的素数也是不能相同的。否则，任何人都可以用欧几里得算法获得（，）= p，结果容易得到，的分解式。（3）由密文泄露明文相关的部分信息量与其他一些密码弱点一样，rsa体制同样存在将明文的部分信息由密文泄露出去的可能。比如给定密文：c=mod ，由可知，其中e必为 奇数情形。根据jcaobi符号容易推出. 因此，只要给定一个密文c，不用通过解密密文就能有效的计算出结果，即反映了在rsa密码系统中，通过加密密

41、文也会泄露一些有关的明文信息。 3.4 公钥密码体制中安全大素数的生成构造rsa公钥密码体制,关键就在于选取大素数p ，q 。产生素数的方法可分为以下两类:确定性素数的产生方法和概率性素数的产生方法。确定性素数产生方法的优点在于产生的数一定是素数,缺点是产生的素数带有一定的限制;而概率性素数产生方法的缺点在于它不能证明该数是素数,也就是说,产生的数只能是伪素数,为合数的可能性很小。但这种可能依然存在。优点在于使用概率性素数产生方法,产生的伪素数速度很快,构造的伪素数无规律性。于是在构造rsa体制中的大素数时,首先利用概率性素数测试产生伪素数,然后再利用确定性素数测试法进行检验,这样可以发挥二者

42、的优越性。所以文中的算法基于这个原理,预先对密钥素数进行筛选,采用montgomery模乘算法优化的概率性素数产生方法miller-rabin算法进行检测,最后用确定性素数产生方法pocklington定理进行验证。3.4.1 素数筛选对于产生的大数,在进行后面的素数判别时会比较耗时,所以,在把大数送入到素数判别程序前,将一些容易判别出的合数过滤掉。这里采用大数除以小素数过滤掉一部分合数,选取53个小素数进行对大数的过滤。算法的步骤如下:(1) 随机产生一个大整数n ;(2) 选取从2 开始的一组个数约为53个的素数,记为ai ;(3) i 0;(4) 当i 53时,计算y n (mod ai

43、);(5) 若y = 0,表示没有余数,则数n 不为素数,结束;否则,i i+ 1,转(4);(6) 若i= 52,返回n 为素数。3.4.2 素数检测素性检测就是判断一个整数是否为素数的准则。最简单的素性检测就是“试除法”,对于给定的数n ,用p 进行试除(0p)。检测一个数n 是素数的最确定的方法就是验证它不能被2和之间的任何数整除,但这种方法计算量太大,十分耗时,在实际中需要更有效的素性检测方法。miller- rabin算法检测是实际中应用最多的素性检测,它在计算上较省时、容易实现且错误概率较低。(1). miller - rabin算法miller-rabin算法是fermat算法的

44、一个变形改进,它的理论基础是由fermat定理引申而来。fermat定理:n是一个奇素数,a是任何整数(1an-1) ,则a= 1(mod n)。miller-rabin算法的理论基础:如果n是一个奇素数,将n-1= 2m ,r是非负整数,m是正奇数, a 是和n互素的任何整数,那么a1(mod n)或者对某个h(0hr-1),等式a 1(mod n)成立,其中w =2m 。这个理论是通过一个事实经由fermat定理推导而来:n是一个奇素数,则方程x=1mod n有1两个解。miller-rabin算法的步骤如下: 将n-1表示成2m(其中r 是非负整数, m 是正奇数) ; 随机产生一个整数

45、a(1an-1); i0 ,计算xa(mod n); 若x=1或x=n-1,则n 通过测试,转(7); 若i=1,则n为非素数,结束;否则转(6); 当ir 时,ii+1,xx(mod n),若x=n-1,则n 通过测试,转(7)。否则转(5); 返回n为素数。miller-rabin算法并不是一个确定算法。若n 是奇合数,则n通过以a 为基的miller-rabin算法测试的数目最多为(n-1)/4,1an - 1。若n 是正整数,选k个小于n 的正整数,以这k 个数作为基用miller-rabin算法进行测试,若n 是合数,k 次测试全部通过的概率为(1/4)。比如: k = 100, n

46、 是合数, 但测试全部通过的概率为(1/4), 这是很小的数,说明这样的事情几乎不可能发生。(2). 采用montgomery 算法进行优化miller-rabin算法最耗时的步骤是(3)和(6)的模幂运算。montgomery算法将部分积对任意的n 取模转化为对基数r 取模,简化了计算过程, 提高了模幂运算的速度.montgomery算法的理论基础是:设n 和r是互素的两个整数,且rr- nn=1(n=-nmod r) ,则对于任意整数t,当m = tnmod r 时,( t+ mn)/r 为整数,且满足(t+mn) / r =trmod n 。上述理论中,t+mn =t+(tn- kr)n

47、 =t(1+ nn)-krn = trr - krn ,为r的倍数,所以(t+mn)/r为整数。又因为t+ mn =t modn , 所以可以很容易推导出(t+ mn)/r= trmodn 。可以看出,montgomery在算法中选取0 t n r ,这样(t+mn)/r2n ,(t+mn)/r与trmod n 也就至多相差一个n ,只需一次额外的大数减法。这样就给出了满足0tnr 的任意整数t时tr mod n的快速算法, 那么就可以类似于abmodn 的模乘运算,其中0a ,b n 。所以s=mon(a ,b ,n)=a*b*rmod n的计算步骤如下: 计算aar mod n ,bb r

48、 mod n ,tab; 选择与n互素的基数r ,并选取r和n,满足0r n 及0 n t; 计算s t+(tmod r )nmod rn/r ; 若sn , s=s-n ; 返回s 。然而,这样计算出的结果s 并不是严格意义上的模乘abmod n ,而是多了一个因子r,那么模乘abmod n 可以通过两次montgomery算法得到,即:abmod n =(a*b *rmod n)*rmod n =mon(a,b,n) *r mod n = s*1*r mod n =mon(mon(a ,b,n),1,n)。所以模幂运算z=a(mod n) 的计算步骤如下: im -1; 计算zmon(a,

49、1,n); 计算zmon(z,1,n); ii- 1,若i 0,转(3),否则转(5); 返回z。可以看出, 如果仅仅是求模乘运算,montgomery算法需要用到一般的模运算和模逆运算进行预处理,montgomery算法并不能有任何速度上的提高,但对于模幂运算,模幂运算中约有(3log e)/2次的模乘运算,这样预处理时,只要处理一次就可以进行多次的没有除法的montgomery模乘运算,这样将大大提高模幂运算的速度,进而提高miller-rabin算法的速度。(3). 素数验证采用pocklington定理对素数进行验证,基于pocklington定理的确定性素数产生方法,它需要已知n -

50、 1的部分素因子。pocklington定理:设n = r *f + 1, 这里f=,其中q,q,q是不同的素数,若存在a 满足:a1(mod n)且gcd(a- 1,n) = 1,其中j =1, r 。那么n 的每一个素因子p 都有p=f *m + 1的形式(m 1)。于是若f ,则n 为素数。则此算法的步骤如下:, 分解n - 1,使n - 1= r f ,其中f ; 分解f ,使f = ,其中q( j = 1,2,r)为不同的素数; a 1; a a + 1; 若a (mod n) = 1,则转(7); 转(4) ,否则n 可能不是素数,转(8); 若对于任意的j(j =1,2,r),g

51、cd(a- 1,n)= 1,则n 是素数,否则转(4); 退出。3.5 rsa的matlab实现3.5.1算法原理 rsa算法的理论基础是数论中的欧拉函数，他的安全性基于大数分解的困难性，在理论上要计算两个大素数的乘积是容易的，但反过来要把一个大数分解成两个素数因子相乘的形式是很困难的，正是由于这个原因保证了此算法的安全性。rsa的安全性依赖于大数分解。公钥和私钥都是两个大素数 （ 大于 100个十进制位）的函数。据猜测，从一个密钥和密文推断出明文的难度等同于分解两个大素数的积。 密钥对的产生:选择两个大素数，p 和q 。计算：n = p * q 。然后随机选择加密密钥e，要求 e 和 ( p - 1 ) * ( q - 1 ) 互质。最后，利用euclid 算法计算解密密钥d, 满足 e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) ) 其中n和d也要互质。数e和 n是公钥，d是私钥。两个素数p和q不再需要，应该丢弃，不要让任何人知道。 加密信息 m（二进制表示）时，首先把m分成等长数据块 m1 ,m2,., mi ，块长s，其中 2s = n, s 尽可能的大。对应的密文是：ci = mie ( mod n ) ( a ) 解密时作如下计算： mi = cid ( mod n ) ( b )算法流程（1）. 产生密