Common Modulus Attack
概要
RSA暗号において、平文を
が同一かつ
が異なる公開鍵
でそれぞれ暗号化した暗号文
があり、
\begin{align}
\mathrm{gcd}(e_1,e_2) = 1
\end{align}
の時、
から平文
を導出することができる攻撃。
証明
RSA暗号の定義より、暗号文は以下で与えられる
\begin{align}
c_1 \equiv m^{e_1} \pmod{\ n} \\
c_2 \equiv m^{e_2} \pmod{\ n}
\end{align}
この攻撃の定義より、
\begin{align}
\mathrm{gcd}(e_1,e_2) = 1
\end{align}
拡張ユークリッドの互除法により、以下を満たす
を求めることができる
\begin{align}
{e_1}x+{e_2}y = \mathrm{gcd}(e_1,e_2)
\end{align}
はどちらかが、負の値を持つ。今、
が負であると仮定すると、
は以下のように計算される。
\begin{align}
({c_1}^{-1})^{-x} (c_2)^{y} \equiv {c_1}^{x}{c_2}^{y} \pmod{\ n}
\end{align}
暗号文はであるので、
\begin{align}
&\equiv (m^{e_1})^{x}(m^{e_2})^{y} \pmod{\ n} \\
&\equiv m^{e_1x+e_2y} \pmod{\ n}
\end{align}
今、
であるので、
\begin{align}
\equiv m \pmod{\ n}
\end{align}
となる。
であるので、
\begin{align}
= m
\end{align}
よって平文
を求めることができる。
別のパターン
\begin{align}
\mathrm{gcd}(e_1,e_2) \neq 1
\end{align}
となってこの攻撃の条件であるだけが違う場合、
であるので、
\begin{align}
m^{e_1x+e_2y} = m^{gcd(e_1,e_2)} \pmod{\ n}
\end{align}
となり
の
乗の値が求まる。
よって平文は、
乗根を取ると求まる。
\begin{align}
m = \sqrt[gcd(e_1,e_2)]{m^{gcd(e_1,e_2)}}
\end{align}
