实验报告3----RSA

陕西师范大学数学与信息科学学院信息安全实验报告学号________姓名__班级______时间_____成绩______实验名称公钥密码算法RSA实验目的通过编程实现RSA的加密和解密过程，加深对公钥（非对称）密码算法的认识。实验原理公钥密码算法是指一个加密系统的加密密钥和解密密钥是不同的，或者说不能用其中一个推导出另一个。在公钥密码算法的两个密钥中，一个是用于加密的密钥，它是可以公开的，称为公钥；另一个是用于解密的密钥，是保密的，称为私钥。公钥密码算法解决了对称密码体制中密钥管理的难题，并提供了对信息发送人的身份进行验证的手段，是现代密码学最重要的发明。RSA密码体制是目前为止最成功的公钥密码算法，虽然它的安全性还未能得到理论证明，但经过20多年的密码分析和攻击，迄今仍然被实践证明是安全的。RSA算法描述如下：1．公钥选择两个互异的大素数p和q,n是二者的乘积，即n二pq使D(n)=(p-1)(q-1),D(n)为欧拉函数。随机选取正整数e,使其满足gcd(e,(D(n))=1，即e和D(n)互质，则将(n,e)作为公钥。2.私钥求出正数d,使其满足ed=1modD(n),则将(p,q,d)作为私钥。3.加密算法对于明文M,由C=Memodn，得到密文C。4.解密算法对于密文C,由M=Cdmodn,得到明文M如果窃密者获得了n,e和密文C,为了破解密文必须计算出私钥d，为此需要先分解n为了提高破解难度，达到更高的安全性，一般商业应用要求n的长度不小于1024位，更重要的场合不小于2048位。实验环境运行Windows的PC机，具有VC++等c语言编译环境。实验内容(1)编程实现模n的大数幂乘的快速算法（dashumicheng.c），随机输入3个较大的数x,e,n,输出计算xemodn(2)编程实现模n求逆的算法(moni.c)，计算私钥。(3)编写RSA解密程序(jiemi.c)，完成文件data.txt中内容的解密，以字符形式输出明文。已知系统公开参数为n=18923,e=1261。实验过程1.首先编写模n的大数幂乘的快速算法，即计算x^r(modn)，此算法的计算过程是：（1）当x的指数为偶数时，指数变为原来的1/2，x等于x*x(modn)；（2）当x的指数为奇数时，指数自减1，x的系数等于原来的值乘上x后模n；（3）重复上述步骤，直到x的系数为0，即得计算结果。核心的算法程序为：while(b!=0){if(b%2==0){//当n为偶数时的运算b=b/2;a=(a*a)%n;}else{//当n为奇数时的运算b=b-1;c=(c*a)%n;}}returnc;2.首先编写模n求逆的函数，求逆运算的思想是辗转相除法，具体过程为：n1=n;n2=u;b1=0;b2=1;q=n1/n2;r=n1-q*n2;while(r!=0){n1=n2;n2=r;t=b2;b2=b1-q*b2;b1=t;q=n1/n2;r=n1-q*n2;}此时应注意，如果计算出的n2不为1，则说明所给的书模n不存在逆元，反之，则存在逆元。如果计算出的逆元为负，则应给该数加上n，算法程序如下：if(n2!=1)coutu模n不存在逆元endl;if(n2==1){d=b2%n;if(d0)d=d+n;coutu模n的逆元为：dendl;}return(d);3.求n的欧拉函数，先将n分解为两个素数的乘积q*p，则n的欧拉函数为（q-1）*(p-1)；先分解n，分解的过程要检验q和p是否为素数，具体实现过程如下：for(p=2;pn/2&&flag==0;p++){if(n%p==0){a=1;for(inti=2;ip&&a!=0;i++){//检验p是否为素数a=p%i;}if(a!=0){q=n/p;b=1;for(intj=2;jq&&b!=0;j++){//检验q是否为素数b=q%j;}if(a!=0&&b!=0)flag=1;}}}4.编写解密程序时，首先根据已给的n和e，调用前面的编写的求n的欧拉函的程序求出欧拉函数，在调用模n求逆的算法计算解密密钥d。从已知的数据文件data.txt中读取数据，c语言中已经提供了这一类函数，fopen，其调用格式为FILE*fp；fp=fopen(“文件名”,”r”)打开文件的方式通常为if(fp==NULL){printf(can'topenfile\n;exit(0);}然后调用大数幂乘的快速算法对输入的密文进行解密。5.对解密后的明文进行处理。考虑到每个数字明文对应一个26的三次多项式，而多项式的系数即对应字母明文对应的0到25的数字。即a1=m1/(26*26);a2=(m1-a1*26*26)/26;a3=m1-a1*26*26-a2*26;于是，通过求整系数的规则，求得每一个密文，对应的明文的数字。若想转化成大写字母，则给相应的数字加上‘A’，若要求变成小写字母，则加上‘a’，最后输出就得到实验要求的明文。实验结果实验心得从实验的设计思想上看，这次的实验比上两次的实验都要复杂，本次实验需要有很强的逻辑性；从实验编写过程来看，本次试验相对上两次实验要简单一点，只要把每一步都做好，然后把每一个程序块组合在一起就能减少错误。而且有了上两次的实验基础，这次实验实现起来明显比上两次更容易上手，但在编程过程中也有不少的问题，但解决问题的过程也是发现不足，积累知识的过程。编程的过程也让我们更好的理解和掌握RSA加密算法的实现过程。