[zer0pts CTF 2022] CurveCrypto

task.py

import os
from random import randrange
from Crypto.Util.number import bytes_to_long, long_to_bytes, getStrongPrime
from Crypto.Util.Padding import pad
from fastecdsa.curve import Curve

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def gen():
    while True:
        p = getStrongPrime(512)
        if p % 4 == 3:
            break
    while True:
        q = getStrongPrime(512)
        if q % 4 == 3:
            break
    n = p * q
    a = randrange(n)
    b = randrange(n) 

    while True:
        x = randrange(n)
        y2 = (x**3 + a*x + b) % n
        assert y2 % n == (x**3 + a*x + b) % n
        if pow(y2, (p-1)//2, p) == 1 and pow(y2, (q-1)//2, q) == 1:
            yp, yq = pow(y2, (p + 1) // 4, p), pow(y2, (q + 1) // 4, q)
            _, s, t = xgcd(p, q)
            y = (s*p*yq + t*q*yp) % n
            break
    return Curve(None, n, a, b, None, x, y) 

def encrypt(m, G):
    blocks = [m[16*i:16*(i+1)] for i in range(len(m) // 16)]
    c = []
    for i in range(len(blocks)//2):
        G = G + G
        c.append(G.x ^ bytes_to_long(blocks[2*i]))
        c.append(G.y ^ bytes_to_long(blocks[2*i+1]))
    return c

def decrypt(c, G):
    m = b''
    for i in range(len(c) // 2):
        G = G + G
        m += long_to_bytes(G.x ^ c[2*i])
        m += long_to_bytes(G.y ^ c[2*i+1])
    return m

flag = pad(os.environ.get("FLAG", "fakeflag{sumomomomomomomomonouchi_sumomo_mo_momo_mo_momo_no_uchi}").encode(), 32)
C = gen()
c = encrypt(flag, C.G)
assert decrypt(c, C.G) == flag

print("n = {}".format(C.p))
print("a = {}".format(C.a))
print("b = {}".format(C.b))
print("c = {}".format(c))

G.x and G.y is 128 bytes whereas blocks[...] is 16 bytes. Moreover, MSB blocks[0] is given by flag format. Therefore Coppersmith's method seems work.

 

solver.sage

from Crypto.Util.number import bytes_to_long, long_to_bytes, getStrongPrime

load('coppersmith.sage')

n = 144119247523820514307319742558945817289524321678464785828165262389987364282241677120346992289602773032781170623185859522408681068717004227361637296377314973988883717763449514502353544535632434189976809320943402560377421207936239458384129077990667822889168041784489265932700188699685494064706711885776064499497
a = 83982245487363010227377287615815704138676734572052340268107937333404040064487258387610318909300475704005267406361509228314981566916144028418544919408625857597243933586742790305821574823017061268314657578742703998273111267249007415214833152992932175602495617018238154444547422725699672732735594492967242602718
b = 102854241650706614574910858961148621902783569513613650939938174283440416794379436560775021794677794290971284767314108620894847399989166711219489947662922391647064573171363714323032220660223765035347554282052095512011142748460282601639626032525448005114625186640435086840602281790716023653081557628791656792754
c = [105112301098281496097034027523577403453326764144228787624401074405541577932642530851395484380691290162552636478481380927941044566041120344238783491322553291628678134801814105484196704974017218455216419335693731277825573231392222665423245586612395848380318111988284920983149197374154699808776545479724047776709, 119931822446994265076022490333904239240145849067899601686086810952135061724293475540637951596476598377673280140779509869539582077226280886787012312965074972316057414014195571814522208145587153069696640304889800585974357119323578638404957302760851214606619517664508954712497284900223656294050022339709410514520, 77449803463514047535477961978015960018035778347793833401263588747978475501148536780819549296447786417024775899457091074251167349568353877838782428368954481576827862607179873977973077737374411980559467128298050283927229354740670622117284854556777626729609958202274963553796799701913426256413699327094959918436, 19881898638980767541769585302774976337079209934548061143259050559139791898245439933411471322660256972236103364955342341822881304403603105610433373205174678091884754857958259183427619764249723943787639988589593508171175819610469625589807019978156747244656206732357606116993349990555417285468500357366492529137]


R = Integers(n)
P.<x, y> = PolynomialRing(R)
bounds = (1 << 64, 1 << 128)

xbar = x + (c[0] ^^ bytes_to_long(b'zer0pts{' + b'\x00'*8))
ybar = y + c[1]
f = (xbar^3 + a*xbar + b - ybar^2)

print(small_roots(f,bounds))

x_sol, y_sol = small_roots(f,bounds)[0]

#print(f(x0,y0))

x0 = x_sol + (c[0] ^^ bytes_to_long(b'zer0pts{' + b'\x00'*8))
y0 = y_sol + c[1]

m0 = int(x0) ^^ c[0]
m1 = int(y0) ^^ c[1]


def add(x,y):
  lam = (3*x*x+a) * pow(2*y,-1,n) % n
  nx = (lam^2 - 2*x) % n 
  ny = (lam * (x - nx) - y) % n
  return int(nx),int(ny)

x1,y1 = add(x0,y0)

m2 = int(x1) ^^ c[2]
m3 = int(y1) ^^ c[3]

print(long_to_bytes(m0)+long_to_bytes(m1)+long_to_bytes(m2)+long_to_bytes(m3))