RSA 破解同一模数的其他私钥

  把那些别人认为显然的而我死也想不出来的东西，都记下来

Task

  做作业的时候遇到了这么个题：

Alice and Bob love each other, so they decide to use a single RSA modulus $N$ for their key pairs. Of course each of them does not know the private key of the other. Mathematically, Alice and Bob have their own key pairs $(e_A,d_A)$ and $(e_B,d_B)$ sharing the same $N$. Demonstrate how Bob can derive the private key of Alice.

  大意是说，Alice 和 Bob 用传统的 RSA 进行交流，但用的是同一个模数 $N$。问 Bob 如何利用这一点来破解 Alice 的私钥。

Solution1

  从实际的角度来看：
  既然 Bob 拥有 $N$，那他肯定也拥有 $N$ 的构造方法，也就是他知道 $\varphi(N)$（例如 $N=pq$，其中 $p,q$ 都是质数，那么 $\varphi(N)=(p-1)(q-1)$）。而对于 Alice 有 $e_Ad_A \equiv 1 \pmod{\varphi(N)}$，那么直接 exgcd 解逆元就完事了。

  （就这？就这？上 google 查了下，还真就这。。。

Solution 2

  但如果就这么简单地过掉这个题，也太无聊了。。。

  事实上 Solution 1 是有一个很强的前提条件，就是知道 $\varphi(N)$，于是就没什么可做的了。
  但如果去掉这个条件，那就变成一个有趣的数论题了。

  现在的问题是：已知 Alice 和 Bob 使用了同样的模数 $N$，Bob 拥有 $e_A,e_B,d_B$，求 $d_A$。（这个模数、公钥私钥可以认为是第三方机构提供的，或是地上捡来的，反正你无法知道 $N$ 的构成信息。）

  思路就是：既然无法在模 $\varphi(N)$ 下求逆元，那就想办法在 $\varphi(N)$ 的倍数下求逆元。因为有一个结论：

Lemma1：若 $e_Ad_A \equiv 1 \pmod{km}$，则 $e_Ad_A \equiv 1 \pmod m$ 。

  即若两个数在模 $km$ 下互为逆元，则在模 $m$ 下也为逆元。证明显然，把同余式写成等式就出来了。
  因此我们只要找出 $\varphi(N)$ 的一个倍数 $k\varphi(N)$，使得 $e_A$ 在模 $k\varphi(N)$ 下有逆元，那么这个逆元就是要求的 $d_A$。

  而我们知道，$e_Bd_B-1$ 是一个天然的 $\varphi(N)$ 的倍数，因为 $e_Bd_B \equiv 1 \pmod{\varphi(N)}$，这是 RSA 保证的。我们从这里开始。
  $e_A$ 无法直接在模 $e_Bd_B-1$ 下求逆元，因为它俩可能不互质，那就约去 $d_1=\gcd(e_A,e_Bd_B-1)$，变成 $e_A$ 在模 $\frac{e_Bd_B-1}{d_1}$ 下求逆元。
  这时候仍然可能没逆元，因为 $e_A$ 跟 $\frac{e_Bd_B-1}{d_1}$ 可能仍然不互质。那就继续求 $d_2=\gcd(e_A,\frac{e_Bd_B-1}{d_1})$，变成 $e_A$ 在模 $\frac{e_Bd_B-1}{d_1d_2}$ 下求逆元。
  ……
  重复这个过程，直至 $e_A$ 跟这个模数互质。
  这是一定可以达到的。因为，初始的时候，假设 $e_Bd_B-1=k\varphi(N)$，而由于 $\gcd(e_A,\varphi(N))=1$（RSA 的性质），因此 $d_1=\gcd(e_A,e_Bd_B-1)=\gcd(e_A,k)$，因此模数除以 $d_1$ 也就相当于模数变成 $\frac{k}{d_1}\varphi(N)$。以后的步骤同理，模数一直都会是 $\varphi(N)$ 的倍数。如果除到模数变成 $\varphi(N)$ 了，那也不会继续进行下去了，因为 $\gcd(e_A,\varphi(N))=1$。

  假设最终得到的模数为 $m$，那么就用 exgcd 解 $e_Ad_A \equiv 1 \pmod{m}$，按照 Lemma 1 以及上面说的“$m$ 一定是 $\varphi(N)$ 的倍数”，解出来的 $d_A$ 就是 Alice 的私钥了。

结论

  也就是说，在传统的 RSA 中，如果你发现别人跟你是同一个模数，那无论你知不知道这个模数的具体信息，你都可以直接解出别人的私钥了。