楕円曲線上の離散対数問題に対するアプローチ（Baby-step giant-stepとPollard's rho algorithm）

本稿では楕円曲線暗号の安全性の根拠とされている離散対数問題について、それを高速に解く方法をまとめる。

過去に「CTFにおける離散対数問題に対するアプローチ - sonickun.log」という記事を書いたが、この記事で言う離散対数問題（主にElGamal暗号で利用される）は、有限体上の離散対数問題と呼ばれるのに対し、今回扱うのは楕円曲線上の離散対数問題というものである。ちなみにこれまで楕円曲線上を離散対数問題を題材としたCTF問題に巡り合ったことはほとんどない（あったら教えてください）。

この楕円曲線上の離散対数問題を高速に解く手法として、Baby-step giant-stepとPollard's rho algorithmを紹介し、実際に実装してみる。なお、楕円曲線の基礎知識や楕円曲線暗号のアルゴリズムの説明については省略する。また、厳密な定義や証明は省き、イメージとして理解することを目指す。

楕円曲線上の離散対数問題（ECDLP: Elliptic Curve Discrete Logarithm Problem）

有限体 $\mathbb{F}p$ 上の楕円曲線 $E$ において、 $E$ 上のある点（ベースポイント） $P$ と整数 $d$ から点 $Q = d × P$ （スカラー倍算）を計算するのは容易である。逆に、点 $P$ 、 $Q$ から $Q = d × P$ を満たす整数 $d$ を求めよ、という問題を楕円曲線上の離散対数問題と呼ぶ。

巡回群の位数が巨大な素数となるような楕円曲線とベースポイントを選んだ場合、この離散対数問題を解くことは非常に困難であることが知られている。その理由の一つには、スカラー倍算の結果が離散的に変化するという性質が挙げられている。

言い換えれば、楕円曲線上の点を巡っていく際に、ある点から $d$ 回たどることは簡単だが、始点と終点を与えられたときに、始点から何回たどって終点にたどり着いたかを求めることは困難である、ということである。

楕円曲線上の離散対数問題は、楕円曲線暗号の安全性の根拠とされている。ちなみに、1024ビット鍵長のRSA暗号やElGamal暗号と同等の安全性を持つためには、楕円曲線暗号では160ビットの鍵長で十分であるといわれている。そのため、暗号化・復号や署名認証用のハードウェア規模やソフトウェアの計算速度は、楕円曲線暗号のほうが数倍も優れており、たとえばICカードなど、コンパクト化・軽量化が要求される場合には、楕円曲線暗号が活用されている。

Baby-step giant-step

楕円曲線上の離散対数問題に対するBaby-step giant-stepは、過去記事で解説した、有限体上の離散対数問題に対するBaby-step giant-stepと根本的な考え方は同じである。

離散対数問題 $Q = dP$ に対し、ベースポイント $P$ の位数 $n$ を用いて $d=im+j$ （ $m=\lceil\sqrt{n}\rceil$ 、 $0 \leq i,j \lt m$ ）として、以下の式を得る。

${ \displaystyle Q = dP \\ Q = (im+j)P \\ Q - imP = jP }$

この式において、両辺が一致するように $i$ 、 $j$ を総当たりし、 $d$ を求める。そうすることで、列挙法で $d$ を求めるよりも少ない試行数で離散対数問題が解ける。

各辺の計算にはそれぞれ $m$ 回ずつのスカラー倍算を必要とするため、全体では $2m$ 回、つまり $2\sqrt{n}$ 回程度のスカラー倍算が必要になる。

以上をSageMathで実装したものが以下である。

def baby_step_giant_step(E, P, Q):
    m = int(E.order()^0.5 + 1)

    baby = []
    b = Q
    for j in range(m):
        baby.append(b)
        b -= P

    giant = m * P
    for i in range(1, m):
        if giant in baby:
            d = i*m + baby.index(giant)
            return d
        else:
            giant += (m * P)
    print "not found"
    return -1

p = 229
a = 1
b = 44

E = EllipticCurve(GF(p), [a, b])
P = E([5, 116])
Q = E([155, 166])

d = 176

assert Q == d * P

print d
print baby_step_giant_step(E, P, Q)

実行結果

# sage elliptic.sage
176
176

Pollard's rho algorithm

離散対数問題 $Q = dP$ （位数は $n$ ）に対し、何らかの方法で

${ \displaystyle a_i P + b_i Q = a_j P + b_j Q }$

となる $a_i, b_i, a_j, b_j (a_i \not= a_j, b_i \not= b_j)$ が見つかったとする。ことのき

${ \displaystyle Q = \frac{a_j - a_i}{b_i - b_j}P }$

となり、

${ \displaystyle d = \frac{a_j - a_i}{b_i - b_j} \pmod{n} }$

となるので、離散対数問題の解 $d$ を求まる。

$R_i = a_i P + b_i Q$ としたとき、このアルゴリズムの目標は $R_i = R_j$ となる点のペア $R_i$ 、 $R_j$ を見つけることである。このような点のペアをコリジョンペアと呼ぶ。

ここでは、コリジョンペアを探索するために、楕円曲線上の点をランダムに選んでいく方法をとる。楕円曲線上の点 $R$ をもとにランダムな点を効率的に求めるために、次のようなRandom Walk関数 $f$ を利用する。

${ \displaystyle \begin{eqnarray} f(R)=\left\{ \begin{array}{ll} R + M_0 & (x(R) \equiv 0 \pmod{4}) \\ R + M_1 & (x(R) \equiv 1 \pmod{4}) \\ R + M_2 & (x(R) \equiv 2 \pmod{4}) \\ R + M_3 & (x(R) \equiv 3 \pmod{4}) \\ \end{array} \right. \end{eqnarray} }$

ここで $x(R)$ は点 $R$ の $x$ 座標を表す。ただし、 $M_i = u_i P + v_i Q$ は楕円曲線上からランダムに選ばれた点である。 $R_{i+1} = f(R_i)$ として次々に楕円曲線上の点を求めていくと、確率的にコリジョンペアが見つかる。

上のRandom Walk関数の例ではランダム性を向上させるために4分割されていた（このパラメータを分割数という）が、Pollard's rho algorithmにより大規模な離散対数問題を解く際には、分割数が20程度の関数が使用される。ちなみに、Pollard's rho algorithmでランダムな点を求める方法は他にもあるらしい（Wikipedia）。

以上をSageMathで実装したものが以下である。

from random import randint

def pollards_rho(E, P, Q, div):

    n = E.order()
    R = []
    Rab = []
    a = randint(0, n)
    b = randint(0, n)
    R.append((a*P) + (b*Q))
    Rab.append([a, b])

    M = []
    Mab = []
    for i in range(div):
        a = randint(0, n)
        b = randint(0, n)
        M.append((a*P) + (b*Q))
        Mab.append([a, b])

    S = R[0]
    i = 0
    while True:
        m = int(S[0]) % div
        S = S + M[m]
        Sa = Rab[i][0] + Mab[m][0]
        Sb = Rab[i][1] + Mab[m][1]

        if S in R:
            Ra, Rb = Rab[R.index(S)]
            d = (Sa - Ra)*inverse_mod((Rb - Sb), n) % n
            return d
        else:
            R.append(S)
            Rab.append([Sa, Sb])
            i += 1

p = 229
a = 1
b = 44

E = EllipticCurve(GF(p), [a, b])
P = E([5, 116])
Q = E([155, 166])

d = 176

assert Q == d * P

print d
print pollards_rho(E, P, Q, 20)

実行結果

# sage elliptic.sage
176
176

誕生日のパラドックスによれば、コリジョンペアを見つけるには $\sqrt{n}$ 個の点を計算・保存する必要があるが、保存する点を特徴点（その点の $x$ 座標がある値 $\theta$ で割り切れる点)に限定することで、記憶すべき点の個数を $1/\theta$ に節約することもできる。

したがって、Pollard's rho algorithmは $\sqrt{n}$ 回のスカラー倍算を必要とするため、Baby-step giant-stepと同程度の計算時間を必要とするが、保存するべき点の数は $\sqrt{n}/\theta$ となり、Baby-step giant-stepよりも少なくて済むというメリットがある。

なお、楕円曲線上の離散対数問題に対してはPollard's rho algorithmが最も優れていることが経験的に知られているが、さらに優れた解法が登場することは否定されていない。楕円曲線上の離散対数問題に対するほかのアプローチは、「ECDLPに対する攻撃手法のまとめ - 一般的攻撃手法 - ₍₍ (ง ˘ω˘ )ว ⁾⁾ < 暗号楽しいです」によくまとまっている。