非对称加密系统

为文章叙述的方便，用\( 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 \)。