RSA算法的实现论文

分类号： 10621007) 6056：公 开 编号：2003212004成 都 信 息 工 程 学 院学 位 论 文吴俊杰申请学位专业： 计算机科学与技术申请学位类别： 工学学士指导教师姓名（职称）：游洪跃（副教授）论文提交日期： 2007年06月09日本文设计的是一套完整实用的具体编码实现。本文采用费马小定理测试素数，使用C+实现在32位现可以对任意文件进行过加密的文件以及密钥文件都是文本文件。本文首先给出关键类类图、整个应用程序的结构描述文档，然后对关键模块流程图、详细的接口文档进行阐述，并给出关键的实现代码，最后对应用程序进行测试，对测试结果进行分析研究，进而对应用程序进行改进，对关键算法进行尽可能的优化，最终得到一个在一些相关的可移植组件。关键词： 件加密；马定理a of SA is to to of of +, to on On is of In of it of In an SA 论文总页数：35页1 引言.课题背景.需求分析与总体设计.各部分的设计与开发.核心类库.核心类库的.件整体测试与分析改进.编写测试各项性能需要的精确计时类.测试数据与分析改进.35页1 易于理解和操作，也十分流行。算法的名字以发明者的姓氏首字母命名：然自1978年提出以来，它经历了各种攻击，至今（2006年）未被完全攻破。随着越来越多的商业应用和标准化工作，采用了标准使得上交易加密连接、网上银行身份验证、各种信用卡使用的数字证书、智能移动电话和存储卡的验证功能芯片等，大多数使用今公钥加密更广泛应用于互联网身份认证，本课题将公钥加密算法任意文件加密成文本的解决方案，使其使用更加灵活。整个工程的分层设计，给引用移植和后续开发带来便利。素数p，q，令n=p(素的整数e，由方程de=1 (解出d，二元组(e,n)作为公开密钥，二元组(d,n)作为私有密钥b=ae n，c=bd c (n)经得到了广泛认可和应用。发展至今，电子安全领域的各方面已经形成了较为完备的国际规范。各领域的应用数不胜数。技术成熟的要集中在密连接、数字签名和数字证书的核心算法广泛使用常应用中，有比较著名的工具包一个安全传输协议，在35页件包，由加拿大的 发起编写的。相关详细介绍见)。经在各种操作系统得到非常广泛的应用。另外，家喻户晓的然也实现了成了使用合要用于数字证书和数字签名，对于习惯于使用网上购物和网上银行的用户来说，几乎天天都在使用难看出所以只应用于这些短小数据的加密解密，是因为度是是因为这样，把常文件被想象成大数据块，但是实际上在日常应用中，有些极其重要的文本资料是并不太大的，比如因担心遗忘而用普通文本记录的银行帐号和密码、不应被陌生人知道的重要电话号码、几千字节大的重要小图片等。虽然是在于几千字节的数据进行一次几百位密钥的消耗的时间应该是可以接受的。下面结合大数运算程序的调试，从理论上简单的分析消耗时间。在一台普通配置的为公开密钥的以指数取一个小整数，比如一个70字节长的整数(140位十六进制，大数单元以线性组方式实现，对应到相当于约560调试一个函数测试，按初等数论中的知识对程序进行算法优化，最终在一台配置为外频333理内存512果按这种速度，逐字节对1消耗的时间理论上为45毫秒的1024倍即约45秒。这个时间并不是非常长。其实从一个简单的角度来说，既然就完全可以用于同样大小的普通文件。对于较大的文件，如果分成与数字签名同样大小的段(这里假设数字签名较短，不分段一次计算加密完成)，分开的各段逐一进行加密运算，那所需要的时间也只是按文件大小线性的增长。通常数字签名为几十字节，加密运算并不需要很长的等待，这就说明对于几百字节或一两果进行不会是非常漫长的工作。当然，如果文件更大，加密就显得十分漫长了。比如按前面叙述的45毫秒大数运算程序推理，加密1以，要在普通35页件不能过大，一般可以接受的上限是几果要在较短时间内加密大文件，需要缩短密钥长度以减小运算量，这将带来安全性隐患。本文的第3章将根据实际调试好的软件，测试给出具体的时间消耗数据。例如，在一台配置为外频333理内存512560常记录如银行帐号密码等重要数据的文本文件大小不足百字节，加密只需要数秒钟。所以对于小型文件，进行较长密钥的 型文件加密可以使用如，因担心遗忘而用普通文本记录的银行帐号和密码、不应被陌生人知道的重要电话号码、几千字节大的重要小图片等。可行的方法未必是必要的，本小节讨论何种文件适合用非对称密钥加密，即于前面叙述的带有重要信息的小型文本和二进制数据的维护，如果不加密，将无法放心的保存在计算机上，尤其是连网的或机房里的公共计算机。如果借助功能强大的大型多用户数据保护程序维护几个小型文件，显得十分烦琐，好比杀鸡用牛刀。如果采用对称密钥加密，即加密解密的密钥相同，只适合部分情况。在某些情况下，使用对称密钥加密文件，交流使用不够方便。比如，张三由于某种原因，需要将自己的某个文件在公共计算机上留给李四，而不希望别人看到内容。如果采用对称密钥加密，张三和李四提前约好一个密码就可以。但是如果张三想要在同一台公共计算机上再留一个秘密文件给王五，而不希望别人看到，就要和王五另外约定一个密码。如果需要在这台公共计算机上留十个文件给不同的人，自己就要记和十个人约定好的密码，这样以来交流起来不够方便，因为对于张三，要自己维护太多的密钥。非对称密钥(公开密钥方式)恰好解决这样的问题。只要大家都在这台计算机或这台计算机可以访问到的地方，留下自己的公开密钥，一切就变的容易解决了。张三要留给李四的文件，就用李四的公开密钥加密，要留给王五的文件，就用王五的公开密钥加密。李四和王五只要把留给自己的文件用自己的私有密钥解密，就可以得到留给自己的文件了。显然，非对称密钥体制更适合多用户交流，而将这种加密方式直接应用于文件加密，使我们在公开场合的交流更加灵活方便。综上所述，使用前面叙述的方式加密文件有两点重要意义：应用非对称密钥加密任意文件，使非对称密钥的应用不仅仅局限于互联网络。非对称加密后的数据变换成文本，使得我们可以通过几乎任何方式安全传递任意文件，比如在只有4页 共35页2 们可以将对软件的要求总结如下：可以按要求的位数生成非对称密钥。可以用指定密钥以密生成的数据为纯文本。可以装载加密过的文件，并用指定的密钥解密还原出原文件。提示信息完整、操作舒适、图形界面雅观按上述描述，给出2般来说，需要进行编码的程序有任意文件的读取 各环节必要的数据编码转换图形操作界面。程方案选择综合考虑复用性、可维护性和执行效率，较妥当的方法是分层设计。核心的类库实现，针对用户所在的操作系统封装成本地化组件。其他各功能如文件操作、数据编码转换和图形界面等，由托管代码借助虚拟机平台标准库的功能快速开发实现(述，选用计模式上是完全类似的)。这种开发方式，核心功能集中在最底层，在不断的封装中针对具体环境对组件功能不断扩充，任意一个层面的封装都可以被直接应用到其他项目，比如在35页组件、给嵌入式设备交叉编译算法库等。但是每一层都需要依赖底层的所有组件。图22合考虑复用性、可维护性和执行效率的分层设计选用这种设计方案，上层使用C#，底层算法使用C+，可以由一个调试带来极大的方便。整个工程分四层，实现核心类库、封装C+核心类库的虑到工作量，本软件加解密数据没有严格遵从，而是在满足设计要求的前提下，以一种尽可能简单的方式实现加密和解密。现核心类库1. 大数存储和四则运算根据了实现大数的各种复杂运算，需要首先实现大数存储和基本四则运算的功能。当今开源的大数运算C+类有很多，多用于数学分析、天文计算等，本文选用了一个流行的大数类型，并针对面简单介绍大数存储和四则运算的实现原理。最先完成的功能是大数的存储，存储功能由普通的类型一样，每一个大数对应一个一个无符号整数指针块内存空间用来存储一个大数，所以可以说，大数是被存储在一个以方法x)中通过C+的会调用是第6页 共35页当储空间并不会自动紧缩，这是为了在运算的时候提高执行效率。结合指针a，有两个重要的无符号整数来控制存储，n，数字变大不断增大，不会自己紧缩，而成一个大数的各量型以对于个大数最大可以达到 2*32个字节长，这已经超过了32位机通常的最大内存容量，所以是足够进行2a 存空间图2-3 其派生，得到实现强制转换运算符方便大数类型和普通整数的互相赋值。当大数被强制转换为取其最低四字节的值。四则运算实现的原理十分简单，都是按最基本的算术原理实现的，四则运算过程的本质就是按一定数制对数字的计算，比如相加，就是低位单元对齐，逐单元相加并进位，减法同理。而乘除法和取余也都是按照竖式运算的原理实现，并进行了必要的优化。虽然实现了四则运算函数，但是若是程序里的运算都要调用函数，显得烦琐而且看起来不美观，所以我们另写一个类联(使用样，当我们操作可以像使用一个简单类型一样使用各种运算符号了。之所以将是为了提高执行效率，因为大型对象的拷贝要消耗不少机器时间。2. 大数幂模与乘模运算数的存储和四则运算的功能都完成了。考虑到要准备实现这些运算的方法。所以写一个35页的友元，完成幂模运算功能。幂模运算是法中比重最大的计算，最直接地决定了法的性能，针对快速幂模运算这一课题，西方现代数学家提出了很多的解决方案。经查阅相关数学著作，发现通常都是依据乘模的性质 ，先将幂模运算化简为乘模运算。通常的分解习惯是指数不断的对半分，如果指数是奇数，就先减去一变成偶数，然后再对半分，例如求D= E=15，可分解为如下6个乘模运算。1 12 223 34 4445 556 归纳分析以上方法，对于任意指数E，可采用如图2第8页 共35页开始D=1;P=? E= =E/2结束模运算分解为乘模运算的一种流程按照上述流程，列举两个简单的幂模运算实例来形象的说明这种方法。求 17值开始 D=1 P= 27=2 E =15=n=2 P= n= 4 E=(2 =7=n=8 P= n= 16 E=(2 =3第9页 共35页=n=9 P= n= 1 E=(2 =1=n=9 P= n= 1 E=(2 =0最终D=9 即为所求。求 13值开始 D=1 P= 23=2 E =8=1 P= n= 4 E =E/2 =4=1 P= n= 3 E =E/2 =2=1 P= n= 9 E =E/2 =1=n=9 P= 不需要计算 E =(2 =0最终D=9 即为所求。观察上述算法，发现以要知道需要如何乘模变量，并不需要反复对E 进行除以二或减一除以二的操作，只需要验证E 的二进制各位是0 还是1 就可以了。同样是计算 ，下面给出从右到左扫描二进制位进行的幂模算法描述，设中间变量D,P,0。,E,n) D=1;P=n; to i=1)D=D*P(n);P=P*P(n);有些文献将上述算法称为平方乘积二进制快速算法，例如参考文献中的基于其实这种算法本质上和图2是把根据指数奇偶分开的减一和除以二合并成对指数二进制各位的判断而已。在本软件的代码中采用直接扫描下的问题就是乘模运算了。提高乘模运算的速度是提高模幂运算速度的关键。一般情况下，普通的除法求模而进行乘模运算是不能满足速度的要求的。为此，要著作发表于1985年），从而避免了通常求模算法中费时的除法步骤。本软件仅仅是应用哥马利)算法，算法的具体第10页 共35页推导证明需要颇多数论知识，不在本文的讨论范围内，如需了解可参见蒙哥马利的相关著作。下面简单描述哥马利)算法供参考理解源程序。选择与模数k，n=n)n;x;,E,n) /蒙哥马利幂模 D=C*R n;i=0;第11页 共35页 的当前二进制位1)D=M(D*P); /从低位到高位检测二进制位 i+=1;if(i=M(P*P);*n);在具体的实现中，对应局函数用的时候直接调用. 寻找素数实上，当今的计算机还不足以聪明到立刻计算生成一个很大的随机素数。一般来说，要得到100%准确的大素数，都是通过查已经计算好的素数表的方式。但是素数表的方式给为攻击者如果得到了密钥生成时所使用的素数表，攻破程序起初使用素数表的方式，后来考虑到安全性问题，生成密钥的方式改为随机计算生成。这样，短时间内如果要得到一个100%准确的大素数是很困难的，只能以尽可能高的概率得到一个大素数。有的大数运算功能都准备完毕，在此基础上，本工程将寻找素数的功能置于类部只要调用本类实例的成员 就可以以大数到一个数，这个数是素数的概率很大。下面介绍寻找素数的原理。首先在需要寻找素数的整数范围内对整数进行筛选，把所有确知为合数的整数排除出去。程序中构造了一个数组b，大小为一轮素数搜索的范围，记搜索范围大小为SS。b0到b别对应大数S。b中所有元素先初始化为1，如果对应的大数确定为合数，就将b中对应的元素置为0。最后，只需对那些b中为1的元素对应的大数进行比较确切的素数测试即可，只要被测试的数是素数概率达到一定门限，就判这个数为素数。这样做既保证了这段程序可以在短时间内执行完，又保证了可以以比较高的准确度得到素数。函数的所有元素赋值为1，然后按参数的各元素赋 0 值。下面描述标记数组 b的赋 0 值算法。首先，在类造函数中从2开始搜寻一些小素数，记录在第12页 共35页数组中，共记录些小素数用来当作因子，他们的倍数将被从大素数搜索范围内剔除(即把数组b的对应元素标记为0)，剔除的程序代码如下。i=0;inp;i+) p=pli;r=p);if(r) r=r br= 0;r+= p;这里利用到当前中的对应位置，将其剔除后，不断后移这个小素数因子图2完成对所有小素数因子的类似操作后，他们的倍数在搜索范围内的位置标记br被全部标记为0。实际上这就是2素数搜索范围内剔除小素数因子可能为素数的数(即标记数组b中值为1的元素对应的数)进行素数测试。数论学家利用费马小定理研究出了多种素数测试方法，本程序使用一种最简单的方式，直接应用费马小定理。取一个与于大素数p=1，但是我们把足这个关系的数不一定是素数。这时我们改变A，进行多次测试，如果多次测试都通过，这个数是素数的概率就比较大。按这种原理，我们编写素数测试函数如下。p ) 4; /测试次数第13页 共35页= 2,3,5,7; /测试用的底数i=0; ii+=1 )if(i, ), p)!= );/上一小节叙述的算法编码。/这里ip。;测试通过，程序就判定这个数为找到的素数，将找到的素数返回给上层程序使用。在这里其实有一个不可忽视的问题，就是得到一个测试通过的合数。对于这种情况，一个需要从数学角度论证的问题。因为得到素数的概率很高，经过一整天的生成密钥和加密操作，没有发现失败的密钥，所以本文暂没有对这个问题进行讨论。实际得到素数的流程：(1) 先得到一个随机的大整数2) 确定一个寻找范围的大小(N,N+围内的小素数倍数去掉，即前面叙述的古希腊某人发明的筛选法小素数因子从开始取，取几百个(论文中将小素数因子个数记为(3) 对范围内没有去掉的数逐一进行素数测试，一个数如果通过测试次数达到一定标准，就判为素数(4) 如果范围内没找到素数，就令N=N+到(2)继续寻找用以上算法，直到以某成功概率得到素数为止综上所述，总结素数寻找的流程，如图214页 共35页开始按S ;i=0计数iSS?bi=1?判定为素数?1;i+=1结束返回素数寻找结果数q，我们就可以计算出密钥，进行加密等操作了。4. 二元一次不定方程在法中，往往要在已知A、得 (AB) = 1。即相当于求解B、的最小整数解。而针对不定方程 的最小整数解，古今中外都进行过详尽的研究，西方有著名的欧几里德算法，即一种辗转相除法，中国有秦九韶的“大衍求一术”。欧几里德算法是一种递归算法，较容易理解。下面举例说明用欧几里德算法求解二元一次不定方程的最小整数解。给定不定方程11，求最小的x（1） 111 49（2） 111 11=1第15页 共35页（3） 50逆向代入：令y=0 代入（3）得x=1令x=1 代入（2）得y=2令y=2 代入（1）得x=9x=9;y=2即为所求。程序中，全局函数a, m )用来完成这种算法。对应前面的叙述，参数数数返回值即为. 现算 法 在 此 不 再 赘 述 ， 法 协 议 见（)。为了方便阅读，整个类的源程序中，所使用的变量字母均和类行准备一对随机密钥的操作。之后可以直接使用类的其他成员进行中各成员频繁的用到字符串和为大数是用字符串置入的，而把大数读出，也是保存在字符指针指向的一段内存空间里，所以也是字符串。所以，需要实现一系列的编码转换函数，比如将示成十六进制形式的字符串文本。编码转换通常是用要加密和解密的数据也是通过字符串参数置入的。由于字符串的结尾字符“0”实际上也可能是需要加密的数据，所以置入的串长度并不能以“0”来决定，程序里引入一个样就解决了加密连0数据时候被截断的问题。因为是对文件加密的软件，需要加密的数据通常并不止几字节，本软件默认的分块大小是1字节，即逐个字节作为参数，调用C+核心模块中的方法。加密解密流程均为标准体过程见下图：生成密钥：第16页 共35页图2 ;b=;i=0;ii+)54.0*);if(0)bi=bi=1; s1=b);i=0;ii+) 54.0*);if(0)bi=bi=1;s2=b);第17页 共35页加密过程：图235页图2e)/公