公開鍵暗号 - RSA - Wiener's Attack

攻撃 公開鍵暗号

この記事では、RSA暗号への攻撃の中で恐らく最も有名であろうWiener's Attackについて取り上げる。多くは原論文を参考にしているが、証明の省略やアルゴリズムの一部改変等があるので、この記事を読んで氣になったのであればぜひとも原論文を読んで実際に実装してみて欲しい。

連分数

連分数とは、次の形で表される分数の一種である。

\[ \left. \cfrac{a_1}{q_1 + \cfrac{a_2}{q_2 + \cfrac{a_3}{\ddots\cfrac{}{q _ {m - 1} + \cfrac{a_m}{q_m}}}}}\right. = a_1/(q_1 + a_2/(q_2 + a_3/(\ldots/(q _ {m - 1} + a_m/q_m)))) \]

我々が興味があるのは、連分数の中でも \(a_i\)が全て1と等しいような連分数だ。扱いやすくするために、次のような表記を導入する。

\[ \langle q_0, q_1, \ldots, q_m \rangle = q_0 + 1/(q_1 + 1/(q_2 + 1/(\ \ldots/(q _ {m - 1} + 1/q_m)))) \]

例: \(\langle 0, 2, 1, 3 \rangle = 0 + 1/(2+1/(1+(1/3))) = \frac{4}{11}\)

有理数を連分数に展開することを連分数展開という。

fを連分数展開することはできた。では、\(\langle q_0, q_1, \ldots, q_m \rangle\)からfを復元することは可能だろうか? 先の式を見てもらえればわかるように、これは簡単だ。\(q_m\)から順に足して逆数を求めていくことを\(q_0\)まで繰り返せば良い。しかし、逆に\(q_0\)から順に求めていく方法はあるだろうか?\(n_i\)と\(d_i\)を次の式を満たすように定義する。

\[ \frac{n_i}{d_i} = \langle q_0, q_1, \ldots, q_m \rangle, \mbox{gcd}(n_i, d_i) = 1 \mbox{ for } i = 0, 1, \ldots, m \]

ここで、\(n_i, d_i\)はそれぞれ次のように表すことができる。

\[ \begin{align} n_0 &= q_0\\ n_1 &= q_0q_1 + 1\\ n_i &= q_i n _ {i-1} + n _ {i - 2}\ (\mathrm{for\ } i = 2, 3, \ldots, m.) \end{align} \]

\[ \begin{align} d_0 &= 1\\ d_1 &= q_1\\ d_i &= q_i d _ {i-1} + d _ {i - 2}\ (\mathrm{for\ } i = 2, 3, \ldots, m.) \end{align} \]

その上で、\(f = \frac{n_m}{d_m}\)とすることでfを復元することができる。

この時、面白いアルゴリズムが存在する。それは、ある数値fに対して\(f' = f(1-\delta)\)となるようなf'が存在し、\(\delta\)が十分小さい時に\(f'\)から\(f\)を求められるというもので、次のようにして計算される。なお、to_contfracは引数に与えられた数を連分数展開して\(\langle q_0, q_1, \ldots, q_m \rangle\)形式の配列で返す関数で、to_rationalは上で紹介した手法を用いて連分数から有理数へと変換する関数とする。

function reconstruct_f(f') {
  i ← 0
  q ← to_contfrac(f')
  while true {
    c ← to_rational(q[0], ..., q[i])
    if i is Even {
      if c Equals to_rational(q[0], q[1], ..., q[i-1], q[i]+1) {
        return c
      }
    } else if i is Odd {
      if c Equals to_rational(q[0], q[1], ..., q[i-1], q[i]) {
        return c
      }
    }
    i ← i + 1
  }
}

以上を踏まえて、Wiener's Attackを解説する。

Wiener's Attack

RSA公開鍵\( (e, n)\)と秘密鍵\(d\)があり、\(d\)が十分小さい時、公開鍵から\(d\)を復元することが出来る。

秘密鍵は次のように書くことが出来る。

\[ ed \equiv 1 \mod \phi(n) \]

これを書きなおして、

\[ ed = k\phi(n) + 1 \]

\(\phi(n) = (p-1)(q-1) = (n - p - q + 1)\)なので、

\[ \begin{align} ed &= k(n - p - q + 1) + 1\\ ed &= kn - kp - kq + k + 1\\ \frac{ed}{n} &= k(1-\delta) \ \ \ &\delta = \frac{p+q-1-\frac{1}{k}}{n}\\ \frac{e}{n} &= \frac{k}{d}(1-\delta) \end{align} \]

最後の式で出てきたk, dは\(\delta\)が十分に小さければ先ほど示したアルゴリズムによって求める事ができるので、dを求めることが出来る。*1素因数分解するのであれば先日の公開鍵暗号 RSA - Common Modulus Attack, 秘密鍵からの素因数分解 - ₍₍ (ง ˘ω˘ )ว ⁾⁾ < 暗号楽しいですで紹介した秘密鍵からの素因数分解手法を用いることでp, qを計算することが可能だ。

実装例

ここで、実装例であるpablocelayes/rsa-wiener-attackを見てみよう。ここでは、少しこれを変形したアルゴリズムが使用されている。該当部分はRSAwienerHacker.pyの以下の部分だ。

def hack_RSA(e,n):
    '''
    Finds d knowing (e,n)
    applying the Wiener continued fraction attack
    '''
    frac = ContinuedFractions.rational_to_contfrac(e, n)
    convergents = ContinuedFractions.convergents_from_contfrac(frac)
    
    for (k,d) in convergents:
        
        #check if d is actually the key
        if k!=0 and (e*d-1)%k == 0:
            phi = (e*d-1)//k
            s = n - phi + 1
            # check if the equation x^2 - s*x + n = 0
            # has integer roots
            discr = s*s - 4*n
            if(discr>=0):
                t = Arithmetic.is_perfect_square(discr)
                if t!=-1 and (s+t)%2==0:
                    print("Hacked!")
                    return d

このアルゴリズムではfを求めるアルゴリズムを省き、総当りでk, dをチェックしていることに注意すれば、ほぼやっていることは同じだ。\(ed-1 \mod k\)が0になることは\(ed = k\phi(n)+1\)と同値であるため、この式で正しいdを選べているかどうかがわかる。その下にある式も展開すると、

\[ \begin{align} s &= n - \phi(n) + 1\\ &= pq - (pq - p - q + 1) + 1\\ &= p + q \end{align} \]

さらに、その下にある2次方程式は

\[ \begin{align} x ^ 2 - sx + n &= 0\\ x ^ 2 - (p+q)x + pq &= 0\\ \end{align} \]

2次方程式は \((x-\alpha)(x-\beta) = x ^ 2 - (\alpha + \beta) x + \alpha\beta = 0\)のように表すことが出来るので、上の2次方程式の解は\(p, q\)である。よって、この2次方程式に整数解が2つ存在する時、正しくdを選択できたといえる。

参考文献/参考リンク

多少応用的だが、以下の論文も読むことをおすすめする。

*1:なお、原論文とは少し異なるアプローチをしていたり、値のチェックの省略がある。詳しくは原論文を参照。

公開鍵暗号 - Paillier暗号

公開鍵暗号

この記事では比較的新しい、かつ珍しい加法準同型性を持つPaillier暗号について解説する。

Paillier暗号とは、Pascal Paillierによって1999年に発明された公開鍵暗号で、素因数分解を安全性の根拠としている。この暗号は、メッセージ\(Enc(m_1), Enc(m_2)\)からそれらを足し合わせた暗号文を作ることができるという性質を持っている。これを加法準同型性といい、暗号の中でも非常に少ない(乗法準同型性は他にもRSA, Elgamal等に見られる)、珍しい暗号である。

鍵の生成

  • 2つの大きな素数\(p, q\)をランダムに選択し、\(n = pq\)を計算する。
  • \(k\in\mathbb{Z} _ n\)をランダムに選び、\(g = (kn+1) \mod n ^ 2\)を計算する。

公開鍵を\( (n, g) \)、秘密鍵を\( (p, q) \)とする。

暗号化

暗号化関数\(Enc(m)\)を次のように定義する。 \[Enc(m) := g ^ m\cdot r ^ n\] ただし、\(r\)は\(r\in\mathbb{Z} ^ {*} _ {n ^ 2}\)で、暗号化ごとにランダムに選ばれる。

復号

復号関数\(Dec(c)\)を次のように定義する。 \[Dec(c) := \frac{L(c ^ {\lambda} \mod n ^ 2)}{L(g ^ {\lambda} \mod n ^ 2)} \mod n\] この時、\(L(u) = \frac{u-1}{n}\)で、\(\lambda = \mathrm{lcm}(p-1, q-1)\)である。

根拠

\(\lambda\)という値が出てきた。これは、実際にはカーマイケルの\(\lambda\)関数と呼ばれるもので、オイラーのトーティエント関数を更に厳密にしたようなものと言える。 この関数は、\(\lambda(n)\)として次のように定義される。

\(n=2 ^ e\)の時 \[\lambda(2 ^ e) = \begin{cases} 1 & if\ e = 1\\ 2 & if\ 2 = 2\\ 2 ^ {e-2} & if\ e \geq 3 \end{cases} \]

\(n = p ^ e\)(\(p > 2\)な素数)の時

\[\lambda(p ^ e) = p ^ {e-1}(p-1)\]

\(n = p _ 1 ^ {e _ 1} p _ 2 ^ {e _ 2} \cdots p _ k ^ {e _ k}\)の時

\[\lambda(p _ 1 ^ {e _ 1} p _ 2 ^ {e _ 2} \cdots p _ k ^ {e _ k}) = \mathrm{lcm}(\lambda(p _ 1 ^ {e _ 1}), \lambda(p _ 2 ^ {e _ 2}), \ldots, \lambda(p _ k ^ {e _ k}))\] この\( \lambda(n) \)関数を用いると、以下のカーマイケルの定理を証明できる(ここでは略する)

カーマイケルの定理

\(a, m \in \mathbb{Z}\)があり、それぞれが互いに素な時、 \[a ^ {\lambda(n)} \equiv 1 \mod n\] が成り立つ。

ここで、\(n=p _ 1 p _ 2 \ldots p _ k\)の時、もう一つ次の事実も示す事ができる。

\(a, m \in \mathbb{Z}\)があり、それぞれが互いに素かつ\(n=p _ 1 p _ 2 \ldots p _ k \)な時、 \[a ^ {n\lambda(n)} \equiv 1 \mod n ^ 2\] が成り立つ。

少し計算すれば上の事実は理解できると思うので、こちらも証明は略する。

ところで、二項定理を知っているだろうか。\((x+y) ^ n\)という式を展開するとある規則で全ての項が\(ax ^ b y ^ c\)となるような項の和に分解できる、というものだ。 ここで、その二項定理を用いて次の式を展開してみよう。

\[ (1 + n) ^ k \mod n ^ 2 \]

modがかかっていることに注意すると、以下のように簡潔な式が得られる。

\[ \begin{align} (1 + n) ^ k &= 1 + kn + \frac{k!}{2!(k-2)!} n ^ 2 + \frac{k!}{3!(k-3)!} n ^ 3 + \ldots \mod n ^ 2\\ &= 1 + kn + n ^ 2 (\frac{k!}{2!(k-2)!} + \frac{k!}{3!(k-3)!} n + \ldots) \mod n ^ 2\\ &= 1 + kn \mod n ^ 2\\ \end{align} \]

\(n\)を\(a\cdot n\)と置き換えても同様に\((1 + a\cdot n) ^ k = 1 + akn \mod n ^ 2\)が成り立つことは簡単に確かめられる。

以上を踏まえて、復号処理を追ってみよう。まず、\(c ^ \lambda\)を計算するので、これを展開すると、

\[ \begin{align} c ^ \lambda &= (g ^ m r ^ n) ^ \lambda \mod n ^ 2\\ &= g ^ {m\lambda} r ^ {n\lambda} \mod n ^ 2\\ &= g ^ {m\lambda} \mod n ^ 2\\ &= (1 + kn) ^ {m\lambda} \mod n ^ 2\\ &= 1 + m \lambda k n \mod n ^ 2 \end{align} \]

\(r ^ {n\lambda} \mod n ^ 2\)はカーマイケルの定理より1になることに注意すれば、さほど難しくはない。次に、関数Lを適用する。

\[ \begin{align} L(c ^ \lambda \mod n ^ 2) &= L(1 + m \lambda k n \mod n ^ 2)\\ &= \frac{1 + m \lambda k n - 1}{n}\\ &= m \lambda k \end{align} \]

分子は計算できた。同様に、分母の部分も計算する。

\[ \begin{align} L(g ^ \lambda \mod n ^ 2) &= L(1 + \lambda k n \mod n ^ 2) \mod n ^ 2\\ &= \frac{1 + \lambda k n - 1}{n}\\ &= \lambda k \end{align} \]

これに\(\mod n\)上の除算を適用して、

\[ \begin{align} \frac{m \lambda k}{\lambda k} &= m \mod n \end{align} \]

結果として、平文を得る事ができた。

加法順同型性

Pailier暗号には、珍しい加法順同型性が備わっていると書いた。実際にそれを追ってみよう。 最初に、公開鍵/秘密鍵\(n = pq, g, r_1, r_2\)、平文\(m_1, m_2\)とそれぞれの暗号文\(c_1, c_2\)とする。\(c = c_1 \cdot c_2 \mod n ^ 2\)として、

\[ \begin{align} c &= c_1 \cdot c_2 &= g ^ {m_1 + m_2}\cdot r_1 ^ n\cdot r_2 ^ n \mod n ^ 2\\ c ^ \lambda &= (g ^ {m_1 + m_2}\cdot r_1 ^ n\cdot r_2 ^ n) ^ \lambda \mod n ^ 2\\ &= g ^ {(m_1 + m_2)\lambda}\cdot r_1 ^ {n\lambda}\cdot r_2 ^ {n\lambda} \mod n ^ 2\\ &= g ^ {(m_1 + m_2)\lambda}\cdot 1\cdot 1\mod n ^ 2\\ &= (1 + kn) ^ {(m_1 + m_2)\lambda} \mod n ^ 2\\ &= 1 + (m_1 + m_2) \lambda k n \mod n ^ 2 \end{align} \]

見事に、\(m\)の部分が\(m_1 + m_2\)に置き換わっていることがわかると思う。後は自明な代数の演習なので、暇があれば計算してみると良いと思う。

その他

実は、加法順同型性はPaillier暗号が初めてというわけではなく、その少し前に岡本-内山暗号という暗号系がそれを達成している。そのうち取り上げるかもしれないが、とりあえずWikipediaを読んでおくと良いかと思う。

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

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

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