Edwards Curve - crypto-writeup-public

EllipticCurveの一種。次の式で定義される

$x^2 + y^2 \equiv 1 + dx^2y^2 \pmod p$

加算は $(x_1, y_1) + (x_2, y_2) = (\frac{x_1y_2 + y_1x_2}{1+dx_2x_2y_1y_2}, \frac{y_1y_2 - x_1x_2}{1-dx_2x_2y_1y_2})$ と定義される。

もし d = 0なら加算は $(x_1, y_1) + (x_2, y_2) = (x_1y_2 + y_1x_2, y_1y_2 - x_1x_2)$

（また、 $x^2 - Dy^2 = 1$ とするときもある。このとき $(x_1, y_1) + (x_2, y_2) = (x_1x_2 + Dy_1y_2, x_1y_2 + y_1x_2)$

このような曲線は実は円で（それはそう）、離散対数より弱い問題になる。具体的には $W = X^2 - D \in F_q\lbrack X \rbrack$ と定義して、 $(x, y) \to x + yW$ という写像が作れる。

だいたいこんな感じでdiscrete logを解く

D = 1
F = GF(p)
R.<x> = PolynomialRing(F)
K.<w> = F.extension(x^2 + D)

g_K = g[0] + g[1]*w
B_K = B[0] + B[1]*w
b = discrete_log(B_K, g_K)

$-x^2 + y^2 \equiv 1 + dx^2y^2 \pmod p$