跳转至

4.2 RSA 加密算法

非对称加密系统

为文章叙述的方便，用 \( P_A \) 和 \( S_A \) 分别表示A的公钥与私钥，用 \( P_A() \) 和 \( S_A() \) 分别表示A的公钥与私钥的函数。

非对称加密

Ciphertext = pa(Message)

Message = sa(Ciphertext)

数字签名

Signature = Sign(Message, sk)

Verify(Message, Signature, pk) = True/False

关于非对称加密的工作方式可以看之前的文章中有关非对称加密的部分，这里不在对此系统的工作方式做介绍。

RSA算法

RSA 公钥加密系统主要基于以下事实：寻找大素数是很容易的，但要把一个数分解为两个大素数的积却相当困难。

在 RSA 加密系统中，参与者按下列过程创建他的公钥和私钥：

  1. 找两个很大的素数 \( P \) 和 \( Q \)，使得 P ≠ Q，越大越好，比如 100 位长的，然后计算：

    \[ N = P \times Q \]
    \[ M = (P-1) \times (Q-1) \]

  2. 找到一个和 \( M \) 互素的小奇数 \( E \)

  3. 找一个整数 \( D \)，使得 \( E \times D \pmod M = 1 \)

此时 \( E, N \) 是公钥， \( D, N \) 是私钥，现在对 \( X \) 加密，得到密码 \( Y \)

\[ X^E \pmod N = Y \]

如果不知道 \( D, N \)，很难从 \( Y \) 恢复 \( X \)，但如果有 \( D, N \)，根据费尔马小定理，则只要按下面的公式就可以轻而易举地从 \( Y \) 得到 \( X \)。

\[ Y^D \pmod N = X \]

费尔马小定理：

  1. \( P \) 是一个质数，对于任何整数 \( M \)，如果 \( N \)、 \( P \) 互素，那么 \( N^{P-1} \equiv 1 \pmod P \)。
  2. \( P \) 是一个质数，对于任何整数 \( N^P \equiv N \pmod P \)。