RSA密码算法实验.doc

北京信息科技大学信息管理学院实验指导书实验名称： RSA密码算法实验 实验类别: 课程上机 适用专业： 信息安全 适用班级： 信安08010802 授课教师： 任亚唯 一、实验目的 本实验的目的是使学生通过对RSA算法主要参数和其部分模块功能的验证，理解公钥密码算法RSA的主要参数的基本要求，从而深入理解RSA算法的设计原理。 二、实验原理 非对称密码算法是指一个加密系统的加密密钥和解密密钥是不相同，或者说不能从其中一个推导出另一个。在非对称密码算法的两个密钥中，一个是用于加密的密钥，它是可以公开的称为公钥；另一个是用于解密的密钥，是保密的，称为私钥。非对称密码算法解决了对称密码体制中密钥管理的难题，并提供了对信息发送人的身份进行验证的手段，是现代密码学的最重要的发明和进展。 RSA密码体制是目前为止最为成功的非对称密码算法，是在1977年由Rivest、Shamir和Adleman提出的第一个比较完善的非对称密码算法。它的安全性是建立在“大数分解和素性检测”这个数论难题的基础上，即将两个大素数相乘在计算上容易实现，而将该乘积分解为两个大素数因子的计算量相当大。虽然的安全性还未能得到理论证明，但经过20多年的密码分析和攻击，迄今仍然被实践证明是安全的。 RSA算法描述如下： 1. 公钥 选择两个互异的大素数p和q，n是二者的乘积，即n = pq，使(n)（p-1）(q-1)，(n)为欧拉函数。随机选取正整数e，使其满足gcd(e, (n)=1，即e和(n)互素，则将(n,e)作为公钥。 2. 私钥 求出正数d，使其满足ed=1 mod(n)，则将(n,d)作为私钥。 3. 加密算法 对于明文M，由，得到密文C。 4解密算法 对于密文C，由，得到明文M。 如果窃密者获得了n，e和密文C，为了破解密文他必须计算出私钥d，为此需要先分解n为p和q。为了提高破解难度，达到更高的安全性，一般商业应用要求n的长度不小于1024bit,更重要的场合不小于2048bit。 根据RSA算法描述，整数p和q的素性检测算法，以及由公钥e计算出私钥d的算法如下所示：Miller-Rabin素性概率检测法首先将n-1表示为二进制形式bkbk-1b0，并给d赋初值1，则算法Witness(,n)的核心部分如下： for i=k downto 0 doxd;d(dd) mod n;if d=1 and(x1)and(xn-1)then return False;if bi=1 then d(d) mod nif d1 then return False;return True.此算法有两个输入参数，n是待检验的数，是小于n的整数。如果算法的返回值为False，则n肯定不是素数，如果返回值为True，则n有可能是素数。for循环结束后，有dmod n，由Fermat定理知，若n为素数，则d为1。因此若d1，则n不为素数，所以返回False。因为n-1-1 mod n，所以(x1)and(xn-1),指1(mod n)有不在-1,1中的根，因此n不为素数，返回False。欧几里德算法及扩展的欧几里德算法欧几里德（Euclid）算法是数论中的一个基本技术，是求两个正整数的最大公因子的简化过程。而扩展的Euclid算法不仅可求出两个正整数的最大公因子，而且当两个正整数互素时，还可求出其中一个数关于另一个数的乘法逆元。两个算法的伪代码如下：Euclid（f, d）1. Xf; Yd；2. if Y=0 then return X=gcd(f,d)；3. R=X mod Y；4. X=Y；5. Y=R；6. goto 2。Extended Euclid(f, d) （设 f d） 1. (X1,X2,X3)(1,0,f);(Y1,Y2,Y3)(0,1,d);2. if Y3=0 then return X3=gcd(f, d)；no inverse;3. if Y3=1 then return Y3=gcd(f, d)；Y2=d-1 mod f;4. Q=X3Y3 ；5. (T1,T2,T3)(X1-QY1,X2-QY2,X3-QY3);6. (X1,X2,X3)(Y1,Y2,Y3);7. (Y1,Y2,Y3)(T1,T2,T3);8. goto 2。三、实验环境运行windows操作系统的PC机，具有VC（windows）C语言编译环境。四、实验要求 1熟练使用RSATool验证RSA算法的主要参数的选择和产生。 2用已学程序设计知识编写程序实现RSA算法的部分模块功能，整理程序代码文档，记录程序运行结果。五、实验内容和步骤1根据给出对话框程序RSATool，完成大素数的选取和产生，完成公钥的选取和私钥的计算，完成大整数的因子分解，选取明文进行加密和对所得密文进行解密。具体步骤如下：1）点击RSA-Tool应用程序图标，出现以下对话框：2）点击“start”键，产生随机数据，确定Keysize位数（32bits-4096bits）,确定数的进制（10，16，60，64），确定公钥（16进制表示），点击“generate”键，随机产生P、Q，并计算出N。3）点击“test”键，出现以下对话框，输入明文信息，点击“Encrypt”键，得到密文信息。 4）点击“Decrypt”键，可进行解密验证 按照以上步骤验证RSA算法的参数选择和采用RSA算法对一段字符进行加解密。2复习实验原理中的Miller-Rabin素性概率检测算法和扩展的欧几里德算法的伪代码，并编写程序将其实现。主要步骤如下：1）分析上述两个算法的伪代码； 2）确定变量类型及变量间的关系，编写程序； 3）运行并调试程序； 4）记录程序运行结果，验证结果。 六、实验成绩考核方法根据学生在上机实验课中的纪律