公開鍵暗号 RSA - Common Modulus Attack, 秘密鍵からの素因数分解 - ₍₍ (ง ˘ω˘ )ว ⁾⁾ < 暗号楽しいですRSAにはいくつもの攻撃手法が存在する。その中から、Common Modulus Attackと秘密鍵dからnを素因数分解することを取り上げる。 Common Modulus Attack RSAの教科書にも載るようなわかりやすく、簡単な攻撃で、次のように定義される。 RSA公開鍵\((n, e_1)\), \((n, e_2)\)と平文\(m\)、それぞれの公開鍵で暗号化した暗号文\(c_1, c_2\)があり、\(\mathrm{gcd}(e_1, e_2) = 1\)の時、\(n, e_1, e_2, c_1, c_2\)から平文\(m\)を導出することができる。 証明: \( \begin{align} c_1 &= m ^ {e_1} \mod n\\ c_2 &= m ^ {e_2} \mod n\\ \end{align} \) ここで、\(e_1s_1 + e_2s_2 =
