Low Order を利用した攻撃

考え方

楕円曲線の加法の群の位数が素数でない場合は、点を素因数を位数とした部分群にマップすることができるので、大きな数でも、小さな素因数が掛け合わさった数である場合は、それぞれの素因数を位数にした部分群に点をマップして、その上で離散対数問題を解き、中国剰余定理を使って、その答えを組み上げることで、元の数に対する答えもわかってしまう。

点を部分群にマップする方法

1. cofactor を計算する。楕円曲線の加法の群の位数を、マップ先の群の位数（素数）で割った数が cofactor
2. 点に cofactor を掛ける

例

# 楕円曲線の加法の群の位数 = 966
# マップ先の群の位数 = 23
cofactor = 966 / 23 = 42
[42]P = (890, 665) 

具体例

ベースとなるフィールド

$\mathbb{F}_{1021}$

楕円曲線の式

$y^2 = x^3 + 905x + 100$

加法の群の位数

$ \# E(F_q) = 966 = 2 \cdot 3 \cdot 7 \cdot 23$

ジェネレーター

$P=(1006, 416)$

攻撃内容

$Q=[k]P=(612, 827)$

の $k$ を見つける

手順

1. 群の位数の素因数ごとに、部分群を作り、そこに点をマップして、そのレベルでの答えを見つける

素因数 2

$cofactor = 966/2 = 483$
$P_2 = [483]P = (174, 0)$
$Q_2 = [483]Q = (174, 0)$

$[k_2]P_2 = Q_2$
$P_2$ と $Q_2$ は同じなので、$k_2=1$

素因数 3

$cofactor = 966/3 = 322$
$P_3 = [322]P = (147, 993)$
$Q_3 = [322]Q = O$

$[k_3]P_3 = O$
$P_3$ に掛けて $O$ になる数なので、$k_2=0$

素因数 7

$cofactor = 966/7 = 138$
$P_7 = [483]P = (906, 201)$
$Q_7 = [483]Q = (906, 201)$

$[k_7]P_7 = Q_7$
$P_7$ と $Q_7$ は同じなので、$k_7=1$

素因数 23

$cofactor = 966/23 = 42$
$P_23 = [42]P = (890, 665)$
$Q_23 = [42]Q = (68, 281)$

$[k_23]P_23 = Q_23$
$k_23$ については、すべての数を試す。すると、$k_23=20$ であることがわかる。

2. 中国剰余定理を使って 1 の全ての結果を満たす数を計算する

$k \equiv (k_2 = 1) \pmod 2$
$k \equiv (k_3 = 0) \pmod 3$
$k \equiv (k_7 = 1) \pmod 7$
$k \equiv (k_23 = 20) \pmod {23}$

を、中国剰余定理で解くと、$k \equiv 687$

参考文献

Pairings for beginners / Craig Costello