ASIS CTF Quals 2019 | Halloween Party

#ASISCTFQuals2019

In the halloween party, we want to half a delicious but small cake!

flag = ASIS{P.x}

#!/usr/bin/env python

from fastecdsa.curve import Curve
from fastecdsa.point import Point
from Crypto.Util.number import *
from secret import EC_params, flag, Q


p, a, b, q, Px, Py = EC_params
C = Curve('halloween', p, a, b, q, Px, Py)
P = Point(Px, Py, curve = C)
P1 = Point(p + 1, 467996041489418065436268622304855825266338280723, curve = C)
P2 = Point(p - 1, 373126988100715326072483107245781156204485119489, curve = C)
P3 = Point(p + 3, 245091091146774561796627894715885724307214901148, curve = C)


assert ((9<<8>>4<<9<<12<<6>>9>>2<<5>>3>>4>>8<<12>>1>>5>>7<<13>>12>>12) * P).x == Q.x
assert bytes_to_long(flag) == P.x
assert ((-1) * Q).y == 621803439821606291947646422656643138592770518069

どこからどう見てもEllipticCurveの問題。一瞬sageにみえるけどfastecdsaというライブラリを使っている。P.xを求めるのが目的で、Pの前後のいくつかの点の存在と、Pを何倍かした点Qの存在が明らかになっている。

find parameters

とにかくa, b, pの値くらいは求めないと楕円曲線に辿り着けない。P1, P2, P3から式が立つ。楕円曲線の式は $y^2 = x^3 + ax + b \mod p$ なのでここに変数を当てはめる

$y_1^2 \equiv (p+1)^3 + a(p+1) + b \mod p$

$y_2^2 \equiv (p-1)^3 + a(p-1) + b \mod p$

$y_3^2 \equiv (p+3)^3 + a(p+3) + b \mod p$

適当に開いて $\mod p$ で消えるところを消してみる

$y_1^2 \equiv 1 + a + b \mod p$

$y_2^2 \equiv -1 -a + b \mod p$

$y_3^2 \equiv 27 + 3a + b \mod p$

$y_1^2 - y_2^2 \equiv 2 + 2a \mod p$

$y_1^2 - y_3^2 \equiv -26 - 2a \mod p$

$(y_1^2 - y_2^2) + (y_1^2 - y_3^2) \equiv -24 \mod p$

になるので、 $(y_1^2 - y_2^2) + (y_1^2 - y_3^2) + 24 = tp$ となるはず。というわけで factordb に投げると

$p = 883097976585278660619269873521314064958923370261$ がわかる

$(y_1^2 - y_2^2 - 2) / 2 \equiv a \mod p$

$(y_1^2 + y_2^2) / 2 \equiv b \mod p$

Find Q

剰余方程式を解くテクを使って (-) Qを求める

Q.x, Q.y には $Q.y^2 \equiv Q.x^3 + a*Q.x + b \mod p$ という関係があるので、

$f = Q.x^3 + aQ.x + b - Q.y^2 \in GF(p){x}$

の根を求めれば良い。

Find P

あとは楕円曲線：逆数をかけるをやるだけ

from sage.all import *

y1 = 467996041489418065436268622304855825266338280723
y2 = 373126988100715326072483107245781156204485119489
y3 = 245091091146774561796627894715885724307214901148

# p = factor(2 * (y1**2) - (y2**2) - (y3**2) + 24) from factordb
p = 883097976585278660619269873521314064958923370261

A = (((y1**2) - (y2**2) - 2 ) // 2) % p
B = (((y1**2) + (y2**2)) // 2) % p


iQy = 621803439821606291947646422656643138592770518069
_, x = PolynomialRing(GF(p), name="x").objgen()
f = x**3 + A*x + B - iQy**2
iQx = int(f.roots()[0][0])

EC = EllipticCurve(GF(p), [A, B])
P2 = EC((iQx, iQy))
P = inverse_mod(2, EC.order())  * P2
print(P)

https://blog.bi0s.in/2019/04/23/Crypto/Elliptic-Curves/asis-quals19-halloween-party/