Håstad’s Broadcast Attack

Last updated Unknown Edit Source

平文を互いに素な $N_1, \ldots, N_e$ で暗号化された暗号文が分かっているとき、中国剰余定理を用いて $m$ を求められる。

$$ \begin{aligned} c_1 &≡ m^e \pmod{N_1} \\ c_2 &≡ m^e \pmod{N_2} \\ \vdots \\ c_e &≡ m^e \pmod{N_e} \\ m^e &≡ CRT(c_1, c_2, \dots , c_e) \pmod{N_1N_2\cdots N_e} \\ m^e &= CRT(c_1, c_2, \dots , c_e) \end{aligned} $$

• They Were Eleven - BSides Ahmedabad CTF 2021 author’s writeup