RSA密码算法实验

北京信息科技大学

信息管理学院

实验指导书

实验名称： RSA密码算法实验 实验类别: 课程上机 适用专业： 信息安全

适用班级： 信安0801－0802

授课教师： 任亚唯

一、实验目的

本实验的目的是使学生通过对RSA算法主要参数和其部分模块功能的验证，理解公钥密码算法RSA的主要参数的基本要求，从而深入理解RSA算法的设计原理。

二、实验原理

非对称密码算法是指一个加密系统的加密密钥和解密密钥是不相同，或者说不能从其中一个推导出另一个。在非对称密码算法的两个密钥中，一个是用于加密的密钥，它是可以公开的称为公钥；另一个是用于解密的密钥，是保密的，称为私钥。非对称密码算法解决了对称密码中密钥管理的难题，并提供了对信息发送人的身份进行验证的手段，是现代密码学的最重要的发明和进展。

RSA密码是目前为止最为成功的非对称密码算法，是在1977年由Rivest、Shamir和Adleman提出的第一个比较完善的非对称密码算法。它的安全性是建立在“大数分解和素性检测”这个数论难题的基础上，即将两个大素数相乘在计算上容易实现，而将该乘积分解为两个大素数因子的计算量相当大。虽然的安全性还未能得到理论证明，但经过20多年的密码分析和攻击，迄今仍然被实践证明是安全的。

RSA算法描述如下： 1. 公钥

选择两个互异的大素数p和q，n是二者的乘积，即n = pq，使Φ(n)＝（p-1）(q-1)，Φ(n)为欧拉函数。随机选取正整数e，使其满足(e, Φ(n))=1，即e和Φ(n)互素，则将(n,e)作为公钥。

2. 私钥

求出正数d，使其满足e×d=1 modΦ(n)，则将(n,d)作为私钥。 3. 加密算法

对于明文M，由CMmodn，得到密文C。 4．解密算法

对于密文C，由MCmodn，得到明文M。

如果窃密者获得了n，e和密文C，为了破解密文他必须计算出私钥d，为此需要先分解n为p和q。为了提高破解难度，达到更高的安全性，一般商业应用要求n的长度不小于1024bit,更重要的场合不小于2048bit。

根据RSA算法描述，整数p和q的素性检测算法，以及由公钥e计算出私钥d的算法如下所示：

Miller-Rabin素性概率检测法

首先将n-1表示为二进制形式bkbk-1…b0，并给d赋初值1，则算法Witnessa(a,n)的核心部分如下：

for i=k downto 0 do { x←d;

d←(d×d) mod n;

if d=1 and(x≠1)and(x≠n-1)then return False; if bi=1 then d←(d×a) mod n

de }

if d≠1 then return False; return True.

此算法有两个输入参数，n是待检验的数，如果算法的返回值为False，a是小于n的整数。则n肯定不是素数，如果返回值为True，则n有可能是素数。

for循环结束后，有d≡an1mod n，由Fermat定理知，若n为素数，则d为1。因此若d≠

1，则n不为素数，所以返回False。

因为n-1≡-1 mod n，所以(x≠1)and(x≠n-1),指x≡1(mod n)有不在{-1,1}中的根，因此n不为素数，返回False。

欧几里德算法及扩展的欧几里德算法

欧几里德（Euclid）算法是数论中的一个基本技术，是求两个正整数的最大公因子的简化过程。而扩展的Euclid算法不仅可求出两个正整数的最大公因子，而且当两个正整数互素时，还可求出其中一个数关于另一个数的乘法逆元。两个算法的伪代码如下：

Euclid（f, d） 1. X←f; Y←d；

2. if Y=0 then return X=(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=(f, d)；no inverse; 3. if Y3=1 then return Y3=(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。

2

三、实验环境

运行windows操作系统的PC机，具有VC（windows）C语言编译环境。

四、实验要求

1．熟练使用RSATool验证RSA算法的主要参数的选择和产生。

2．用已学程序设计知识编写程序实现RSA算法的部分模块功能，整理程序代码文档，记录程序运行结果。

五、实验内容和步骤

1．根据给出对话框程序RSATool，完成大素数的选取和产生，完成公钥的选取和私钥的计算，完成大整数的因子分解，选取明文进行加密和对所得密文进行解密。

具体步骤如下：

1）点击RSA-Tool应用程序图标，出现以下对话框：

2）点击“start”键，产生随机数据，确定Keysize位数（32bits-4096bits）,确定数的进制（10，16，60，），确定公钥（16进制表示），点击“generate”键，随机产生P、Q，并计算出N。

3）点击“test”键，出现以下对话框，输入明文信息，点击“Encrypt”键，得到密文信息。

4）点击“Decrypt”键，可进行解密验证

按照以上步骤验证RSA算法的参数选择和采用RSA算法对一段字符进行加解密。

2．复习实验原理中的Miller-Rabin素性概率检测算法和扩展的欧几里德算法的伪代码，并编写程序将其实现。

主要步骤如下：

1）分析上述两个算法的伪代码；

2）确定变量类型及变量间的关系，编写程序； 3）运行并调试程序；

4）记录程序运行结果，验证结果。

六、实验成绩考核方法

根据学生在上机实验课中的纪律表现、程序演示和实验结果、回答问题情况和实验报告的撰写及提交情况，综合给出学生本次实验的成绩。

以百分制记录实验成绩， 90-100分 优秀 80-90分 良好 70-80分 中 60-70分 及格

0-60分 不及格

最后按一定比例折合到密码学课程的平时成绩中。