TL;DR

  • ある曲線上の点$P,Q$のx座標にフラグが仕込まれて、$P+P,Q+Q,P+Q$の3点のみが与えられる
  • $(P+P)+(Q+Q) = (P+Q)+(P+Q)$のx座標とy座標が等しくなることを利用して$p$の倍数を複数求めて最大公約数をとり、$p$を求める
  • $P+P$はそのx座標とy座標の式が$P$のx座標とy座標を変数として表され、2変数の式が2つ得られることから解くことが出来る、$Q$に関しても同様

Writeup

次のPythonスクリプトとその実行結果が与えられる

#!/usr/bin/env python3

from Crypto.Util.number import *
from secret import a, b, p, P, Q
from flag import flag

def onmiff(a, b, p, G):
	x, y = G
	return (a*x*(y**2 - 1) - b*y*(x**2 - 1)) % p == 0

def addmiff(X, Y):
	x_1, y_1 = X
	x_2, y_2 = Y
	x_3 = (x_1 + x_2) * (1 + y_1*y_2) * inverse((1 + x_1*x_2) * (1 - y_1*y_2), p) % p
	y_3 = (y_1 + y_2) * (1 + x_1*x_2) * inverse((1 + y_1*y_2) * (1 - x_1*x_2), p) % p
	return (x_3, y_3)


l = len(flag) // 2
m1, m2 = bytes_to_long(flag[:l]), bytes_to_long(flag[l:])

assert m1 < (p // 2) and m2 < (p // 2)
assert onmiff(a, b, p, P) and onmiff(a, b, p, Q)
assert P[0] == m1 and Q[0] == m2

print(f'P + Q = {addmiff(P, Q)}')
print(f'Q + Q = {addmiff(Q, Q)}')
print(f'P + P = {addmiff(P, P)}')

$ax(y-1)^2 \equiv by(x-1)^2 \mod p$という曲線と曲線上の点の加法(addmiff())が定義され、その上の点$P,Q$に対し、$P+P, Q+Q, P+Q$の3点が与えられている。$P,Q$の$x$座標がフラグとなっている。

$a,b,p$は与えられていないのでひとまず$p$を求める(なお、addmiff()で用いられていないことから、$a,b$を求める必要は無い、というかそもそも一意に定まらない)。

点の加法は可換かつ多分結合律が成り立つので、$(P+P) + (Q+Q) = (P+Q) + (P+Q)$が成り立つ。ということは両辺のx座標とy座標はどちらも$p$を法として合同なのでそれぞれ引くことで$p$の倍数が手に入り、最大公約数を求めると$p$が求められる予感がする。

点の加法は$(x_3, y_3) \coloneqq (x_1, y_1) + (x_2, y_2)$とすると、次のようになっている。

$$ \begin{aligned} x_3 \equiv \frac{(x_1 + x_2)(1+y_1y_2)}{(1+x_1x_2)(1-y_1y_2)} \mod p\cr y_3 \equiv \frac{(y_1+y_2)(1+x_1x_2)}{(1+y_1y_2)(1-x_1x_2)} \mod p \end{aligned} $$

この式から、$P+Q = (x_{PQ}, y_{PQ}), (P+P) = (x_{PP}, y_{PP}), (Q+Q) = (x_{QQ}, y_{QQ})$とおくと、$((P+Q) + (P+Q))_x \equiv ((P+P) + (Q+Q))_x$であるから、次が成り立つ。

$$ (x_{PQ} + x_{PQ})(1+y_{PQ}y_{PQ})(1+x_{PP}x_{QQ})(1-y_{PP}y_{QQ}) \equiv (X_{PP} + x_{QQ})(1+y_{PP}y_{QQ})(1+x_{PQ}x_{PQ})(1-y_{PQ}y_{PQ}) \mod p $$

$p$は不明だが、両辺はどちらも分かっているので、それぞれ計算して差を取ると$p$の倍数が手に入る。$y$座標の計算に関しても同様の事を行うと(面倒なので式は略)、別の$p$の倍数が手に入るので最大公約数を取って、小さい因数を除去して$p$を求める。

続いて、$P,Q$のx座標を求める。$P+P$のような点の2倍算に関しては同じ点の加算なので次のようになる。

$$ P+P = 2P = \left(\frac{2x(1+y^2)}{(1+x^2)(1-y^2)}, \frac{2y(1+x^2)}{(1+y^2)(1-x^2)}\right) $$

既に$P+P$の値はわかっているので$x,y$を変数とした2つの式が手に入る事になる。具体的には次のような2つの式が得られる。

$$ \begin{aligned} f_1(x,y) \coloneqq 2x(1+y^2) - x_{PP}(1+x^2)(1-y^2) \equiv 0 \mod p \cr f_2(x,y) \coloneqq 2y(1+x^2) - y_{PP}(1+y^2)(1-x^2) \equiv 0 \mod p \end{aligned} $$

というわけで$f_1, f_2$の連立方程式を解けば$x,y$が求まりそうな予感がする。解く方法は何でも良いが、SageMathのグレブナー基底では芳しくない結果が得られたので終結式を用いた。

実際解くと$x$が複数求まるので文字列としてvalidなものがフラグになるので、同様にして$Q+Q$から$Q$の$x$座標を求めて$P$の$x$座標と結合するとフラグが得られる。

(※以下、$f_1, f_2$の連立方程式を解く方法についての話)

ちなみに、終結式はシルヴェスター行列の行列式になるのだが、SageMathではなぜか有限体係数の多項式が成分の行列に対して行列式を.determinant()等で求めることが出来ない。内部実装でこれを使っていると思われる.resultant()も同様である。

シルヴェスター行列自体はf1.sylvester_matrix(f2, y)のような形で求めることが出来るので、そこから行列式の置換を用いた定義にしたがって計算すると普通に1変数多項式が求まることからこれを用いて各点の$x$を求めた。

Code

from Crypto.Util.number import *


def onmiff(a, b, p, G):
    x, y = G
    return (a*x*(y**2 - 1) - b*y*(x**2 - 1)) % p == 0


def addmiff(X, Y):
    x_1, y_1 = X
    x_2, y_2 = Y
    x_3 = (x_1 + x_2) * (1 + y_1*y_2) * inverse((1 + x_1*x_2) * (1 - y_1*y_2), p) % p
    y_3 = (y_1 + y_2) * (1 + x_1*x_2) * inverse((1 + y_1*y_2) * (1 - x_1*x_2), p) % p
    return (x_3, y_3)


def resulatant(f1, f2, var):
    sylv = f1.sylvester_matrix(f2, var)
    det = 0
    perm = Permutations([1,2,3,4], 4)
    for _p in perm:
        if Permutation(_p).is_even():
            term = 1
        else:
            term = -1
        _p = [x-1 for x in _p]
        for i in range(4):
            term *= sylv[i][_p[i]]

        det += term

    return det


def all_ascii(s: bytes):
    for c in s:
        if c < 0x20 or c > 0x7f:
            return False

    return True


PQ = (540660810777215925744546848899656347269220877882, 102385886258464739091823423239617164469644309399)
QQ = (814107817937473043563607662608397956822280643025, 961531436304505096581595159128436662629537620355)
PP = (5565164868721370436896101492497307801898270333, 496921328106062528508026412328171886461223562143)

# (P+Q) + (P+Q) = (P+P) + (Q+Q)
# R1 = (P+Q) + (P+Q)
# R2 = (P+P) + (Q+Q)
# R1 = R2

kps = []
R1_x_nume = (PQ[0] + PQ[0]) * (1 + PQ[1]*PQ[1])
R1_x_denom = (1+PQ[0]*PQ[0]) * (1 - PQ[1]*PQ[1])
R2_x_nume = (PP[0] + QQ[0]) * (1 + PP[1]*QQ[1])
R2_x_denom = (1+PP[0]*QQ[0]) * (1 - PP[1]*QQ[1])
R1_y_nume = (PQ[1] + PQ[1]) * (1 + PQ[0]*PQ[0])
R1_y_denom = (1 + PQ[1] * PQ[1]) * (1 - PQ[0] * PQ[0])
R2_y_nume = (PP[1] + QQ[1]) * (1 + PP[0]*QQ[0])
R2_y_denom = (1 + PP[1] * QQ[1]) * (1 - PP[0] * QQ[0])

kps.append(R1_x_nume * R2_x_denom - R2_x_nume * R1_x_denom)
kps.append(R1_y_nume * R2_y_denom - R2_y_nume * R1_y_denom)

p = gcd(kps)
for _p, e in factor(p):
    if e == 1:
        p = _p

"""
PR.<a,b> = PolynomialRing(GF(p))
f1 = a * PQ[0] * (PQ[1]**2 - 1) - b * PQ[1] * (PQ[0]**2 - 1)
f2 = a * PP[0] * (PP[1]**2 - 1) - b * PP[1] * (PP[0]**2 - 1)
f3 = a * QQ[0] * (QQ[1]**2 - 1) - b * QQ[1] * (QQ[0]**2 - 1)

_a = 114514
I = ideal([f1, f2, f3])
B = I.groebner_basis()
b = int(B[0].subs(a=_a).univariate_polynomial().roots()[0][0])
a = _a

assert onmiff(a,b,p,PP)
assert onmiff(a,b,p,QQ)
assert onmiff(a,b,p,PQ)
"""

PR.<x,y> = PolynomialRing(GF(p))

g1 = 2*x*(1+y^2) - PP[0] * (1+x^2) * (1 - y^2)
g2 = 2*y*(1+x^2) - PP[1] * (1+y^2) * (1 - x^2)

r = resulatant(g1, g2, y)

flag = b""
roots = r.univariate_polynomial().roots()
for r, _ in roots:
    m = long_to_bytes(r)
    if all_ascii(m):
        flag += m

g1 = 2*x*(1+y^2) - QQ[0] * (1+x^2) * (1 - y^2)
g2 = 2*y*(1+x^2) - QQ[1] * (1+y^2) * (1 - x^2)

r = resulatant(g1, g2, y)

roots = r.univariate_polynomial().roots()
for r, _ in roots:
    m = long_to_bytes(r)
    if all_ascii(m):
        flag += m

print(flag)

Flag

CCTF{D39enEr47E_ECC_4TtaCk!_iN_Huffs?}