singular curve - crypto-writeup-public

特異点(Singular Point)を持つ楕円曲線のこと。特異点の様子によってNode型かCusp型かに分けられる。

SingularなEllipticCurveは同型な別の群への写像を持ち、離散対数問題が簡単になることがある

CuspかNodeか調べる
特異点（のx座標）を調べる
特異点が原点にくるように平行移動する
楕円曲線上の点を $\mathbb{F_p}$ または $\mathbb{F_p^*}$ に移す（このとき平行移動分点の座標もずれていることに注意する）
discrete logを解く
点を戻す

Cusp型

$EC \cong F_p$ (pは楕円曲線の式に出てくるp）という同型写像が存在する

Node型

CuspかNodeか調べる

def is_cusp(a1, a2, a3, a4, a6, p):
    b2 = pow(a1,2) + 4*a2
    b4 = 2*a4 + a1*a3

    return (pow(b2, 2) - 24*b4) % p == 0

特異点を調べる

def list_singular_points(a, b, p):
    PR.<x> = PolynomialRing(GF(p))
    f = x^3 + a*x + b
    factors = f.factor()

    for term, exp in factors:
        fx = term^exp
        roots = fx.roots()
        for root, e in roots:
            if f(root) == 0:
                yield root

特異点が原点に来るように平行移動する

def move_singular_curve(a, b, p, rx):
    """rx: 特異点のx座標"""
    PR.<x> = PolynomialRing(GF(p))
    f = x^3 + a*x + b
    return f.subs(x=x + rx)

有限体への写像

node型のとき

def get_w(f):
    x = f.parent().gen()
    try:
        f_ = f.parent(f / x^2)
    except TypeError:
        raise ValueError("f is not formed x^2(x + w^2)")

    if f_.degree(x) != 1:
        raise ValueError("f is not formed x^2(x + w^2), especially not (x + w^2)")

    w2 = f_.constant_coefficient()
    if not w2.is_square():
        raise ValueError("f is not formed x^2(x + w^2), especially not w^2")

    return sqrt(w2)

def make_node_map(p, w, rx):
    """
    w: w of curve's formula: f=x^2(x+w^2)
    rx: x coordinate of singular point
    """
    def forward(x, y):
        x = x - rx
        return GF(p)(y + w*x) / GF(p)(y - w*x)

    def backward(t):
        return 2*w^2 / (t-1) + rx, (2*(t+1)*w^3) / (t-1)^2

    return forward, backward