楕円曲線上の離散対数問題は,楕円曲線上の 2点 $P$,$Q$ に関する式,
$Q = x P$
において,$Q$ から自然数 $x\ (1 \le x \le r,\ r$ は $P$ の位数) をを求める問題である.
ここで,$P$ は既知とし,$x P$ は $P$ をスカラー倍する演算である.
総当たり法 (Brute force method) は,楕円離散対数問題を解くのに,
$2P,\ 3P,\ \ldots,\ (r-1)P$
を順番に計算していく方法である.$mP$ が $Q$ に一致するような $m\ (2, 3, \ldots, r-1)$ が見つかるまで繰り返す.
$Q = xP = (sm + t) P = s (mP) + tP = sR + tP$
となり,$s$,$t$ は$Q - tP = sR$
という関係式を満たす.そこで,2種類のデータベース(事前計算値) として$Q,\ Q - P,\ Q - 2P,\ Q - 3P,\ \ldots,\ Q - (m-1)P$
と${\cal O},\ R,\ 2R,\ 3R,\ \ldots,\ (m-1)R$
を計算しておく.もし,2つのデータベースに同じ点が見つかった場合, 対応する値が $s$,$t$ として得られ, 目的の $x$ が求まる.$P$ | : | 楕円点 |
$Q$ | : | 離散対数計算対象楕円点($Q = xP$) |
$m$ | : | 事前計算テーブルパラメータ |
$z$ | : | 探索の初期値 |
$n$ | : | 探索の最大値 |
$\mathrm{TBL}[i]=i * P\ (i = -m+1,\ \cdots,-1,\ 0,\ 1,\ \cdots,m-1)$
$s P + t Q = s' P + t' Q$
となる整数 $s,\ t,\ s',\ t'\ (s \ne s',\ t \ne t')$ が見つかったとする.このとき,$(t - t')Q = (s' - s)P$
すなわち,$Q = (s' - s) / (t - t')P$
となり, $(s' - s) / (t - t')$ として楕円離散対数問題の解 $x$ が求まる (位数を $r$ とした $\bmod r$ での計算).