RSA

从这一期开始，我们要聊非对称加密了，非对称加密的代表就是公钥私钥加密。

上一期我们聊了 Diffie–Hellman key exchange 迪菲-赫尔曼密钥交换,受这个的启发，有三个人在1977年提出了RSA加密算法，这三个人分别是：罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman），RSA 就是他们三人姓氏开头字母拼在一起组成的。

公钥私钥加密算法实际上还有很多，但是我们这里就先不介绍了。

RSA的数学原理和证明

网上关于RSA讲解的文章非常多，感兴趣的同学可以自行搜索，比如阮一峰老师曾讲过RSA的算法原理：

RSA Python简单测试

我们这里就按照维基百科，简单的通过Python代码来做一个RSA算法的加密解密过程。其中可能会需要一些简单的数学知识，比如什么是质数，什么叫互为质数，欧拉函数等等。

公钥私钥的生成

生成公钥私钥一共有4步，具体的证明我们就不讲了。

第一步，随机选择俩个不同的质数，或者叫素数，p和q，得到 N=p*q

这里用到的是sympy这个python库，建议大家使用 Anaconda 的jupyter notebook

import sympy

min_n = 1000
max_n = 5000

def get_pq():

    while True:
        p = sympy.randprime(min_n, max_n)
        q = sympy.randprime(min_n, max_n)
        if p != q:
            return p, q

p, q = get_pq()

N = p * q
print(f"p = {p}")
print(f"q = {q}")
print(f"N = p*q = {p*q}")

比如结果如下（随机）

p = 4547
q = 2221
N = p*q = 10098887

第二步，根据欧拉函数 求出 r, 证明方法就不展开了。

r =  φ(N) =  φ(p) x  φ(q) = (p-1)(q-1)

>>> r = (p - 1)*(q - 1)
>>> r
10092120

第三步，随机选择一个整数e，条件是1< e < φ(N)，且e与φ(N) 互质。

φ(N) = 10092120, 也就是在1到10092120之间，选择一个数e，e和10092120互为质数（也就是他俩的最大公约数=1）

满足条件的e很多，如果一个一个算，这一步会耗费大量时间，通常我们会让 e=65537，至于为什么，可以参考这篇文章https://www.johndcook.com/blog/2018/12/12/rsa-exponent/

第四步，求得e关于r的模逆元，命名为d，如果模逆元不存在，则重复步骤一二三。

import random
import math

def get_d(r):
    e = 65537
    for d in range(2, r):
        if d*e % r == 1:
            return d

d = get_d(r)
print(d)

得到 d=2217473

最后，将N和e封装成公钥，N和d封装成私钥。

公钥: N = 10098887, e = 65537

私钥：N = 10098887, d = 2217473

加密和解密

加密用到公钥（N，e），假如要加密的消息m=100，则加密就是计算 m的e次方然后对n取模

m = 100
N = 10098887
e = 65537

cipher = m**e % N

print(cipher)

密文为 cipher = 7065819

解密要用到私钥（N，d），解密就是把密文进行d次方，然后对N取余

N = 10098887
d = 2217473
cipher = 7065819

plaintext = cipher**d % N

print(plaintext)

得到明文 plaintext = 100

RSA的安全性

通过分析RSA的加密算法公钥私钥的生成过程，不难看到攻击者如果要破解获取到私钥，必须通过N进行因数分解得到p和q

N = p x q

而因数分解这个事，除了暴力穷举，没有别得办法，但如果N选的足够大，暴力破解是不可能完成的任务（除非量子计算机问世）。

维基百科说“2020年为止，世界上还没有任何可靠的攻击RSA算法的方式”，实际上到目前2022年，应该也没有什么可靠的算法。

N多大才算安全？

目前大多数的SSH客户端sshkey都会默认用RSA生成3072位key，因为这是最低安全标准，业界的共识一般是推荐使用4096位。

那这里的RSA key的位数是什么意思呢？ 这个位数实际上指的是N的二进制表示的位数。比如对于我们的前面的演示：

p = 4547
q = 2221
N = p*q = 10098887

N转换成二进制是100110100001100011000111，也就是24位，所以最后生成的key就是24位的。

以下内容来自维基百科：

针对RSA最流行的攻击一般是基于大数因数分解。1999年，RSA-155 (512 bits)被成功分解，花了五个月时间（约8000 MIPS年）和224 CPU hours在一台有3.2G中央内存的Cray C916计算机上完成。

RSA-155表示如下：

39505874583265144526419767800614481996020776460304936454139376051579355626529450683609
727842468219535093544305870490251995655335710209799226484977949442955603

= 3388495837466721394368393204672181522815830368604993048084925840555281177×
  11658823406671259903148376558383270818131012258146392600439520994131344334162924536139

2009年12月12日，编号为RSA-768（768 bits, 232 digits）数也被成功分解。这一事件威胁了现通行的1024-bit密钥的安全性，普遍认为用户应尽快升级到2048-bit或以上。

RSA-768表示如下：

123018668453011775513049495838496272077285356959533479219732245215172640050726
365751874520219978646938995647494277406384592519255732630345373154826850791702
6122142913461670429214311602221240479274737794080665351419597459856902143413

= 3347807169895689878604416984821269081770479498371376856891
  2431388982883793878002287614711652531743087737814467999489×
  3674604366679959042824463379962795263227915816434308764267
  6032283815739666511279233373417143396810270092798736308917

Python大因数分解

暴力的方法进行大因数分解并不难，也有很多现成的Python库可以用，比如sympy就可以。

以上面我们的N为例

p = 4547
q = 2221
N = p*q = 10098887

通过N去破解p和q非常简单，这个N只有22位，一秒就可以出结果。

from sympy import factorint

a = factorint(10098887)
print(a)

得到的结果a是

{2221: 1, 4547: 1}

也就是2221和4547.

最后

当然，针对RSA的攻击方法还有很多，这里就不展开了，感兴趣的同学可以自行查找相关资料。