RSA算法 夏之冰雪

1 一点概念 密码学 对称加密 非对称加密 公钥加密 RSA算法

密码学 1 编码学和破译学统称为密码学。 研究编制密码和破译密码的技术科学。 编码学——研究密码变化的客观规律，应用于编制密码以保守通信秘密的。 破译学——应用于破译密码以获取通信情报的。 编码学和破译学统称为密码学。

对称加密 1 密钥——分为加密密钥和解密密钥。 明文——没有进行加密，能够直接代表原文含义的信息。 密文——经过加密处理处理之后，隐藏原文含义的信息。 加密——将明文转换成密文的实施过程。 解密——将密文转换成明文的实施过程。

1 非对称加密 非对称加密算法需要两个密钥——公开密钥和私有密钥。 公钥加密的信息只有私钥解得开，只要私钥不泄露，整个通讯就是安全的。

1 公钥加密 1976年，两位美国计算机学家Whitfield Diffie 和 Martin Hellman，提出了一种崭新构思，可以在不直接传递密钥的情况下，完成解密。这被称为“Diffie-Hellman密钥交换算法”。

1 RSA算法 1977年，三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法。 RSA算法一直是最广为使用的”非对称加密算法”。

历史回顾 1 公元前480年 波斯秘密集结军队准备攻击雅典和斯巴达，狄马拉图斯密文解救希腊。 1976年以前 一直对称加密统治 1844年 莫尔斯发明电报，莫尔斯电码诞生。 1976年 Diffie-Hellman密钥交换算法，即非对称加密算法问世 1977年，三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密

2 一点也不难 同余符号 质数的简单概念 欧拉函数 模反元素

同余符号 2 两个整数a、b，若它们除以整数m所得的余数相等，则称a与b对于模m同余，或a同余于b模m。 记作 a≡b (mod m) 两个整数除以同一个整数，若得到相同的余数，那么这两个整数同余。 比如对于被除数7，那么1，8，15，22除以7余数都为1，这些数同余。 两个整数a、b，若它们除以整数m所得的余数相等，则称a与b对于模m同余，或a同余于b模m。 记作 a≡b (mod m) 例如 8≡22 (mod 7)， 53≡123 (mod 10)

同余性质 2 反身性 a≡a (mod m) 对称性 若a≡b(mod m)，则b≡a (mod m) 传递性 若a≡b (mod m)，b≡c (mod m)，则a≡c (mod m) 相加性 若a≡b (mod m)，c≡d(mod m)，则a+-c≡b+-d (mod m) 相乘性 若a≡b (mod m)，c≡d(mod m)，则ac≡bd (mod m)

质数的简单概念 2 任意两个质数构成互质关系。（5、17） 一个数是质数，另一个数只要不是前者的倍数。（7、24） 质数：一个大于1的自然数，除了1和它本身外，不能被其他自然数整除。 例如，3、5、7、31等。 互质：如果两个正整数，除了1以外，没有其他公因子。 例如，3和5互质，24和49互质。 任意两个质数构成互质关系。（5、17） 一个数是质数，另一个数只要不是前者的倍数。（7、24） 两个数之中，较大的那个数是质数，两者构成互质关系。（48、71） 1和任意一个自然数是都是互质关系。（1、99） p是大于1的整数，则p和p-1构成互质关系。（26、27） p是大于1的奇数，则p和p-2构成互质关系。（25、27）

2 欧拉函数 欧拉函数 欧拉函数是数论中很重要的一个函数，欧拉函数是指：对于一个正整数 n ，小于 n 且和 n 互质的正整数（包括 1）的个数，记作 φ(n) 。 欧拉定理 对于互质的正整数 a 和 n ，有 aΦ(n)≡1 (mod n) 费马定理 若正整数 a 与素数 p 互质，则有 ap-1≡1 (mod p)

欧拉函数 2 n = 1 Φ(1) = 1 n是质数 Φ(n) = n - 1 n是某个质数的次方，即n = pk （p为质数，k大于1整数） Φ(pk) = pk – pk-1 n可以分解成两个互质的整数之积，n = p1 * p2 Φ(n) = Φ(p1 * p2) = Φ(p1) * Φ(p2) 任意一个大于1的正整数n，都可以写成一系列质数的积 n = p1k1 p2k2 … prkr Φ(n) = n (1-1/p1)(1-1/p2)…(1-1/pr)

2 欧拉定理 如果两个正整数a和n互质 aΦ(n）≡1 (mod n)

模反元素 2 由欧拉定理 aΦ(n）≡1 (mod n) 得到 a * aΦ(n）-1≡1 (mod n) 如果两个正整数 a 和 n 互质，那么一定可以找到整数b： ab≡1 (mod n) 由欧拉定理 aΦ(n）≡1 (mod n) 得到 a * aΦ(n）-1≡1 (mod n) 因此模反元素 b = aΦ(n）-1

RSA过程 3 选择两个不相等质数 p，q p = 61，q = 53 2. 计算 p * q 的乘积 n n = p * q = 3233 （二进制12位，2048位绝对安全） 3. 计算 n 的欧拉函数 Φ(n) = (p - 1)(q - 1) = 3120 4. 随机选择整数 e，使得 1 < e < Φ(n)，且与Φ(n)互质 e = 17 （通常选择65537） 5. 计算 e 对于Φ(n)的模反元素d ed≡1 (mod Φ(n)) d = 2753 6. 将n和e封装成公钥，n和d封装成私钥 公钥 = (3233, 17)， 私钥 = (3233, 2753)

加密解密 3 所谓加密，就是算出式子 me≡c (mod n) 中 c 的值。 假设m = 65, 6517≡c (mod 3233) 有消息 m 需要进行通讯，m 必须是整数，且 m 小于 n。 所谓加密，就是算出式子 me≡c (mod n) 中 c 的值。 假设m = 65, 6517≡c (mod 3233) 计算得到，c = 2790 我们只要把2790发给对方即可。 解密神奇之处在于，以下等式一定成立： cd≡m (mod n) 27902753≡m (mod 3233) 计算得到，m = 65 因此我们知道，发送的消息是65。

RSA证明 3 证明：cd≡m (mod n) 因为 me≡c (mod n) 于是 c 可以写成 c = me – kn (me – kn)d≡m (mod n) 等同于 med≡m (mod n) 由于ed≡1 (mod φ(n)) 所以ed = hφ(n) + 1，带入上式得到 mhΦ(n)+1≡m (mod n) 若m与n互质， mΦ(n）≡1 (mod n) (mΦ(n）)h m≡1h m (mod n) 若m与n不互质，n = p * q 因此 m 一定为 kp 或 kq 以 m = kp 为例， 则k与q互质，kp与q互质 欧拉定理知 (kp)q-1≡1 (mod q) ((kp)q-1)h(p-1) * kp≡kp (mod q) (kp)h(p-1)(q-1)+1 ≡kp (mod q) (kp)hΦ(n)+1≡kp (mod q) (kp)hΦ(n)+1 = tq + kp (kp)hΦ(n)+1 = t1pq + kp 将m = kp， n = pq代入，得到 mhΦ(n)+1 = t1n + m 即 mhΦ(n)+1≡m (mod n)

RSA安全性 3 通过公钥（n, e）能否得到私钥（n, d）？ （1）ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。 （2）φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。 （3）n=pq。只有将n因数分解，才能算出p和q。 结论：如果n可以被因数分解，d就可以算出，也就意味着私钥被破解。

3 RSA安全性 目前已知的计算机因式分解的最大数（二进制768位）： 1230186684530117755130494958384962720772853569595334 7921973224521517264005072636575187452021997864693899 5647494277406384592519255732630345373154826850791702 6122142913461670429214311602221240479274737794080665 351419597459856902143413 它等于这两个数的乘积： 33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489 × 36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917 因此目前被破解的最长RSA为768位。

4 简单总结 RSA加密，CPU 计算资源消耗非常大。一次完全 TLS 握手，密钥交换时的非对称解密计算量占整个握手过程的 90% 以上。而对称加密的计算量只相当于非对称加密的 0.1%，如果应用层数据也使用非对称加解密，性能开销太大，无法承受。 算法对加密内容的长度有限制，不能超过公钥长度。例如公钥长度是 2048 位，意味着待加密内容不能超过 256 个字节。 目前只能用来作密钥交换或者内容签名，不适合用来做应用层传输内容的加解密。

The End