这篇文章上次修改于 253 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

RSA（Rivest–Shamir–Adleman）是早期被广泛使用的非对称加密算法。不过后来 ECC 成为主流，因为 ECC 比 RSA 的安全性更高，密钥更短。

加密：A 用 B 的公钥加密，B 用自己的私钥解密
签名：A 用自己的私钥签名，B 用 A 的公钥验证

RSA 加密

算法描述

  • 密钥生成

    随机选择两个不同的大素数 $p$、$q$，计算 $n = pq$，$\phi = (p-1)(q-1)$

    随机选择 $e$ 满足 $1 < e < \phi$ 且 $e$ 和 $\phi$ 互质

    计算 $e$ 的逆 $d$，即 $ed = 1$ mod $\phi$，

  • 公钥：$n, e$
  • 私钥：$n, d$
  • 注意：$p, q, \phi$ 保密
  • 加密：给定公钥及明文 $m$，计算密文 $c = (m^e$ mod $n)$
  • 解密：给定私钥及密文 $c$，计算明文 $m = (c^d$ mod $n)$

  • 原理

    找到秘密指数 $d$ 需要一定的技巧。我们需要公开指数 $e$ 在模群阶下的逆元：

    $$ d = e^{-1} \space mod \space order $$

    通过扩展欧几里得算法可求得逆元，但是我们还需要知道群的阶。对于素数 $p$，阶是 $p-1$，所以可以求得 $d$，过程如下。

    根据欧拉定理，对于任何与 $p$ 互素的 $m$ 有

    $$ m^{order}=1 \space mod \space p $$

    order 表示模 $p$ 整数乘法群中元素的个数。意味着，对于任意整数乘法，有

    $$ m^{1 + multiple \times order} = m \times (m^{order})^{multiple} \space mod \space p = m \space mod \space p $$

    解密的等式等价于

    $$ m^{e \times d} = m \space mod \space p $$

    所以

    $$ e \times d = 1 + multiple \times order $$

    即

    $$ e \times d = 1 \space mod \space order $$

    由定义可知，$d$ 是 $e$ 在模 order 下的逆元。

    通过隐藏群的阶，可以防止其他人利用公开指数 $e$ 算出秘密指数 $d$。RSA 巧妙利用了这点：如果我们使用的模不是素数，而是两个素数的乘积 $N=p \times q$，则只要不知道 $p, q$，就不容易算出乘法群的阶。

攻击

  • 如果 $\phi$ 被公开，可以联合 $n = pq$ 和 $\phi = (p-1)(q-1)$ 解出 $p, q$

  • 同模攻击，可根据两个公钥推出明文

    两个密文 $c_1 = m^{e_1}$ mod $n$ 和 $c_2 = m^{e_2}$ mod $n$

    如果 $e_1$ 和 $e_2$ 互质，可根据 Euclidean 扩展算法找出 $r, s$，满足 $re_1 + se_2 = 1$

    假如 $r$ 是负数（$r$ 和 $s$ 必有一个是负数），那么再用 Euclidean 算法计算 $c_1^{-1}$

    进而算出 $(c_1^{-1})^{-r} \times c_2^s = m$ (mod $n$)

  • 选择密文攻击，提问 $c$ 之外的任意明文 $m = c^d$ mod $n$

    随机选择 $x \in Z_n^*$，计算 $c' = c \cdot x^e$ mod $n$，提问 $c'$，得到 $c'^{d} = mx$ mod $n$，从而得到

RSA 签名

在相同的安全级别下，RSA 的密钥和签名比 ECDSA 长。3071-bit 的 RSA 签名与 256-bit 的 ECDSA 签名有着相同的安全性。

  • 签名：使用私钥对消息 $m$ 签名 $s = m^d$ mod $n$
  • 验签：使用公钥验证 $m' = s^e$ mod $n$，如果 $m'=m$，则成功

参考

The RSA Cryptosystem - Concepts

RSA Signatures

戴维-王. 深入浅出密码学[M]