实验报告3----RSA

信 息 安 全 实 验 报 告

学号____ ____姓名__ 班级____ __时间____ _ 成绩____ __ 实验名称 实验目的 公钥密码算法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,输出计算xe mod n (2) 编程实现模n求逆的算法(moni.c)，计算私钥。 (3) 编写RSA解密程序(jiemi.c)，完成文件data.txt中内容的解密，以字符形式输出明文。已知系统公开参数为n=123, e=1261。 实 验 过 程 1.首先编写模n的大数幂乘的快速算法，即计算x^r(mod n)，此算法的计算过程是： （1）当x的指数为偶数时，指数变为原来的1/2，x等于x*x(mod n)； （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; } } return c; 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)cout<从实验的设计思想上看，这次的实验比上两次的实验都要复杂，本次实验需要有很强的逻辑性；从实验编写过程来看，本次试验相对上两次实验要简单一点，只要把每一步都做好，然后把每一个程序块组合在一起就能减少错误。而且有了上两次的实验基础，这次实验实现起来明显比上两次更容易上手，但在编程过程中也有不少的问题，但解决问题的过程也是发现不足，积累知识的过程。编程的过程也让我们更好的理解和掌握RSA加密算法的实现过程。