RSA是一种非对称加密算法。谓之“非对称”,是因为加密和解密使用的是不同的密钥。RSA算法利用公钥来加密,用私钥来解密;公钥可以随意公布,任何人都可以利用公钥来加密一条信息,但只有私钥持有者才能把信息解密。

  这是非常有用的加密体系。譬如,Alice 想给 Bob 发送一条信息,那么她可以在网上找到 Bob 的公钥,然后加密信息,并通过随便什么渠道传送给 Bob. 假设有一位窃听者 Eve 得到了加密后的信息,他也无法解密,因为没有私钥。

  RSA另有一个特点:用私钥加密的信息,用公钥可以解密。这让基于RSA的数字签名成为可能。假如我写了一篇文章,我可以用私钥加密这一篇文本的md5值,把密文(也就是签名)附在文章后面。读者从可信的渠道得到我的公钥,利用公钥解密签名,发现与这篇文章的md5值一致,于是可以确信这篇文章确实是我写的。

  RSA是极其巧妙的算法,而它的数学基础却出奇地简单,代码实现也不复杂。RSA同时是一个难以破解的密码体系,破解RSA的速度取决于大整数分解的速度。从RSA中,我们可以看到数论在现实生活中的运用,以及令人惊叹的人类智慧。

  RSA算法的发明者是:Ron Rivest、Adi Shamir、Leonard Adleman,算法提出于1977年。

RSA的数学基础

  学过数论的同学,对欧拉函数不会陌生。它是一个数论函数(定义域为正整数集,值域为复数集),定义是:$\varphi(n)$ 为 $\{1, 2,3,\cdots ,n\}$ 中与$n$互质的数的个数。

  举几个例子:$\varphi(6)=2$,因为6以内与6互质的数只有1和5. 而$\varphi(10)=4$,因为10以内与10互质的数有1、3、7、9,共4个。另外,不难发现,对于质数$p$,有$\varphi(p) = p-1$.

  为了更深入地讨论欧拉函数的性质,我们需要知道欧拉函数的通项公式。如果您只是想知道 RSA 算法怎么写、怎么用,则下面一段可以跳过。


  欧拉函数的通项公式是什么?我们先给出结论,再谈谈是如何找到这个结论的。$$\varphi(n) = n \cdot \prod_{p}(1 - \frac1p)~~,其中p是n的质因子$$

  想求出$\varphi(n)$,那就得统计出 $n$ 以内有多少个与 $n$ 互质的数。那么,与 $n$ 互质的数 $r$ 有什么特点呢?关键在于: $n$ 拥有的质因子, $r$ 全都没有。换句话讲:假设 $n$ 的质因数分解为$$n = p_1^{k_1}\cdot p_2 ^ {k_2} \cdots p_c ^{k_c}$$则 $r$ 必然满足 $r \% p_1 = 0, r\% p_2=0,\cdots$ 既然如此,研究 $r$ 模掉 $n$ 的质因子们所得到的结果,就可以看出 $r$ 的一些性质。我们来造一个函数:$G(x) = (x\% p_1^ {k_1}, ~ x\% p_2 ^ {k_2},  ~ \cdots x \% p_c ^ {k_c})$,有性质如下:

  $r$ 与 $n$ 互质,当且仅当 $G(r)$ 生成的元组中,对于第 $i$ 位,总有它不能被 $p_i$ 整除。我们把这种元组称为合法元组。

  这是一条很平凡的性质,但它可以成为计数的一把钥匙。直接统计 $n$ 以内与 $n$ 互质的数是困难的,但统计有多少个合法元组则简单得多。合法元组的第 $i$ 位不能是 $p_i$ 的倍数或0,那么这一位有 $p_i^{k_i} \cdot (1-\frac1{p_i})$ 种取值,故依据乘法原理,合法元组的总数是:$$\prod_{i<c}p_i ^ {k_i} (1-\frac1{p_i}) ~ = ~ \prod_{i<c}p_i ^ {k_i} \prod_{i<c}(1-\frac1{p_i})  ~ =  ~ n \prod_{i<c}(1-\frac1{p_i})$$

  这个式子要成为欧拉函数的通项公式,还有最后一步路要走:$G$目前只是一个普通映射,既有可能多个 $r$ 对应同一个合法元组,也可能一个合法元组对应不了任何 $r$. 从而合法元组的数量未必恰好就是与 $n$ 互质的数的数量。接下来的任务是:证明 $G: \{1,2,3,\cdots ,n\} \to (元组)$ 是一个双射。

  还记得中国剩余定理(CRT)吗?它通过一个精妙的构造,指出了 $(元组)\to \{1,2,3,\cdots ,n\}$是一个双射(当然了,这个结论只是CRT的一个副产品)。中国剩余定理在这里不再赘述,感兴趣的读者可以去查阅相关资料。总之,既然元组与 $n$ 以内的整数是一一对应的,那么合法元组的数量就是 $n$ 以内与 $n$ 互质的数的个数。从而我们得到了欧拉函数的通项公式:$$\varphi(n) = n \cdot \prod_{p}(1 - \frac1p)~~,其中p是n的质因子$$


  现在我们手上有欧拉函数的通项公式了。可以随便挑几个数验证一下:$$\varphi(10) = 10 \times \frac12 \times \frac45 = 4,\quad \varphi(24) = 24 \times \frac12 \times \frac23 = 8$$

  利用欧拉函数的通项公式,可以得到两条性质:

  1. $\varphi$ 是积性函数。若 $a,b$ 互质,则有$\varphi(ab) = \varphi(a)\cdot \varphi(b)$      
  2. 欧拉定理。若 $a, m$ 互质,则有 $a^{\varphi(m)} \equiv 1 \pmod m$
    不难发现,费马小定理是欧拉定理在 $m$ 为质数下的情形。              

  以上这堆性质的证明、欧拉函数通项的求法、线性筛欧拉函数、扩展欧几里得算法,是接下来代码实现的基础。我一年前给高中生讲数论的时候做了篇课件,恰好涵盖了这些内容,点这里下载

  欧拉定理是欧拉函数最大的作用。利用欧拉定理可以得到结论:若$a,m$互质,则$$a^b \equiv a ^ {b \% \varphi(m)} \pmod m$$ 这不仅大大降低了计算复杂度(可以利用快速幂算法),也是 RSA 算法的基石。

RSA算法

  RSA算法的过程如下:

  1. 随便选择两个极大的质数,分别记为 $p, q$. 当然这里 $p\neq q$.
  2. 记 $N = p\cdot q$, 则由欧拉函数的积性有 $\varphi(N) = (p-1)(q-1)$.
  3. 选取一个小于 $ N $ 的 $e$, 使得 $\gcd(e, N)=1$. 求出 $e$ 在模 $\varphi(N)$ 意义下的逆元,记为$d$.
  4. 我们得到了$(N, e)$作为公钥,$(N, d)$作为私钥。
    P.S. 注意到 $e$ 和 $d$ 是对称的,把 $e$ 拿去当私钥,把 $d$ 拿去当公钥也可行。

  公钥可以分发给所有人,私钥必须保存好。接下来,别人可以用公钥加密信息发给我,我用私钥可以解密这条信息。下面来讨论加密、解密算法。

  假设 Alice 想给 Bob 发一条信息,于是搞到了 Bob 的公钥$(N, e)$. 设 $m$ 为明文,则我们这样计算出密文:$$c \equiv m^e \pmod N$$ Bob 收到密文 $c$ 之后,用自己手上的私钥解密:$$m \equiv c^ d \pmod N$$

  为什么这样就可以恢复出明文 $m$?注意到$$c^d \equiv (m^e) ^ d \equiv m^{ed} \equiv m^ {ed \% \varphi(N)} \pmod N$$而 $e,d$ 在模$\varphi(N)$意义下互为逆元,故$ed \% \varphi(N) = 1$. 从而 $m^ {ed \% \varphi(N)} \equiv m \pmod N$. 证毕。

  代码实现RSA加密、解密异常简单,只需要会扩展欧几里得算法、快速幂就行了。如下:

def exgcd(a, b):                   # 扩展欧几里得算法
    if b==0: return (1, 0)
    x, y = exgcd(b, a%b)
    return (y, x-a//b*y)

def getInv(a, mod):                # exgcd求逆元
    x, y = exgcd(a, mod)
    return x
    # Python下负数模正数得到正数。如果是其他语言,得返回 (x % mod + mod) % mod

def quickPow(x, p, mod):           # 模 mod 意义下求 x 的 p 次方
    if p==0: return 1
    if p==1: return x

    t = quickPow(x, p//2, mod)
    if p%2 == 0: return t * t % mod
    return t * t * x % mod

def encrypt(m, N, e):           # 加密
    return quickPow(m, e, N)

def decrypt(c, N, d):           # 解密
    return quickPow(c, d, N)

# 拿 bsdgames 里面的 `primes` 程序随便造的 p, q
p = 100088459
q = 1000049473

N = p * q
phi = (p-1) * (q-1)
e = 2333333
d = getInv(e, phi)

c = encrypt(123454321, N, e)
print(c) # 加密 `123454321`,得到密文:`8922052926595796`

m = decrypt(c, N, d)
print(m) # 解密,得到明文 `123454321`
RSA加密和解密

RSA的安全性

  RSA是一个简单的算法,(主流的)攻击思路也不复杂:解密是需要私钥 $(N, d)$ 的,那么目标就是取得 $d$;由于$d$是 $e$ 在模 $\varphi(N)$ 意义下的逆元,故只需要知道 $\varphi(N)$ 就可以由公钥推出私钥;而要想知道 $\varphi(N)$ 是多少,只需要质因数分解$N$——因此,一般认为,RSA的安全性取决于分解$N$的难度。

  目前,分解质因数是极端困难的。人们没有找到多项式时间内分解质因数的做法。而生成一个质数却很简单——我们拥有判断一个数是否为质数的快速算法(例如Miller-Rabin算法),又有质数定理: $\Pi (n) \sim n/\ln n$ 保证了 $n$ 附近期望每 $\ln n$ 个数里面就有一个质数。想找到适合RSA的大质数 $p,q$,只需要随机生成很大的数,然后检验是不是质数,重复几次就可以达到目标。

  尽管现在没有多项式时间内分解质因数的算法,但有些算法还是比较快的——例如 Pollard's rho. 此外,量子计算机上可以实现Shor算法,但目前没有多大的应用价值。推荐使用不低于2048位的密钥,这里的密钥长度是指模数 $N$ 的二进制长度。

生成RSA密钥对

  ssh-keygen 程序可以造一个RSA密钥对,接下来这个密钥对可以用于git身份验证、ssh服务器身份验证等很多功能。

生成一个RSA密钥对 

  接下来,我们来看这里面有什么东西。 hello 是私钥文件, hello.pub 是公钥文件。里面的东西都是base64编码过的,可以用RsaCtfTool来查看。

公钥文件 
私钥文件 

几道CTF题

Jarvis OJ: veryeasyRSA

已知RSA公钥生成参数:
p = 3487583947589437589237958723892346254777
q = 8767867843568934765983476584376578389
e = 65537, 求d
In [2]: p = 3487583947589437589237958723892346254777

In [3]: q = 8767867843568934765983476584376578389

In [4]: e = 65537

In [5]: phi = (p-1) * (q-1)

In [6]: gmpy2.invert(e, phi)
Out[6]: mpz(19178568796155560423675975774142829153827883709027717723363077606260717434369)
JarvisOJ: Easy RSA

还记得veryeasy RSA吗?是不是不难?那继续来看看这题吧,这题也不难。
已知一段RSA加密的信息为:0xdc2eeeb2782c
已知加密所用的公钥:(N=322831561921859 e = 23)
请解密出明文,提交时请将数字转化为ascii码提交
In [2]: c = 0xdc2eeeb2782c

In [3]: n = 322831561921859

In [4]: e = 23

In [7]: !factor {n}
322831561921859: 13574881 23781539

In [8]: p = 13574881; q = 23781539

In [9]: phi = (p-1)*(q-1)

In [10]: d = gmpy2.invert(e, phi)

In [14]: hex(gmpy2.powmod(c, d, n))
Out[14]: '0x33613559'

In [16]: codecs.decode('33613559', 'hex')
Out[16]: b'3a5Y'
BUUCTF: RSA

在一次RSA密钥对生成中,假设p=473398607161,q=4511491,e=17
求解出d作为flag提交
In [21]: p = 473398607161

In [22]: q = 473398607161

In [23]: e = 17

In [24]: gmpy2.invert(e, (p-1)*(q-1))
Out[24]: mpz(13182720074178117839153)
BUUCTF: rsarsa

Math is cool! Use the RSA algorithm to decode the secret message, c, p, q, and e are parameters for the RSA algorithm.
(给定了 p, q, e, c)
Use RSA to find the secret message
In [25]: p =  96484230290105156765905517400104265349457376392357398006439893520398525072984913995610350091634    ...: 27050370107570733633350911691280297777160200625281665378483

In [26]: q =  11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732    ...: 443992230647903887510065547947313543299303261986053486569407

In [27]: e =  65537

In [28]: c =  83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605    ...: 6473166465764865262174570063768422808697285817267464015837058999417682141387422596893348407356335530    ...: 5388764184765117377625182029308721288567018036740680740676592363897316137581739273774783276275169010    ...: 4423869019034

In [29]: d = gmpy2.invert(e, (p-1)*(q-1))

In [30]: gmpy2.powmod(c, d, p*q)
Out[30]: mpz(5577446633554466577768879988)