一、什么是 RSA 算法
1977 年，三位数学家 Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。
（1）甲方选择某一种加密规则，对信息进行加密；

（2）乙方使用同一种规则，对信息进行解密。

二、互质关系
如果两个正整数，除了 1 以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。比如，15 和 32 没有公因子，所以它们是互质关系。这说明，不是质数也可以构成互质关系。

三、欧拉函数
任意给定正整数 n，请问在小于等于 n 的正整数之中，有多少个与 n 构成互质关系？（比如，在 1 到 8 之中，有多少个数与 8 构成互质关系？）
计算这个值的方法就叫做欧拉函数，以 φ(n) 表示。在 1 到 8 之中，与 8 形成互质关系的是 1、3、5、7，所以 φ(n) = 4。

四、欧拉定理
欧拉函数的用处，在于欧拉定理。” 欧拉定理” 指的是：
如果两个正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式成立：
a^φ(n) ≡ 1 (mod n)
也就是说，a 的 φ(n) 次方被 n 除的余数为 1。或者说，a 的 φ(n) 次方减去 1，可以被 n 整除。

比如，3 和 7 互质，而 7 的欧拉函数 φ(7) 等于 6，所以 3 的 6 次方（729）减去 1，可以被 7 整除（728/7=104）。

五、最大公约数
最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b 的最大公约数记为（a，b），同样的，a，b，c 的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。与最大公约数相对应的概念是最小公倍数，a，b 的最小公倍数记为 [a，b]。

由于两个数的乘积等于这两个数的最大公约数与最小公倍数的积。即（a，b）×[a，b]=a×b。所以，求两个数的最小公倍数，就可以先求出它们的最大公约数，然后用上述公式求出它们的最小公倍数。

4   |108    96
3   |27     24
     9      8
最大公约数是4*3 = 12
最小公倍数是4*3*9*8 = 864 或 108*96/12 = 864

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

ab ≡ 1 (mod n)

这时，b就叫做a的"模反元素"。比如，3 和 11 互质，那么 3 的模反元素就是 4，因为 (3 × 4)-1 可以被 11 整除。显然，模反元素不止一个， 4 加减 11 的整数倍都是 3 的模反元素 {…,-18,-7,4,15,26,…}，即如果 b 是 a 的模反元素，则 b+kn 都是 a 的模反元素。

七、密钥生成的步骤
1.随机选择两个不相等的质数。p=61，q=53。（实际应用中，这两个质数越大，就越难破解。）
2.计算 p 和 q 的乘积 n。

n = 61×53 = 3233

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

3.计算 n 的欧拉函数 φ(n)，并求出最小公倍数。

λ(n) = lcm((p-1),(q-1)) = 780

4.随机选择一个整数 e，条件是 1 <e < λ(n)，且 e 与 λ(n) 互质。
随机选择17。（实际应用中，常常选择65537。）
5.计算 e 对于 λ(n) 的模反元素 d。所谓 “模反元素” 就是指有一个整数 d，可以使得 ed 被 λ(n) 除的余数为 1。

ed ≡ 1 (mod λ(n)) = 17 * d % λ(n) = 1

d = 413 或者更大倍数的数值
6.公钥为为 (n = 3233, e = 17)。明文消息为 m，密文信息为 c，加密公式为

c = m^17 mod 3233

7.私钥为 (n = 3233, d = 413)。明文消息为 m，密文信息为 c，解密公式为

m = c^413 mod 3233

八、使用密钥进行加密解密
例如，为了加密 m = 65，我们计算

c = 64^17 mod 3233 = 2790

为了解密 c = 2790，我们计算

m = 2790^413 mod 3233 = 65