RSA算法

文章目录

1. 1. 密钥生成步骤
2. 2. 算法可靠性
3. 3. 加密和解密

RSA算法被认为是目前地球上最重要的加密算法，所以作为互联网的热爱者来说，想了解一下它的神秘感，加深对网络安全方面的认识。

在数论那一章铺垫了很多要实现RSA算法的准备工作，现在主要讲解一下如何生成密钥。

密钥生成步骤

假设A要和B进行加密通信，她就需要生成公钥和私钥。公钥用来给A加密信息，私钥用来解密。

1.第一步，随机选择两个不相等的质数p和q。
假设A选择了61和53。（实际应用中，这两个质数越大，就越难破解。）

2.第二步，计算p和q的乘积n。

n = 61×53 = 3233

n的长度就是密钥长度。3233写成二进制是110010100001，一共有12位，所以这个密钥就是12位。实际应用中，RSA密钥一般是1024位，重要场合则为2048位。

3.第三步，计算n的欧拉函数φ(n)。

φ(n) = (p-1)(q-1)

算出φ(3233)等于60×52，即3120。

4.第四步，随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质。
在1到3120之间，随机选择了17。（实际应用中，常常选择65537。）

5.第五步，计算e对于φ(n)的模反元素d。
所谓”模反元素”就是指有一个整数d，可以使得ed被φ(n)除的余数为1。

    ed ≡ 1 (mod φ(n))
即：
    ed + 1 = φ(n)x
已知 e=17, φ(n)=3120，
所以：
    17d +1 =3120x
求出一组解为（d,x）=(2753,-15) ,即d = 2753

至此所有计算完成。

6.第六步，将n和e封装成公钥，n和d封装成私钥。
n=3233，e=17，d=2753，所以公钥就是 (3233,17)，私钥就是（3233, 2753）。
实际应用中，公钥和私钥的数据都采用ASN.1格式表达（实例）。

算法可靠性

密钥生成步骤中，（n，e）是公钥，是公开的，p,q,φ(n),d是不公开的，其中最关键的是d，因为n和d组成了私钥，一旦d泄漏，就等于私钥泄漏。

那么，有无可能在已知n和e的情况下，推导出d？

（1）ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。
（2）φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。
（3）n=pq。只有将n因数分解，才能算出p和q。

结论：如果n可以被因数分解，d就可以算出，也就意味着私钥被破解。
可是，大整数的因数分解，是一件非常困难的事情。目前，除了暴力破解，还没有发现别的有效方法。

加密和解密

（1）加密要用公钥 (n,e)
假设B要向A发送加密信息m，他就要用A的公钥 (n,e) 对m进行加密。这里需要注意，m必须是整数（字符串可以取ascii值或unicode值），且m必须小于n。
所谓”加密”，就是算出下式的c：

　c = ( m^e) mod n

A的公钥是 (3233, 17)，B的m假设是65，那么可以算出下面的等式：

　　c =( 65^17) mod 3233 =  2790

c = 2790,B把2790发给A

（2）解密要用私钥(n,d)
A收到B发过来的2790后，就用自己的私钥（3233,2753）进行解密。

m = (c^d) mod n
即：
m = (2790^2753) mod 3233 = 65

A知道了B加密前的原文就是65。

至此，”加密–解密”的整个过程全部完成。
我们可以看到，如果不知道d，就没有办法从c求出m。而前面已经说过，要知道d就必须分解n，这是极难做到的，所以RSA算法保证了通信安全。
你可能会问，公钥(n,e) 只能加密小于n的整数m，那么如果要加密大于n的整数，该怎么办？有两种解决方法：一种是把长信息分割成若干段短消息，每段分别加密；另一种是先选择一种”对称性加密算法”（比如DES），用这种算法的密钥加密信息，再用RSA公钥加密DES密钥。

参考文章：
http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html