Challenge Files



registration


n, a, e are given.

	def verify(self, msg, s):
		if type(msg) == str: msg = msg.encode()
		h = number.bytes_to_long(sha256(msg).digest())
		return pow(s,self.e,self.n) == pow(self.a, h, self.n)

Given some H, to verify, we must solve for a valid S, such that:

\[S^e \equiv a^H \pmod n\]

Rearrange for S:

\[S \equiv (a^H)^d \equiv a^{d \cdot H} \pmod n\]


We can also collect as many signatures as we want.

	def sign(self, msg):
		if type(msg) == str: msg = msg.encode()
		h = number.bytes_to_long(sha256(msg).digest())
		return pow(self.a, h * self.d, self.n)

We receive some si and hi, where:

\[s_i \equiv a^{h_i \cdot d} \pmod n\]


Now let’s introduce some new unknowns xi.

Suppose we construct S as

\[S \equiv {s_0}^{x_0} \cdot {s_1}^{x_1} \cdot {s_2}^{x_2} \cdot ... \pmod n\]

Now we just want to solve for these xi.

Substitute in our previous expressions for S and si:

\[a^{d \cdot H} \equiv a^{d \cdot x_0 \cdot h_0} \cdot a^{d \cdot x_1 \cdot h_1} \cdot a^{d \cdot x_2 \cdot h_2} \cdot ... \pmod n\] \[a^{d \cdot H} \equiv a^{d \cdot (x_0 \cdot h_0 + x_1 \cdot h_1 + x_2 \cdot h_2 + ...)} \pmod n\] \[H = x_0 \cdot h_0 + x_1 \cdot h_1 + x_2 \cdot h_2 + ...\]

And we can try solve this with LLL.


Solve script:

from sage.all import *
from pwn import remote
from hashlib import sha256

def hsh(x):
    return int(sha256(bytes.fromhex(x.decode())).hexdigest(), 16)

def main():
    io = remote('52.59.124.14', 5026)
    try:
        n = int(io.recvline().split()[-1])
        io.recvline() # a is not needed :)
        io.recvline() # e is not needed :)

        # collect hi and si
        N = 100
        io.send(b'1\n' * N)
        recv = io.recvlines(5*N)
        hi = vector([hsh(line.split()[-1]) for line in recv[3::5]])
        si = [int(line.split()[-1]) for line in recv[4::5]]

        # collect H
        io.recv()
        io.sendline(b'2')
        H = hsh(io.recvline().split()[-1])

        M = identity_matrix(N).augment(hi).stack(vector([0]*N + [H]))
        for row in M.LLL():
            for row in [row, -row]:
                xi = row[:-1]
                if xi*hi != H:
                    continue
                S = prod(pow(s, x, n) for s, x in zip(si, xi)) % n
                io.recv()
                io.sendline(str(S).encode())
                print(io.recvline().decode())
                return True
        print('no solution found, retrying...')
    except:
        pass
    io.close()

while True:
    if main():
        break

# ENO{ha5h_ev3ryth1ng_th3y_s4id_s00o_s3cur3}







coinflip

If we just keep betting 1 amount then we can collect many outputs and use that to determine some states.

then if we can just solve a and m, we can predict future states.

            self.state = self.a * pow(self.state, 3, self.m) % self.m
\[s_{i+1} = a \cdot s_i^3 \pmod m\]

We can try eliminate a and then get m with gcd like so

from Crypto.Util.number import *

n = 64
m = getRandomNBitInteger(n)
print(f'{m = }')

while True:
    a = bytes_to_long(os.urandom(n >> 3)) % m # n/8 bytes
    if gcd(a, m) == 1: break
while True:
    s0 = bytes_to_long(os.urandom(n >> 3)) % m # n/8 bytes
    if gcd(s0, m) == 1: break

s1 = a * pow(s0, 3, m) % m
s2 = a * pow(s1, 3, m) % m
s3 = a * pow(s2, 3, m) % m
...

assert s1 * pow(s0, -3, m) % m == a % m
assert s2 * pow(s1, -3, m) % m == a % m
assert s3 * pow(s2, -3, m) % m == a % m
...


assert ((s1 * s1**3) - (s2 * s0**3)) % m == 0
assert ((s2 * s2**3) - (s3 * s1**3)) % m == 0

mm = gcd((s1 * s1**3) - (s2 * s0**3), (s2 * s2**3) - (s3 * s1**3))
print(f'{mm = }')


Final solve script:

from pwn import remote
from math import gcd

def start():
    while True:
        io = remote('52.59.124.14', 5032)
        try:
            io.send(b'1\nhead\n'*64*4)
            recv = io.recvlines(3*64*4)
            return io, recv
        except:
            io.close()

io, recv = start()
recv = ['0' if b'win' in line else '1' for line in recv[2::3]]
s0 = int(''.join(recv[:64]), 2)
s1 = int(''.join(recv[64:128]), 2)
s2 = int(''.join(recv[128:192]), 2)
s3 = int(''.join(recv[192:]), 2)

m = gcd((s1 * s1**3) - (s2 * s0**3), (s2 * s2**3) - (s3 * s1**3))
a = s1 * pow(s0, -3, m) % m 



s4 = a * pow(s3, 3, m) % m
buffer = [int(bit) for bit in bin(s4)[2:].zfill(64)]
to_bet = 1
for b in buffer:
    print(io.recv())
    io.sendline(str(to_bet).encode())
    print(io.recv())
    io.sendline([b'head', b'tails'][b])
    to_bet *= 2
# ENO{1nfin1t3_r1che5_3re_y0ur5_1t_s33m5}





next-level

from pwn import remote
from gmpy2 import iroot, next_prime

io = remote('52.59.124.14', 5028)
n = int(io.recvline())
c = int(io.recvline())
e = 0x10001

p = next_prime(iroot(n, 3)[0])
assert n%p == 0
flag = pow(c, pow(e, -1, p-1), p)
print(bytes.fromhex(f'{flag:x}'))
# ENO{1_l0ve_7h3_pr1me_numb3r_the0r3m}


kleinvieh

from math import isqrt
n = 123478096241280364670962652250405187135677205589718111459493149962577739081187795982860395854714430939628907753414209475535232237859888263943995193440085650470423977781096613357495769010922395819095023507620908240797541546863744965624796522452543464875196533943396427785995290939050936636955447563027745679377
c = 77628487658893896220661847757290784292662262378387512724956478473883885554341297046249919230536341773341256727418777179462763043017367869438255024390966651705078565690271228162236626313519640870358976726577499711921457546321449494612008358074930154972571393221926233201707908214569445622263631145131680881658
strange = 11519395324733889428998199861620021305356608571856051121451410451257032517261285528888324473164306329355782680120640320262135517302025844260832350017955127625053351256653287330703220294568460211384842833586028123185201232184080106340230097212868897257794101622865852490355812546172336607114197297201223620901
phi = n - isqrt(strange + 4*n)
print(bytes.fromhex(f'{pow(c, pow(65537, -1, phi), n):x}'))
# ENO{4_b1t_0f_ph1_4nd_a_bi1_0f_bru13_f0rc3_br3ak5_1t}


kleinvieh_2

from sage.all import *
from sympy import cbrt
from Crypto.Util.number import *
load('https://raw.githubusercontent.com/Connor-McCartney/coppersmith/refs/heads/main/coppersmith.sage')

c1 = 220063927409019701680780388734859413263649938528559880958114989945319210396443096153070875125175228115415476201776095239222264863
c2 = 521405777679638898956934268538900625825553438750301296652588113926908675649695287473044872094704614120486323959657990026640254596060659622526156708812669359650586620385290808935734592790788255073585330621151468871219769656595135843333814407503403584485725875093573131958504623569333490646639116961719078216840229603919536018487825851994866357917761987217050792416697381377048912395473353778387941958191907824408107449076068401916848269614839157102521989010679392116485801486351905021880108912590420172605418475794616003449288680484874497236175444664128438401914724753429360434711903099273327857734995750524336685921743399501618966233467673179877216701974657036419446491274854437281396070824372634560507303755215464570159167837973755757084277460889038540426254099700613477619367190997235567982845416706558020882785247647017658533190054489579620395565959077232929730085201031313238724372408560517067025821200011117585158799293570307490792480672057216647059928346781983773928742745961020992758462787355967282442061725370293489410415806016306004266400903317110818168429756442671778827765363252714782616931406456862197207387559816797319132734318242504254436838880072071853192476696183220292931118231156006566093505435792459195491243680582
c3 = 270666484654665630744901461996006692323963839982688652821336211084979467239347411813160298980515940583603861222174521984995420008548684262439808167328926021870579303960012771121601180529687766238396064375729105115543248938593316359682370849163035376370382430086321848989469101241917690539277074390985259902303859203469942292526312785642432913613936993258827179590899881832319079212987637373648192635781867448864854757206430089991579140087742146982306295873762255307312524837239897502872553828380739799963200435212855355849421115331904398013024635259514540481471626803307520164323612306097337438109957993918779265436327033558060626053354750562352860044802675727693412211125966360236444057953485024215560142475510160722114624532935356913983972915673608523025209720167213909179022327299978019112977846926119199262414918029479523990318896183663433071251579236571042002734675157891234966022932698905198698241706452025453847010887618278823570050783989170662300961633292513523806788091889082274722372602239592372048577727269817482906420208931626412130427401917267155522492175168008656904232528370893411707370782832090829602128710489070166301148107529844470225377087526762510454613609000260941022095648201987928579356978933393880920171979201
c4 = 653824340069025689137734254884130538700629136163559226740194794484993327658776187767570065320577134162743283784425272380809589160993088925874733196055173409287931015748252064633449072261545303183579447460502965342804624603405929157397131141984984644568357653302213965819415468460642952197339991556281367534783709497954301841184449070203282829556818406681886900718807834059676277878423047814575995317125009067646248518224341963179051812872833920966444865854397107596362642091691676816880789051432546280982801936460897107739053704289586862815777802365195344200436339914632247470287475059508482642321374344266084746769130713777040613388188063244264539412036380560226898399218628361640805872727932488302521211097971713325651815102241321497845489911517697687601337373561866169629605144418239966598946278151568343055898100847891792937851579379932984962575775149818916217268297467279875725571404166944999117855879952146915514369003878816227211205583465391314024099614444033724650197415698616726563650695337089763944873372957911180655004798934831152909017151923470147174567931032793367193038245769647005250292165097213630935925441110568790329108402080201984414111112552177466252777781418725448757243067372449888316330317213717511659267093522
c5 = 358008688390962979576377899144327321078101097951911268175317488500603502519487932330612462905624620597194558963905078036617959827652774950608159539755872698070336695988156123259549872787213397592148258199055613243895883287122890753360508292871837174063088420693224462093920149982044282287843545879889673811146267351528090047294284591799007589644031290908451176760853222636619363811207185693725681140126798792027873548626157363148637874670590965485611082128311321694683523699469128409485949494113757646949983087406842230923148769118322570130431421259760535420603207584288801345366412235455743468488327636151425392848303200702882860489019370153190810988494600882544600108525238483037309140333051358221984674540701977879624246387893765464282113949391789532777484259814371861241414118348867987309273292578129887971446610687731851915056696448523460974558006120340055071716623978233935275849865817975522109696101884471525506261697387468489779620579480299246665603825623773259263912587161909414417437045900004826755951647391749631385635652448151832357232824962202646901774457696625192040117636828038808343932086478692164048901540300465526784540912169577834838256728624868904132298644241575543460006379361856217382572895303794378838795856964
n = 0xAB4AAEA67D1D40F076281C64A8A6C7A9576541522700BF8F56D388AA23DF00ABA899E8803C5A92C589D5B33C7C397EDEB0CBA5845FC95C4465D7B1A573B9EBD5FE20E53A8244174B8E7ECBE541507E74C382CD07D1E1045E40E8EAE8C5ACFED20828F09B8BB4610504D789C814393678B363ED41D7357BEC4CB85D27A71A866310D14A5C34BBC9D94B6AFA63E7C47438B7C59F01EF4B78C192C321EF37A696DF772B26558803BABE5122F1A908DF3955F6FE718C87F8546625A4216AD4BB90EB6CDD7CEECD54B85A7F5CCB207D314C8001707BCCB3C0E4B934173DEC7E2105E7210D2088A54C18774EE99263C4A27ED5F6C52E41AB0CF3852A833BD24014C5BCFF2E2A5CD9A67A0C21515027588F3943AC7FA458121C36AE0CB020A81620B0D4BAD72B061326FEC672611D48AA261C40151A27D8DE090F29264E46B536F607F3030E56B35B7EE24263E8A541AE691024591569484342D38FF7A5AE7B8344778CA7DF55EBEC34D38F71D56F799F42354277E9C9021CC9158E1B704E3DC286108992AD0426C98565C48C7B9756B5412CEAD666FCE5E4C820889095B6FBD6EFE9F0F102E1AD63A54A1CA0D87854B59DFB9F03C7C8ECBD36D8EFBE0FD9E42E70576DB8BC7629E14BD49F4D2F46A91E666C49B936F193D1B1BBE186D83B83B2D463D38493AD31756E361D6A7AFCC380A2853D094F4EA97BF2EE19870F93DAE9103C6B
e = 3

bytelength = int(math.floor(math.log2(n))) // 8
r = 688234005348009046360676388021599552323079007705479727954148955984833460337936950913921276804334830417982234720038650432729780498514155995618937412575604196815690605161835755609341381092145548153312943119696398326144902639226831471200542337105282064399184931676924592908530791494346900227871404063095592748764296028255530577278656680463782655139421219302422899667665339277824718421901831817043159552132252016945226370677278067424506514993298100924479619565269428391036310378044733517453768164252655931111202089432697078947184486267865943138659836155939343134738408972426979329158506027280653209318479413895259774319848662706808171929571545923310500352950348748809789292920278241362015278963315481777028997344480172010960294002098578989469089294022590134823913936869548907125294447477430739096767474026401347928008150737871869441842515706902681140123776591020038755234642184699856517326004574393922162918839396336541620212296870832659576195010466896701249003808553560895239860454162846759635434691728716499056221797005696650174933343585361153344017021747827389193405667073333443569659567562247406283282451284155149780737904760989910944550499316655128394899229284796584787198689342431338201610314893908441661953172106881929330452489260
v = bytes_to_long(b'\x42' * (bytelength - 18) + b'\x00'*18)
PR = PolynomialRing(Zmod(n), names='x')
x = PR.gens()[0]
f1 = (sum([x*256**(18*i) for i in range(28)]))**3 - c4
f2 = (v + x)**3 - c5

m1 = cbrt(c1)
m2 = cbrt((c2 * pow(r, -3, n)) % n)
m3 = cbrt(c3 * pow(256, -3*(bytelength-18), n) % n)
m4 = univariate(f1, X=256**18, m=2)[0]
m5 = univariate(f2, X=256**18, m=2)[0]

flag = b''.join([long_to_bytes(int(i)) for i in [m1, m2, m3, m4, m5]])
print(flag.decode())
# ENO{s0m3_0f_th35e_me1hod5_4ctua1ly_h4d_th3_sam3_1de3_th4t_i5_why_1t_i5_jBu5t_1_ch4ll3nge}