把那些别人认为显然的而我死也想不出来的东西，都记下来
做作业的时候遇到了这么个题：
Alice and Bob love each other, so they decide to use a single RSA modulus N N 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 ) (e_A,d_A) (eA,dA) and ( e B , d B ) (e_B,d_B) (eB,dB) sharing the same N N N. Demonstrate how Bob can derive the private key of Alice.
大意是说，Alice 和 Bob 用传统的 RSA 进行交流，但用的是同一个模数 N N N。问 Bob 如何利用这一点来破解 Alice 的私钥。
\\ \\ \\
从实际的角度来看： 既然 Bob 拥有 N N N，那他肯定也拥有 N N N 的构造方法，也就是他知道 φ ( N ) \varphi(N) φ(N)（例如 N = p q N=pq N=pq，其中 p , q p,q p,q 都是质数，那么 φ ( N ) = ( p − 1 ) ( q − 1 ) \varphi(N)=(p-1)(q-1) φ(N)=(p−1)(q−1)）。而对于 Alice 有 e A d A ≡ 1 ( m o d φ ( N ) ) e_Ad_A \equiv 1 \pmod{\varphi(N)} eAdA≡1(modφ(N))，那么直接 exgcd 解逆元就完事了。
（就这？就这？上 google 查了下，还真就这。。。
但如果就这么简单地过掉这个题，也太无聊了。。。
事实上 Solution 1 是有一个很强的前提条件，就是知道 φ ( N ) \varphi(N) φ(N)，于是就没什么可做的了。 但如果去掉这个条件，那就变成一个有趣的数论题了。
现在的问题是：已知 Alice 和 Bob 使用了同样的模数 N N N，Bob 拥有 e A , e B , d B e_A,e_B,d_B eA,eB,dB，求 d A d_A dA。（这个模数、公钥私钥可以认为是第三方机构提供的，或是地上捡来的，反正你无法知道 N N N 的构成信息。）
\\ \\
思路就是：既然无法在模 φ ( N ) \varphi(N) φ(N) 下求逆元，那就想办法在 φ ( N ) \varphi(N) φ(N) 的倍数下求逆元。因为有一个结论：
Lemma1：若 e A d A ≡ 1 ( m o d k m ) e_Ad_A \equiv 1 \pmod{km} eAdA≡1(modkm)，则 e A d A ≡ 1 ( m o d m ) e_Ad_A \equiv 1 \pmod m eAdA≡1(modm) 。
即若两个数在模 k m km km 下互为逆元，则在模 m m m 下也为逆元。证明显然，把同余式写成等式就出来了。 因此我们只要找出 φ ( N ) \varphi(N) φ(N) 的一个倍数 k φ ( N ) k\varphi(N) kφ(N)，使得 e A e_A eA 在模 k φ ( N ) k\varphi(N) kφ(N) 下有逆元，那么这个逆元就是要求的 d A d_A dA。
而我们知道， e B d B − 1 e_Bd_B-1 eBdB−1 是一个天然的 φ ( N ) \varphi(N) φ(N) 的倍数，因为 e B d B ≡ 1 ( m o d φ ( N ) ) e_Bd_B \equiv 1 \pmod{\varphi(N)} eBdB≡1(modφ(N))，这是 RSA 保证的。我们从这里开始。 e A e_A eA 无法直接在模 e B d B − 1 e_Bd_B-1 eBdB−1 下求逆元，因为它俩可能不互质，那就约去 d 1 = gcd ( e A , e B d B − 1 ) d_1=\gcd(e_A,e_Bd_B-1) d1=gcd(eA,eBdB−1)，变成 e A e_A eA 在模 e B d B − 1 d 1 \frac{e_Bd_B-1}{d_1} d1eBdB−1 下求逆元。 这时候仍然可能没逆元，因为 e A e_A eA 跟 e B d B − 1 d 1 \frac{e_Bd_B-1}{d_1} d1eBdB−1 可能仍然不互质。那就继续求 d 2 = gcd ( e A , e B d B − 1 d 1 ) d_2=\gcd(e_A,\frac{e_Bd_B-1}{d_1}) d2=gcd(eA,d1eBdB−1)，变成 e A e_A eA 在模 e B d B − 1 d 1 d 2 \frac{e_Bd_B-1}{d_1d_2} d1d2eBdB−1 下求逆元。 …… 重复这个过程，直至 e A e_A eA 跟这个模数互质。 这是一定可以达到的。因为，初始的时候，假设 e B d B − 1 = k φ ( N ) e_Bd_B-1=k\varphi(N) eBdB−1=kφ(N)，而由于 gcd ( e A , φ ( N ) ) = 1 \gcd(e_A,\varphi(N))=1 gcd(eA,φ(N))=1（RSA 的性质），因此 d 1 = gcd ( e A , e B d B − 1 ) = gcd ( e A , k ) d_1=\gcd(e_A,e_Bd_B-1)=\gcd(e_A,k) d1=gcd(eA,eBdB−1)=gcd(eA,k)，因此模数除以 d 1 d_1 d1 也就相当于模数变成 k d 1 φ ( N ) \frac{k}{d_1}\varphi(N) d1kφ(N)。以后的步骤同理，模数一直都会是 φ ( N ) \varphi(N) φ(N) 的倍数。如果除到模数变成 φ ( N ) \varphi(N) φ(N) 了，那也不会继续进行下去了，因为 gcd ( e A , φ ( N ) ) = 1 \gcd(e_A,\varphi(N))=1 gcd(eA,φ(N))=1。
假设最终得到的模数为 m m m，那么就用 exgcd 解 e A d A ≡ 1 ( m o d m ) e_Ad_A \equiv 1 \pmod{m} eAdA≡1(modm)，按照 Lemma 1 以及上面说的“ m m m 一定是 φ ( N ) \varphi(N) φ(N) 的倍数”，解出来的 d A d_A dA 就是 Alice 的私钥了。
也就是说，在传统的 RSA 中，如果你发现别人跟你是同一个模数，那无论你知不知道这个模数的具体信息，你都可以直接解出别人的私钥了。
