Skip to content

Common Modulus Attack

有兩個公鑰 (n, e_1), (n, e_2) 有相同的 n (modulus),且 gcd(e_1, e_2) = 1

我們攔截到分別用這兩把公鑰加密 mc_1, c_2

那麼我們就可以在不分解 n 的情況下,還原 m

原理

e_1s_1 + e_2s_2 = gcd(e_1, e_2) = 1 根據貝祖定理 s_1, s_2 有整數解

可以用擴展歐幾里得求出 s_1, s_2

c_1^{s_1}c_2^{s_2} \equiv m^{e_1s_1}m^{e_2s_2} = m^{e_1s_1 + e_2s_2} = m \pmod{n}