ECDLPに対する攻撃手法のまとめ 概要編

楕円曲線離散対数問題(Elliptic Curve Discrete Logarithm Problem, 以下ECDLP)が解けるか否か, という問題は暗号理論において楕円曲線が用いられる際の安全性基準として一般的である. 本記事から數回に分けてECDLPに対する攻撃手法についてまとめる.

ECDLPについて

楕円曲線についてかいつまんで述べる. 体$K$の上の楕円曲線$E/K$をWeierstrass標準形$E/K: y^{2} + a_1xy + a_3y = x ^ 3 + a_2x^{2} + a_4x + a_6$で定義する. 体$K$の標数が2, 3のどちらでもない場合は変数変換により$y^{2} = x^{3}+ax+b$と出来るため, 標数が2, 3で無い時にはこれを明示した上で使用する.

点$P, Q \in E/K$について, 群演算を以下のように定める. ここで, $x(P), y(P)$はそれぞれ楕円曲線の点$P$の$x$座標, $y$座標を表す.

演算 $P+Q$: $$ \begin{align} R &:= P+Q\\ x(R) &= \lambda^{2}+a_1\lambda+a_2-x(P)-x(Q)\\ y(R) &= -(\lambda + a_1)x(R) - \nu - a_3\\ \lambda &= \begin{cases} \frac{y(Q) - y(P)}{x(Q) - x(P)} & (P \ne Q)\\ \frac{3x(P)^{2}+2a_2x(P)+a_4-a_1y(P)}{2y(P)+a_1x(P)+a_3} & (P = Q)\\ \end{cases}\\ \nu &= \begin{cases} \frac{y(P)x(Q) - y(Q)x(P)}{x(Q) - x(P)} & (P \ne Q)\\ \frac{-x(P)^{3}+a_4x(P)+2a_6-a_3y(P)}{2y(P)+a_1x(P)+a_3} & (P = Q)\\ \end{cases}\\ \end{align} $$

逆元 $-P$: $$ -P := (x(P), -y(P)-a_1x(P)-a_3) $$

これらの演算により, $E/K$は群となる. この群の位数を$\#E/K$と表す. 単位元無限遠点 $\cal O$ とする.

また, これらの演算から乗法を定義することが出来る. ここで, $P \in E/K$, $m\in\mathbb{Z}$.

$$ mP := \underbrace{P + P + \cdots + P}_{m\ \mathrm{times\ repeat}} $$

点$P\in E/K$について, その位数$\#P$を$xP = O$となるような$x$と定義する. そのような$x$が存在しない場合, $\#P = \infty$とする.

この時, 楕円曲線離散対数問題(Elliptic Curve Discrete Logarithm Problem, ECDLP)を以下のように定義する.

入力: 楕円曲線$E/K$, 点$P$, $Q$
出力: $Q = dP$を満たす$d$

この$d$を求めることが計算量的に困難であることが楕円曲線を用いた暗号の安全性根拠となっている. 逆に, ECDLPが解けるならばその暗号は安全ではない. 安全性は計算量的なものであるため, 単純に基礎体$K$の位数を増やせば(=体を大きくすれば)安全性は向上する. しかし, 計算自体がかなり複雑なものであるため, 性能と安全性のトレードオフを考える必要がある. 現時点では160bitの素数$p$を用いるのが安全とされている.

ECDLPへの攻撃

一般的手法

一般的な巡回群に対する攻撃の中でECDLPへ適用可能なものとしては, 以下のようなものが挙げられる.

  • Exhaustive Search法
  • Baby-step Giant-step法
  • Pollard Rho法
  • Pollard Lambda法(またはKangaroo法)
  • Index-Calculus法
  • Pohlig-Hellman法

現時点で, 一番成果を挙げているのはPollard Rho法である.

特殊な曲線に対する手法

一般的手法とは違い, ある特性を持っている・ある基礎体上で定義されている等の特殊な条件を持つ楕円曲線に対して定義される手法で, 一般的手法と異なり計算量がかなり低く(SSSA-Attackについては多項式時間!)抑えられることがある.

  • MOV-reduction (Supersingularな楕円曲線に対するWeil-pairingを用いたDLPへの帰着)
  • Frey-Rück Reduction (同上, Tate-pairingを用いる)
  • SSSA-Attack (Anomalous曲線と曲線に付随する形式群を用いた解法で, 多項式時間解法の一つ. )
  • Weil-Descent Attack (有限体の $n$ 次拡大体の上の楕円曲線のECDLPをDLPへ帰着し, Index-calculus法を併用してECDLPを解く. )
  • Xedni-Calculus法 (特定条件下の楕円曲線におけるIndex-Calculusの効率化. XedniはIndexの逆. )
  • Yasuda-Attack ($p$進展開を利用した$p$進数体・有理数体におけるECDLP解法, 名前は特に付けられていないようなので発案者の安田氏の名前とした)

実装上の問題を突いた手法

楕円曲線の利用時にはもちろんコードを実装する必要がある. この計算時に意図しない値を入れて得られる結果からECDLPを解く手法.

  • Small-Subgroup Attack (位数の少ない点を指定し, それぞれについて何度も小さなECDLPを解き, 中国人剰余定理を用いてECDLPを解く. )
  • Invalid-curve Attack (楕円曲線上に存在しない点を代入し, 機械的に計算された結果を見ることで内部情報を読み取る手法)
    • Montgomery-Ladder Fault (Montgomery-Ladder法を用いて乗算処理を行う際, Invalid-curve Attackを用いて存在しない点に対して処理を行わせるとある別の楕円曲線での計算結果に帰着できる. もし, この曲線でPohlig-Hellman Attackのような別の攻撃を用いれる場合, ECDLPは間接的に解けてしまう. )

参考文献