RSA 算法原理（三）：补充知识

# RSA算法原理（三）：补充知识

补充下关于 RSA 的更多细节

# RSA 算法：公钥指数的选取

我们回顾下公私玥的生成

首先，Alice 选择一对不相等且足够大的质数，记为 p 和 q
计算 pq 的乘积，记为 n，也就是 p × q = n
计算 n 的欧拉函数，φ(n) = φ(p×q) = φ(p) × φ(q) = (p -1 ) × (q - 1)
随机选取一个与 φ(n) 互质的数 e，并且 1 < e < φ(n)
计算出一个 e 对于 φ(n)的模反元素 d，也就是说 ed mod φ(n) = 1

公钥：（n，e）私钥：（d，n）

加密公式： m^e mod n = c

解密公式：c^d mod n = m

关于 e ：

第 4 步，e 到底是怎么选取呢？其实，是可以随机的，但是为了提高 RSA 的加密速度实际使用中公钥指数最长用的三个值是 3、17、65537（65536 = 2¹⁶ +1）。这样选取主要是为了性能，将公钥指数选小一点，这样计算密文就方便一点；

但是这样会导致解密会麻烦一点。因为正常使用中都是用公钥加密，所以需要节约大部分人的时间。而极少部分人也会选用私钥解密，那么就只能少数服从多数了。

在选用公钥指数时，人们普遍会认为 3 和 17 没有 65537 安全。然而这种想法并没有合理的依据。实际上采用这三个值中的任何一个都不存在安全问题。前提是使用正确的填充方案。

关于 d 是怎么计算出来的：

我们知道 ed mod φ(n) = 1
那么也就是说，存在一个整数 k，使得 ed ÷ φ(n) = k....1 （商为 k，余数为 1）
也就是 ed - 1 = kφ(n)，变化一下就是 ed + kφ(n) = 1.
我们已知 e 和 φ(n)的值，d 和 k 的值未知。其实，以上公式就是对这个二元一次方程求解：ex + φ(n)y = 1
这个方程可以用扩展欧几里得算法 (opens new window)求解，此处省略具体过程

# RSA 算法的一个例子

我们来举个例子，具体演示下算法的运作过程。本例子用到的数字都特别小，实际应用中，一般会成百上千位的数字进行计算。

第一步，选取 p = 61， q=53

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

第三步：计算 n 的欧拉函数：φ(n) = (p-1)(q-1) = 3120

第四步：随机选取一个整数 e，这里选择 17

第五步：计算 e 对于 φ(n)的模反元素 d，使得 ed mod φ(n) = 1. 上一小节我们说过 ed + kφ(n) = 1，代入 e 和 φ(n)，也就是 17d + 3120k = 1，可以根据扩展欧几里得算法 (opens new window)算得一组整数 d = 2753， k=-15。

因此，公钥就是（3233，17），私钥就是（3233,2753）

假设我们要加密字符 ‘A’，其 ASCII 码为 65；根据加密公式可得 65¹⁷ mod 3233 = 2790，因此密文 c 就是 2790

解密：通过解密公式 c^d ≡ m (mod n)，可得 2790²⁷⁵³ mod 3233 = 65。

至此，"加密--解密"的整个过程全部完成。