はじめに

はてなブログ謎オラクルによるブログのスパム認定が解除されたので、yoshi-campの参加記続きを書いていきまーす。

Day 0とDay 1はこっち：

ptr-yudai.hatenablog.com

はじめに
yoshi-camp

yoshi-camp

Day 2

[mitsu] ネコちゃん式　～安全な曲線の生成～

yoshi-camp一番の鬼講師ことmitsu先生が今回も楕円曲線についてお話してくれました。

タイトル通り安全な楕円曲線を作る方法を考えるのですが、これは楕円曲線の位数を計算すると確認できます。つまり、この講義では楕円曲線の位数を計算するためのSchoofのアルゴリズムの原理と高速化についてお勉強しました。

Frobenius写像とHasseの定理

Hasseの定理は楕円曲線の本には必ずといっていいほど書いてある定理です。

$|\# E(\mathbb{F}_p) - (p+1)| \leq 2\sqrt{p}$

ここで、左辺の絶対値の中身はFrobenius写像という写像のトレースになっています。 Frobenius写像も有名ですが、次のように定義される写像のことです。

$\phi: E(\mathbb{\bar{F}}_p) \ni (x, y) \mapsto (x^{p}, y^{p}) \in E(\mathbb{\bar{F}}_p)$

楕円曲線の位数がFrobenius写像のトレースから計算できるというのは、pwnerの私でも知っている話でした。しかし、具体的にトレースをどう計算するかは一切知らなかったので、ここから新しい内容に入ります。

等分多項式

Schoofのアルゴリズム本体に入る前に、アルゴリズムで必要となる楕円曲線の等分多項式を計算します。つまり、n-ねじれ点のx座標を根に持つ多項式を求めます。

多項式自体は簡単に求められます。単純に楕円曲線の加算公式を使い、 $(m-1)P = P$ を計算して方程式が得られるからです。

簡単でも面倒なので、mitsuくんからの天啓を使ってみましょう。楕円曲線 $E/\mathbb{F}_{p}$ に付随する多項式 $\psi_{m}$ を計算して出来上がったものがこちらになります。

$\psi_{0} = 0$
$\psi_{1} = 1$
$\psi_{2} = 2y$
$\psi_{3} = 3x^{4} + 6ax^{2} + 12bx - a^{2}$
$\psi_{4} = 4y(x^{6} + 5ax^{4} + 20bx^{3} - 5a^{2}x^{2} - 4abx - 8b^{2} - a^{3})$
$\psi_{2m+1} = \psi_{m+2}\psi_{m}^{3} - \psi_{m-1}\psi_{m+1}^{3} \ \ \ \ (m \geq 2)$
$\psi_{2m} = \cfrac{\psi_{m}}{2y}(\psi_{m+2}\psi_{m-1}^{2} - \psi_{m-2}\psi_{m+1}^{2}) \ \ \ \ (m \geq 3)$

これ自体は等分多項式ではなく、等分多項式は、次のように $y$ を消去した関数として定義されています。

$f_{m} = 1 \ \ \ \ (m = 1)$
$f_{m} = \psi_{m} \ \ \ \ (m \ \ \mathrm{is} \ \ \mathrm{odd})$
$f_{m} = \cfrac{\psi_{m}}{\psi_{2}} \ \ \ \ (m \ \ \mathrm{is} \ \ \mathrm{even})$

$\psi, f_{m}$ の定義に照らしあわせると、 $f_{m}$ は帰納的に計算できます。実装してみましょう。

from functools import cache

@cache
def division_polynomial(E, m):
    f = lambda m: division_polynomial(E, m)
    a, b = E.a4(), E.a6()
    PR = PolynomialRing(E.base(), 'x')
    x = PR.gen()
    if m == 0:
        return PR(0)
    elif m == 1 or m == 2:
        return PR(1)
    elif m == 3:
        return 3*x^4 + 6*a*x^2 + 12*b*x - a^2
    elif m == 4:
        return 2*(x^6 + 5*a*x^4 + 20*b*x^3 - 5*a^2*x^2 - 4*a*b*x - 8*b^2 - a^3)
    elif m % 2 == 0:
        n = m // 2
        return (f(n+2)*f(n-1)^2 - f(n-2)*f(n+1)^2) * f(n)
    else:
        n = (m-1) // 2
        F = 4*(x^3 + a*x + b)
        if n % 2 == 1:
            return f(n+2)*f(n)^3 - F^2*f(n-1)*f(n+1)^3
        else:
            return F^2*f(n+2)*f(n)^3 - f(n-1)*f(n+1)^3

この関数で求めた方程式の根が、ねじれ点のx座標になっていることを確認します。

E = EllipticCurve(GF(13), [2, 3])
m = 9
f = division_polynomial(E, m)
print(f)

for x, _ in f.roots():
    try:
        P = E.lift_x(x)
        print(P, m*P)
    except ValueError:
        pass

結果：

9*x^40 + 8*x^38 + x^37 + 3*x^36 + 10*x^35 + 12*x^33 + 10*x^32 + 11*x^31 + 3*x^30 + 5*x^29 + 9*x^28 + 2*x^27 + x^26 + x^23 + 4*x^21 + 9*x^20 + 6*x^19 + 6*x^18 + 2*x^17 + 12*x^16 + 2*x^15 + 6*x^14 + 5*x^13 + 3*x^12 + 9*x^11 + 7*x^10 + 9*x^9 + 2*x^8 + 10*x^7 + 3*x^6 + 3*x^5 + x^4 + 4*x^3 + 11*x^2 + 6*x
(0 : 9 : 1) (0 : 1 : 0)
(11 : 2 : 1) (0 : 1 : 0)
(9 : 3 : 1) (0 : 1 : 0)
(3 : 7 : 1) (0 : 1 : 0)

できました！

Schoofのアルゴリズム

Schoofのアルゴリズムの本質は中国人剰余定理です。 Frobenius写像のトレース $t$ は、 $p$ 未満の小さな素数 $l_{1}, l_{2}, \cdots, l_{n}$ を使って

$t \equiv t_{l_{i}} \mod l_{i}$

となるような $t_{l_{i}}$ を計算し、これらから $t$ を中国人剰余定理で復元します。中国人剰余定理とHasseの定理から、必要な素数は

$\displaystyle M = \prod_{i} l_{i} \geq 4\sqrt{p}$

を満たすまで取ってくれば良いです。（Hasse boundに入れるために、実際にはこれで求まった $t_{0}$ から $M$ を引く必要があります。）

もう１つの重要情報として、Frobenius写像 $\phi$ の特性多項式は

$\lambda(X) = X^{2} - tX + p$

で表されます。綺麗ですね。受験生のお供、Cayley-Hamiltonの定理より

$\displaystyle \lambda(\phi) = \phi^{2} - [t]\phi + [p] = [0]$

ですので、ここに $l_{i}$ -ねじれ点Pを代入すれば、

$\phi^{2}(P) - t\phi(P) + pP = \mathcal{O}$

つまり、 $P = (x,y)$ とおくと

$(x^{p^{2}}, y^{p^{2}}) + p(x, y) = t(x^{p}, y^{p})$

であり、 $p_{l_{i}} \equiv p \mod {l_{i}}$ とおくと、

$(x^{p^{2}}, y^{p^{2}}) + p_{l_{i}}(x, y) = t_{l_{i}}(x^{p}, y^{p})$

が成り立ちます。この式で計算できないのは $t_{l_{i}}$ だけですが、この値は十分に小さいので全探索します。（実際にはもっと賢い方法があり、後で登場します。）

実装の上での問題

ここまでの理論を実装しようと思うと、いくつかの問題が発生します。

1つ目の問題が、多項式の計算方法です。さきほどの $t_{l_{i}}$ を求めるための方程式は具体的な点 $P$ に対して計算するのではなく、一般的なねじれ点 $P$ に対して計算するので、多項式環の上で計算する必要があります。これは、「等分多項式を満たす」「楕円曲線上の演算である」という制約を加えれば良いので、剰余環 $R_{l_{i}} = \mathbb{F}_{p}[x, y] / (f_{l}, y^{2} - x^{3} - ax - b)$ の上で計算することで解決します。

2つ目の問題が、点の計算です。一般に $p$ は大きいので、 $(x^{p^{2}}, y^{p^{2}})$ といった計算は愚直にやると終わりません。

まず、 $(x^{p}, y^{p})$ ですが、今考えている $R_{l_{i}}$ 上では

$(x^{p}, y^{p}) = (x^{p} \mod f_{l}, ((y^{2})^{\frac{p-1}{2}} \mod f_{l})y)$

なので、 $y^{2}$ の部分を楕円曲線の式で置き換えれば、y座標もほぼ $x$ の計算で終わります。

同様に $(x^{p^{2}}, y^{p^{2}})$ も

$(x^{p^{2}}, y^{p^{2}}) = (x^{p^{2}} \mod f_{l}, ((y^{2})^{\frac{p^{2}-1}{2}} \mod f_{l})y)$

と計算できます。

点の加算についても高速化を考えてみましょう。 2つの点を $P=(a_{1}(x), b_{1}(x)y), Q=(a_{2}(x), b_{2}(x)y)$ （ただし、 $a_{1}(x), b_{1}(x), a_{2}(x), b_{2}(x) \in \mathbb{F}_{p}[x]$ ）とおき、 $P+Q=(A, B)$ を考えます。

まず、 $a_{1} \neq a_{2}$ のとき、

$r = \cfrac{b_{1}(x)y - b_{2}(x)y}{a_{1}(x) - a_{2}(x)}$

とおくと、

$A = r^{2} - a_{1}(x) - a_{2}(x)$
$B = r(a_{1}(x) - A) - b_{1}(x)y$

となります。 $A$ では $r^{2}$ の項に $y$ が登場しますが、2乗されているので[tex: y²]となり、ここが楕円曲線の $x$ に関する式に置換できます。

$A = \left( \cfrac{b_{1}(x) - b_{2}(x)}{a_{1}(x) - a_{2}(x)} \right)^{2} F(x) - a_{1}(x) - a_{2}(x)$

（ $F(x) = x^{3} + ax + b$ です。今後も $F(x)$ はこの定義で書きます。）一方、 $B$ では $y$ は消えませんが、 $r$ 中の $y$ と外側の $y$ をまとめて

$B = \left\{ \left( \cfrac{b_{1}(x) - b_{2}(x)}{a_{1}(x) - a_{2}(x)} \right) (a_{1}(x) - A) - b_{1}(x) \right\} y$

と書けます。

$a_{1} = a_{2}$ のときも、

$r = \cfrac{3a_{1}^2(x) + a}{2b_{1}(x)y} = \cfrac{3a_{1}^2(x) + a}{2b_{1}(x)F(x)} y$

と表せるので同様に $2P = (a_{3}(x), b_{3}(x) y)$ の形で書けます。

3つ目が $f_{l}$ で剰余が取れない問題です。 $r$ の計算で分数があるので逆元を計算する必要がありますが、これが $f_{l}$ を法として存在しないことがあります。どうすればいいでしょうか？

逆元を取りたい多項式を $d \in \mathbb{F}_{p}[x]$ とおきます。具体的には、 $d = a_{1}(x) - a_{2}(x)$ または $d = 2b_{1}(x)F(x)$ です。

今、 $d$ は法 $f_{l}$ の下で逆元を持たないと仮定しているので、 $g = \gcd(d, f_{l}) \neq 1$ です。 $d = a_{1}(x) - a_{2}(x)$ のとき、 $a_{1}(x), a_{2}(x)$ の定義より $\deg{g} \lt \deg{f_{l}}$ です。 $d = 2b_{1}(x)F(x)$ のとき、まず $F(x)$ と $g$ の関係についてですが、 $F(x)$ の根は $F(x)=0$ 、つまり位数が2の点のx座標になります。しかし、 $f_{l}$ の $l$ は3以上の素数なので位数は奇数であり、 $f_{l}$ と $F(x)$ は互いに素です。そのため $g$ は $b_{1}(x)$ の因子となるわけですが、 $b_{1}(x)$ の定義より $\deg{d} \lt \deg{f_{l}}$ です。したがって、いずれのケースでも $\deg{g} \lt \deg{f_{l}}$ です。

つまり、 $d$ の逆元が存在しない場合は

$R_{l} = \mathbb{F}_{p}[x, y] / (g, y^{2} - x^{3} - ax - b)$

上で計算すれば良いです。（ $E[l]$ の元であれば何でもいい。）

最後に、講義中は特に言及されませんでしたが、実装している上で一番詰まった点として、 $y$ の扱いがあります。私は $R_{l}$ 上での楕円曲線演算を、SymbolicEllipticCurveOverQuotientRingというクラスを作って実装したのですが、この際sageの機能を使って

self.PR = PolynomialRing(E.base(), 'xx')
self.xx = self.PR.gen()
self.QR = self.PR.quotient(f, 'x')
self.x  = self.QR.gen()

と定義しました。 $x$ はこれで良いのですが、楕円曲線の加算の式を見返すと $y$ が登場します。困ったなぁ。これには、優秀な先人のyoshi-camp参加記を参考に $y$ を1にする方法で解決しました。

furutsuki.hatenablog.com

というのも、今回の計算においてはどれだけ加算や乗算を繰り返しても、y座標は必ず $h(x)y$ という形になることを知っています。そして、Schoofのアルゴリズムにおいては点の比較のみが重要となるため、 $y$ の部分を1に置き換えても問題ありません。

Schoofのアルゴリズムの実装

長かったよ......

class SymbolicEllipticCurvePointOverQuotientRing(object):
    def __init__(self, E, x, y):
        self.E = E
        self.x, self.y = x, y

    def __eq__(self, other):
        return self.E == other.E \
          and self.x == other.x \
          and self.y == other.y

    def __add__(self, other):
        P, Q, O = self, other, self.E(0, 0)
        if P == O:
            return Q
        elif Q == O:
            return P

        a1, b1 = P.x, P.y
        a2, b2 = Q.x, Q.y
        if a1 != a2:
            n = b1 - b2
            d = a1 - a2
        else:
            n = 3 * a1^2 + self.E.a
            d = 2 * b1 * self.E.F

        # g = gcd(d, fl) != 1ならgで剰余環を構成し直す
        dd = self.E.f.parent()(d.list())
        g = self.E.f.gcd(dd)
        if g == 1:
            # 逆元が存在する
            r = n / d
            a3 = r^2 * self.E.F - a1 - a2
            b3 = r * (a1 - a3) - b1
            return self.E(a3, b3)

        else:
            # 逆元が存在しない場合、fをgに取り替えて計算
            EE = SymbolicEllipticCurveOverQuotientRing(self.E.base, g)
            PP = EE(P.x.list(), P.y.list())
            QQ = EE(Q.x.list(), Q.y.list())
            RR = PP + QQ
            return self.E(RR.x.list(), RR.y.list())

    def __mul__(self, n):
        P = self
        Q = self.E(0, 0)
        while n > 0:
            if n % 2 == 1:
                Q = P + Q
            P = P + P
            n >>= 1
        return Q

    def __rmul__(self, n):
        return self * n

class SymbolicEllipticCurveOverQuotientRing(object):
    def __init__(self, E, f):
        self.base = E
        self.PR = PolynomialRing(E.base(), 'xx')
        self.xx = self.PR.gen()
        self.QR = self.PR.quotient(f, 'x')
        self.x = self.QR.gen()
        self.f = f

        self.a, self.b = self.PR(E.a4()), self.PR(E.a6())
        self.F = self.x^3 + self.a*self.x + self.b

    def __call__(self, x, y):
        return SymbolicEllipticCurvePointOverQuotientRing(
            self, self.QR(x), self.QR(y)
        )

def frobenius_trace(E):
    a, b, p = E.a4(), E.a6(), E.base().order()
    l_prod, li = 1, 2
    # CRTで使うt_{l_i}を集める
    t_list, l_list = [], []
    while l_prod < 4 * sqrt(p): # Hasse boundに収める
        li = next_prime(li)

        # li等分多項式を商環とした楕円曲線を定義する
        fl = division_polynomial(E, li)
        EE = SymbolicEllipticCurveOverQuotientRing(E, fl)

        pl = p % li

        L = EE(EE.x^(p^2), EE.F^((p^2-1)//2)) + pl*EE(EE.x, 1)
        for tli in range(1, li):
            # phi(phi(P)) + li*P == tli*phi(P)を満たすtliを見つける
            R = tli * EE(EE.x^p, EE.F^((p-1)//2))

            if L == R:
                t_list.append(tli)
                l_list.append(li)
                l_prod *= li
                break

    t = CRT(t_list, l_list)
    if t >= 2 * sqrt(p):
        t -= l_prod
    return t

def schoof(E):
    return -frobenius_trace(E) + E.base().order() + 1

mitsuくんは真面目にPolynomialRingのPolynomialRingを作り、剰余環を真面目に実装したそうです。sage力が欲しい。

実行してみましょう。

p = random_prime(1<<31, 1<<32)
a = randrange(0, p)
b = randrange(0, p)
F = GF(p)
E = EllipticCurve(F, [a, b])

print("sage's order:", timeit('E.order()'))
print("ptr-schoof:", timeit('schoof(E)'))

print("Order:", E.order())
print("Order:", schoof(E))

やはり、tを総当りしていることもあり、sageの実装には多くの場合勝てません。

sage's order: 625 loops, best of 3: 146 ns per loop
ptr-schoof: 5 loops, best of 3: 350 ms per loop
Order: 435017356
Order: 435017356

素数が64-bitくらいなら数十秒以内に求まります。

Schoof-Elkie-Atkinsという高速化されたアルゴリズムもお勉強しました。これのwriteupも途中まで書いていましたが、書けば書くほど無限に内容が増えるので全部コメントアウトして消しました。

モジュラー多項式と楕円曲線の関係を、複素平面上の格子を経由して学ぶことでアハ体験できる講義内容になっていました。興味のある方はyoshi-campに参加しましょう。

[Xornet] Bilinyar Map in CTF

ここから人間味あふれる講義に戻ります。 Xornetさんの講義はタイトルがよくわかりませんが、楕円曲線でおなじみのペアリングについてお勉強できます。

ペアリングの重要な性質として、双線型性というものがあります。双線型性は2変数関数に対する性質で、次のようなものです。

$f(x_{1} + x_{2}, y) = f(x_{1}, y) + f(x_{2}, y)$
$f(x, y_{1} + y_{2}) = f(x, y_{1}) + f(x, y_{2})$

これより、スカラー倍に対して次の性質があります。

$f(ax, y) = a f(x, y)$
$f(x, ay) = a f(x, y)$

わかりやすいですね。楕円曲線上のペアリングでは、次のようになります。

$f(P_{1} + P_{2}, Q) = f(P_{1}, Q) f(P_{2}, Q)$
$f(P, Q_{1} + Q_{2}) = f(P, Q_{1}) + f(P, Q_{2})$
$f(aP, Q) = f(P, Q)^{a}$
$f(P, aQ) = f(P, Q)^{a}$

楽しいですね。ペアリングというのは楕円曲線に対して1つ定まるようなものではなく、こういう性質さえ満たせば良いのでいろいろと定義できます。

Weil Pairing

親のペアリングより見たペアリングですね。名前の読み方が初見殺しのペアリングランキングでは常にNo. 1です。

$e: E[n] \times E[n] \rightarrow \mu_{n}$

n-ねじれ点を2つ渡すと、有限体上のn乗根が返ってきます。

n-ねじれ点どうしでしかペアリングは計算できず、 $e(P, P) = 1$ という性質があるため、線形従属な2点では1が返ってきてしまいます。

Tate Pairing

名前がかわいいペアリングランキングでいつも上位にいる常連さんです。

$\tau_{q}: E[q] \times E(\mathbb{F}_{p^{k}})/qE(\mathbb{F}_{p^{k}}) \rightarrow \mathbb{F}_{p^{k}}^{*}/(\mathbb{F}_{p^{k}}^{*})^{q}$

という定義です。怖いですね。

$\tau_{q}(P, Q)^{q} = 1$ といった性質があります。

DDH問題

ペアリングを使って解ける代表的な問題としてDDH問題があります。これは、 $P, aP, bP$ が既知のときに、与えられた点 $Q$ が $Q=abP$ かどうかを判別する問題です。

Tate Pairingを使うと

$e(aP, bP) = e(P, P)^{ab}$
$e(P, cP) = e(P, P)^{c}$

なので、 $c=ab$ のときに両者の値が一致します。

確認してみましょう。

p = 0x3a05ce0b044dade60c9a52fb6a3035fc9117b307ca21ae1b6577fef7acd651c1f1c9c06a644fd82955694af6cd4e88f540010f2e8fdf037c769135dbe29bf16a154b62e614bb441f318a82ccd1e493ffa565e5ffd5a708251a50d145f3159a5
k = 2 # embedding degree
E = EllipticCurve(GF(p), [1, 0])
assert (p^k - 1) % E.order() == 0

P = E.random_point()
aP = 314159265 * P
bP = 2718281828 * P

Q1 = 314159265 * 2718281828 * P
Q2 = randrange(0, E.order()) * P

print(aP.tate_pairing(bP, n=E.order(), k=k))
print(P.tate_pairing(Q1, n=E.order(), k=k))
print(P.tate_pairing(Q2, n=E.order(), k=k))

埋め込み次数*3を知っている必要があるので、講義で用意されていた埋め込み次数の小さい楕円曲線を使っています。

15128028...
15128028...
85119939...

と、DDH問題が解けていることがわかります。

MOV Attack

楕円曲線上の離散対数問題について、ベースポイント $G$ の埋め込み次数 $k$ が小さいときに使える攻撃です。古のyoshi-campで「猫でもわかる楕円曲線暗号」を発表したときに理論無視実装コードだけやりました。

$G$ の位数を $r$ とすると、ペアリング $e: E[r] \times E[r] \rightarrow \mathbb{F}_{p^{k}}$ が定義できます。適当な点 $Q$ に対して

$e(xP, Q) = e(P, Q)^{x}$

が成り立つので、拡大体上での離散対数問題として解くことができ、楕円曲線上でやるよりはマシに計算できます。*4

以下、パラメータは「Cyber Apocalypse CTF 2022: Intergalactic Chase / MOVs Like Jagger」という問題から取っているそうです。

# 問題設定
a = -35
b = 98
p = 434252269029337012720086440207
E = EllipticCurve(GF(p), [a, b])
ec_order = 434252269029337012720086440208

G = E(16378704336066569231287640165, 377857010369614774097663166640)
x = randint(1, ec_order)
xG = x * G

# 埋め込み次数を調べる
k = 1
while (p^k - 1) % ec_order:
    k += 1
print("Embedding degree:", k)

# 拡大体F_{p^k}上の楕円曲線を作る
Ee = EllipticCurve(GF(p^k), [a, b])
Ge, xGe = Ee(G), Ee(xG)

# 線形独立な点を適当に作る
T = Ee.random_point()
Q = (T.order() // gcd(T.order(), G.order())) * T
assert G.order() / Q.order() in ZZ

# ペアリングを計算する
a = Ge.weil_pairing(Q, G.order())
b = xGe.weil_pairing(Q, G.order())

print("e(G, Q) =", a)
print("e(xG, Q) =", b)
y = b.log(a)

print(x)
print(y)

1分くらいで解けました。

Embedding degree: 2
e(G, Q) = 20183620868354029403390095407*z2 + 340156830587302922110931927752
e(xG, Q) = 382029521819594423509410822768*z2 + 81650503901539005236114419028
25571984854458949809049655853
25571984854458949809049655853

BLS

BLS(Boneh-Lynn-Shacham)は署名方式の名前で、CDH問題を解くのが難しいがDDH問題は簡単に解けるような曲線を利用した署名です。検証者はDDH問題をペアリングで解くことで、署名の正当性を検証します。

まず、鍵生成で署名者は鍵ペアを生成します。

秘密鍵： $G$ の位数未満の整数 $x$ を選ぶ。
公開鍵： $G, P=xG$ を公開する。

次に、この鍵で署名します。署名したいメッセージ $m$ をハッシュ関数を通して楕円曲線上の点 $H(m)$ に変換し、署名を作ります。

署名： $\sigma = x H(m)$

最後に、検証者は公開鍵と署名、メッセージから署名の正当性を調べます。

検証： $e(\sigma, G) = e(H(m), P)$ を検証する。

正しい署名であれば、

$e(\sigma, G) = e(xH(m), G) = e(H(m), xG) = e(H(m), P)$

より両者の値は一致するはずです。

実装してみましょう。

import hashlib

# メッセージからE[2*r]上の点を作る
def h(m: bytes):
    h = hashlib.sha256(m).digest()
    x = Integer(int.from_bytes(h, "little"))

    while True:
        rhs = K(x**3 + a*x + b)
        if rhs.is_square():
            return E.lift_x(x)

        x += 1

# BLSに適した楕円曲線
q = 0x3a05ce0b044dade60c9a52fb6a3035fc9117b307ca21ae1b6577fef7acd651c1f1c9c06a644fd82955694af6cd4e88f540010f2e8fdf037c769135dbe29bf16a154b62e614bb441f318a82ccd1e493ffa565e5ffd5a708251a50d145f3159a5
a, b = 1, 0
o = 21992493417575896428286087521674334179336251497851906051131955410904158485314789427947788692030188502157019527331790513011401920585195969087140918256569620608732530453375717414098148438918130733211117668960801178110820764957628836
r = 2344807743588794553832391292516279194397209456764712786969868894104465782493871625440983981162219279755855675661203
k = 2
assert (q^2 - 1) % r == 0
assert o == 2**2 * r**2

K = GF(q)
E = EllipticCurve(K, [a, b])
G = E.gens()[0]

msg = b"neko to innu"
H = h(msg)

# 鍵生成
x = 5963
P = x * G

# 署名
S = x * H

# 検証
wp1 = S.tate_pairing(G, n=o, k=k)
wp2 = H.tate_pairing(P, n=o, k=k)
wp3 = E.random_point().tate_pairing(G, n=o, k=k)

print(wp1 == wp2)
print(wp3 == wp2)

実行すると、署名が正しいときのみTrueになります。

BLS12-381

BLS12-381はBLSで使える楕円曲線の一種です。*5 埋め込み次数12、381-bitの素数qで定義されており、 $\mathbb{F}_{q^{12}}$ 上の楕円曲線でペアリングします。

12次の拡大体についてですが、既約多項式で逐次的に拡大して構成するのが効率的だそうで、 $\mathbb{F}_{q^{12}}$ は次のような多段の拡大になっています。

$\mathbb{F}_{q^{2}} = \mathbb{F}_{q}[u] / (u^{2} + 1)$
$\mathbb{F}_{q^{6}} = \mathbb{F}_{q}^{2}[v] / (v^{3} - (u + 1))$
$\mathbb{F}_{q^{12}} = \mathbb{F}_{q}^{6}[w] / (w^{2} - v)$

埋め込み次数 $k$ に対して $E/\mathbb{F}_{q^{k}}$ には位数 $r$ の部分群が複数存在し、これにはペアリングもニッコリ。

しかし、 $\mathbb{F}_{q^{12}}$ は計算が重いという問題があり、当然その上での楕円曲線の演算も重くなってしまいます。実際、381-bitの素数でGF(q^12)を作ろうとするとPCがｷｭｲｨｨｨｲﾝと泣きます。なぜ計算量を増やしてこんな面倒なことをするかというと、計算機上で実装する際の効率が良いみたいな恩恵もあるらしいです。

でも計算できなければ使い物になりません。 BLSで登場する演算は、ペアリングを除いて点のスカラー倍だけです。そこでBLS12-381では、次の2つの曲線が使われます。

$E/\mathbb{F}_{q}: y^{2} = x^{3} + 4$
$E'/\mathbb{F}_{q^{2}}: y^{2} = x^{3} + 4(1+i)$

ここで $i$ は-1の平方根なので、次のようにも書けます。

$\mathbb{F}_{q^{2}} = \mathbb{F}_{p}[x]/(x^{2} + 1)$

さて、1つ目の楕円曲線上の点は $E/\mathbb{F}_{q^{12}}$ 上の点とみなしても良いですが、2つ目の楕円曲線は曲線が違うのでダメそうです。そこで、次のような写像を考えます。ただし、 $z^{6} = (1 + i)^{-1}$ です。

$E'/\mathbb{F}_{q^{2}} \ni (x, y) \mapsto (z^{2}x, z^{3}y) \in E/\mathbb{F}_{q^{12}}$

$x = x' z^{-2}, y=y' z^{-3}$ を $E/\mathbb{F}_{q^{2}}$ の式に代入すると

$z^{-6}y^{2} = z^{-6}x^{3} + 4(1 + i)$
$y^{2} = x^{3} + 4(1 + i)z^{6} = x^{3} + 4(1 + i)(1 + i)^{-1} = x^{3} + 4$

となり、 $E/\mathbb{F}_{q^{12}}: y^{2} = x^{3} + 4$ に移ります。*6 （これで $z^{6} = (1 + i)^{-1}$ にした理由がわかりましたね。）

実装パート

Circle City Con 2021というCTFのRandom is Also Validという問題を解きます。この問題では謎の方法でBLS12-381が実装されており、その上でDDH問題を解かなければなりません。問題の詳細はXornetさんのブログを読みましょう。

project-euphoria.dev

逐次拡大体を整理すると、

$u^{2} + 1 = 0$
$v^{3} + (u + 1) = 0$
$w^{2} - v = 0$

なので

$w^{6} = v^{3} = u + 1$

より、 $u = w^{6} - 1$ となります。また、辺々2乗して、

$w^{12} = u^{2} + 2u + 1 = 2u = 2w^{6} - 2$

ですから、 $w^{12} - 2w^{6} + 2$ が剰余多項式です。

こんな感じで解く。

import json
out = json.load(open("out.txt", "r"))

# 問題パラメータ
q = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
r = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001
# 埋め込み次数は12
k = 12
assert (q^k - 1) % r == 0

G1_x = 4
G1_y = 0x0a989badd40d6212b33cffc3f3763e9bc760f988c9926b26da9dd85e928483446346b8ed00e1de5d5ea93e354abe706c
G1_mul = 0x396c8c005555e1568c00aaab0000aaab
G2_x = [2]
G2_y = [0x013a59858b6809fca4d9a3b6539246a70051a3c88899964a42bc9a69cf9acdd9dd387cfa9086b894185b9a46a402be73, 0x02d27e0ec3356299a346a09ad7dc4ef68a483c3aed53f9139d2f929a3eecebf72082e5e58c6da24ee32e03040c406d4f]
G2_mul = 0x5d543a95414e7f1091d50792876a202cd91de4547085abaa68a205b2e5a7ddfa628f1cb4d9e82ef21537e293a6691ae1616ec6e786f0c70cf1c38e31c7238e5

# 以下の逐次拡大体をFq12/w^12-2w^6+2として作る
# F_q2 = Fq[u]/(u^2 + 1)
# F_q6 = Fq^2[v]/(v^3-(u+1))
# F_q12 = Fq^6[w]/(w^2-v)
F12 = GF(q^12, 'w', modulus=x^12-2*x^6+2)
w = F12.gen()
E = EllipticCurve(F12, [0, 4])

def twist(Px, Py):
    # 点をE'/Fq2からE/Fq12に移す
    z = w^-1
    # u = w^6 - 1
    if isinstance(Px, list):
        Px = sum(map(lambda v: v[1]*(w^6-1)^v[0], enumerate(Px)))
    if isinstance(Py, list):
        Py = sum(map(lambda v: v[1]*(w^6-1)^v[0], enumerate(Py)))
    return z^2 * F12(Px), z^3 * F12(Py)

# 点をE/(Fp12[w]/(w^12-2w^6+2))上に移す
G1 = G1_mul * E(G1_x, G1_y)
G2 = G2_mul * E(twist(G2_x, G2_y))

o = E.order()
dec = lambda v: list(map(lambda x: int(x, 16), v))
m = 0
for i, bitinfo in enumerate(out):
    # PA = a*G1
    PA = E(dec(bitinfo['P_A_x']), dec(bitinfo['P_A_y']))
    # PB = b*G2
    PB = E(twist(dec(bitinfo['P_B_x']), dec(bitinfo['P_B_y'])))

    # DDH問題を解く
    wp2 = PA.weil_pairing(PB, n=r) # e(a*G1, b*G2) = e(G1, G2)^{ab}
    if len(bitinfo['P_C_x']) == 1 and len(bitinfo['P_C_y']) == 1:
        # e(c*G1, G2) = e(G1, G2)^{c}
        PC = E(dec(bitinfo['P_C_x']), dec(bitinfo['P_C_y']))
        wp1 = PC.weil_pairing(G2, n=r)
    else:
        # e(G1, c*G2) = e(G1, G2)^{c}
        PC = E(twist(dec(bitinfo['P_C_x']), dec(bitinfo['P_C_y'])))
        wp1 = G1.weil_pairing(PC, n=r)

    m = (m << 1) | int(wp1 == wp2)
    if i % 8 == 7:
        print(int.to_bytes(int(m), i//8+1, 'little')[::-1])

詰まりポイントとしては、PC.weil_pairing(G)なのかG.weil_pairing(PC)なのかで結果が変わるので注意しましょう。（1敗）

CCC{Diffie_0r_Hellman_wh4t_d0_y0U_d3c1d3?}

ツイストできたので満足ですが、実は宿題のzipfelを解かなければなりません。これはそのうちやりますやります。

[ﾈｺﾁｬﾝ] Tornado Cats

~~マネーロンダリング~~ Tornado Cashというミキサープロトコルとゼロ知識証明についての勉強です。いろいろとスクリプトを組んでいたのですが、PCを入れ替えて全部消えたのでここで公開できる成果物がありません！

しかし、すべての講義の中でたぶん一番資料が充実しており、なんか10,000円くらいの鈍器本として売ってそうな内容でした。時間がなくてTornado Cash本体に到達していませんが、いつかkitakitsune*7ですべてが解明されると思います。

Day 3

帰りは基本バスの中ですやすやしてました。箱根駅に着いたら、大通りから離れた場所にめちゃくちゃおいしい焼肉屋があり、もぐもぐしてました。

あとはなんか源泉かけ流し謎温泉に入ったり、1個50円くらいのお菓子を買ったりしていました。

写真集

おわりに

楽しかったです。また春か夏にやりましょう。 @everyone

あと、まだ宿泊費を振り込んでない人は、これを見たら振り込みましょう。宿から焼肉からすべて負担させられると破産しちゃいます。

*1:Atkinがいなかった世界線でのSchoofのアルゴリズムを指します。

*2:Dewagheの手法

*3:位数rがp^k-1を割り切れる最小のk

*4:拡大体上での離散対数問題は解きやすいらしいです。

*5:BLSのB,SはBoneh,Shachamですが、BLS12-381のB,SはBarreto,Scottだそうです。（は？）

*6:頭が死んでおりここで1728時間くらい無駄にした。

*7:yoshi-camp中にできなかったことをupsolveするボイチャ

CTFするぞ

CTF以外のことも書くよ

yoshi-camp 2022 winter参加記【Day 2-3】

はじめに

yoshi-camp

Day 2

[mitsu] ネコちゃん式　～安全な曲線の生成～

Frobenius写像とHasseの定理

等分多項式

Schoofのアルゴリズム

実装の上での問題

Schoofのアルゴリズムの実装

[Xornet] Bilinyar Map in CTF

Weil Pairing

Tate Pairing

DDH問題

MOV Attack

BLS

BLS12-381

実装パート

[ﾈｺﾁｬﾝ] Tornado Cats

Day 3

写真集

おわりに

はじめに

yoshi-camp

Day 2

[mitsu] ネコちゃん式 ～安全な曲線の生成～

Frobenius写像とHasseの定理

等分多項式

Schoofのアルゴリズム

実装の上での問題

Schoofのアルゴリズムの実装

[Xornet] Bilinyar Map in CTF

Weil Pairing

Tate Pairing

DDH問題

MOV Attack

BLS

BLS12-381

実装パート

[ﾈｺﾁｬﾝ] Tornado Cats

Day 3

写真集

おわりに

[mitsu] ネコちゃん式　～安全な曲線の生成～