AES 加密是一种对称加密算法，密钥必须传递给对方才能解密，如何保证密钥安全成为一个重要问题。1977 年，三位数学家 Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密，也就是本文要讨论的 RSA 算法。使用非对称加密算法需要生成公钥和私钥，使用公钥加密，使用私钥解密。
互质关系
首先回顾一下质数的定义。质数 (prime number) 又称素数，有无限个。一个大于 1 的自然数，除了 1 和它本身外，不能被其他自然数整除，换句话说就是该数除了 1 和它本身以外不再有其他的因数；否则称为合数。
如果两个正整数，除了 1 以外，没有其他公因子，我们就称这两个数是互质关系。互质关系不要求两个数都是质数，合数也可以和一个质数构成互质关系。
欧拉函数
对正整数 n，欧拉函数是小于 n 的正整数中与 n 互质的数的数目，用 φ(n) 表示。例如 φ(8) = 4，因为 1 3 5 7 均和 8 互质。欧拉函数可以表示为
其中 p1, p2 …… pn 为 x 的所有质因数，x 是不为 0 的整数。且 φ(1) = 1。每种质因数只用一个。比如 12 = 2 * 2 * 3 那么
φ(12) = 12 * ( 1 - 1 / 2) * ( 1 - 1 / 3 ) = 4
若 n 是质数 p 的 k 次幂，除了 p 的倍数外，其他数都跟 n 互质，则
若 m,n 互质，则
当 n 为奇数时，则
当 n 为质数时，则
模反元素
如果两个正整数 a 和 n 互质，那么一定可以找到整数 b，使得 ab - 1 被 n 整除，或者说 ab 被 n 除的余数是 1。这时，b 就叫做 a 的 “模反元素”。表示如下：
ab ≡ 1 (mod n)
比如，3 和 11 互质，那么 3 的模反元素就是 4，因为 (3 × 4) - 1 可以被 11 整除。显然，模反元素不止一个，4 加减 11 的整数倍都是 3 的模反元素 {…, -18, -7, 4, 15, 26, …}，即如果 b 是 a 的模反元素，则 b + k n 都是 a 的模反元素。
欧拉定理
欧拉定理是一个关于同余的性质。欧拉定理表明，若 n,a 为正整数，且 n,a 互质，则有
a^φ(n) ≡ 1 (mod n)
证明过程较复杂，此处略过。
假设正整数 a 与质数 p 互质，因为 φ(p) = p-1，则欧拉定理可以写成
a^(p-1) ≡ 1 (mod p)
RSA 公钥与私钥的生成
生成密钥的过程如下：
- 首先选择两个质数 p 和 q，并且越大越好。
- 计算出 n = pq ，n 的二进制位数即为密钥的位数。
- 计算出 n 的欧拉函数
- φ(n) = φ(p)φ(q) = (p-1) (q-1)
- 随机选择一个整数 e，条件是 1 < e < φ(n)，且 e 与 φ(n) 互质
- 计算 e 对于 φ(n) 的模反元素 d
- ed ≡ 1 (mod φ(n))
- 上面的公式等价于如下的一元二次方程，d 和 k 有无穷多种组合方式，选取一个 d 值即可
- ed + k φ(n) = 1
- 将 n 和 e 封装成公钥，n 和 d 封装成私钥
RSA 加密与解密
使用公钥 (n,e) 进行加密的过程，可以表示为如下公式，实际上就是根据明文 m
计算出密文 c 的过程。m 必须是整数（字符串可以取 ascii 值或 unicode 值），且 m 必须小于 n。
m^e ≡ c (mod n)
使用私钥 (n,d) 进行解密的过程，可以表示为如下公式，实际上就是根据密文 c 计算出明文 m 的过程。此处证明比较复杂，感兴趣的朋友可以自己看一下。
c^d ≡ m (mod n)
RSA 加解密过程示例
首先生成密钥：
- 取 p = 61, q = 53
- 计算出 n = 61 * 53 = 3233
- 计算出 n 的欧拉函数 φ(3233) = 60 * 52 = 3120
- 随机选择一个整数 e = 17
- 计算 e 对于 φ(n) 的模反元素 d = 2753
使用公钥进行加密，假设明文 m = 65，表示大写字母 A，根据公式计算出密文为 2790。
65^17 ≡ 2790 (mod 3233)
使用私钥进行解密，密文为 2790，根据公式可以计算出明文为 65，表示大写字母 A。
2790^2753 ≡ 65 (mod 3233)
分享学习笔记和技术总结，内容涉及 Java 进阶、架构设计、前沿技术、算法与数据结构、数据库、中间件等多个领域，欢迎关注。本文首发于微信公众号“后端开发那点事儿”。