实验报告----RSA_2012

信 息 安 全 实 验 报 告

学号40905197 姓名 程晓红 班级_09信科_ 时间2012/5/17_成绩____ __ 实验名称 实验目的 公钥密码算法RSA 通过编程实现RSA的加密和解密过程，加深对公钥（非对称）密码算法的认识。 公钥密码算法是指一个加密系统的加密密钥和解密密钥是不同的，或者说不能用其中一个推导出另一个。在公钥密码算法的两个密钥中，一个是用于加密的密钥，它是可以公开的，称为公钥；另一个是用于解密的密钥，是保密的，称为私钥。公钥密码算法解决了对称密码中密钥管理的难题，并提供了对信息发送人的身份进行验证的手段，是现代密码学最重要的发明。 RSA密码是目前为止最成功的公钥密码算法，虽然它的安全性还未能得到理论证明，实 验 原 理 但经过20多年的密码分析和攻击，迄今仍然被实践证明是安全的。 RSA算法描述如下： 1．公钥 选择两个互异的大素数p和q, n是二者的乘积，即n二pq使D(n)=(p-1)(q-1), D(n)为欧拉函数。随机选取正整数e,使其满足(e, (D(n))=1，即e和D (n)互质，则将(n,e)作为公钥。 2.私钥 求出正数d,使其满足e d=1 mod D (n),则将(p,q,d)作为私钥。 3.加密算法 对于明文M,由C=M mod n，得到密文C。 4.解密算法 对于密文C,由M=C mod n,得到明文M 如果窃密者获得了n, e和密文C,为了破解密文必须计算出私钥d，为此需要先分解n为了提高破解难度，达到更高的安全性，一般商业应用要求n的长度不小于1024位，更重要的场合不小于2048位。 de实验环境 实验 内容 运行Windows的 PC机，具有VC++等c语言编译环境。 (1) 编程实现模n的大数幂乘的快速算法（dashumicheng.c），随机输入3个较大的数x, e, n,输出计算x mod n (2) 编程实现模n求逆的算法(moni.c)，计算私钥。 (3) 编写RSA解密程序(jiemi.c)，完成文件data.txt中内容的解密，以字符形式输出明文。已知系统公开参数为n=123, e=1261。 e一、实验准备： 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\ {printf(\"cannot open the file\\n\"); exit(0); } while(!feof(fp)) {fscanf(fp,\"%d\ i++; } sl=i-1; printf(\"打开文件密文数据:\\n\"); for(j=0;j0 && j%10==0) printf(\"\\n\");} } 2、整数的素因子分解 ① 输入数据n=123，利用遍历算法寻找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; 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进行求解n(p1)*(q1)求得n=188； ②输入数据e=1261，并根据de1(mod(n))，并对算法进行分析利用辗转相除的原理实现算法求逆； 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\} else printf(\"逆元不存在：\"); } ③根据以上算法，可以得数据：d=5797； 4、大数幂乘算法 ①根据导入数据的参数密文c：12423 11524 7243 7459 14303 6127 109 16399 9272 13629调用，以及mcdmod(n)进行求解m： for(i=0;i0) {if(b%2==0) {b=b/2; a=(a*a)%n;} else{b=b-1;c1=(c1*a)%n;}} ②根据算法可得明文数据：5438 13 2925 14571 14303 5746 8805 4588 1144 40 三、数字转化为字符 ① 将所得的数字数据转化为字符数据： for(i=0;i=0;k--) printf(\"%c\printf(\"%c\③ 输出的数据： ibe cam ein vol ved ina nar gum bsa bo 实 验 结 果 实验 心得

打开文件密文数据: 12423 11524 7243 7459 14303 6127 109 16399 9272 13629 请输出n的值:123 请输出p、q的值：127 149 请输出nn的值：188 请输出e的值：1261 请输出逆元：5797 请输出明文： 5438 13 2925 14571 14303 5746 8805 4588 1144 40 请输出明文： ibe cam ein vol ved ina nar gum bsa bo Press any key to continue 这个实验的算法实现根据课本较容易实现，但真正掌握这个算法需要对算法进行深入的分析，这个算法的实现需要特别注意细节：例如：数据的导入，需将数据文件明确位置；明文字符的反向输出。在这次实验的实现过程中，较为顺畅！