sonickun.log

備忘録

CTFにおける離散対数問題に対するアプローチ

CTF セキュリティ

CTFの暗号分野では、離散対数問題を利用したアルゴリズム（ElGamal暗号、Diffe-Hellman鍵共有など）がよく扱われる。本稿ではこの離散対数を高速に解く方法を備忘録としてまとめておく。

離散対数問題（DLP: Discrete Logarithm Problem）

素数{\displaystyle p} と定数{\displaystyle g} が与えられたとき

{ \displaystyle g^x \equiv y\pmod{p} }

において、{\displaystyle x}から{\displaystyle y}を計算することは容易だが、その逆の、{\displaystyle y}から{\displaystyle x}を求めることは困難であることを、離散対数問題と呼ぶ。公開鍵暗号方式では、このことを安全性の根拠とした暗号アルゴリズムがいくつか考案されている。CTFでは、この離散対数を解き、暗号の秘密鍵を特定する問題が出題される。

離散対数に対するアプローチ

離散対数に対するアプローチとして、列挙法、Baby-step Giant-step algorithm、Pohlig–Hellman algorithmの3つの手法を紹介する。

列挙法

列挙法は最もシンプルな手法であり、上式において、{\displaystyle x=1,2,3,4,...}に対して合同式が成り立つかどうかを一つひとつ確認していく方法である。ただし、{\displaystyle g}の位数が大きいときは膨大な試行数になるため現実的ではない。オーダーは{\mathcal{O}(n)}。

Baby-step Giant-step algorithm

Baby-step Giant-step algorithmは列挙法による試行数を削減したアルゴリズムであり、オーダーは{\mathcal{O}(\sqrt{n}\log n)}となる。

{ \displaystyle g^x \equiv y\pmod{p} }

において、{\displaystyle x=im+j}（{\displaystyle m=\lceil\sqrt{p}\rceil}、{\displaystyle 0 \leq i,j \lt m}）として、以下の式を得る。

\begin{align} g^{im+j} &\equiv y\pmod{p} \\ g^j &\equiv y(g^{-m})^i\pmod{p} \end{align}

このアルゴリズムでは上式の両辺が一致するように{\displaystyle i}と{\displaystyle j}を総当たりし、{\displaystyle x}を求める。そうすることで、列挙法よりも試行数が少なくて済む。
Baby-step Giant-step algorithmの詳細な手順は以下のとおりである。

1. {\displaystyle m\leftarrow \lceil\sqrt{p}\rceil}
2. {\displaystyle 0 \leq j \lt m}を満たすすべての{\displaystyle j}について（Baby-step）：
　1. {g^j \pmod{p}}を計算し、{(j, g^j \pmod{p})}のペアをテーブルに保存する
3. {g^{-m}}を計算する
4. {\displaystyle \gamma\leftarrow y}
5. {\displaystyle i=0}から{\displaystyle (m-1)}まで（Giant-step）：
　1. {\gamma}がテーブルの第二要素{(g^j \pmod{p})}に含まれるかチェックする
　2. もし含まれていれば、{\displaystyle x=im+j}を返す
　3. もしそうでなければ、{\displaystyle \gamma\leftarrow \gamma \cdot g^{-m}}とする

Pohlig–Hellman algorithm

Pohlig–Hellman algorithmは、

{ \displaystyle g^x \equiv y\pmod{p} }

に対し、{\displaystyle \phi(p)}の素因数が小さいときに有効に働くアルゴリズムである。ここで{\displaystyle \phi(n)}とはオイラー特性関数であり、{\displaystyle n}より小さい自然数のうち{\displaystyle n}と互いに素なものの個数を示し、特に{\displaystyle n}が素数の場合は{\displaystyle \phi(n)=n-1}となる。

Pohlig–Hellman algorithmのアイデアとしては、{\displaystyle g}の位数が大きすぎて総当たりが困難だったものを、{\displaystyle g}の位数が小さな離散対数問題に分割して解き、後で結合するといったものである。

まず、{\displaystyle \phi(p)}を以下のように素因数分解する。

{ \displaystyle \phi(p) = p_1 \cdot p_2 \cdot\cdot\cdot p_n }

このとき、{\displaystyle p_i}の値は小さい（英語では"smooth"という）ことが望ましい。
{\displaystyle x = a_k p_k+b_k}としたとき、それぞれの{\displaystyle k}についてオイラーの定理より以下の計算を行う。

\begin{align} y^{\phi(p)/p_k} &\equiv (g^x)^{\phi(p)/p_k}\pmod{p} \\ &\equiv (g^{\phi(p)})^{a_k}g^{b_k\phi(p)/p_k}\pmod{p} \\ &\equiv (g^{\phi(p)/p_k})^{b_k}\pmod{p} \end{align}

この合同式は最初に示した離散対数問題の形に帰着されるが、{\displaystyle b_k}は{\displaystyle p_k}よりも小さいため、比較的容易に{\displaystyle b_k}を求めることが可能である（Baby-step Giant-step algorithmも組み合わせればより高速になる）。
これにより{\displaystyle b_k}の値が定まると、{\displaystyle x\equiv b_k \pmod{p_k}}が求まったことになる。

{ \displaystyle x\equiv b_1 \pmod{p_1} \\ x\equiv b_2 \pmod{p_2} \\ \cdot\cdot\cdot \\ x\equiv b_n \pmod{p_n} \\ }

について、{\displaystyle p_1, p_2,..., p_n}は互いに素なので、中国人剰余定理より、これらを満たす整数{\displaystyle x}が{ \displaystyle \phi(p) = p_1 \cdot p_2 \cdot\cdot\cdot p_n }を法として唯一つ定まる。こうして求まった{ \displaystyle x \pmod{\phi(p)}}が最初に示した離散対数問題の解となる（{\displaystyle p}は素数であるため、{\displaystyle g}の位数は{\displaystyle \phi(p)=p-1}である）。Pohlig–Hellman algorithmのオーダーは{\mathcal{O}(\sqrt{n})}だが、{\displaystyle \phi(p)}が小さいほどより効率的となる。

Pohlig–Hellman algorithmを使った攻撃の回避策として、安全素数を使う方法がある。安全素数は、{\displaystyle q}と{\displaystyle 2q+1}がともに素数である場合における{\displaystyle 2p+1}である。このとき、{\displaystyle q}のほうはSophie Germain素数と呼ばれる。安全素数{\displaystyle p}を使うことで、{\displaystyle \phi(p)=p-1=2q}となり、{\displaystyle \phi(p)}が大きな素因数を持つことになるため、Pohlig–Hellman algorithmが有効に働かなくなる。安全素数が無限に存在するという予想は未だ証明されていないが、実用的には十分存在するといわれている。

実装例

離散対数問題を安全性の根拠としている暗号方式として、ElGamal暗号を取り上げる。ElGamal暗号では、素数{\displaystyle p}、整数{\displaystyle g}、乱数{\displaystyle x}{\displaystyle (0\leq x \lt p)}を選んで、

{ \displaystyle y = g^x \mod{p} }

を計算し、{\displaystyle y, g, p}を公開鍵、{\displaystyle x}を秘密鍵とする。
暗号化フェーズでは、平文{\displaystyle m}と乱数{\displaystyle r}を用いて、以下のように暗号文{\displaystyle c_1, c_2}を計算する。

{ \displaystyle c_1 = g^r \mod{p} \\ c_2 = my^r \mod{p} = mg^{rx} \mod{p} }

復号フェーズでは、平文{\displaystyle m}を以下のように算出する。

{ \displaystyle c_2(c_1^x)^{-1} \mod{p} = mg^{rx}(g^{rx})^{-1} \mod{p} = m }

以上が、ElGamal暗号のアルゴリズムである。
今回は、ElGamal暗号の例題として、MMA CTF 1st 2015で出題された「Alicegame」という問題を扱う。問題より、ElGamal暗号における以下の値が判明している（本当は鍵がランダムに生成され、最適なpが引けるまでガチャを回す必要があるのだが今回はその部分を割愛）。

c1 = 1851635883910479967256646617880733235123029676545812189105888 
c2 = 2279140729739532482438192630521498934347693926502811537441460 
g = 1828219035112142373387222893932751631772945852477987101590090 
y = 1012750243445446249248731524345776923711031192963358920130436 
p = 3047318456124223787871095946374791137939076290647203431778747 
phi_p = 2 * 3 * 7 * 281 * 585131 * 2283091 * 66558319 * 38812459031 * 8407411055293 * 8899182573469

{\displaystyle \phi(p)}の素因数が小さいので、Pohlig–Hellman algorithmを用いた攻撃が可能である。今回は、Baby-step Giant-step algorithmも併用して以下のようにソルバーを書いた。
gist.github.com
無事、平文を復号できたことがわかる。

参考