RSA 加密算法

RSA 加密算法是一种，是最早的公钥密码系统之一。

1978年，MIT 的 Ron Rivest，Adi Shamir 和 Leonard Adleman 三人一起提出 RSA 加密算法

原理

1. 选择 2 个质数 p 和 q
2. 计算 n = p * q
3. 根据欧拉函数 φ(n) = (p - 1) * (q - 1) 计算出 φ(n)
4. 确定公钥（整数）e，要求：1 < e < φ(n) 且 e 和 φ(n) 互质
5. 确定私钥（整数）d，要求：(e * d) / φ(n) 的余数为 1
6. 加密：原文 m，计算 m 的 e 次幂除以 n，求余数 c，c 就是加密后所得的密文
7. 解密：密文 c，计算 c 的 d 次幂除以 n，求余数得到原文 m

示例（来自 wikipedia）

1. p = 61，q = 53
2. n = 61 * 53 = 3233
3. φ(n) = (61 - 1) * (53 - 1) = 60 * 52 = 3120
4. e = 17
5. d = 2753
6. 公钥 (3233,17)，私钥 (3233,2753)
7. 原文 18，公钥加密密文 2100，私钥解密得到原文 18
8. 原文 81，私钥加密密文 2083，公钥解密得到原文 81

安全性

1. 加解需要 n 和公钥 e 生成密文 c
2. 解密需要 n 、密钥 d 和密文 c
3. 公开场合窃听者只能获取 n e c，但是获取不到密钥 d，需要通过 e 计算出 d
4. 如果想通过 e 计算出 d 则必须知道 φ(n)
5. 想知道 φ(n) 必须求出 p 和 q
6. 因为 n = p * q 而 n 已知，所以必须进行【质因数分解】，数学证明大数质因数分解十分困难，这也是 RSA 算法安全性的根本保证