RSA算法

算法简介

1976年以前，所有的加密方法都是对称加密算法。这种算法加密和解密使用的是同一个密钥。这种模式密钥的传递很不安全。

1977年，两位美国计算机学家 Whitfield Diffie 和 Martin Hellman，提出了一种新的构思，可以在不传递密钥的情况下，完成解密。这被称为 Diffie-Hellman 密钥交换算法。这个构思引出了后来的非对称加密模式。

1977年，三位数学家 Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。算法用他们三个人名字命名，叫RSA算法。直到现在，依旧目前最广泛使用的非对称加密算法。

算法所需知识

互质关系

如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系.

关于互质可以得到以下结论：

• 任意两个制数构成互质关系，比如13和61.
• 一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，如3和10。
• 如果两个数中，较大的那个数是质数，则两者构成互质关系，如97和57。
• 1和任意一个自然数都是互质关系，如1和99。
• p是大于1的整数，则p和p-1构成互质关系，如57和56。
• p是大于1的奇数，则p和p-2构成互质关系，如17和15。

欧拉函数

请思考以下问题：

任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？（比如，在1到8之中，有多少个数与8构成互质关系？）

计算这个值的方法就是欧拉函数，以φ(n)表示。在1到8之中，与8形成互质关系的是1、3、5、7，所以 φ(n) = 4。

对于φ(n)的计算有如下方式：

• 当n=1时，则φ(1) = 1.因为1与任何数（包括自身）都构成互质关系。
• 当n是质数，则φ(n) = n-1。因为质数与小于它的每一个数，都构成互质关系。如5与1、2、3、4都构成互质关系。
• 如果n是质数的某一次方，即n = p^k(p为质数，k为大于等于1的整数).则$\phi(p^k) = p^k-p^{k-1}$

比如φ(8) = φ(2^3) = 2^3 - 2^2 = 8-4 = 4.
这是因为只有当一个数不包含质数p，才可能与n互质。而包含质数p的数一共有p^(k-1)个，即1×p、2×p、3×p、…、p^(k-1)×p，把它们去除，剩下的就是与n互质的数。
上面的式子还可以写成下面的形式：

$$\phi(p^k) = p^k-p^{k-1} = p^k(1-1/p)$$

可以看出，上面第二条是k=1时的特例。

• 如果n可以分解成两个互质的整数之积，n = p1 × p2，则φ(n) = φ(p1p2) = φ(p1)φ(p2) 即积的欧拉函数等于各个因子的欧拉函数之积。
• 因为任意一共大于1的正整数，都可以写成一系列质数的积。`

$$n = p_1^{k_1}p_2^{k_2}...p_r^{k_r}$$

根据第四点得到：

$$\phi(n) = \phi(p_1^{k_1})\phi(p_2^{k_2})...\phi(p_r^{k_r})$$

再根据第三点结论得到：

$$\phi(n) = p_1^{k_1}p_2^{k_2}...p_r^{k_r}(1-1/{p_1})(1-1/{p_2})...(1-1/{p_r})$$

也就等于:

$$\phi(n) = n(1-1/{p_1})(1-1/{p_2})...(1-1/{p_r})$$

这就是欧拉函数的通用计算公式。

欧拉定理

欧拉函数的用处，在于欧拉定理)。欧拉定理指，

如果两个正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式成立：

$$a^{\phi(n)} ≡ 1\,(mod\,\phi(n))$$

也就是说，a的φ(n)次方被n除的余数为1。或者说，a的φ(n)次方减去1，可以被n整除。比如，3和7互质，而7的欧拉函数φ(7)等于6，所以3的6次方（729）减去1，可以被7整除（728/7=104）。

欧拉定理有一个特殊的情况。

假设正整数a与质数p互质，因为质数p的φ(p)等于p-1，则欧拉定理可以写成

$$a^{p-1} ≡ 1\,(mod\,p)$$

这就是著名的费马小定理。它是欧拉定理的特例。

模反元素

如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。

$$ab ≡ 1\,(mod\,n)$$

欧拉定理可以用来证明模反元素必然存在。

$$a^{\phi(n)} = a\times a^{\phi(n)-1} ≡ 1\,(mod\,n)$$

可以看到，a的 φ(n)-1 次方，就是a的模反元素。

算法详解

假设爱丽丝和鲍勃进行加密通信，怎么生成公钥和私钥呢？

密钥生成

1.随机选择两个不想等的质数p和q

爱丽丝选择了61和53.（实际应用中，这两个质数越大，就越难破解）。

2.计算p和q的乘积n

爱丽丝把61和53相乘。
n = 61×53 = 3233

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

3.计算n的欧拉函数φ(n)

根据公式：φ(n) = （p-1）（q-1）
算出 φ(3233) 为 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 = kφ(n)

于是，找到模反元素d，实质上就是对下面这个二元一次方程求解

ex + φ(n)y = 1
爱丽丝算出一组整数解为 (x,y)=(2753,-15)，即 d=2753。

至此所有计算完成。

讲n和e封装成公钥，n和d封装成私钥

在爱丽丝的例子中，n=3233，e=17，d=2753，所以公钥就是 (3233,17)，私钥就是（3233, 2753）。

实际应用中，公钥和私钥的数据都采用ASN.1格式表达（实例）。

加密和解密

用公钥加密

假设鲍勃要向爱丽丝发送加密信息m，他就要用爱丽丝的公钥 (n,e) 对m进行加密。这里需要注意，m必须是整数（字符串可以取ascii值或unicode值），且m必须小于n。

可以得到以下式子c：

$${m^e} ≡ c \,(\,mod\,n)$$

用私钥解密

爱丽丝拿到鲍勃发来的密文以后，就用自己的私钥（n，d）进行解密。可以证明，下面的等式一定成立：

$$c^d ≡ m\,(mod\,n)$$

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