bi0sCTF 2024 Crypto Writeups

Right after the Lantern Festival, we (Never Stop Exploiting abbr. NeSE) participated in bi0sCTF. I spent a whole day on the crypto challenges, most of which are well-designed and impressive. This writeup includes all 6 crypto challenges in this CTF.

 

lalala, 80 solves

Source Code

from random import randint
from re import search

flag = "bi0sctf{%s}" % f"{randint(2**39, 2**40):x}"

p = random_prime(2**1024)
unknowns = [randint(0, 2**32) for _ in range(10)]
unknowns = [f + i - (i%1000)  for i, f in zip(unknowns, search("{(.*)}", flag).group(1).encode())]

output = []
for _ in range(100):
    aa = [randint(0, 2**1024) for _ in range(1000)]
    bb = [randint(0, 9) for _ in range(1000)]
    cc = [randint(0, 9) for _ in range(1000)]
    output.append(aa)
    output.append(bb)
    output.append(cc)
    output.append(sum([a + unknowns[b]^2 * unknowns[c]^3 for a, b, c in zip(aa, bb, cc)]) % p)

print(f"{p = }")
print(f"{output = }")

 

Solution

Just a few equations. We are given 100 equations and there are 10 unknown variables denoted as $x_0, \cdots, x_{10}$. In every equation, we have three parameter lists : $A = [a_0, \cdots,a_{1000}], a_i \in [0,2^{1024}], B = [b_0, \cdots,b_{1000}], b_i \in [0,9]$, and $C = [c_0, \cdots,c_{1000}], c_i \in [0,9]$ which meet:

$$y = \sum a_i + \sum_i x_{b_i}^2 x_{c_i}^3 \mod p$$

The unknown monomials are all in the form of $x_i^2x_j^3$ and there are total 100 possible monomials which can be perfectly linearized with 100 equations. That’s it! Linearization and gaussian elimination.

 

Exp

Sage 9.2

from out import p, output

Zp = GF(p)
N = len(output)

M = []
B = []
for i in range(0, N, 4):
    coeff = [0] * 100
    aa,bb,cc,s = output[i:i+4]
    const = 0
    for a,b,c in zip(aa,bb,cc):
        const += a
        const %= p
        coeff[b*10 + c] += 1
    M.append(coeff)
    B.append((s - const) % p)

Mat = matrix(Zp, M)
B_vec = vector(Zp, B)
X = Mat^-1 *B_vec

xs = []
for i in range(10):
    xi= (ZZ(X[i*10 + i]).nth_root(5)) % 1000
    xs.append(xi)
print(bytes(xs))

 

rr

Source Code

from Crypto.Util.number import *
from FLAG import flag
from random import randint

flag = bytes_to_long(flag)
n = 472993274721871037103726599805149366727531552333249750035977291933239067588481589544777397613192273114354221827196579379954069925604091911249655707080927769808587176515295614018992848517984372306879552247519117116110554431341268358177159108949791969262793325836353834899335531293329721598226413212541536002401507477776699642647348576111445702197483449777741566350285229621935507081895389023444249054515395783080003733803406382744631528246608154546123270319561514117323480441428953306734274538511770278887429407127143049023747710881993279361892937905382946820141513009017756811296722630617325141162244806884220212939955235410280899112731530527048274396186038160728562551536558223235783656985493518204710943916486379681906506757757594165379493317173050550893487151879681122510523721157284728808336110950008840684602353984682117748018347433177541603140491131603068512706893984834735290809952944273565203183330739252949245209529232254867201402656024997949207918675051941911990640248052951780195402390132237903538546705181463959793972284823588987652138458328270662652334799233015314673544813649692428544375538627858921763941533600553536579901589575693816746953261108022490849251974419402753031545629158199093099096735356165044275617408697
rr = 11898141078345200236264081467585899457224809417108457314508072413792599039332439547789237898270544336909458761754683941320649771736625000667170176071314483
ks = [randint(0, rr**(i+1)) for i in range(20)]
c1 = pow(sum(k*flag**i for i, k in enumerate(ks)), (1<<7)-1, n)
c2 = pow(flag, (1<<16)+1, n)
ks = [pow(69, k, rr**(i+2)) for i, k in enumerate(ks)]
print(f"{ks = }")
print(f"{c1 = }")
print(f"{c2 = }")

 

Solution

This is an awesome challenge. I love the way to solve discrete logarithm with modulus that seems strongly safe. This challenge gives two ciphertext of flag :

$$\left\{\begin{array}{lr} c_1 = (\sum_{i=1}^{20} k_i flag^i)^{127} \mod n \\ c_2 = flag^{65537} \mod \end{array}\right.$$

If all coefficients $k_1,\cdots,k_{20}$ are known, we can easily construct two polynomials $f(x) = (\sum_{i=1}^{20} k_i x^i)^{127} - c_1$ and $g(x) = x^{65537} - c_2$ in $\mathbb{Z}_n$. Computing the polynomial $\mathcal{GCD}$ of $f(x)$ and $g(x)$ yields the solution of flag.

 

Discrete Logarithm Over $\mathbb{Z}_{p^r}$

Things are far from that simple. Denote $rr$ as $p$ for simplicity. The output $k$ list is obfuscated by power in $\mathbb{Z}_{p^i}$ and $p$ is a strong prime :

$$K_i = 64 ^ {k_i} \mod p^{i+1}, k_i < p^{i}, i \in [1..20]$$

Let’s focus on the first case $i=1$, which I encountered in some previous competitions.

$$K_1 = 64^{k_1} \mod p^2, k_1 < p$$

We require a bit of finesse to transform the above equation, achieved by raising both sides of the equation to the power of q simultaneously :

$$K_1^q = (64^q)^{k_1} \mod p^2$$

By Fermat’s little theorem, the equation can be rewritten as follows:

$$\underbrace{(c_1 p + 1)}_{K_1^q \mod p^2} = {\underbrace{(d_1 p + 1)}_{64^q \mod p^2}}^{k_1} \mod p^2$$

Expand the right side :

$$c_1 p + 1 = \binom{k_1}{0} 1^n (d_1p)^0 + \binom{k_1}{1}1^{n-1}(d_1p)^1 \underbrace{ + \cdots }_{0 \mod p^2} \mod p^2$$

That is:

$$c_1p + 1 = 1 + d_1k_1p \mod p^2 \\ \implies c_1 = d_1k_1 \mod p$$

where $c_1, d_1$ is known and $k_1 < p$ can be fully recovered.

Talk is cheap, let’s show the code:

from data import ks, rr, n, c1, c2
p = rr
q = rr - 1
K1 = ks[0]
# K1  = 69^x \mod p^2
C = ZZ(pow(K1, q, p^2))
base = ZZ(pow(69, q, p^2))
# base = k * p + 1
# C = pow(base, k1, p^2) = (k * p + 1)^x mod p^2
kx = (C - 1)//p
k = (base - 1)//p
x = ZZ(kx * pow(k, -1, p) % p)
print(f"{x = }")
print(f"check {pow(69, x, p^2) == K1}")

 

Now we focus on solving the discrete logarithm over $\mathbb{Z}_{p^r}$ in the general form. Given $y,g,r$ and a safe prime $p$, solve for $x$ such that :

$$y = g ^ {x} \mod p^{r+1}, x < p^{r}$$

Let $x = x_{r-1} p^{r-1} + \cdots + x_1p + x_0$ , $q = p-1$ and $d = g^q, c = y^q$, we can first compute $x_0$ by downgrading the equation to mod $p^2$ or doing $p$-digit expansion similarly

$$y^q = (g^q) ^ {x} \mod p^{r+1}, x < p^{r} \\ \iff \underbrace{(c_r p^r + \cdots + c_1 p + 1)}_{c = y^q \mod p^{r+1}} = {\underbrace{(d_r p^r + \cdots + d_1 p + 1)}_{d = g^q \mod p^{r+1}}}^{x_{r-1} p^{r-1} + \cdots + x_1p + x_0} \mod p^{r+1} \\ \implies c_1 = d_1x_0 \mod p$$

After $x_0$ is recovered, the equation becomes :

$$y^q = (g^q)^x \mod p^{r+1} \\ \iff y^q = (g^q)^{x_{r-1} p^{r-1} + \cdots + x_1p + x_0} \mod p^{r+1} \\ \iff (\underbrace{y g^{-x_0}}_{y^\prime})^q =(\underbrace{g^{p}}_{g^\prime})^{q(x_{r-1} p^{r-2} + \cdots +x_2 p + x_1)} \mod p^{r+1}$$

We have circled back to the case of $r = 2$, this time we can solve for $x_1$. We can repeat until $g^{p^rq} =1 \mod p^{r+1}$ which means the computable discrete logarithm is up to $p^r$ for modulo $p^{r+1}$. That’s why we restrict $x$ to be less than $p^r$.

 

Remarks

When $g^\prime = g^p \mod q$ , $(g^\prime)^q = g^{qp} = 1 \mod p^2$. Therefore, we actually downgrade the equation to mod $p^3$ and solve for $x_1$ in the same way as the trivial case $r=2$. The sage codes show the details:

def binomial_dlog_sub(y,g,p,q,r=2):
    C = ZZ(pow(y, q, p^r))
    B = ZZ(pow(g, q, p^r))
    kx = (C - 1)//p^(r-1)
    k =  (B - 1)//p^(r-1)
    x = ZZ(kx * pow(k, -1, p) % p)
    return x

def binomial_dlog(y,g,p,q,r):
    # solve y = g^x \mod p^r where q=phi(p) such that g^q = 1 \mod p
    assert r >= 2
    y = ZZ(y)
    g = ZZ(g)
    xs = []
    for i in range(r-1):
        xi = binomial_dlog_sub(y, g, p, q, i + 2)
        xs.append(xi)
        y = ZZ(y * pow(g,-xi,p^r) % p^r)
        g = ZZ(pow(g,p,p^r))
    return ZZ(xs, p)

binomial_dlog function works for composite modulo if we pass in parameter $q = \varphi(p)$! You can see this function working in challenge Katyusha’s Campervan with composite modulo.

 

I find some other solutions from the discussion in discord:

1. Discrete logarithm modulo powers of a small prime.
2. Using $p$-adic Ring in sage to compute discrete logarithm ：Zpr(y).log() / Zpr(g).log().

 

Polynomial $\mathcal{GCD}$

Now we have polynomials in $\mathbb{Z}_n$

$$f(x) = (\sum_{i=1}^{20} k_i x^i)^{127} - c_1 \\ g(x) = x^{65537} - c_2$$

If you don’t care about efficiency, use the following simple Euclidean division $\mathcal{GCD}$ :

def gcd(g1, g2):
    while g2:
        g1, g2 = g2, g1 % g2
    return g1.monic()

I recommend using the $\mathcal{HGCD}$ method for polynomial. You can find an implementation in jvdsn’s crypto-attacks. Then we derive the common root of $f,g$ which is the flag.

 

Exp

from Crypto.Util.number import long_to_bytes

def binomial_dlog_sub(y,g,p,q,r=2):
    C = ZZ(pow(y, q, p^r))
    B = ZZ(pow(g, q, p^r))
    kx = (C - 1)//p^(r-1)
    k =  (B - 1)//p^(r-1)
    x = ZZ(kx * pow(k, -1, p) % p)
    return x

def binomial_dlog(y,g,p,q,r):
    assert r >= 2
    y = ZZ(y)
    g = ZZ(g)
    xs = []
    for i in range(r-1):
        xi = binomial_dlog_sub(y, g, p, q, i + 2)
        xs.append(xi)
        y = ZZ(y * pow(g,-xi,p^r) % p^r)
        g = ZZ(pow(g,p,p^r))
    return ZZ(xs, p)
    
def pgcd(g1, g2):
    while g2:
        g1, g2 = g2, g1 % g2
    return g1.monic()


n = 472993274721871037103726599805149366727531552333249750035977291933239067588481589544777397613192273114354221827196579379954069925604091911249655707080927769808587176515295614018992848517984372306879552247519117116110554431341268358177159108949791969262793325836353834899335531293329721598226413212541536002401507477776699642647348576111445702197483449777741566350285229621935507081895389023444249054515395783080003733803406382744631528246608154546123270319561514117323480441428953306734274538511770278887429407127143049023747710881993279361892937905382946820141513009017756811296722630617325141162244806884220212939955235410280899112731530527048274396186038160728562551536558223235783656985493518204710943916486379681906506757757594165379493317173050550893487151879681122510523721157284728808336110950008840684602353984682117748018347433177541603140491131603068512706893984834735290809952944273565203183330739252949245209529232254867201402656024997949207918675051941911990640248052951780195402390132237903538546705181463959793972284823588987652138458328270662652334799233015314673544813649692428544375538627858921763941533600553536579901589575693816746953261108022490849251974419402753031545629158199093099096735356165044275617408697
rr = 11898141078345200236264081467585899457224809417108457314508072413792599039332439547789237898270544336909458761754683941320649771736625000667170176071314483
ks = [70919577137553948225026829359952892017992369857129233935883277162711194324842921363974903163099339145663781137475483907364966326977551417231001550576764817820516163821184399579767358412593344390685967830624912399576493839556742404454603286678744840244326074550605619842953886917531674151849027712320806953974, 1586108873597391376836939152773916771199419430148746028994598635314207622876880309743918818337868362567381559351794167759189888511638843573658493573224872606875791806197785716699244941157408616339109560220419366940367073774670236004358536849619947730285579590276109244127957488346479731255052507957500475196663482736129905127061478659059965496695871052300679384505335339869571680122338240010854218887449488927419432924645685776896752663604190618459629585126636931, 16105249320854231353712056433168127388219050743196438394808578852514784890899470591687262701989809826051326776069638569543425789510695557187529156649045280567864308704983669242573659732021875485179423299316798511944581159478233194022428387179648163476227379501389407302369695382769632714814620098533469630829834526499732092025373129734207514222947986298511582213836146172336213933260310325360516978788241905234357736251842247806697950831919497545528932364337617791958596862379397335748596700536707937791600121022373841665060235247211427705387645938338412222076454395612365294533781738834482413165404129693091995737649, 68803785893095646291018085677204540454193293340202105548420563011725184276073469353439249315485845184249517440056499901708909757797682359771424715819571405205467882996453753399283594776434278871941932665157687945192811717684784271844454976066996087189664144128066230306970661296197739781242332248956094050494028108809702291817039062154908406188450313036861699383490036491717014319004697564507408149031832749463879053875905354398383980006790138563315800091434577297772230619313352414566500059714217289735686868117607117039064236691044052221098317597162101064805429905399575292444756519691758243289246266244254147267141395141498300191602730707656016596869247841502099400019261408016592445392739970382771631823810427698603156127755969621288063343264296795746377165374854146, 1086435820407082053696092455065855714644658146027569809978334216710020684638587028534314819312030439215953111354369099674373838918522792138476536153417064461459768484068178390824870529936133993668318781819652044212529732355921356304043998570573043842050148140863661377427269853520673433965456019087255580609833639804207010624795139217086363760135213125489091713906706097757660954665526764639180932120269491608840968758118167810492075744889422474852533899689942464403533891485166579890256441467378615277987544299103398986661269892041901056431601410883773820770109827286743447083409026860245509922459158108099893815351940303345927471488462328231358212689263799624029638146086814497672902922735732417842375825310866869265879971574011697623699126513575435491792349834690364537702633394602198365534362611967246255797092643731649541240870734686024696949651404201176829256656221708429594464515559310545508949564603991764490641142674, 28609232492396312935743850989010940611652842421660555622855351990396978406387028457650628985123620811235468274935572669724411891023143315183233627728957714354401533940681834966456776604187386524765527798089395166018941189443059739526606511963412857174702113533114349938228403169325242565014845032097151083542029960815674715700248304544505236018005378194025180906942570419435370695576161499949634230635551746926165557110860374112414090383920605205588740856500005618186246972231456570678464365331273467051595924449040329574571753265897464408871097615548050149699746704617652926188994105749189829550360217132831318050961371597154023088901604582548584294898932647764086215622590075859650073260435039277967092549765370236795949787991883324936339353623472562309089417091161146879593323222830096509580747355458046543563043334948823957347505908285850567608000385705235403664969720542312418189835060446004561901705681706312116426563462515273997775896879163283721268707758691555893430806802298978389864598611264948918292959498189343068790892695775215347420419467119438879898701927301606869, 191417841809872735054146655184512650098083726789767559817591892788038174397378953834495817796996284957501894288441008148397612383074280349701443335577799717053258077299534006085380559302673747925386918245066681576834137041095749332038353330585645180656054656489472256945293288666200340789172882405120456043990434640294964416374099721306113199958866994245919506128904422665371689236379907440548962545523404682095001292254826882461330681965063224441705966253886025512613127648615132746851029825614853302623452982966903869314675785895302662910074161998198916621112531107627623481472565967029401207761966265090626536144517030656081267415543811779720415102359344485132236715271755091025638448558016707084982114125369940233518851284778221830182802108489363182088230022786032593523363359661580034221193972144769858394597696874554891254394750771889443933840536157432802067771709659067883080122884610000331228087060807575707327755176739090571153604658341308954049003059383580774064963055701213142129175885433208390912829750669280383778028791133960269780159216051822061007566218659564809341109749775004565845588118274276291465933207543789351800827414670830089761319699102472010282122214147360722014317557663943262076671120974041614409458368389, 4304789707563337259810803922746754256091876355134356996759997600505561723288875563684547307156817226191351473706665959205224732847427878997834273793118458043999140891510796058401208465634686288162086185925182871752382730131945706500743680182230785260233894501009619281020694567496679065345097866719736117150568849818731880133710998784990616985923511874002221589529200129760976665462837856498784468525737217347202152169913627727174496288099010585937568663838423263255265609351864559392553496267551371972331076671847964714954122852083783123869220432296438358938094139688844778535776899028033325308996274341523384254986945959374461694249185740716922199777809197366235218226603444950643569187970155872972278468383726615580849671193094610721184099890573045285051170553508351269735472612322682796276557561903205969748402096188933652127089726737539989231549745480900375142076214299110324566402276851387690665164737187018201021673686918665665211416526254305256833561136150564149429321591201969362186709785526504319165743707276569038640516180340705643372712929171952510943871648132905304723947439548513016747136997255772779385556796190089311656001630992978578183210450813195209985914937741021520674341081432339360749895096368199987931163754876132489581396908106171771451664884357778296043065790545424953016182752302328100057011439139522567053735361749294823303989598990270462721441317382375041381, 17038958926285455544299337693983197384094856299956806606003289456852850879730590483285519606703579022386521143497011819316912064584729658026427110539315617230283868665576078459638619860092492584735387619990452249390194353185298454203653590076023324176951553561398691674916864932937894307360459739592355805043990587348221038110525573680488812750629648047235880656320512055286587954153157693091320506714520279640855258235109679442666214835982856678549358609166005962495812290769336495454119842682223241280912286031331748005669982365468092416744436510221600161902547601746120466492608779652532859895490033176865193407556189534659004897785751674274662362043008831937095174035856851303539154827665243232902174398468971673135836006392832146825262826456901504071160797970165670974117583856113885354061587985972571439359592540268330306544976666538899053837564023161771830858902956849163507715491211348474863914099173214009003604109994378358006374399305730783928103504930232504308427156078156569943633838533090687706000642284992907253640442821481380122374642477032169456966050888573659832537988575741591634739783906034948740683218935531542463117672237215670649690607404448935357892459915001327853837712861188831005110280220425257562531745785770688981266473523096390615139846343581936452716472120904428058786392446268146114767133550377556565428131734541353353145416738880516830139487858141854829879843122149755357370351238085049298862052731781606096395504815594413927240193138127132074836030642327831935137271682152549451006848723521340872121862045776, 223655710855739961286564415335195053402868745113261044098914825701135517676482696285031952948322574010215729351255910239375069379011868816734856611243723789275687858192302717042607918967245485050335279669885499835120486426276800029381220109037348715562138074561222821215334894122309703234824912840582194437870627976113153805766232638879001049571542945472836516863093691217863326410639680691871115787994712058281427443032070845080584112395857538058509780874700406111282162893372947211852683030793858205019084537987171038157739446975105255436416354848934359838155849941622358927313009530127835709577977990783506420443516394872932862627175716783791178417637305017123952549926808513925112135416915166213646845999736059022795930373076178279974448185960306023399066064655790100700493276109827644279572324655503823568012633856937701703304517255968668070933019224786822542200986300062324555457481628689023900329385872398607032536473924856644217750510990695844405080373191465174603057673174257302367274439245382649135715625822557424813823270412418013847776008275290127798569382290480916032000383681697980032123818714141884145229638065478540803408716075714926609812266232391357511580902228735010235539319733026858345316525071759867087651574043122216542726419754912599373929325061605474552803890639810124631115484489844536692635914410454978717064296802432217362619933991007221715074664068955849556513542815434424116989279100515724149334396921447061712158801487110379635187028759923934101802606319974466642788548143476623840862770682496620560683059631934719099179301602462121382804810286362726514654228725805631084427386299980640573931447237360918768862089785798050777127901758334547331804664874298989403554, 4761920524246169367580622962844432633118639431106791955659013266665183165806370527968984704438479383060767550866626163698038576313753430985927264339931030779198258709067793421848488493352467532191054142189156726257736795761832238654930492660022087326432205422463180979785138776343693690231961205340091997662281803906280510987307931773230667536651561681682730065010353741268348716872020899852916437220004846470241086029945093197282361522102191260194715051804490722175078373495609117329886316593665235897404091710521017844936698226441642185402258732609600239733690533925977234929526243734732271453530227625681297919745332179322081524837771426383315384946725904236637402148906040967090397635075057736298162926304530368288985586503090371382877921296286476263401303849592598332993482874235583165126624181330207781197494747073601091954350418939829953035484845248028441317772197357590654555164459898730981291052678658466616660019768079194412033261840671745526709782117382859711384050354747132694977554847517376591793241808317232619645368532308216325902531501024396593146726757675968352151919263485297244012234805401889527641181487727566781192856306185677858146101703860271997143943704360334049157612719266307534163530930437000385445798495557931948320319666983372207941100508173689280720138899633674060671787688676285633833615706342927378123557223606440144947716797630721169745221620747475672518024123337556459170992019534454231653118410142027490983522505835516697916547761761739799434920644649736704392571118749179379660829581424836853963135398977503449559267562506238451963214176615264353329366366000933515469183285035952746929376438583477105821917163549780939510917921610797615709675334419197922792559769340461600380753259412741266898379777155953771924286198848612699915756853813937744606485190333748760018823079128298458670728890633670929092964800036508, 1619584858941878762430473940096747748546598197705929364740537206711933130681646188982037753366854879340780434214601172194419584750370632177161867948075626205894859712413890562303660235400469652198218927878889142310525338756869309205312078331240205425016102329092387381850633555673392860150079383271838460863619153830676559248116567887187080007740373497955917117349248643311589497577041950358597208354318659397406255348147462039835727252285684153964889478900747105534651658626377876812380143310564159604832556994504530154079693951353461197927147973279020968615938773697076098717784080040549481992707904636249491865352006570079480743975331336087496743584137537057335412336274316996440087265539425898422178493079947902687491009899561576100739834701935115771583924080459780777927911347240117105944291584941778929524743065290029329913226896351403128214690567316711385990579873530477025379394678009712448144079902343766250836164950607429791339482693128720430661856339237065623198768556662223512768963828714387605468601211288606282381373683312004085502621584585256948444657682349817354825463391501392892055311008990286703324236739653577477990533584739153470882865942084741435039249371892141494398173801464794732963041792822143149974501213779801081326359251645084138059423478326076432773827127226856232347318751971625643023460956071068357649917824082253559904169166964552519712271675684420340925739991739032933647215354727105959242264136801756025408559691027405038763418963124403179853283186674285056284011401198118009024715424230849534739495749837925050486294653606905988718257037097894726472115832768580205712874214733398346393198850774258301101414212375301627233700103775434428080874197335506537593604808557791223416458603533024505293916782618671325542073368562530607537656473334637016609107850383548051883806422057683714655944505050716402521970970820246436139131238048777694168709356341372623024638131529091871639253333438166896760944645183826187445116069079723496828911913922255807222213189810074129958467, 398962149370138126899253400332789080370314499389058875688940442880253156700518541426014088432015869729610041714204683608584557043873015412693896804482546747127803370165130525315310371567322414728265410436172301777596227244189500078231681097921347921087308990249151707918735065866598529104382943742808232741741774501085461712371265127735951621501027997208923546323674948718279769658394153342858146775049208059140629980407033794665176924062649835033413819865217024966668988263139867819562075178268403137828878852910392747253934576565813357124109581475690728225450121657956256547631307668443024063482202187519645349180442201041611153852272474965779285876213889496082553856721336694287952017595572514632086812218379153068581534153297696738828794694465508313285196262932422046539810193313676432047447806618691874639492505161881956320109421457673777437519134818275980724761899452570021876167424126123476028669705357418205809062604166988043321755230178890106499337235237294666764578272751937786679763151518798250179354422935256119737199613010800039602004572044056591471079373506287376423056321207149931793134260346230047099190415131645649213047398807333470752873850299386372482714416199942814729359346578084246815034404511533657838216011835090907664451211116640930866613725761656004295906240443425001675677280245476367304136533600002207247552670992554778694258567062428265079483164447094118664681277968777745970677401277497975129699471193495683849157294722388264418815329536556416868257922066860016058453125368152486052608470261392104928177247967452420388785625719853851881621799428786356735223829409138068053183421645526715293362469602797973696571423747282268981525733016854796916878158547620492991316298974215216944545684592918741417531554680108468618513670291465417692594214789364280405519425776026914809770934103487705233613584685532315875321708474658496199741692901480149474320209544162090985147140459681327238538108572801304939018117180785150776115195123177537884255032093231401479210419340889571921083867623925354343272287156136634029657291652514933452017500125621273606551468310360278221194678861924849810415112284806720071932158456012987754157919560777202, 146988229050104926875833670889214090147000397427124952099047346002064676569102806270979611979709883382611323297759051410018814356478814953773427172601670367245464809918621225703977123247028642030387994577573841023151100509971130333090022014075421988077599406092813259184844241349092828320457860972913821321277156169777266947027735911770559491072896209879010877910528915832300763177291909858861775642800741882625594560527103883846796749425069117090768026349563754089994499925155548547386253907884558868555235001346105929420467917716292538452063752228124970813279617790071964805621778124279053225052138617744933960023132144265727131471470712083793020672454220707587140211514995310965570340827290133296801887197811181088199459662962806479086975776088535421966666072328662444839795704155009307458567770278339913793490518843227860471205383062662302322266204968503196777681440229341501642807072403928142860485409908808291168994236309834662133277162594619132069614934387345657152618710767723498230738704721959791763227044769676226548394868493249184253404636247186186447694981914563366310725253800040259121255838845464164535827713899987104564730517152850052576680985767739081253865871460386628544938271922048246281810413352083257852909909200637115972176348634288103636951682688044263030570548807622750571086317462714383145922232403173568433081500310693912466541069299389187941978078959626729458470099214583444708820159063314988973480141132235566735854824894593363164587902725091467638556908268918562227256221536490305641917658889197027978365294686527535161053066288978625387768517645568084814946669703655200933278539572205848783303465929654567161031877386574869929481471112683489695872991882164146029917137237646947492739895097220707544482552689107279182494599828051799956992061004696446386429893779804423742345900293332629482737909297351097104659601098992819554114891558875169954822466396690798552125500772676055809408560821673791493603067659941062344177917354428975226981269696504793572006911470954842741447872157680626185832600671527896428797596584211945380478262118044976209460463921804534976667851567468346596623595447440326150495326594952822206012607813129562221269890885827666057067949192324585833018224109963060009466194002073537793678599030596237338561583467939080179738805793499738021663971818934270224239368, 117440347873699781524105976847523938374653066702240273413866720941736067077086254218321499014932405324456724541687105116855976439881987617775286672517788462515590199758441969680992503605979474447170821598371258219024113401053368079127473201933829238966833560877112446176962003827856812963409356573060473154623854898519954904447184224488577281766280895966903203970394047253038843577651249806970707930013312392911096291171924220426206758834162367578422373003359397795596052363607700162442176658129506232819379737727805279925334089729206323752367855675671171522486230626555176039971966947598114735955425256776117865027327388063548574073509434523726950486194258905861335924284678977174149295244097561234499771020033779142964026267524680857080395291212960096031423630724157721949645661310650925755360924972399154871013382076115705860588819556139373742348787687456433289205742099946415267387961770073246593786983568393396251786093589350090537508983515353193015087214476268102508232136887357961330417124630684374092670987818335928145818602399409281753365003629756460593013518578602381782645864741102800959811484196657887833737262451819158354126102631283207570636727670421789544175009236402371447101512909910289272458352201505755381605931108670352340596761379575670757088296401174186140237627135398944380566591932960930772726945887189785011064643039934645658664020366466110908406691580801292961955325190917960180099233018419897506333544828568436120928412518450859423819768750504986330941435470612846709030192681019355861076962155774800716996631610850241414650448907886163582386579347382023368290769125734135461308910833828033895005366553039629741492365436485104618980167771206560641958015409459262393369667187522247963340058889542530135812513196747361254371193691802541310919087094546249411649663632312586141897286806630111839300800391949517340673160492984636912165987971966245673494253720910584319186588082749166875255588864858244735712789513300852454737120184599156339200076463674860738305810034043944644629006869247278412577114102974503426923083133198020079274857483280454783392916192477651996043999896852212873740740998668309242791043336807732888542043439240572298835432672412127655765633232074899960240652649161826548504488632610422267756011971750757060457048600235365355029955209305180846096609285801513640325924705489887227428581721962872172763004305359141915587679888275575058845725193069212046987640672801330498644844833670106519402809606457313947369243544577546302, 838008938974021347744246081242683076991744563163587402466348647979976338120651315375512115744986141797135951627279475063184670178055419509135466927744367115217000419967808595622711984796737413882943523657484999017063369255310712696271654365714668607649575424604397779492522698239362890980253502484850497787973225603494430069879407158126245876267963626839041580452314081277273250400233569707982361776994153421218491564630978307001890782691536693710121807755407008932839036217666589108188633444519100789393410997858606699793676213549330024247648781392100526194108756506738620353755633246188129008993897345901803003977673352841569149240171672858700692287126448571524617425808833826801212869513737196821415883987171582549714227725788502196700169833100435157495797871391735277045916979912616821887622216294734015292891864275932567027004357023840585191187912657334317755964804979593595842545442852771858603028008051898487501645985139732362875134274802537362981148561482409711127183773823476709173718104839480660626020108045033561572036558791229305250521043639755601637739854083344490551189586237652190124412726602148297599839649867063601562758497796700678519692713609785153365361685558068280029785267354932395867903908656138504248722552244674740585586996190955405057047089369961214626900687310374146708635745848954539061997819982824208550453343802939368112206964442760192427768699886492972371130377106716287672124411979644846848944207878636301740882060688972515181290640290141435120458947307343774578680596447797626392814686379089791645107371936985391452207093702112436404131410947458892480675240977619873580656911571315119468542375586810141845982659446938821102815054166396124278103419701371244558603866565749965098030601002706714668342531967192873591592232039951052833875179822608571451409779272294682105893249308864405569628761219201634553921973172579855913911460058782699490073415904563068227343232087330199357278249161293363027917407100536049996131226528247243208638089791750051604050799133801895067901231443312235220713904904773426566905198282656065765680498660348339706929057318466492572734533526859216925066333255309998283699925314974297140489428702191405598608343295190935247006532856188547313148920094269745151666214863262603123942875779548666067912954500200266282543158004853597440262667111191751237413729931179304302544165221186866457683778755320858140932138167695813292105681624844079958739318296521523014114808525304051401394039918004670416528309214011405109600909605035675822174898618652311385091756045642622886529319926790275600334584180260614772348123566679766324335871734602230147505887973136663993328153244, 16283029513858872607939884149497747442975093740757447104813706303663336753370540194530157039891804770254848672161639373429582626303963122764411871748091298613393387716958701275094201312766441765520025175356717965901695385533146663321646013811794032114030511303468940514362971201402934540647303838370196606312493927208305554538890964831508550886103034707350598676796292187297068363719976601820297002244113258194333326017731413596904623522615301610863741698852476355829739485368043550851558723915881103525513348926593881971313036496002461276185841258911584405097524891162478144685858453197207358186344300958635713364039955217631754072814655695403244554688709400338721248320875790259268866087893838619558842780779653549440267906938969527819878910355987914327548005183228659350928009406643783351863335700069622779820109223575884387855977791568860423676433399864470127612676678703467951069131790814771447471776484065613100046593134643978814046292846177346367012805941149355468976886816627898062664918478114532188403791190846633487738915056223100207736021832886863526962212736510280812198722985216952871853968061233195872291315697459461688409525486245017632573716142018625361329614508378465339103765721313154350758824662810251023539370837907647186107452432779338750229289494393749069685249893591637086608416200837065330836209355432716182418591261210086317580951657516627988435426608922763490933073855213169907254212888543107933442532904002380023645056478552807323278979357742949504591497796493238616296009548201630918455210521137145476279104170305794451963251239626132335404517611933750364228704706818028986052963944615862163686030471635801925945661861273335335066939686972228225344763596833233151635691855233783390134868727590166698343182033981496592740255233506257710598304191255740957108633659057870487901316050558566336149124208133267010844968069693844056597982833758674051400009800859290401809898759069276060510666252996698061207916388972944729897149365808771538833747367896836835704512657508499412464771828418680977008609856137333263325789736783578812711781993681395654139965395203823017517611802681368242297378071724880184148620550310441638496571363097066123271347766572388964947778786264992310117824895551169053637949847358773533584582352263173836194908413212709056359475605667489058167330900714483106437667468801678879338176410837490251836013111806029684166469061382563835655065458231266077766323044094033291850286568766400490320720705805450852111066246594065502202802745470872888478883886091975712616332144440373903918854983145560291043896868233756780202188106460732717655796746591458073983988913804906161562441211613932945437946173013828272555369168431801971267602332910118856519414745559617324649740764310136024128667082370290158703637035966205151131341048748835573355, 249520371263084037841738179882512904586153182079672925461414050331317855239306624996192770812737822998037800311408597496713168935908506284676562605929346211408534591372594118291442754172289181361032358754195206908345325588124357032112278925080146435932390899521411548375334576302956152016838931261001094646666917000881740377514070577538553773303867461475938645549329867997417461077010627748920313110658493709802441974051936285042613081140047308532091660800299505756394755271928637669600256812619323913049771546607857870478375965253929579609273900619029201477668308022579654567444665879549998024501927728502564349506747933745816945792694722062981013838027146068995833208849998730134020068068899878466030301945827465379273363750385146119145059616525902251956377621865964519015171405446293363413737205625733277727341120870442066424312432616099009536589831885032624581653158299027557492542530364186872932493337244304092811333535905882845818987116114709625956193031848399430072854927170410984618257069132741880561979847046362607309297454013761951362909285411883923538157242506492451027908090228059284578078081776724499685155036079832790576231618724027081148164917996318860308389490820174995475609215648498032536560233781064391055845143982475766057058417598407202033157112563901508925096018118813649996543735810889746515294744477497765745885345501118899939394569339633015340160305374085703515406597845331918105775068798010995301557436440300140454567646287311253570350555041214337592715544479671635857218944295500882552601496161357309353484073706506137114133381323409608036346080506775891189380519542919539978817403104817352607540600423633477339577691683029197051857254416817838515012316962097726861443428042787847073889540712503056820606277344781738873515415363697529172434945007443648628092955460263083713973840404208287829179321930516104056823858564186480108773740608359769134578453133732598242798340233032074821854435778632027403702300706502687761991906659366371923903817894636532641041318425881526004014484503932387676572246664286682034967967888745486046892647869477718607948589176453856806424114040627358815675127831463260636849042034567299041041961558047144430128833374561502685022776831945114285782012398315681022458090392641737668452273577674284896396916038392172277711689898229558394798826898537506977212831202527973928671813030779551714121610517030485624626732501230797402615468870603423061807113554530281723316446234900718936130988528217726417018023165744221351565499625661021385355373895505704213734528976513111098682560943099401065043067948063900855747701702312541118265175272904763229268229714518740248169140985487466457451971087678237289825809859945113957617377081747761520937748681135736760493307182074082066371784411353794590906010179391430505265611344250719249099724231311546773612035181034605428216644362330688139043378359908157851113484242396052695081252034203226409619809445389736297133274346335630470075320620068, 1653230148158065316185893361488318940512542937027670960446779165008561050733140882356408323912677950432807150122611774845709575219649487589710436624213303044211176057086687088378261682244021964620252096458643113161983440578119466517969740964024694558876937140281233276985811546333381757691776881478673793279475064945870938676889791917216814831911235066080515714456326379639338021637305425176969827007206174920775549396530519060893746596000455236062970725153269417758050254676258365035830707838757795252541242958024315775103457232372973463913116932926552675250276126108913364037881849770734138871848129934209742653306384116581554684028646514515686490762899884997132140550590990300558775030258653598185528500632046769370401102474218728720663287119970354218087563621915595269210055367946788454918360378813441506929603361774280929723465641673443910110080932446635554341206749571366536909750631156178471223034694623012758208835029572603359001726615644048065668042842721807340049737575378203166522049706734750599573299630446139608955965402672984682880796122332571764199000051910835168538152852755197140038482451357596209808376473025603381561359221681051142912578285735856039834893083202136427497003167580112221675995506830103761340424929937108380259302242577572012341925019880375040865352347223963479332125337256172996333975234273184070844075192653249844536533887003328118262967043688132033928635943746858378591286246398857952046925636515338820315847766527848433101448810475184494351568433307943757093252064970231984559771926223928021529915959538719881441271860862614392399384082186106768849671630763052457401524592617197984839717786615703308732716099385531927036821892526683344438405570940452601189388500140683214603356668592067706610566457660329866719557044808576045872085636848625754984446520478967868656221306525324724985560333801343122251449355577892274567863308881218021319809457426575440036046497944786702671783410656998549985067811214198578183611852182795465756929713301638155851846366353244524152464448068321731134504479000511137287952022114683883064602710346895107929516470853811050210754704296634844628426580755531025856167695200521743890421055748539801540916674373036949014409633083554107300021133055104550278398020856511487841507458352821584895923517248015338500956037890549046711860227724339729986866461315684553092717336523479980906898845118859435253560726581443406405103436458442807143986164037322743311859416077544468232670694682744055535398383487272658707284409357178368622861100040301468796985538467056308992972496558922974068487140259499921949120429894852066958384540527562247162635657079964039864385840948050939911577059661736328368126015105260088120097453278239806670035916642646219323688919166041266833509647222862961170041370320491957776063287169346079355354684252328654368254079893923923905303222452675933942180750923246922778429063479794286208269393032545554597872410355622548929363962300230214439474892319634809866716430178826920482392684422132590015992001982376989281414056054261329165862555688914385129660020664377023601869227374228875191872830727677252738686, 27583615506724225747830051756935229938586148196576320792583708307344659553091150651269734905391609244098852443503034249567271204789111004325879865208154128299074946814013530914017696992016057569444275793092254552858602061618364422984680500198059572027426694470413735782280125978746920240656236110492924612988374423559227225952575192265729052838753836856887375451193873376133663940906271761265282892640669483647056741624302784396931283368923136650155886034707608400321666627272211091036077975251846090492458939675745798682412788147848656430756228450757586754381875850324777976848089412000002244372771984223822227652790365006762551443165170750894204265294217459157426418077971337774542663480795656920193044321183576987159533813400456012528948291722330814452043863355578814074893791403512541277487382444975094340130390895619599810500228906129780449752710185676375746220816107878525517250026062996505619007128904013835173474391892879790204893705267961732299385445616116728057540242244493984614593483201727355738004586637950780594921802956174027211720737229595302726883654267488783871116858376457169583014487407193004969428473179007897477677094275873801494275806051275796718293137559167013212457042506921681914341481637872024054229564504852070851993173777160480794303640095704800501170963384863012181030133239620784593127247519418530763524660384457424478230421584868172744263274300772199956346331486149741040411008603729656493560280368801296329219355157492161238622838430364627874283024599781328118161237942006969419465463895773051452146937528978008580872310365022195456159125386279038276879709287021874123945790143866620173107847380376959771055196804791938641711065682937929720702895563544827290271433581313013154710576015528419447150443780830464934068467347511597680987086427206245371529441798559755855745959501008394659165512387107644169309425951950512252266431693723051466103248643011113878678031986911881678591864707042148361832515215656233301734129567244939175378984987846810436928473150486101927918046421636375466621605082111908243490147391601056641082958289801745453069567269885671464786571562697404293738806908944753477010911732717472309625695098340987054386631139705644553969839373595650292774149983411231092495245755166378056026626493662154767391087247525161828226370035897196258010494592885571954399143161944620066385578685093699711866363659671550869437277222354606486856186812049550589344341693403664822711470637653857431352101487484256374409178413214403186255389997719996703218968210008504670797321243942117231151859517628630349569653058698118066187391026716043545159059654577176332268476602672472482739905635999480906228670289633504973415762993972907766272134865991043814805419896534931073246213850637679606858129338795065133349542850065726766936036299370922408774380505025968168284345386665377281249588248580545930400466171993441348890777681408413792261782078132393405173617156978069157554987085001342749548897628772071501746485297338419567888447916576003827942243149921603766457101091934913083638519107992861960578751085440622105975591590796253493717379898678559428399312159501744049589763462109224611155470651431242674376807346030648379920779387984431062472207125815283005595053785608059359105377596317033846677529976095247]
c1 = 7605669437754751751610476177793759131922826980747104093542357000818497060063913924107087845360990601930555408671050799948028724299883081716937328931603327401754338192339874262419488256716174631370326490340322668255296557552788673471486135418120341918433421647466085611610623888947334038786158937441805452533779600853534965842279605411321369490368670863839480487248494416704364066973130408803943616027255257877265692956494766498575455080145534197710328071265029220229973018465376670403863050749617402496374129377281908954174277237051375359314753601975945322974975570323160950506786156943455904003195428000040276467333916553152559367716005398458970735998218533906822986614299001007314233841439480404236525261687328038543324776121839450265774921153183345047339005819754225618642933897260628741960692674491434237804555672449292585007134274881211775018630205737481800980716413758823216367911098490923039835682350013993053684506179413463125160869092176051667542368444607398819075749260134926892765114967445127938787413294708846094647437461502267474667647867530967839403461015520221145207732126447194067557777391537487237333127763013412323290051592125035563889974597343703747815163057904878702293699906325918583118298615404197934183092127
c2 = 341595253067503923027327180174884110317813506975617387801656377695966015427686992630676476188327503408928085530907804759965585203559484367772124285327044892961629152280475590498801311792956675772793138973517344692373412012812998574478644589545065453486056173491581210032155813257019845037925319344376991506868743154964217562974928300531437171616809706704371442171341158262483303393798575086111986530515621947452872485483738996766520943353286418825902780535165645491929283298305830157842776174911337005056657154851248032434586871455775785545734893373260979956976838120485456101872762991318750097419353639388326793460456278111983200869520970167760379097780850230957583925571903440260148961903310505297970989113233530838499106591857410273351285355702857494584543267209020635318257337528755084279019440848085269494771572479426796336187894016370761010594614057637109736684003912143131304981577819937788747670575676678950510781062647916588578603909110042289909263266437689901085935181226833845096239377544115217945572972017727703955324255969922780264799462917178616823113780902728249289228180706493867880051515747381052636943269639252221899055560858043281118088505415270127127991418414117681127980674701604093707405807834115516687426674435
p = rr
q = rr - 1

rks = []
for rd in range(20):
    g  = 69
    y = ks[rd]
    r = rd + 2
    x = binomial_dlog(y,g,p,q,r)
    print(f"[+] rounds {rd} check ", ZZ(pow(g, x, p^r)) == y)
    rks.append(x)

# c1 = pow(sum(k*flag**i for i, k in enumerate(ks)), (1<<7)-1, n)
# c2 = pow(flag, (1<<16)+1, n)
# ks = [pow(69, k, rr**(i+2)) for i, k in enumerate(ks)]
PR.<x> = PolynomialRing(Zmod(n))
f1 =  (sum(k*x**i for i, k in enumerate(rks)))^((1<<7)-1) - c1
f2 = x^(65537) - c2
f0 = pgcd(f1,f2)
print(long_to_bytes(int(- f0.constant_coefficient() % n)))

 

daisy_bell, 18 solves

Source Code

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

p = getPrime(1024)
q = getPrime(1024)
n = p*q
c = pow(bytes_to_long(flag), 65537, n)

print(f"{n = }")
print(f"{c = }")
print(f"{p>>545 = }")
print(f"{pow(q, -1, p) % 2**955 = }")

"""
n = 13588728652719624755959883276683763133718032506385075564663911572182122683301137849695983901955409352570565954387309667773401321714456342417045969608223003274884588192404087467681912193490842964059556524020070120310323930195454952260589778875740130941386109889075203869687321923491643408665507068588775784988078288075734265698139186318796736818313573197531378070122258446846208696332202140441601055183195303569747035132295102566133393090514109468599210157777972423137199252708312341156832737997619441957665736148319038440282486060886586224131974679312528053652031230440066166198113855072834035367567388441662394921517
c = 7060838742565811829053558838657804279560845154018091084158194272242803343929257245220709122923033772911542382343773476464462744720309804214665483545776864536554160598105614284148492704321209780195710704395654076907393829026429576058565918764797151566768444714762765178980092544794628672937881382544636805227077720169176946129920142293086900071813356620614543192022828873063643117868270870962617888384354361974190741650616048081060091900625145189833527870538922263654770794491259583457490475874562534779132633901804342550348074225239826562480855270209799871618945586788242205776542517623475113537574232969491066289349
p>>545 = 914008410449727213564879221428424249291351166169082040257173225209300987827116859791069006794049057028194309080727806930559540622366140212043574
pow(q, -1, p) % 2**955 = 233711553660002890828408402929574055694919789676036615130193612611783600781851865414087175789069599573385415793271613481055557735270487304894489126945877209821010875514064660591650207399293638328583774864637538897214896592130226433845320032466980448406433179399820207629371214346685408858
"""

 

Solution

Classic coppersmith for RSA partial key leakage. We have $1024 - 545$ high bits of $p$ denoted as $p_h$ and 955 low bits of $q^{-1} \mod p$ denoted $q_l^{-1}$. The high bits of $q$ denoted as $q_h$ can also be derived from $p_h$ and $n=pq$.

$$p(x) = x + p_h 2^{545} \\ q^{-1}(y) = q^{-1}_l + 2^{955} y \\ q(z) = z + q_h 2^{545}$$

where $x < 2^{545}, y<2^{69}$.

We use the following equations:

$$q^{-1} q = 1 \mod p \implies nq^{-1} = p \mod p^2$$

Then we have polynomials:

$$f(x,y) = nq^{-1}(y) - p(x) \mod p^2 \\ g(y,z) = q(z)^2 q^{-1}(y) - q(z) \mod n$$

In this writeup, we use polynomial $g(y,z)$ as the coppersmith polynomial. I recommend the coppersmith repository from Kiona. It can automate parameter tuning and works fine for this challenge.

 

Exp

Sage

from coppersmith_multivariate_heuristic import coppersmith_multivariate_heuristic
from Crypto.Util.number import long_to_bytes

n = 13588728652719624755959883276683763133718032506385075564663911572182122683301137849695983901955409352570565954387309667773401321714456342417045969608223003274884588192404087467681912193490842964059556524020070120310323930195454952260589778875740130941386109889075203869687321923491643408665507068588775784988078288075734265698139186318796736818313573197531378070122258446846208696332202140441601055183195303569747035132295102566133393090514109468599210157777972423137199252708312341156832737997619441957665736148319038440282486060886586224131974679312528053652031230440066166198113855072834035367567388441662394921517
c = 7060838742565811829053558838657804279560845154018091084158194272242803343929257245220709122923033772911542382343773476464462744720309804214665483545776864536554160598105614284148492704321209780195710704395654076907393829026429576058565918764797151566768444714762765178980092544794628672937881382544636805227077720169176946129920142293086900071813356620614543192022828873063643117868270870962617888384354361974190741650616048081060091900625145189833527870538922263654770794491259583457490475874562534779132633901804342550348074225239826562480855270209799871618945586788242205776542517623475113537574232969491066289349
ph = 914008410449727213564879221428424249291351166169082040257173225209300987827116859791069006794049057028194309080727806930559540622366140212043574
qh = (n // (ph << 545)) >> 545
q1l = 233711553660002890828408402929574055694919789676036615130193612611783600781851865414087175789069599573385415793271613481055557735270487304894489126945877209821010875514064660591650207399293638328583774864637538897214896592130226433845320032466980448406433179399820207629371214346685408858

PR1.<x,y> = PolynomialRing(Zmod(n), 2)
PR2.<a, b> = PolynomialRing(Zmod(n), 2)
# PR2.<a, b> = PolynomialRing(Zmod(n**2), 2)


pa = a + ph * 2^545
qx = x + qh * 2^545
qa = a + qh * 2^545

q1y = y * (2 ** 955) + q1l
q1b = b * (2 ** 955) + q1l

# f = pa - n * q1b
# f = q1b * qa - 1
g = qx**2 * q1y - qx
rs1 = coppersmith_multivariate_heuristic(g, [2**545, 2**69], beta = 1)
print(f"[+] {rs1 = }")
# rs2 = coppersmith_multivariate_heuristic(f, [2**545, 2**69], beta = 0.48)
# print(f"[+] {rs2 = }")

ql = rs1[0][0]
q = int(ql + qh * 2^545)
p = n//q
phi = (p - 1) * (q - 1)
m = pow(c, inverse_mod(65537, phi), n)
print(long_to_bytes(int(m)))

 

Katyusha’s Campervan

Source Code

from Crypto.Util.number import *
from random import randint
from FLAG import flag

p = getPrime(1024)
q = getPrime(1024)
e = getPrime(132)
n = p*q
hint = pow(e, -1, (p-1)*(q-1))
hint %= p-1
hint %= 2**892
c = pow(3, int.from_bytes(flag), n**5) * pow(randint(0, n**5), n**4, n**5) % n**5

print(f"{n = }")
print(f"{e = }")
print(f"{c = }")
print(f"{hint = }")

"""
n = 9722343735487336242847355367175705096672092545117029199851527087227001665095112331406581010290318957921703096325328326862768861459201224096506317060919486835667369908780262880850949861734346363939614200227301344831209845565227637590016962469165064818450385339408084789219460490771570003649248250098125549751883777385917121014908647963900636814694225913533250242569263841750262192296795919177720443516042006972193940464844059718044438878017817432336475087436031866077325402373438547950481634275773767410248698596974769981162966656910136575149455523084473445761780201089182021418781347413453726696240548842411960178397
e = 5323153428600607366474827268153522064873
c = 9128106076400211790302891811252824557365859263295914819806672313027356017879597156259276057232557597614548050742418485365280305524694004426832069896531486671692562462063184624416012268348059935087037828161901243824582067161433586878141008884976330185561348052441637304755454643398179479215116505856245944555306345757777557395022121796068140566220391012921030768420736902592726104037200041403396506760483386523374366225161516294778224985920562226457769686733422726488624795847474711454397538514349555958637417188665977095558680525349235100286527905789576869572972662715040982208185436819557790062517857608731996417066519220133987864808243896151962316613504271341630230274953625158957103434031391582637694278277176886221304131078005240692954168656292222792833722555464070627220306776632641544334188357810067577550784029449834217848676080193960627138929032912578951880151284003878323853182114030012207949896373695734783631698004600675811512726913649141626146115066425891236975554237158682938964099745220780884079884347052906073216530490633243676915134831324804418410566989306886192743687590855529757605789691981493863292029273401139254934543448966341439303948513266699261650278938684067402860913507689842621595391519090227639907684629841162983852454124546030986411283762938101536264676221777904450717178547838152674410566294280937400196290368544481636850750666313771438253636667634601122561235018292316232335633111595474772273810349284893171480302604833719250453453781210093266339454843926482821341993360016434693250661347303203216948599305102121353574445652764255573536572077762409837628479280331295047290459975370026620838169978316921035609492162085052786943829915442906137063599836720584533200385074702683101049336194258783047318183521466098437420153628598968954236332678203275614402446435216223033804260963642393142002417568855964535316709986640977596845897721671783670070696907220894520837335160816494605130683705587464386202643385688263935088026204614056121745160246499509455752793089324629215884008499726564579763845757062068182946721730306128755414268910929410742220199282343421146810430121947827801171056425435942640932150535954546458772114121498557119913825127286832860975814307160175273154886250581960709573672488119996389986116735407178214281982766051391618187878672106737928646489671994503814871652107136752677107398141842179907758909246276653861569864776043204134345135427118784118473462309509988521112691717301811627018054555866015966545532047340607162395739241626423495285835953128906640802690450118128515355353064004001500408400502946613169130088974076348640048144323898309719773358195921400217897006053213222160549929081452233342133235896129215938411225808985658983546168950790935530147276940650250749733176085747359261765601961315474656996860052862883712183817510581189564814317141703276878435707070103680294131643312657511316154324112431403040644741385541670392956841467233434250239028068493523495064777560338358557481051862932373791428839612299758545173203569689546354726917373906408317003812591905738578665930636367780742749804408217333909091324486584514813293
hint = 27203100406560381632094006926903753857553395157680133688133088561775139188704414077278965969307544535945156850786509365882724900390893075998971604081115196824585813017775953048912421386424701714952968924065123981186929525951094688699758239739587719869990140385720389865
"""

 

Solution

Another RSA partial key leak challenge. Let $d_p = hint + 2^{892}x$ , we have:

$$ed_p = k(p-1) + 1 \\ \implies ed_p(x) - 1 + k = 0 \mod p$$

where $x<2^{132}, k < 2^{132}$ ($k$ is the same size with $e$).

Let $f(x,k) = ed_p(x) - 1 + k$, we can solve for $x,k$ using multivariate-coppersmith from coppersmith repository mentioned in daisy bell.

After the factorization of $n$, we need to compute the discrete logarithm over $\mathbb{Z}_{n^r}$ which is mentioned in challenge rr. Check the detailed analysis there.

 

Some papers are related to the scenarios of Katyusha's Campervan and daisy_bell. Put it here for later need:

1. Some Applications of Lattice Based Root Finding Techniques
2. New Results for Partial Key Exposure on RSA with Exponent Blinding

 

Exp

Sage

from coppersmith_multivariate_heuristic import coppersmith_multivariate_heuristic
from Crypto.Util.number import long_to_bytes

def binomial_dlog_sub(y,g,p,q,r=2):
    C = ZZ(pow(y, q, p^r))
    B = ZZ(pow(g, q, p^r))
    kx = (C - 1)//p^(r-1)
    k =  (B - 1)//p^(r-1)
    x = ZZ(kx * pow(k, -1, p) % p)
    return x

def binomial_dlog(y,g,p,q,r):
    assert r >= 2
    y = ZZ(y)
    g = ZZ(g)
    xs = []
    for i in range(r-1):
        xi = binomial_dlog_sub(y, g, p, q, i + 2)
        xs.append(xi)
        y = ZZ(y * pow(g,-xi,p^r) % p^r)
        g = ZZ(pow(g,p,p^r))
    return ZZ(xs, p)

n = 9722343735487336242847355367175705096672092545117029199851527087227001665095112331406581010290318957921703096325328326862768861459201224096506317060919486835667369908780262880850949861734346363939614200227301344831209845565227637590016962469165064818450385339408084789219460490771570003649248250098125549751883777385917121014908647963900636814694225913533250242569263841750262192296795919177720443516042006972193940464844059718044438878017817432336475087436031866077325402373438547950481634275773767410248698596974769981162966656910136575149455523084473445761780201089182021418781347413453726696240548842411960178397
e = 5323153428600607366474827268153522064873
c = 9128106076400211790302891811252824557365859263295914819806672313027356017879597156259276057232557597614548050742418485365280305524694004426832069896531486671692562462063184624416012268348059935087037828161901243824582067161433586878141008884976330185561348052441637304755454643398179479215116505856245944555306345757777557395022121796068140566220391012921030768420736902592726104037200041403396506760483386523374366225161516294778224985920562226457769686733422726488624795847474711454397538514349555958637417188665977095558680525349235100286527905789576869572972662715040982208185436819557790062517857608731996417066519220133987864808243896151962316613504271341630230274953625158957103434031391582637694278277176886221304131078005240692954168656292222792833722555464070627220306776632641544334188357810067577550784029449834217848676080193960627138929032912578951880151284003878323853182114030012207949896373695734783631698004600675811512726913649141626146115066425891236975554237158682938964099745220780884079884347052906073216530490633243676915134831324804418410566989306886192743687590855529757605789691981493863292029273401139254934543448966341439303948513266699261650278938684067402860913507689842621595391519090227639907684629841162983852454124546030986411283762938101536264676221777904450717178547838152674410566294280937400196290368544481636850750666313771438253636667634601122561235018292316232335633111595474772273810349284893171480302604833719250453453781210093266339454843926482821341993360016434693250661347303203216948599305102121353574445652764255573536572077762409837628479280331295047290459975370026620838169978316921035609492162085052786943829915442906137063599836720584533200385074702683101049336194258783047318183521466098437420153628598968954236332678203275614402446435216223033804260963642393142002417568855964535316709986640977596845897721671783670070696907220894520837335160816494605130683705587464386202643385688263935088026204614056121745160246499509455752793089324629215884008499726564579763845757062068182946721730306128755414268910929410742220199282343421146810430121947827801171056425435942640932150535954546458772114121498557119913825127286832860975814307160175273154886250581960709573672488119996389986116735407178214281982766051391618187878672106737928646489671994503814871652107136752677107398141842179907758909246276653861569864776043204134345135427118784118473462309509988521112691717301811627018054555866015966545532047340607162395739241626423495285835953128906640802690450118128515355353064004001500408400502946613169130088974076348640048144323898309719773358195921400217897006053213222160549929081452233342133235896129215938411225808985658983546168950790935530147276940650250749733176085747359261765601961315474656996860052862883712183817510581189564814317141703276878435707070103680294131643312657511316154324112431403040644741385541670392956841467233434250239028068493523495064777560338358557481051862932373791428839612299758545173203569689546354726917373906408317003812591905738578665930636367780742749804408217333909091324486584514813293
hint = 27203100406560381632094006926903753857553395157680133688133088561775139188704414077278965969307544535945156850786509365882724900390893075998971604081115196824585813017775953048912421386424701714952968924065123981186929525951094688699758239739587719869990140385720389865
PR.<x, y> = PolynomialRing(Zmod(n))
leak_bits = 892
un_known = 1024 - leak_bits 
f = e * (hint + x * 2**892) - 1 + y
# x <= 2**un_known, y<= 2** 132
sols = coppersmith_multivariate_heuristic(f, [2**132, 2**132], beta = 0.499)
sol = sols[0]
dp = hint + sol[0] * 2**892
k = sol[1]
p = (e * dp - 1)//k + 1
q = n//p
# p = 107137790764109294435738452887955149442794115385917421133088316383957513812938944418454606256987491520085074052815215859908950491406982768196727659910881462433670091921679086357171751905670595866834745181195419362013584004876446081357773024790677648597247435270479338298917890197185252569905294212062983995409
# q = 90746165906048159474154095991389030950712801945941795430201281468665317834501062751616036041934198161203798480412193507303323619830943569148411089764905202815514556117346348126016453518349943163524986909838095207733566566591045379396133769593776454928828989448679093566272816546270747251714472002195562821133


assert p * q == n
print(f"{p = }")
print(f"{q = }")

phi  = (p-1)*(q-1)
x = binomial_dlog(c, 3, n, phi, 5)
print(long_to_bytes(int(x)))
# print(len(long_to_bytes(int(x))))
# print(long_to_bytes(int(x)).hex())

 

challengename

Source Code

from ecdsa.ecdsa import Public_key, Private_key
from ecdsa import ellipticcurve
from hashlib import md5
import random
import os
import json

flag = open("flag", "rb").read()[:-1]

magic = os.urandom(16)

p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = ###REDACTED###
b = ###REDACTED###
G = ###REDACTED###

q = G.order()

def bigsur(a,b):
    a,b = [[a,b],[b,a]][len(a) < len(b)]
    return bytes([i ^ j for i,j in zip(a,bytes([int(bin(int(b.hex(),16))[2:].zfill(len(f'{int(a.hex(), 16):b}'))[:len(a) - len(b)] + bin(int(b.hex(),16))[2:].zfill(len(bin(int(a.hex(), 16))[2:]))[:len(bin(int(a.hex(), 16))[2:]) - len(bin(int(b.hex(), 16))[2:])][i:i+8], 2) for i in range(0,len(bin(int(a.hex(), 16))[2:]) - len(bin(int(b.hex(), 16))[2:]),8)]) + b)])

def bytes_to_long(s):
    return int.from_bytes(s, 'big')

def genkeys():
    d = random.randint(1,q-1)
    pubkey = Public_key(G, d*G)
    return pubkey, Private_key(pubkey, d)

def sign(msg,nonce,privkey):
    hsh = md5(msg).digest()
    nunce = md5(bigsur(nonce,magic)).digest()
    sig = privkey.sign(bytes_to_long(hsh), bytes_to_long(nunce))
    return json.dumps({"msg": msg.hex(), "r": hex(sig.r), "s": hex(sig.s)})

def enc(privkey):
    x = int(flag.hex(),16)
    y = pow((x**3 + a*x + b) % p, (p+3)//4, p)
    F = ellipticcurve.Point('--REDACTED--', x, y)
    Q = F * privkey.secret_multiplier
    return (int(Q.x()), int(Q.y()))

pubkey, privkey = genkeys()
print("Public key:",(int(pubkey.point.x()),int(pubkey.point.y())))
print("Encrypted flag:",enc(privkey))

nonces = set()

for _ in '01':
    try:
        msg = bytes.fromhex(input("Message: "))
        nonce = bytes.fromhex(input("Nonce: "))
        if nonce in nonces:
            print("Nonce already used")
            continue
        nonces.add(nonce)
        print(sign(msg,nonce,privkey))
    except ValueError:
        print("No hex?")
        exit()

 

Solution

This modulo is from the standard curve secp256r1. By validating the points from remote server, we can make sure that the curve for ECDSA is exactly secp256r1. Note that the digesting results from md5 hash is only 128 bit while the ECDSA is defined in 256-bit curve, the short nonce attack can be applied in this case! Two signatures are enough to recover private key by the lattice theory.

 

By the way, the intended solution is the nonce reuse attack by exploiting the flaw of bigsur implementation. Here are two writeups using the nonce-reuse attack :

1. https://berliangabriel.github.io/post/bi0s-ctf-2024/
2. https://gist.github.com/Hisokap3/f446034f6d6ca9bcfeee05c1dad0aaa4

 

Exp

Not optimized attack, probabilistic exp.

from hashlib import md5
from Crypto.Util.number import long_to_bytes, bytes_to_long
from pwn import remote
from ast import literal_eval

def short_nonce_attack(h1, h2, sig1, sig2, kbit, q):
    r1,s1 = sig1
    r2,s2 = sig2
    a1 = h1 * pow(s1, -1, q)
    a2 = h2 * pow(s2, -1, q)
    b1 = r1 * pow(s1, -1, q)
    b2 = r2 * pow(s2, -1, q)
    M = [
        [a1, a2, 2**kbit, 0 ],
        [b1, b2, 0, 2**kbit/q],
        [ q,  0,  0, 0],
        [ 0,  q,  0, 0]
    ]
    L = matrix(QQ, M).LLL()
    
    for l in L:
        row_bits = [ int(num).bit_length() for num in l]
        
        if all( 66 < rb <= 129  for rb in row_bits):
            assert abs(l[2]) == 2 ** kbit
            sig = l[2] // 2 ** kbit
            d = sig * ZZ(l[-1]*q/2**kbit) % q
            k1 = sig * ZZ(l[0]) % q
            k2 = sig * ZZ(l[1]) % q
            d1 = ZZ((s1*Mod(k1, q) - h1) * pow(r1, -1, q) % q)
            d2 = ZZ((s2*Mod(k2, q) - h2) * pow(r2, -1, q) % q)     
            assert d == d1 == d2
            print(f"[+] private key hacked {d = }")
            return d

p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b  
G = (0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5)
E = EllipticCurve(GF(p), (a, b))
G = E(G)
q = G.order()

io = remote("13.201.224.182",int(30773))
pk = literal_eval(io.recvline().decode().strip()[len("Public key: "):])
enc = literal_eval(io.recvline().decode().strip()[len("Encrypted flag: "):])
msg1 = os.urandom(16)
non1 = os.urandom(16)
msg2 = os.urandom(16)
non2 = os.urandom(16)

io.sendlineafter(b"Message: ", msg1.hex().encode())
io.sendlineafter(b"Nonce: ", non1.hex().encode())
data1 = literal_eval(io.recvline().decode().strip())
io.sendlineafter(b"Message: ", msg2.hex().encode())
io.sendlineafter(b"Nonce: ", non2.hex().encode())
data2 = literal_eval(io.recvline().decode().strip())
r1,s1 = eval(data1["r"]), eval(data1["s"])
r2,s2 = eval(data2["r"]), eval(data2["s"])
h1 = bytes_to_long(md5(msg1).digest())
h2 = bytes_to_long(md5(msg2).digest())
d = short_nonce_attack(h1, h2, (r1,s1), (r2,s2), 128, q)
P = E(pk)
Q = E(enc)

FLAG = (ZZ(pow(d % q, -1, q)) * Q).xy()[0]
print(long_to_bytes(int(FLAG)))

 

predictable, 9 solves

This challenge did not provide the source code. By the description :

Can you help me test out this PRNG I implemented? I’m inserting a backdoor, but I’m sure you can’t find it. Oh btw, I did some optimizing, so version 2 is faster. You can still try out version 1 though. They’re the same anyway.

And the information from nc port :

$$ nc 13.201.224.182 32291
Choose your version [1/2]
> 2
Computing parameters...
Curve: secp192r1
(2293001194541150274215482316213105496109852432703623632365, 5138032477357433568745355477968816064902296975478092081150)
(2009389419019814261106085493821011653542185845274559892427, 3548044933390299525522715419339491238117118302301308620875)
1. Get a random number
2. Predict
3. Exit

➤ 1
5975173324401374804038251361166465897519018446118941563889
➤

It must be Dual-EC prng with a backdoor. If you’re not familiar with Dual EC, try to search it in google and read relative blog. You can also read my blog if you are familiar with Chinese. I will not explain Dual EC and its backdoor in this blog.

I did not solve this challenge during this CTF since I did not realize the timing information in period of computing parameters.

 

Timing Attack

The timing information can be obtained from the refresh frequency of \r. The time intervals between two adjacent \r occurrences are as follows :

[Log] 1 Time info: 0.4543850680001924
[Log] 2 Time info: 2.9992302959999506
[Log] 3 Time info: 3.0042528319991106
[Log] 4 Time info: 0.5015156319987
[Log] 5 Time info: 3.0020693789992947
[Log] 6 Time info: 0.5006758780000382
...

For curve secp192r1, there are exactly 192 \r occurrences. We guess the Computing parameters means the fast scalar multiplication process (similar to fast power ) for elliptic curve point associated with backdoor d. Then the longer time interval stands for bit 1 and the shorter one stands for bit 0.

I finally recovered the bits of d in version 1 since in version 2, the network latency in China affects the timing information a lot.

 

Exp

Sage exp only works for version 1 and curve secp192r1.

from pwn import remote, context
import time
from ast import literal_eval
from tqdm import tqdm
from Crypto.Util.number import long_to_bytes

verbose = True
# context.log_level = "debug"

def init_curve(curve:str):
    if curve == "secp192r1":
        p = 0xfffffffffffffffffffffffffffffffeffffffffffffffff
        K = GF(p)
        a = K(0xfffffffffffffffffffffffffffffffefffffffffffffffc)
        b = K(0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1)
        E = EllipticCurve(K, (a, b))
        G = E(0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012, 0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811)
        E.set_order(0xffffffffffffffffffffffff99def836146bc9b1b4d22831 * 0x1)
        return E
    elif curve == "secp256k1":
        p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
        K = GF(p)
        a = K(0x0000000000000000000000000000000000000000000000000000000000000000)
        b = K(0x0000000000000000000000000000000000000000000000000000000000000007)
        E = EllipticCurve(K, (a, b))
        G = E(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
        E.set_order(0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 * 0x1)
        return E
    else:
        assert False, f"Bad Curve String {curve}"

def collect_timing_info(io:remote):
    time_freq = []
    cnt = 0
    while True:
        cnt += 1
        st =  time.perf_counter()
        response = io.recvuntil((b"\r", b"Curve: "))
        et = time.perf_counter()
        if verbose:
            print(f"[Log] {cnt} Time info: {et - st}")
        if response == b"Curve: ":
            break
        time_freq.append(et - st)
    return time_freq

def timeing_to_bits(time_freq, threshold=None):
    if threshold is None:
        threshold = sum(time_freq) / len(time_freq)
    bits = []
    for t in time_freq:
        if t > threshold:
            bits.append(1)
        else:
            bits.append(0)
    return bits

def init_dual_curve(io:remote):
    curve = io.recvline().decode().strip()
    E = init_curve(curve)
    P = E(literal_eval(io.recvline().decode().strip()))
    Q = E(literal_eval(io.recvline().decode().strip()))
    if verbose:
        print("[Log] curve ", E)
        print("[Log] P ", P)
        print("[Log] Q ", Q)
    return E, P, Q

def dual_ec_round_partial(E, P, Q, state, high):
    # drop 16 bits
    n = E.base_ring().cardinality()
    nb = n.nbits()
    if high:
        out = int((state * Q).xy()[0]) >> 16
    else:
        out = int((state * Q).xy()[0]) % 2**(nb -16)
    # update state
    state = int((state * P).xy()[0])
    return out, state

def dual_ec_hack_high(E, P, Q, d, outs):
    # exploit the Dual EC Backdoor, at least 2 outs
    assert len(outs) >= 2
    out1 = outs[0] << 16
    out2 = outs[1]
    # recover the low 16 bits , k is the backdoor
    for i in tqdm(range(2**16)):
        Rx = ZZ(out1 + i)
        try:
            # there are bad x-coordinates
            R = E.lift_x(Rx)
        except:
            continue
        s = ZZ((d * R).xy()[0])
        next_out = int((s * Q).xy()[0]) >> 16
        if next_out == out2 :
            print(f"[+] state recovered { s = }")
            return s
        
def dual_ec_hack_low(E, P, Q, d, outs):
    # exploit the Dual EC Backdoor, at least 2 outs
    assert len(outs) >= 2
    n = E.base_ring().cardinality()
    nb = n.nbits()
    out1 = outs[0]
    out2 = outs[1]
    # recover the high 16 bits , k is the backdoor
    for i in tqdm(range(2**16)):
        Rx = ZZ(out1 + (i<<(nb-16)))
        try:
            # there are bad x-coordinates
            R = E.lift_x(Rx)
        except:
            continue
        s = ZZ((d * R).xy()[0])
        next_out = int((s * Q).xy()[0]) % 2**(nb - 16)
        if next_out == out2 :
            print(f"[+] state recovered { s = }")
            return s
        
def dual_ec_hack(E, P, Q, d, outs):
    # no bits eliminated
    out1 = outs[0]
    out2 = outs[1]
    Rx = ZZ(out1)
    R = E.lift_x(Rx)
    s = ZZ((d * R).xy()[0])
    next_out = int((s * Q).xy()[0])
    assert next_out == out2, "not dual ec outputs or backdoor is wrong"
    return s
    
def dual_ec_round_full(E, P, Q, state):
    # drop 16 bits
    out = int((state * Q).xy()[0])
    # update state
    state = int((state * P).xy()[0])
    return out, state

def get_rand_out(io:remote):
    io.sendlineafter(b'\xe2\x9e\xa4', b"1")
    return int(io.recvline().decode().strip())

def predict(io:remote, number):
    io.sendlineafter(b'\xe2\x9e\xa4', b"2")
    io.sendlineafter(b"Enter your prediction: ", str(number).encode())
    print(f"[+] response {(io.recvline().decode().strip())}")
    return int(io.recvline().decode().strip())
    

# nc 13.201.224.182 31685
# nc 13.201.224.182 31731
io = remote("13.201.224.182", 31060)
io.sendlineafter(b">", b"1")

print(io.recvline())
freqs = collect_timing_info(io)
dbits = timeing_to_bits(freqs)
# d = int("".join(map(str, dbits)), 2)
d = int("".join(map(str, dbits[::-1])), 2)

E, P, Q = init_dual_curve(io)
print(f"[+] check backdoor {d*P == Q}")
# print(f"[+] check backdoor {d*Q == P}")

outs = [get_rand_out(io) for _ in range(2)]
        
k = ZZ(pow(d, -1, E.order()))
assert P == k*Q, "Bad Backdoor"

# state = dual_ec_hack_high(E, P, Q, k, outs)
# state = dual_ec_hack_low(E, P, Q, k, outs)
state = dual_ec_hack(E, P, Q, k, outs)
out, state = dual_ec_round_full(E,P,Q,state)
print("[+] check state ", out == outs[1])
pred, state = dual_ec_round_full(E,P,Q,state)
res = predict(io, pred)
flag = long_to_bytes(int(res))
print(f"[+] Over : {flag}")