信息安全-RSA加密算法实验报告

实验报告学号：2011221104220026姓名：孙元喜课程名称信息安全课程设计实验课时n实验项目RSA加密算法的实现实验时间2013.06.02实验目的通过编程实现RSA的加密和解密过程，加深对公钥（非对称）密码算法的认识。实验环境Windows7VS2012实验内容（算法、程序、步骤和方法）实验原理：公钥密码算法是指一个加密系统的加密密钥和解密密钥是不同的，或者说不能用其中一个推导出另一个。在公钥密码算法的两个密钥中，一个是用于加密的密钥，它是可以公开的，称为公钥；另一个是用于解密的密钥，是保密的，称为私钥。公钥密码算法解决了对称密码体制中密钥管理的难题，并提供了对信息发送人的身份进行验证的手段，是现代密码学最重要的发明。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位。实验内容(1)编程实现模n的大数幂乘的快速算法（dashumicheng.c），随机输入3个较大的数x,e,n,输出计算xemodn(2)编程实现模n求逆的算法(moni.c)，计算私钥。(3)编写RSA解密程序(jiemi.c)，完成文件data.txt中内容的解密，以字符形式输出明文。已知系统公开参数为n=18923,e=1261。一、实验准备：1、对RSA公钥密码体制进行分析，它是基于大整数素分解问题，且包含参数：n公开参数，e公钥，以及解密参数p,q，n其中p，q是两个大素数，n是关于p，q的参数，d是解密密钥，由n，e计算所得。2、根据参数分析以及必要的数学基础分析，需要两基本算法：模n的大数幂乘的快速算法；模n求逆的算法。3、算法实现需要参数导入。二、算法的分步实现1、根据算法首先对密文数据进行文件导入并存入相应的数组：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;ji-1;j++){printf(%d,c[j]);if(j0&&j%10==0)printf(\n);}}2、整数的素因子分解①输入数据n=18923，利用遍历算法寻找n的因子；②对n的因子数据p，q进行素数检验；for(i=n-1;i1;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进行求解)1(*)1(nqp求得n=18648；②输入数据e=1261，并根据))((mod1den，并对算法进行分析利用辗转相除的原理实现算法求逆；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：1242311524724374591430361271096416399927213629调用，以及)(modmncd进行求解m：for(i=0;isl;i++){charm1[100];c1=1;j=0;a=c[i];b=d;while(b0){if(b%2==0){b=b/2;a=(a*a)%n;}else{b=b-1;c1=(c1*a)%n;}}②根据算法可得明文数据：5438136429251457114303574688054588114440三、数字转化为字符①将所得的数字数据转化为字符数据：for(i=0;isl;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结论（结果）这个实验的算法实现根据课本较容易实现，但真正掌握这个算法需要对算法进行深入的分析，这个算法的实现需要特别注意细节：例如：数据的导入，需将数据文件明确位置；明文字符的反向输出。在这次实验的实现过程中，较为顺畅！