RSA加密算法原理

简介

RSA加密算法是一种非对称加密算法。

所需数学知识

想要完整地理解RSA加密算法，需要了解不少数论知识，下面介绍几点核心内容。

同余

同余是数论中的一种等价关系。两个整数 $a$、$b$，若它们除以正整数 $m$ 所得的余数相等，则称 $a$、$b$ 对于模 $m$ 同余，表示为：
$$a \equiv b \quad (mod \quad m)$$

同余式有多种性质：

整除性
$$a\equiv b{\pmod {m}}\Rightarrow c\cdot m=a-b,c\in \mathbb {Z}$$
传递性
$$ \left.{\begin{matrix}a\equiv b{\pmod {m}}\\b\equiv c{\pmod {m}}\end{matrix}}\right\} \Rightarrow a\equiv c{\pmod {m}}$$
保持基本运算
$$\left.{\begin{matrix}a\equiv b{\pmod {m}}\\c\equiv d{\pmod {m}}\end{matrix}}\right\}\Rightarrow \left\{{\begin{matrix}a\pm c\equiv b\pm d{\pmod {m}}\\ac\equiv bd{\pmod {m}}\end{matrix}}\right.$$
当 $c=d$ 时，则为等量加法、减法：$a\pm c\equiv b\pm c{\pmod {m}}$

此性质更可进一步引申成：
$$ a\equiv b{\pmod {m}}\Rightarrow {\begin{cases}an\equiv bn{\pmod {m}},\forall n\in \mathbb {Z} \\a^{n}\equiv b^{n}{\pmod {m}},\forall n\in \mathbb {N} ^{0}\end{cases}}$$
更多性质见同余 - 维基百科

欧拉定理

在数论中，欧拉定理)是一个关于同余的性质。

若 $n$, $a$ 为正整数，且 $n$, $a$ 互质，即 $gcd(n,a)=1$，则
$$a^{\varphi(n)}\equiv1 \quad (mod \quad n)$$
其中 $\varphi(n)$ 为欧拉函数。

欧拉函数

在数论中，对正整数 $n$，欧拉函数 $\varphi (n)$ 是小于或等于 $n$ 的正整数中与 $n$ 互质的数的数目。
特别地：

若 $n$ 为质数，则 $\varphi(n) = n - 1$
若 $n$ 可以表示为两个互质的整数之积，比如 $n=pq$，则 $\varphi(n)=\varphi(p)\varphi(q)$
若 $n$ 可以表示为两个质数之积，比如 $n=pq$，则 $\varphi(n)=\varphi(p)\varphi(q) = (p-1)(q-1)$

扩展欧几里得算法

扩展欧几里得算法是欧几里得算法的扩展。已知整数 $a$、$b$，扩展欧几里得算法在求得 $gcd(a,b)$ 的同时，能找到整数 $x$、$y$，使它们满足裴蜀等式：
$$ax+by=gcd(a,b)$$

扩展欧几里得算法可用于求解裴蜀等式：
$$ax+by=m$$

当且仅当 $m$ 是 $a$ 与 $b$ 的最大公约数的倍数时，该方程有解，且有解时必有无数组解。

模反元素

模反元素也称为模倒数，或者模逆元。

一整数 $a$ 对同余 $n$ 之模逆元是指满足以下公式的整数 $b$
$$a^{-1}\equiv b{\pmod {n}}$$

也可以写成以下的式子
$$ab\equiv 1{\pmod {n}}$$

或者
$$ab{\pmod n}=1$$

由定义可得：
$$ab = 1 + kn \Rightarrow ab - kn = 1$$

要求解 $b$，就需要求不定方程 $ax + ny = 1$ 的解，根据裴蜀定理，当且仅当 $1$ 是 $gcd(a, n)$ 的整数倍时，即 $a$ 与 $n$ 互质时，上述方程有解。用扩展欧几里得算法求得的 $x$ 即为模反元素 $b$。

生成密钥

假设Alice想要通过一个不可靠的媒体接收Bob的一条私人信息。她可以用以下的方式来产生一个公钥和一个私钥：

任意选取两个大质数 $p$、$q$，保证 $p \neq q$ ，计算 $N=pq$
根据欧拉函数，计算 $$\begin{equation}\begin{split} \varphi(N)&=\varphi(pq)\\\\ &=\varphi(p)\varphi(q)\\\\ &=(p-1)(q-1)\end{split}\end{equation}$$
选择一个小于 $\varphi(N)$ 的整数 $e$，使 $e$ 与 $\varphi(N)$ 互质，并求得 $e$ 关于 $\varphi(N)$ 的模逆元，称为 $d$。
由模逆元的定义可得： $ed \equiv 1 {\pmod {\varphi(N)}}$
则有 $ed + h\varphi(N) = 1$
已知 $e$ 与 $\varphi(N)$ 互质，根据裴蜀定理知该不定方程有解，利用扩展欧几里得算法即可求得 $e$ 的模逆元 $d$
销毁 $p$、$q$、$\varphi(N)$

Alice将她的公钥 $(N,e)$ 传给Bob，而将她的私钥 $(N,d)$ 藏起来。

加密与解密

加密

假设Bob想给Alice送一个消息，他知道Alice产生的 $N$ 和 $e$。他使用起先与Alice约好的格式将消息转换为一个小于 $N$ 的非负整数 $m$，比如他可以将每一个字转换为这个字的Unicode码，然后将这些数字连在一起组成一个数字。假如他的信息非常长的话，他可以将这个信息分为几段，然后将每一段转换为 $m$。用下面这个公式他可以将 $m$ 加密为 $c$：
$$ c\equiv m^e {\pmod N}$$

计算 $c$ 并不复杂。Bob算出 $c$ 后就可以将它传递给Alice。

解密

Alice得到Bob的消息 $c$ 后就可以利用她的密钥 $N$ 和 $d$ 来解码。她可以用以下这个公式来将 $c$ 转换为 $m$：
$$m \equiv c^d {\pmod N}$$

得到 $m$ 后，她可以将原来的信息重新复原。

解密原理

根据加密公式可得：

$$\begin{equation}\begin{split} &c \equiv m^e {\pmod N} \Rightarrow\\\\ &(c)^d \equiv (m^e)^d {\pmod N} \Rightarrow\\\\ &c^d \equiv m^{ed} {\pmod N}\\\\ \end{split}\end{equation}$$

只要能证明下面的式子，就说明解密公式是正确的：

$$\begin{equation} c^d \equiv m^{ed} \equiv m {\pmod N} \end{equation}$$

证明：
根据密钥推导过程，可知 $ed = 1 + h\varphi(N) $，则
$$m^{ed} = m^{1+h\varphi(N)} = (m^{\varphi(N)})^h m$$

若明文 $m$ 与 $N$ 互质，根据欧拉定理可得：

$$\begin{equation}\begin{split} &m^{\varphi(N)} \equiv 1 {\pmod N} \Rightarrow\\\\ &(m^{\varphi(N)})^h \equiv (1)^h {\pmod N} \Rightarrow\\\\ &(m^{\varphi(N)})^hm \equiv (1)^hm {\pmod N} \Rightarrow\\\\ &m^{ed} \equiv m {\pmod N} \Rightarrow\\\\ &c^{d} \equiv m {\pmod N}\\\\ \end{split}\end{equation}$$

若明文 $m$ 与 $N$ 不互质，由于 $N=pq$，且$p$、$q$均为质数，而 $0 < m < N$，故 $m=kp$ 或 $m=kq$，下面以 $m=kp$ 为例展开证明：

如果 $m=kp$，则 $m$ 不会是 $q$ 的倍数，否则 $m$ 就会大于等于 $N$，违反了前提条件，而 $q$ 又是质数，故 $m$ 与 $q$ 互质，根据欧拉定理可得：
$$\begin{equation}\begin{split} &m^{\varphi(q)} \equiv 1 {\pmod q} \Rightarrow\\\\ &(m^{\varphi(q)})^{\varphi(p)} \equiv (1)^{\varphi(p)} {\pmod q} \Rightarrow\\\\ &m^{\varphi(q)\varphi(p)} \equiv 1 {\pmod q} \Rightarrow\\\\ &m^{\varphi(N)} \equiv 1 {\pmod q} \Rightarrow\\\\ &m^{h\varphi(N)} \equiv 1 {\pmod q} \Rightarrow\\\\ &m^{1+h\varphi(N)} \equiv m {\pmod q} \Rightarrow\\\\ &(kp)^{1+h\varphi(N)} \equiv kp {\pmod q} \Rightarrow\\\\ \end{split}\end{equation}$$

由上式可得：

$$\begin{equation}\begin{split} &kp(kp)^{h\varphi(N)} = kp + tq\\\\ \end{split}\end{equation}$$

由于$p$ 与 $q$ 互质，要使该式成立，须有 $t=t’p$，代入上式可得：

$$\begin{equation}\begin{split} &(kp)^{1+h\varphi(N)} = kp + t‘qp \Rightarrow\\\\ &(kp)^{1+h\varphi(N)} = kp + t‘N \Rightarrow\\\\ &m^{1+h\varphi(N)} = m + t‘N \Rightarrow\\\\ &m^{1+h\varphi(N)} \equiv m {\pmod N} \Rightarrow \end{split}\end{equation}$$

结合 $m^{ed} = m^{1+h\varphi(N)} = (m^{\varphi(N)})^h m$ 可得：

$$\begin{equation}\begin{split} &c^d \equiv m^{ed} \equiv m^{1+h\varphi(N)} \equiv m {\pmod N} \end{split}\end{equation}$$

签名与验证

见RSA加密算法 - 维基百科。

基本原理与加密、解密基本一致，只是用私钥加密，用公钥解密。

算法安全性

假设偷听者Eve获得了Alice的公钥 $n$ 和 $e$ 以及Bob的加密消息 $c$，但她无法直接获得Alice的密钥 $d$。要获得 $d$，最简单的方法是将 $n$ 分解为 $p$ 和 $q$，这样她可以得到同余方程 $ed\equiv 1{\pmod{(p-1)(q-1)}}$并解出 $d$，然后代入解密公式
$$c^{d}\equiv m\ (\mathrm {mod} \ n)$$

导出m（破密）。但至今为止还没有人找到一个多项式时间的算法来分解一个大的整数的因子，同时也还没有人能够证明这种算法不存在（见因数分解）。

至今为止也没有人能够证明对 $n$ 进行因数分解是唯一的从 $c$ 导出 $n$ 的方法，直到今天也还没有找到比它更简单的方法。（至少没有公开的方法。）

因此今天一般认为只要 $n$ 足够大，那么黑客就没有办法了。

假如 $n$ 的长度小于或等于256位，那么用一台个人电脑在几个小时内就可以分解它的因子了。1999年，数百台电脑合作分解了一个512位长的 $n$。一个由Shamir 和Tromer在2003年从理论上构建的硬件TWIRL，使人们开始质疑1024位长的 $n$ 的安全性，目前推荐 $n$ 的长度至少为2048位。

1994年彼得·秀尔（Peter Shor）证明一台量子计算机可以在多项式时间内进行因数分解。假如量子计算机有朝一日可以成为一种可行的技术的话，那么秀尔的算法可以淘汰RSA和相关的派生算法。（即依赖于分解大整数困难性的加密算法）

假如有人能够找到一种有效的分解大整数的算法的话，或者假如量子计算机可行的话，那么在解密和制造更长的钥匙之间就会展开一场竞争。但从原理上来说RSA在这种情况下是不可靠的。

DEMO

下面的代码根据上述原理实现了一个简单版本的RSA密钥生成、加密、解密的DEMO。

本以为应该不难实现，结果发现大质数的生成本身就是问题，除此之外还有其它的一些问题。关键问题以及大致思路：

质数的生成，经过查阅资料，得知大致方法是随机选取大整数，并通过一些方法判断它是不是质数，然而暴力的方法复杂度极高，目前有几种比较有效的质数判定方法，在此不再赘述，可自行查阅相关资料。下列程序当中使用了 Crypto 模块的素数生成功能。
公钥参数 $e$ 的生成， $e$ 需要与 $\varphi(N)$ 互质，一种简单的思路是选取一个质数 $e$，只要 $\phi(N)$ 不是它的整数倍即可。

具体代码如下:

from typing import Tuple


class RSAKey:
  class RSAParams:
    def __init__(self, p, q, N, phiN, e, d) -> None:
        self.p = p
        self.q = q
        self.N = N
        self.phiN = phiN
        self.e = e
        self.d = d

    def __str__(self) -> str:
        return f"""{{
  p: {self.p}\n
  q: {self.q}\n
  N: {self.N}\n
  phiN: {self.phiN}\n
  e: {self.e}\n
  d: {self.d}
}}"""

  def __init__(self) -> None:
    self.params = self.__generateRSAParams()

  def getPublicKey(self) -> Tuple[int, int]:
    """get public key
    Returns:
        Tuple[int, int]: (N, e)
    """
    return (self.params.N, self.params.e)

  def getPrivateKey(self) -> Tuple[int, int]:
    """get private key
    Returns:
        Tuple[int, int]: (N, d)
    """
    return (self.params.N, self.params.d)

  def __generateRSAParams(self) -> RSAParams:
    """Generate parameters for RSA
    Returns:
        RSAParams: instance of RSAParams
    """
    # 产生两个大素数
    from Crypto.Util import number
    p : int = number.getPrime(10)
    q : int = number.getPrime(10)

    # p 与 q 不能相等
    while q == p:
      q : int = number.getPrime(10)

    # N = p x q
    N : int = p * q

    # phi(N)
    phiN : int = (p - 1) * (q - 1)

    # 取公钥参数 e，e 应小于 phi(N) 且与 phi(N) 互质
    # 一种简单的思路是找到一个质数 e，只要 phi(N) 不是它的倍数即可
    e : int = number.getPrime(16)
    while phiN % e == 0:
      e : int = number.getPrime(16)

    # 使用扩展欧几里得算法求解 e 的模逆元 d
    _, d, _ = self.__exgcd(e, phiN)

    # 如果计算得到的 d 是负数，则加上 phi(N) 将其转为正数，仍然与 phi(N) 保持同余关系 
    if d < 0:
      d = d + phiN

    return self.RSAParams(p, q, N, phiN, e, d)

  def __exgcd(self, a, b):
    """扩展欧几里得算法
    Args:
        a (int): a
        b (int): b
    Returns:
        int: (gcd, x, y)
    """
    ri :int = a
    rj :int = b
    si :int = 1
    sj :int = 0
    ti :int = 0
    tj :int = 1

    while rj != 0:
      qi = ri // rj

      rtemp = rj
      rj = ri - qi * rj
      ri = rtemp

      stemp = sj
      sj = si - qi * sj
      si = stemp

      ttemp = tj
      tj = ti - qi * tj
      ti = ttemp
    
    return ri, si, ti


def encrypt(m, publicKey) -> int:
  """encrypt message using public key
  Args:
      m (int): origin message m
      publicKey (Tuple[int, int]): (N, e)
  Returns:
      int: encrypted message c
  """
  N, e = publicKey
  c = m ** e % N
  return c


def decrypt(c, privateKey) -> int:
  """decrypt message using private key
  Args:
      c (int): encrypted message c
      privateKey (Tuple[int, int]): (N, d)
  Returns:
      int: origin message m
  """
  N, d = privateKey
  m = c ** d % N
  return m


def main():
  rsakey = RSAKey()
  publicKey = rsakey.getPublicKey()
  privateKey = rsakey.getPrivateKey()

  print(f"publicKey: {publicKey}")
  print(f"privateKey: {privateKey}")

  message = 12345
  encryptedMessage = encrypt(message, publicKey)
  decryptedMessage = decrypt(encryptedMessage, privateKey)

  print(f"origin message: {message}")
  print(f"encrypted message: {encryptedMessage}")
  print(f"decrypted message: {decryptedMessage}")


if __name__ == '__main__':
  main()

参考资料

扩展欧几里得算法 - 维基百科
 同余 - 维基百科
 欧拉定理 - 维基百科)
欧拉函数 - 维基百科
 模反元素 - 维基百科
 RSA加密算法 - 维基百科
 阮一峰：RSA算法原理（一）
阮一峰：RSA算法原理（二）
阮一峰：数字签名是什么？
RSA算法的数学原理与证明