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

实 验 报 告 学号： 2011221104220026 姓名：孙元喜 课程名称 信息安全课程设计 实验课时 n 实验项目  RSA加密算法的实现 实验时间 2013.06.02 实验目的通过编程实现RSA的加密和解密过程，加深对公钥（非对称）密码算法的认识。 实验环境 Windows7 VS2012实验内容（算法、程序、步骤和方法） 实验原理： 公钥密码算法是指一个加密系统的加密密钥和解密密钥是不同的，或者说不能用其中一个推导出另一个。在公钥密码算法的两个密钥中，一个是用于加密的密钥，它是可以公开的，称为公钥；另一个是用于解密的密钥，是保密的，称为私钥。公钥密码算法解决了对称密码体制中密钥管理的难题，并提供了对信息发送人的身份进行验证的手段，是现代密码学最重要的发明。 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,使其满足e d=1 mod D (n),则将(p,q,d)作为私钥。 3.加密算法 对于明文M,由C=Me mod n，得到密文C。 4.解密算法 对于密文C,由M=Cd mod n,得到明文M 如果窃密者获得了n, e和密文C,为了破解密文必须计算出私钥d，为此需要先分解n为了提高破解难度，达到更高的安全性，一般商业应用要求n的长度不小于1024位，更重要的场合不小于2048位。 实验内容 编程实现模n的大数幂乘的快速算法（dashumicheng.c），随机输入3个较大的数x, e, n,输出计算xe mod n 编程实现模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(cannot open the file\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);} } 整数的素因子分解 输入数据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; else continue; for(j=2;j=q1;j++) if(q1%j==0)break; if(j==q1)q=q1; else continue; } ③ 根据以上算法，可以得数据：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); } else printf(逆元不存在：); } ③根据以上算法，可以得数据：d=5797； 4、大数幂乘算法 ①根据导入数据的参数密文c：12423 115