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 = 1\)となるような\(s_1, s_2\)を拡張ユークリッドの互除法によって見つけたとする。
\( \begin{align} c_1 ^ {s_1} c_2 ^ {s_2} &= (m ^ {e_1}) ^ {s_1} (m ^ {e_2}) ^ {s_2} \mod n \\ &= m ^ {e_1 s_1} m ^ {e_2 s_2} \mod n \\ &= m ^ {e_1 s_1 + e_2 s_2} \mod n \\ &= m ^ 1\\ &= m \\ \end{align} \)
よって、平文mを導出できた。
擬似コードで示すと以下のようになる。
function common_modulus_attack(e1, e2, c1, c2, n) { s1, s2 ← extended_gcd(e1, e2) v ← c1 ^ s1 mod n w ← c2 ^ s2 mod n x ← v * w mod n return x }
秘密鍵からの素因数分解
秘密鍵が漏洩した時、秘密鍵からnを素因数分解することができる、というもの。少々複雑で実際には使われることはなさそうな攻撃だが、非常に興味深い攻撃だ。
RSA公開鍵\((n, e)\)と対応するRSA秘密鍵\(d\)が判明している時、\(n\)を\(n = pq\)となるような\(p, q\)に素因数分解することが出来る。
証明: d, eが判明しているため、次の式を考えてみる。
\[ \begin{align} de &\equiv 1 \mod \phi\\ de &= 1 + l\phi(n)\\ de - 1 &= l\phi(n) \end{align} \]
ここで、\(k = de - 1\)としよう。重要な点として、\(k\)は偶数である。(気になるのであれば、自分で考えてみると良い。良い頭の体操になる。)ということは、\(k = 2 ^ t r\)と表せる。rは奇数、tは1以上の整数だ。 ここで、\(g\)を\(2 \leq g \leq n-1\)なランダムな数として、2で割れる限界まで\(x = g ^ {k/2}, g ^ {k/4}, \ldots, g ^ {k/2 ^ {t}} \mod n\)を計算する。これらは何を意味するかというと、もしも「アタリ」のg, tになった時にこれを計算すると、
\[ \begin{align} k &= de - 1 = l\phi(n)\\ 2 ^ tr &= l\phi(n)\\ r &= \frac{l}{2 ^ t}\phi(n)\\ g ^ r &= g ^ {\frac{l}{2 ^ t}\phi(n)} \mod n\\ \end{align} \] ここで、\(\gamma = \frac{l}{2 ^ t}\)、\(x = g ^ \gamma\)として、\(x ^ {\phi(n)} \mod n\)はオイラーの定理より1になることがわかると思う。
\[ \begin{align} x ^ {\phi(n)} &\equiv 1 \mod n \\ x ^ {\phi(n)} - 1 &\equiv 0 \mod n \\ \end{align} \]
つまり、そのようなg, tを発見できた場合、nを割り切る値を発見することが出来る! 以上を踏まえて、擬似コードにしたものを下に示す。
function factor_given_d(n, e, d) { k ← de - 1 while true { g ← random(2, n - 1) t ← k while true { if t mod 2 = 0 { t ← t / 2 x ← g ^ t if x > 1 and gcd ( x - 1, n ) > 1 { p = gcd ( x - 1, n) q = n / p return (p, q) } else { continue } } else { break } } } }
なぜ乱数を使うのか、に関しては乱択アルゴリズムのWikipediaや数学ガール 第4巻辺りを読むとわかった(気になれる)のでおすすめ。
リファレンス/参考リンク
- Twenty Years of Attacks on the RSA Cryptosystem : https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf
- RSA: how to factorize N given d : http://www.di-mgt.com.au/rsa_factorize_n.html
- RSA Prime factorization for known public and private key - Mathematics Stack Exchange : http://math.stackexchange.com/questions/634862/rsa-prime-factorization-for-known-public-and-private-key