CYBER APOCALYPSE CTF 2021 | Super Metroid

#cyber_apocalypse_ctf_2021

from Crypto.Util.number import bytes_to_long, getPrime
from secrets import FLAG

def gen_key():
    from secrets import a,b
    E1 = EllipticCurve(F, [a,b])
    assert E.is_isomorphic(E1)
    key = - F(1728) * F(4*a)^3 / F(E1.discriminant())
    return key

def encrypt(message, key):
    m = bytes_to_long(message)
    e = 0x10001
    G = E.lift_x(Integer(m))
    P = e*G
    return int(P[0])^^int(key)

p = getPrime(256)
F = GF(p)
E = EllipticCurve(F, [1,2])
key = gen_key()

c1 = encrypt(FLAG[:22], 0)
c2 = encrypt(FLAG[22:], key)

print(f'p = {p}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')

overview

#EllipticCurve
$E: y^2 \equiv x^3 + x + 2 \mod p$ と isomorphism な曲線 $E_1$ を構成している
$key = \frac{-1728 * (4a)^3}{ -16(4a^3 + 27b^2) } = \frac{1728\cdot 4a^3}{4a^3 + 27b^2}$
$P_1 = (m_1, y_1), P_2 = (m_2, y_2)$ として、暗号化は次の通り
$Q_1 = eP_1$ として $c_1 = Q_1.x$
$Q_2 = eP_2$ として $c_2 = Q_2.x \oplus key$

solution

1728 という数字に見覚えがあるはず。これが j-invariant で用いられていたマジックナンバーで、 $key$ は $E_1$ の j-invariant そのもの
$E$ と $E_1$ は同型なので、位数を調整するテクや j-invariant は同じになる

from Crypto.Util.number import long_to_bytes

p = 103286641759600285797850797617629977324547405479993669860676630672349238970323
c1 = 39515350190224022595423324336682561295008443386321945222926612155252852069385
c2 = 102036897442608703406754776248651511553323754723619976410650252804157884591552

F = GF(p)
E = EllipticCurve(F, [1,2])

n = E.order()
d = inverse_mod(0x10001, n)
key = int(E.j_invariant())

P1 = E.lift_x(Integer(c1))
P2 = E.lift_x(Integer(c2^^key))

G1 = d*P1
G2 = d*P2

flag = long_to_bytes(int(G1[0])) + long_to_bytes(int(G2[0]))
print(flag)