RSA加密算法实验报告

四川大学计算机学院实验报告学号：姓名：班级：班第周试验课程名称信息安全课程设计实验课时2实验项目RSA加密算法的实现实验时间2013.06.02实验目的通过编程实现RSA的加密和解密过程，加深对公钥（非对称）密码算法的认识。实验环境Windows8VS2012实验内容（算法、程序、步骤和方法） 实验原理：公钥密码算法是指一个加密系统的加密密钥和解密密钥是不同的，或者说不能用其中一个推导出另一个。在公钥密码算法的两个密钥中，一个是用于加密的密钥，它是可以公开的，称为公钥；另一个是用于解密的密钥，是保密的，称为私钥。公钥密码算法解决了对称密码体制中密钥管理的难题，并提供了对信息发送人的身份进行验证的手段，是现代密码学最重要的发明。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位。 实验内容编程实现模n的大数幂乘的快速算法（dashumicheng.c），随机输入3个较大的数x,e,n,输出计算xemodn编程实现模n求逆的算法(moni.c)，计算私钥。编写RSA解密程序(jiemi.c)，完成文件data.txt中内容的解密，以字符形式输出明文。已知系统公开参数为n=18923,e=1261。实验准备：对RSA公钥密码体制进行分析，它是基于大整数素分解问题，且包含参数：n公开参数，e公钥，以及解密参数p,q，其中p，q是两个大素数，是关于p，q的参数，d是解密密钥，由，e计算所得。根据参数分析以及必要的数学基础分析，需要两基本算法：模n的大数幂乘的快速算法；模n求逆的算法。算法实现需要参数导入。算法的分步实现根据算法首先对密文数据进行文件导入并存入相应的数组：if((fp=fopen("data.txt","r"))==NULL){printf("cannotopenthefile\n");exit(0);}while(!feof(fp)){fscanf(fp,"%d",&c[i]);i++;}sl=i-1;printf("打开文件密文数据:\n");for(j=0;j<i-1;j++){printf("%d",c[j]);if(j>0&&j%10==0)printf("\n");}}整数的素因子分解输入数据n=18923，利用遍历算法寻找n的因子；对n的因子数据p，q进行素数检验；for(i=n-1;i>1;i--)if(n%i==0){p1=i;q1=n/i;for(i=2;i<=p1;i++)if(p1%i==0)break;if(i==p1)p=p1;elsecontinue;for(j=2;j<=q1;j++)if(q1%j==0)break;if(j==q1)q=q1;elsecontinue;}③根据以上算法，可以得数据：p=127，q=149；3、模n求逆算法①根据2所得的p，q进行求解求得=18648；②输入数据e=1261，并根据，并对算法进行分析利用辗转相除的原理实现算法求逆；n1=nn;n2=e;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;}if(n2==1){d=(b2+nn)%nn;printf("请输出逆元：%d\n",d);}elseprintf("逆元不存在：");}③根据以上算法，可以得数据：d=5797；4、大数幂乘算法①根据导入数据的参数密文c：12423115247243745914303612710964163999272 13629调用，以及进行求解m：for(i=0;i<sl;i++){charm1[100];c1=1;j=0;a=c[i];b=d;while(b>0){if(b%2==0){b=b/2;a=(a*a)%n;}else{b=b-1;c1=(c1*a)%n;}}②根据算法可得明文数据：5438136429251457114303574688054588114440数字转化为字符将所得的数字数据转化为字符数据：for(i=0;i<sl;i++){intj=0;charm1[100];while(m[i]!=0){m1[j]=m[i]%26+'a';m[i]=m[i]/26;j++;}将所得的字符数据的方向输出：for(k=j-1;k>=0;k--)printf("%c",m1[k]);printf("%c",'');}输出的数据：ibecameinvolvedinanargumbsabo实验数据记录打开文件密文数据:1242311524724374591430361271096416399927213629请输出n的值:18923请输出p、q的值：127149请输出nn的值：18648请输出e的值：1261请输出逆元：5797请输出明文：5438136429251457114303574688054588114440请输出明文：ibecameinvolvedinanargumbsaboPressanykeytocontinue结论（结果）这个实验的算法实