babyecc

from Crypto.Util.number import *
from secret import flag

m = Integer(int.from_bytes(flag, 'big'))

for _ in range(7):
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    while 1:
        try:
            a = randint(0,n)
            b = randint(0,n)
            Ep = EllipticCurve(GF(p), [a,b])
            Gp = Ep.lift_x(m) * 2
            Eq = EllipticCurve(GF(q), [a,b])
            Gq = Eq.lift_x(m) * 2
            y = crt([int(Gp[1]),int(Gq[1])],[p,q])
            break
        except Exception as err:
            pass
    print(n, a, b, y)

172294871449219734798107561390050953188521804048922822821089133469311203282838373380377875439026704763161795744755842077098168865000919622849058673563093367982208461406754463061486548381031910500664522644112851433538900220678158500614358889303283424512500613989230182706150280378108198120547975067586971516137 96364198848848705158285537079110423277195642567952259110364340716064235491391751428297894031158531380770390132279773351908864500464136898214435682124920058680787844361038830281655403525413688733800204992965035715298006768830075744486662160034641936095862260725417156381782604284050422013822430528431227361197 159671991296677830056301471254363341009296510275785264872785778012113694456980363802313449256308519721141732376201460773400245993593482589976204166133901861729668851862460623196007194950257183079347864250025089670843915918257755173390253034175544519724905752818035812997127673241875836037243219829705927834235 12488950718303582218034044014469231718831962762275496002247643231013156969740771432142283441219754679322796472657777272189002660471344265360278317729760143808888761286079001687689905847842340334026140684913862478238950679283842053262939984135114755914484999538131508882930756717834516619580846526035684240079
68223999778327454147340278776103578457271553299042143933393545815264609973076698756926443268448068478170652356574414692081569784751387548589991131379073395697581788909441130777261041802381911726085217610218552072019955091687392945670505312431379412346500975722411035854097380678429943612541679085918327184211 17770738203348676394013528065573927253738684355484382993047842078725009503696773096846474265836623641852326745278003624730438619552362071702422399552544609521188676816688215350418290389310564969049643786010837155281593524360805215661135722530433990410365868360692605842180028752038342347560333735922237369889 51098779961961751158122915158869440252746637314825788279336277128573162559246638101764647720433607480890890353266404408862366250798238531789338353122957455620883022785518154730850781795813200407904530871476660815008994170944440212300679621717029986782069464962522083711578039350861054405841275173019925642093 66166716533207612504484627791108393201158937155973610986551130733271280578971089095120371889664007733286220189256643852916722857958108530989447774212301117302384387307543583321894175828438280849870887046734108846642477438172082973113653660108354098554353657568190553303062608249271483295596847725316287446947
69746411945288680494756625186262685100915769718266292828317232438356233082561457717802913380129463210508761458218383450347346543878887508111863823958801568318184343480949172473544777648327814945820830887234292193752526478863127665281603760310028685488010810374501002997654985226277837410385612336235789850487 35863433752003593718423506765770617029528142232119703360783695175632253222988642577448933602236360173888236658825392990787632391883856639629797550839027484460834276938254229716767734096212580735483050576113358898294845949901713373921320977266743302353193505619551975822052525104591593619094885194563759053232 61506888586914853748952584136999168853842713393989804770066310267385965404827751126077340386083884094392293257188958096424196079983180753698925334131753282172406136172626322186930421581433234090454842658630759776836012464473239198489670974246600345527623012180678219362862337775047849600595500703273175382703 23074173610330067975119318094549104916729459916683840171011959880097244030586124074672098644510552431454003148712810460842866906744010629559390690271268680358736511730336715376566599109974114862237643003353529058235474898207867615210853332379567542323247567216796697852808056755511484166810776261406177054777
141780415980139617437215295846801567101402173619252056827987183835073254193657239443065408850513736462591151306400635298582358011825422183971334048391966413113755453698068836508230018713283240471925059428429812726435729369274579669831159812818547912726106821393226089324568082296082476059592963374588189677903 138746424736113892630456472492513519297466193136237748713651792342224061188757613931171106142936354280921317637536324608330692729231708881940151586955111567707002290198592160272885704125491274615556183787626484145861344784010051348839767532854926101536139055358860932766313079790639566311374298333660022416019 51726115599556454603920201657250521837735902629404616832316825062102322966835183071269936236690928753491837133603376577256803231041384630057026503126306733001505942744679790303330123718230247169888465167921020819210505089269412155033260560735554086852090518639465729269946494965164436190741639956526409236643 109654409762022740069514851260972908347716034747536569205325610944369939818174396230317316392277341065510361034050535743153611162427943916414124861678979771914963184421776448698855312979564147449272690263825911213298037101520123605413049352651130798112394668303713018564867048267647962314886530354112656660927
134695529317631291539146989750080778456288116909537330643076226015019499585100645219201149819193483942761047608937632376000045678037096949063251694636264176978864350498001325274216745015187611426633155307352514688833306265311483797036137536737138146820693626589997367590775993967122039778179174477656098285151 5739321199968321627369946084893217618156071099515645889496757563432120794798492968096997315087609783917559636235489259519655394193193715753364023338741839200775528051686566670968651457520145892918236829346679247967821973265175306801170339421046331421835781903320059400232340368113764816537593043564619129091 19673160600783884558420797494268753813890359647736289572838063131711269874000492472573124412257756881986515876284947639879236228461164246881762817017531477201318279812271247605969526804283198993102225186731231831294213792057134691470071907311239898997202853181993775441584378767147396666275272938837258357423 16897173108120076789922861933836017988034034913979337434078332952051799507194042012051980050429727113676699771772883294665409080790164523153924333774353032403848045609407735317482100956730663470698029136912240237112767052198706217408124644467054727063902614284435035076029952831418531957452256906889271788660
108631997335203066432695467871764765359535346338288176017618709868611883736328359105943651466896885704753893021031355220198313022607240746637026558990572053372001779938093596718948899761553876823305187704800253652009189892280549587130446638129290899670752310731109594745013563422110453795138476510927065537819 53186625650395498513439276601148324935331371411190607911833993964075202667438243234505710009859940105805328184291501428682891944699728069011511208448749132382024172290085402121472873185791975075398049469908097240414598661986593060452061227701643807521128142747260925759613091495839896971643248717676885197644 52709509084184104167650277788945043330126097533959255658173397630643774367938336071212214281041856314502929120225540280940224731284318314188334401609349175298441766962844025460361899368481713758076026229654035313132750449381123295594073954550981806651354410007449428669257683889916088487170632832744327614463 100260604505216418319923489428146996468156773172005794829064325549637959539041791314163531463726947409321908377241081956519122122262033227578640846072409813184989637914837945813897560451295053865278594114754492413312832734981399784589146893658856979887630033309457853967429746353718137461785133619446282493126
107338361645955025621587108367500347348984102219339572552748381028739611029946302714920823684765311935547487453509535204574142858361737866739285841603885839441733030101476343149903190982542554096941815202891147725076023628145124709929620451309674856615713933442851718371615889591966077523086598769484929332367 100872379615239890056528793994805290254429184626178615179949021889055871474237228059318594996850343091819482928969268211528584474928620075395005093777657472616646086984808630643337673511907312828907027299569420774094158785966357193601409625830742669863851550399504009908003166662860318527135193218238780676800 52637469044026090728662077516653409825725186092147185410215323273449329656983845536711234923756687817513771235055035977388966611329613167758082577958758423429648769821507972676781188078791048118663252233256924489724994317727922287107822238963194994782575166160292521918653409858431855957865223409101119244152 57971958593516466763891620734062821771076712450708456876484562483981622035231519724366540336500884101001407519929342324257929081898526022577405465205118192907601214300359691638071300661277784420068767639904239138656962018735555155063349452232501292852176876546222413194770858197241287367089881969293760207489

Challenge Overview

In this challenge we are given seven tuples $(n_i, a_i, b_i, y_i)$ where:

$n_i = p_i q_i$ for random 512-bit primes $p_i$ and $q_i$
an elliptic curve is defined with the parameters $a_i, b_i$ and over $\mathbb{Z}/n_i\mathbb{Z}$ . i.e. $E_i = E_{a_i, b_i}(\mathbb{Z}/n_i\mathbb{Z})$
$y_i$ is the $y$ -coordinate of the elliptic curve point given by doubling the point whose $x$ -coordinate is the flag. i.e. $(x_i, y_i) = 2 (m_x, m_{y,i})$ , where $m_x$ is the flag

Solution

The main idea to solving the challenge is that we can obtain expressions involving only $m_x$ modulo each of the $n_i$ . If we have this, we can combine them in a Håstad's broadcast attack style way to obtain one expression modulo the product of the $n_i$ . Once we have this, the unknown will be small relative to the modulus, and so we can hope to recover it by Coppersmith's method.

We have the following equations, the first is from the Weierstrass equation defining each elliptic curve, and the others are from the point doubling formula. For ease of reading, we will drop the subscripts but keep in mind that this applies to all seven instances. We also keep in mind that all equations are in $\mathbb{Z}/n\mathbb{Z}$ .

\begin{aligned} m_y^2 &= m_x^3 + am_x + b \pmod{n} \\ \lambda &= \frac{3m_x^2 + a}{2m_y} \\ x &= \lambda^2 - 2m_x \\ y &= \lambda (m_x - x) - m_y \end{aligned}

Our goal is to get a single expression involving only $m_x$ and the known values $a, b, y$ . To do this, we start with our expression for $y$ and replace things until the only unknown is $m_x$ .

\begin{aligned} y &= \lambda (m_x - x) - m_y \\ &= \frac{(3m_x^2 + a)(m_x - x)}{2 m_y} - m_y \\ \implies 2 y m_y &= (3m_x^2 + a)(m_x - x) - 2m_y^2 \\ &= (3m_x^2 + a)(3m_x - \lambda^2) - 2m_y^2 \\ &= (3m_x^2 + a)\left (3m_x - \frac{(3m_x^2+a)^2}{4m_y^2}\right ) - 2m_y^2 \\ \implies 8 y m_y^3 &= (3m_x^2 + a)(12 m_x m_y^2 - (3m_x^2 + a)^2) - 8m_y^4 \\ &= 12 m_x m_y^2 (3m_x^2 + a) - (3m_x^2+a)^3 - 8m_y^4 \\ \implies 64 y^2 m_y^6 &= (12 m_x m_y^2 (3m_x^2 + a) - (3m_x^2+a)^3 - 8m_y^4)^2 \\ \implies 64 y^2 m_y^6 &- (12 m_x m_y^2 (3m_x^2 + a) - (3m_x^2+a)^3 - 8m_y^4)^2 = 0 \end{aligned}

Noting that $m_y^2 = m_x^3 + am_x + b$ , this expression contains only $m_x$ as the unknown. We can write the left hand side as $g_i(x)$ which will be a degree 12 polynomial satisfying $g_i(m_x) = 0 \pmod{n_i}$ .

Now that we have seven univariate polynomials with a root at $m_x$ modulo each $n_i$ , we can combine them to get one polynomial $g$ wiht a root at $m_x$ modulo the product of the $n_i$ . To do this, we use the Chinese Remainder Theorem to find values $T_i$ that satisfy

\begin{aligned} T_i &= 1 \pmod{n_i} \\ T_i &= 0 \pmod{n_j} \end{aligned}

for all $i \neq j$ . Then, we have $g(x) = \sum_i T_i g_i(x)$ and $g(m_x) = 0 \pmod{\prod_i{n_i}}$ .

All that's left is to run Coppersmith's method on the polynomial to find small roots. We can also use the fact that we know some of the flag from the flag format to loosen the bounds a bit.

d = open('./output.txt', 'r').read().splitlines()
N, A, B, Y = [], [], [], []
for l in d:
    n, a, b, y = map(int, l.split())
    N.append(n)
    A.append(a)
    B.append(b)
    Y.append(y)

T_i = []
for i in range(len(N)):
    Z = [0] * len(N)
    Z[i] = 1
    T_i.append(crt(Z, N))

flaglen = 37
P.<m> = PolynomialRing(Zmod(prod(N)), implementation='NTL')
g_i = []
for n, a, b, y, t_i in zip(N, A, B, Y, T_i):
    m_x = int.from_bytes('n1ctf{'.encode(), 'big') * 2^(8*flaglen) + m
    m_y2 = m_x^3 + a*m_x + b
    f = 64 * y^2 * m_y2^3 - ((12 * m_x * m_y2) * (3 * m_x^2 + a) - (3 * m_x^2 + a)^3 - 8*m_y2^2)^2
    g_i.append(t_i * f)
g = sum(g_i)
g = g.monic()

roots = g.small_roots(X=2^(8*flaglen), beta=0.5)
m = roots[0]
print('n1ctf{' + long_to_bytes(int(m)).decode())
# n1ctf{7140f171-5fb5-484d-92f4-9f7ba02c33d0}