实验四 RSA算法

信息安全技术实验指导

实验四 RSA算法

1.实验目的

（1）了解RSA算法的特点

（2）掌握RSA算法的加解密原理

2.实验内容

阅读学习本实验第三部分（知识点），通过RSA算法实现的Flash短片，理解并掌握RSA算法的详细实现过程；在VC环境下，调试运行RSA算法，简单了解RSA算法的C++语言实现过程。

（1）RSA算法原理演示

步骤1：打开实验五文件夹中的“RSA.exe”文件（如图41所示）；

图4-1 RSA算法演示文件

步骤2：依据演示文稿，逐步学习RSA算法。

（2）RSA算法的实现

该部分，主要通过在VC++6.0中，采用C++语言来编程实现RSA算法来更进一步的理解和掌握RSA算法。具体步骤如下：

步骤1：打开VC开发环境，打开RSA.cpp文件；

步骤2：依据RSA算法实现原理，阅读完善算法； 实验四 RSA算法

步骤3：编译运行程序，并进行具体测试。

３.知识点

1978年美国MIT的三名数学家R.Rivest(里维斯特)，A.Shamir(沙摩尔)和L.Adleman(阿德尔曼)提出了著名的公钥密码体制：RSA算法，它的安全性依赖于大数分解。公钥和私钥都是两个大素数（长度为100位以上的十进制数）的函数。据猜测，从一个密钥和密文推断出明文的难度等同于分解两个大素数的积。迄今为止，RSA算法是思想最简单、分析最透彻、应用最广泛的公钥密码体制。RSA算法非常容易理解和实现，经受住了密码分析，密码分析者不既不能证明也不能否定它的安全性，这恰恰说明了RSA具有一定的可信度。

（1）RSA算法描述

① 密钥对的产生

● 选择两个互异的大素数，p 和q ；

● 计算： n = p * q , (n)=(p-1)(q-1)，其中(n)是n的欧拉函数值；

● 选一整数e，满足1

● 计算d，满足de≡1 mod (n)，即d是e在模(n)下的乘法逆元；

● {e,n}为公钥， （d,n）为私钥。

② 加、解密过程

● 加密时首先将明文比特串分组，使得每个分组对应的十进制数小于n，即分组长度小于log2 n；

● 对每个明文分组m，作加密运算：

c≡me mod n

● 解密时对每个密文分组做如下计算：

m ≡ cd（mod n)

（2）RSA算法论证

证明：由加密过程 ：

cd mod n ≡（me）d mod n ≡ m k (n)+1 mod n (ed ≡ 1 mod ( n))

● 若m与n互素，由欧拉定理 m (n)≡1 mod n

有 mk (n)≡ 1 mod n,

mk(n)+1≡ m mod n

● 若m与n不互素，即 gcd(m, n) ≠1,则m必与两个素数p、q中的一个互素，假定与p互素，与q不互素，不妨设m=cq （c < q），此时gcd(m, p)=1,由欧拉定理，

m (p)≡1 mod p，[m (p)]k (q)≡1 mod p

即m k (n) ≡1 mod p，

于是存在一整数r，使mk (n) = 1＋rp ，

两边同乘m=cq, 得 ：

mk (n)+1= (m+rcpq) = (m+rcn) 信息安全技术实验指导

即mk(n)+1≡ m mod n

（3）RSA算法参数的选择

为了确保RSA密码的安全，必须认真选择密码参数

①ｐ和ｑ要足够大；

一般应用：p和q应512b 重要应用：p和q应1024b

②ｐ和ｑ应为强素数；

文献指出，只要(p-1)、(p+1)、(q-1)、(q+1)四个数之一只有小的素因子，n就容易分解。

③ｐ和ｑ的差要合适；

④ e的选择；

随机且含1多就安全，但加密速度慢。

⑤ d的选择；

d不能太小，要足够大。

⑥不要许多用户公用一个模n。

易受共模攻击

（4）快速指数运算（平方乘运算）

问题：求am mod n=?，其中a,m是正整数。

将m表示为二进制形式bkbk-1…b0，即：

m=bk2k+bk-12k-1+„+b12+b0

因此，

实现平方乘法运算的伪代码如下所示：

m=bk2k+bk-12k-1+„+b12+b0，求am mod n=?

d=1;

for i=k downto 0 {

d ≡(d×d) mod n;

if bi=1 then {

d ≡(d×a) mod n

}

}

return d

（5）Miller-Rabin素性检测算法

引理：若p是奇素数,则方程式：

x2  1 (mod p)

只有两个解 x = +1 或 x = –1。该引理的逆命题就是：如果方程式x2  1 (mod p)存在除了+1 和 –1 以外的其他解,n 就不是素数。上述引理的逆命题就是著名的Miller-Rabin素性检验算法的基本依据之一。

Miller-Rabin素性检测算法伪代码： 实验四 RSA算法

Miller-Rabin (a, n):

1. represent (n-1) as binary bkbk-1…b0;

2. d←1;

3. For i←k downto 0 do

4. { x←d;

5. d←(d×d) mod n;

6. if d=1 and x1 and xn-1

7. then return TRUE;

8. if bi=1

9. then d(d×a) mod n }

10. if d1

11. then return TRUE;

12. return FALSE;

此算法的两个输入中，n是待检测数，a是小于n的整数。如果算法返回的值为TRUE，则n肯定不是素数；如果返回的值为FALSE，则ｎ有可能是素数。

由于RSA是简单且比较成熟的一种公钥密码体制，许多公司及研究团体都对它进行了实现。除RSA公司的产品RSAref以外，主要还有IBM的CCA、Cryptix、Cryptlib、Crypto++、Cryptolib、Python、SSLava、SSLeay及CRYPTOMAThIC的实现等。

RSA算法的软硬件实现都已经比较成熟，但是其软硬件实现加解密速度都远远不及DES等传统密码，RSA多用于密钥交换和认证。 如果适当选择RSA的参数，可以大大加快速度。例如，选e为3、17或65 537(216+1)的二进制表示式中都只有两/个1，大大减少了运算量。X. 509建议用65 537[1989]，PEM建议用3，而PKCS#1建议用65537，当消息后填充随机数字时，不会有任何安全问题。

4．常见问题回答

（1）从密码分析的角度来讲，公钥密码体制比传统密码更安全吗？

解答：事实上，任何加密方法的安全性以来于密钥的长度和破译密文所需要的计算量。从抗击密码分析的角度看，原则上不能说传统密码优于公钥密码，也不能说公钥密码优于传统密码。

（2）公开密钥是一种通用的方法，传统密码是不是已经过时？

解答：传统密码并没有过时，由于现有的公钥密码计算量大，所以取代传统密码不太可能。就像公钥密码的发明者之一所说的“公钥密码学仅限于用在密钥管理和签名这类应用之中，这几乎是被广泛接受的事实。”

5．思考题

（1）简述RSA算法加解密过程？ 信息安全技术实验指导

（2）如何理解RSA算法是基于大数分解的数学难题的？

（3）RSA算法中，令p=3,q=11,e=7,c=14,计算明文m。（要求：给出详细步骤）

（4）调试运行该实验中给出的RSA算法源码时，密钥生成若选择p、q值分别为5、7可以吗（试通过修改代码测试）？为什么？

（5）描述采用DES算法及RSA算法进行混合加密的方法过程及特点。