公開鍵暗号 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 = 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巻辺りを読むとわかった(気になれる)のでおすすめ。

リファレンス/参考リンク