Skip to content

Common Factor Attack

當兩個公鑰 (n_1, e_1), (n_2, e_2)n_1, n_2共同的質因數

我們直接用 gcd(n_1, n_2)O(log(min(n_1, n_2)) 的時間內分解 n_1, n_2

Batch GCD

當我們有一群公鑰,等於是我們有一堆 n,我們想知道是否有其中一對 n共同的質因數

z_1 為例,以下推導 gcd(N_1, \frac{z_1}{N_1}) 實際上就是 gcd(N_1, N_2 \cdots N_m)

我們可以把 z_1 寫成 z_1 = N_1 N_2 \cdots N_m \text{ mod } N_1^2 = N_1 N_2 \cdots N_m - k N_1^2 \text{ for some } k,那麼

\begin{align} &\frac{z_1}{N_1} = \frac{N_1 N_2 \cdots N_m - k N_1^2}{N_1} = N_2 \cdots N_m - k N_1 \\ &gcd(N_1, \frac{z_1}{N_1}) = gcd(N_1, N_2 \cdots N_m - k N_1) = gcd(N_1, N_2 \cdots N_m) \end{align}

第一步驟求乘法時用 product tree 加速
第二步驟求餘數時用 remainder tree 加速

相關資源

CTF 題目

SECCON 2017 Online CTF - Ps and Qs