SECCON CTF 2021 Writeups

Super Guessers won SECCON CTF 2021, with a clean all-solve. I have repeated in this CTF, i.e. won this CTF two years in a row, last year with a strong union of (mostly) Korean cybersecurity professionals. The writeups from last year is at https://rkm0959.tistory.com/165.

This year, there is no collab, only Super Guesser, which is cool :)

 

Due to some other busy work, I didn't participate fully and solved 3 out of 6 cryptography challenges, and others were done by Baaarkingdog. I also finished one misc challenge, (it was our final solve) but it built on work of many others. (I just finished the challenge)

 

Challenges were very clean and good, and not painfully difficult (this is usually expected from Japan I think, :))

 

Super Guesser's first "major" CTF win (without collab)

 

oOoOoO (by kurenaif)

import signal
from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime
import random
from flag import flag
 
message = b""
for _ in range(128):
    message += b"o" if random.getrandbits(1) == 1 else b"O"
 
M = getPrime(len(message) * 5)
S = bytes_to_long(message) % M
 
print("M =", M)
print('S =', S)
print('MESSAGE =', message.upper().decode("utf-8"))
 
signal.alarm(600)
ans = input('message =').strip().encode()
 
if ans == message:
    print(flag)
else:
    print("🧙")
 

 

Thinking about the effect of each "o" or "O" for the value of bytes_to_long(message), we see that this problem is essentially a subset sum problem over modulo $M$. Indeed, the problem is equivalent to solving the system $$ \sum_{i=0}^{127} [79^k \text{   or   } 111^k] \equiv S \pmod{M}$$ which is same as $$\sum_{i=0}^{127} [79^k \pmod{M} \text{   or   } 111^k \pmod{M}] \equiv S \pmod{M}$$ Since the left hand side is between $0$ and $128M$, we can just solve the following for $0 \le c \le 127$. $$\sum_{i=0}^{127} [79^k \pmod{M} \text{  or   } 111^k \pmod{M}] = (S \pmod{M}) + cM$$ which is now a standard knapsack problem, and can be solved via CJLOSS algorithm.

 

# https://github.com/jhs7jhs/LLL/tree/master/low-density-attack
 
def inthroot(a, n):
    return a.nth_root(n, truncate_mode=True)[0]
 
class HighDensityException(Exception):
    pass
 
 
class CJLOSSAttack:
 
    def __init__(self, array, target_sum, try_on_high_density=False):
        self.array = array
        self.n = len(self.array)
        self.target_sum = target_sum
        self.density = self._calc_density()
        self.try_on_high_density = try_on_high_density
 
    def _calc_density(self):
        return self.n / log(max(self.array), 2)
 
    def _check_ans(self, ans):
        calc_sum = sum(map(lambda x: x[0] * x[1], zip(self.array, ans)))
        return self.target_sum == calc_sum
 
    def solve(self):
        if self.density >= 0.9408 and not self.try_on_high_density:
            raise HighDensityException()
 
        # 1. Initialize Lattice
        L = Matrix(ZZ, self.n + 1, self.n + 1)
        N = inthroot(Integer(self.n), 2) // 2
        for i in range(self.n + 1):
            for j in range(self.n + 1):
                if j == self.n and i < self.n:
                    L[i, j] = 2 * N * self.array[i]
                elif j == self.n:
                    L[i, j] = 2 * N * self.target_sum
                elif i == j:
                    L[i, j] = 2
                elif i == self.n:
                    L[i, j] = 1
                else:
                    L[i, j] = 0
 
        # 2. LLL!
        B = L.LLL()
 
        # 3. Find answer
        for i in range(self.n + 1):
            if B[i, self.n] != 0:
                continue
 
            if all(v == -1 or v == 1 for v in B[i][:self.n]):
                ans = [ (-B[i, j] + 1) // 2 for j in range(self.n)]
                if self._check_ans(ans):
                    return ans
 
        # Failed to find answer
        return None
 
conn = remote('oooooo.quals.seccon.jp', 8000)
 
REMOTE = True
 
if REMOTE:
    M = int(conn.recvline().split()[-1])
    S = int(conn.recvline().split()[-1])
    conn.recvline()
else:
    message = b""
    for _ in range(128):
        message += b"o" if rand.getrandbits(1) == 1 else b"O"
    print(message)
 
    M = getPrime(len(message) * 5)
    S = bytes_to_long(message) % M
 
base = 0
for i in range(128):
    base += 79 * (256 ** i)
 
 
sums = ((S - base) * inverse(32, M)) % M
 
arr = [(256 ** i) % M for i in range(128)]
target_sum = sums
 
st = time.time()
 
for i in tqdm(range(128)):
    attack = CJLOSSAttack(arr, target_sum + i * M, True)
    res = attack.solve()
    if res != None:
        msg = ""
        for i in range(128):
            if res[i] == 0:
                msg += "O"
            else:
                msg += "o"
        msg = msg[::-1]
        conn.sendline(msg.encode())
        print(conn.recvline())
 
 
en = time.time()
 
print(en - st)
 

 

XXX (by theoremoon)

import os
 
flag = os.getenv("FLAG", "fake{fakeflag_blahblah}")
x = int.from_bytes(flag.encode(), "big")
 
p = random_prime(1 << int(x.bit_length() * 2.5))
Fp = GF(p)
 
params = []
while len(params) != 6:
    try:
        y = randint(2, x)
        a = randint(2, p-1)
        b = (y^2 - (x^3 + a*x)) % p
 
        EC = EllipticCurve(Fp, [a, b])
        EC(x, y)
 
        params.append([a, b])
    except ValueError:
        pass
 
print(p)
print(params)
 

 

We have 796 bit prime $p$ and around 320 bit $x$, which is the flag.

We are given 6 parameters $(a_i, b_i)$ such that $y_i^2 \equiv x^3 + a_ix + b_i \pmod{p}$ and $y_i < x$. 

 

Subtracting, we see that $$(a_1 - a_j)x + (b_1 - b_j) \equiv y_1^2 - y_j^2 \pmod{p}$$ so $$-2^{640} < (a_1 - a_j) x + (b_1 - b_j) \pmod{p} < 2^{640}$$ which can be rewritten as $$ -2^{640} < (a_1 - a_j) x + (b_1 - b_j) + p c_j< 2^{640}$$ for $2 \le j \le 6$. Since we know all $a_j, b_j$ values, the only unknown is $x$ and $c_j$ values, and this can be plugged in my CVP repository. 

 

 
# Directly taken from rbtree's LLL repository
# From https://oddcoder.com/LOL-34c3/, https://hackmd.io/@hakatashi/B1OM7HFVI
def Babai_CVP(mat, target):
    M = IntegerLattice(mat, lll_reduce=True).reduced_basis
    G = M.gram_schmidt()[0]
    diff = target
    for i in reversed(range(G.nrows())):
        diff -=  M[i] * ((diff * G[i]) / (G[i] * G[i])).round()
    return target - diff
 
 
def solve(mat, lb, ub, weight = None):
    num_var  = mat.nrows()
    num_ineq = mat.ncols()
 
    max_element = 0 
    for i in range(num_var):
        for j in range(num_ineq):
            max_element = max(max_element, abs(mat[i, j]))
 
    if weight == None:
        weight = num_ineq * max_element
 
    # sanity checker
    if len(lb) != num_ineq:
        print("Fail: len(lb) != num_ineq")
        return
 
    if len(ub) != num_ineq:
        print("Fail: len(ub) != num_ineq")
        return
 
    for i in range(num_ineq):
        if lb[i] > ub[i]:
            print("Fail: lb[i] > ub[i] at index", i)
            return
 
        # heuristic for number of solutions
    DET = 0
 
    if num_var == num_ineq:
        DET = abs(mat.det())
        num_sol = 1
        for i in range(num_ineq):
            num_sol *= (ub[i] - lb[i])
        if DET == 0:
            print("Zero Determinant")
        else:
            num_sol //= DET
            # + 1 added in for the sake of not making it zero...
            print("Expected Number of Solutions : ", num_sol + 1)
 
    # scaling process begins
    max_diff = max([ub[i] - lb[i] for i in range(num_ineq)])
    applied_weights = []
 
    for i in range(num_ineq):
        ineq_weight = weight if lb[i] == ub[i] else max_diff // (ub[i] - lb[i])
        applied_weights.append(ineq_weight)
        for j in range(num_var):
            mat[j, i] *= ineq_weight
        lb[i] *= ineq_weight
        ub[i] *= ineq_weight
 
    # Solve CVP
    target = vector([(lb[i] + ub[i]) // 2 for i in range(num_ineq)])
    result = Babai_CVP(mat, target)
 
    for i in range(num_ineq):
        if (lb[i] <= result[i] <= ub[i]) == False:
            print("Fail : inequality does not hold after solving")
            break
    
        # recover x
    fin = None
 
    if DET != 0:
        mat = mat.transpose()
        fin = mat.solve_right(result)
    
    ## recover your result
    return result, applied_weights, fin
 
 
p = 238351830708404244219528012300346183698089704036958197073088590986781126046128139277876261847918986388464392075919752504036124478387675086320279831883061575773130731731512289308600548817918823754759741014480607490178191084213685771095081699
params = [[61721446814822499191022412902217320153137633897387846710512310039336410477728264217681745891863200893378034581997664894522756658992873501693353425063400655105194107970249009691442632015429658305792298714043235777934090212343625933540920419, 38215859743437160276358618194105173963536621422404142018824002222927344371846641995139103441786202367296704680389815780441043250270096100089370169391316241550354639472704197195039115443263083720157181161573037786722518518073244876576521645], [193846031065431615171138398907554474490243593010426445660159995023421690918389029501570918601414789147460375901577546434319012002193067152560178159337882412597981169953017381602553449608161376011387225337945790490301205500988070592667260307, 182624605832152240064165962388331595893516884552600324435147374044032575325900262356701606616541732441503871912325334315545721127713601115727804588364391211951651086408749934094159068720206922998283686393892033283362379079277585875317733125], [186116431294956584507622251083552464237708766317037184701883695099192545170797758914491959325056548294443112027689221562090922906211642613451222485059412249593287539268632182815867453113262026976033832305075048778306269837158521655897206104, 188291640755725711120730552161550568363878329035151394705358843149734090074525252662747799270008290175006002913694732659518178709233238519205580102532883270488509830279127451754878651121923932212399426641171488518541036604555898762653636767], [147690737704193380929256042516354642591634312528093128869923487184997632263182669491324548799394778507341925228715095053166787082158079876801508640863174460376667578857398193776134734184654976792585753897823602173550210678811026343180632574, 90919616852165947744756990575400745193091744707583913218090901120971522401412921713920030755420236486444344985420141669115268509030823280811858196495296299291522098961629224878356500400137160049480897176934761512803911650692781199738944358], [147919066213305504909474311411803269104114976277480371373734903513860210330631554119249090143860674441819199276919740940095535099825251133312941478015230935296046855247122689436697731644543102898280018067875178726421332069314230553359546674, 233189046301154960459915044289449599538936202863814191691219472024725663885482828960872087873090796952667099967198895490748125927000604303160065032535117589864975437392352615652017307656160862671237257143553966268386859872891179982158931538], [137450316462129268877711035250763668980618551403674476273480945205694245899369623646082468202341690739837762419221648759226283935459299779254296497766202256170266366890970940886869389464332464546003480305741255956702385666111816886488497002, 42626852637723346847761898432034196330200006970228231831316278507491404141071325164359383210554480496801017672657717855189744860778897395023272448045289999028710960807199386287807443723368642574520040320693565244086076826717435666078357317]]
 
# x 320 bit
 
# a1x + b1 + x^3 == y1^2 (mod p)
 
M = Matrix(ZZ, 6, 6)
lb = [0] * 6
ub = [0] * 6
for i in range(1, 6):
    dif_a = (params[0][0] - params[i][0]) % p 
    dif_b = (params[0][1] - params[i][1]) % p 
    # -2^640 <= dif_a * x + dif_b <= 2^640 mod p
    M[0, i - 1] = dif_a 
    M[i, i - 1] = p
    lb[i - 1] = - (1 << 640) - dif_b
    ub[i - 1] = (1 << 640) - dif_b
M[0, 5] = 1
lb[5] = 0
ub[5] = 1 << 320
 
result, applied_weights, fin = solve(M, lb, ub)
 
x = int(fin[0] % p)
 
 
print(long_to_bytes(x))

 

Sign Wars

from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.Util.Padding import pad
import random
from secret import msg1, msg2, flag
 
flag = pad(flag, 96)
flag1 = flag[:48]
flag2 = flag[48:]
 
# P-384 Curve
p = 39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319
a = -3
b = 27580193559959705877849011840389048093056905856361568521428707301988689241309860865136260764883745107765439761230575
curve = EllipticCurve(GF(p), [a, b])
order = 39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643
Z_n = GF(order)
gx = 26247035095799689268623156744566981891852923491109213387815615900925518854738050089022388053975719786650872476732087
gy = 8325710961489029985546751289520108179287853048861315594709205902480503199884419224438643760392947333078086511627871
G = curve(gx, gy)
 
for b in msg1:
    assert b >= 0x20 and b <= 0x7f
z1 = bytes_to_long(msg1)
assert z1 < 2^128
 
for b in msg2:
    assert b >= 0x20 and b <= 0x7f
z2 = bytes_to_long(msg2)
assert z2 < 2^384
 
# prequel trilogy
def sign_prequel():
    d = bytes_to_long(flag1)
    sigs = []
    for _ in range(80):
        # normal ECDSA. all bits of k are unknown.
        k1 = random.getrandbits(128)
        k2 = z1
        k3 = random.getrandbits(128)
        k = (k3 << 256) + (k2 << 128) + k1
        kG = k*G
        r, _ = kG.xy()
        r = Z_n(r)
        k = Z_n(k)
        s = (z1 + r*d) / k
        sigs.append((r,s))
 
    return sigs
 
# original trilogy
def sign_original():
    d = bytes_to_long(flag2)
    sigs = []
    for _ in range(3):
        # normal ECDSA
        k = random.getrandbits(384)
        kG = k*G
        r, _ = kG.xy()
        r = Z_n(r)
        k = Z_n(k)
        s = (z2 + r*d) / k
        sigs.append((r,s))
 
    return sigs
 
 
def sign():
    sigs1 = sign_prequel()
    print(sigs1)
    sigs2 = sign_original()
    print(sigs2)
 
 
if __name__ == "__main__":
    sign()

 

There are two mistakes - one is the insecure random of "prequel" which fixes the middle 128 bits, and the insecure python random which is used in the "original". The natural plan is to attack the "prequel" first using the insecure random via standard LLL, find the python random seed using some library, then directly find the random $k$ values for the "original". The latter part can be done very easily with some libraries, so we'll focus on the first one. We write the system as follows. For each 60 equations, we have $$ks \equiv z_1 + rd \pmod{n}$$ $$k \equiv s^{-1}z_1 + rs^{-1}d \pmod{n}$$ $$k_1 + z_1 \cdot 2^{128} + k_3 \cdot 2^{256} \equiv s^{-1}z_1 + rs^{-1}d \pmod{n}$$ $$ 0 \le k_1 = z_1(s^{-1} - 2^{128}) + rs^{-1}d - k_3 \cdot 2^{256} \pmod{n} < 2^{128}$$ $$0 \le z_1(s^{-1} - 2^{128}) + rs^{-1}d - k_3 \cdot 2^{256} + cn < 2^{128}$$ and now this can be plugged in CVP repository. Note that $d, z_1$ is fixed and $0 \le z_1 < 2^{128}$, $0 \le k_3 < 2^{128}$. 

 

# Directly taken from rbtree's LLL repository
# From https://oddcoder.com/LOL-34c3/, https://hackmd.io/@hakatashi/B1OM7HFVI
def Babai_CVP(mat, target):
    M = IntegerLattice(mat, lll_reduce=True).reduced_basis
    G = M.gram_schmidt()[0]
    diff = target
    for i in reversed(range(G.nrows())):
        diff -=  M[i] * ((diff * G[i]) / (G[i] * G[i])).round()
    return target - diff
 
 
def solve(mat, lb, ub, weight = None):
    num_var  = mat.nrows()
    num_ineq = mat.ncols()
 
    max_element = 0 
    for i in range(num_var):
        for j in range(num_ineq):
            max_element = max(max_element, abs(mat[i, j]))
 
    if weight == None:
        weight = num_ineq * max_element
 
    # sanity checker
    if len(lb) != num_ineq:
        print("Fail: len(lb) != num_ineq")
        return
 
    if len(ub) != num_ineq:
        print("Fail: len(ub) != num_ineq")
        return
 
    for i in range(num_ineq):
        if lb[i] > ub[i]:
            print("Fail: lb[i] > ub[i] at index", i)
            return
 
        # heuristic for number of solutions
    DET = 0
 
    if num_var == num_ineq:
        DET = abs(mat.det())
        num_sol = 1
        for i in range(num_ineq):
            num_sol *= (ub[i] - lb[i])
        if DET == 0:
            print("Zero Determinant")
        else:
            num_sol //= DET
            # + 1 added in for the sake of not making it zero...
            print("Expected Number of Solutions : ", num_sol + 1)
 
    # scaling process begins
    max_diff = max([ub[i] - lb[i] for i in range(num_ineq)])
    applied_weights = []
 
    for i in range(num_ineq):
        ineq_weight = weight if lb[i] == ub[i] else max_diff // (ub[i] - lb[i])
        applied_weights.append(ineq_weight)
        for j in range(num_var):
            mat[j, i] *= ineq_weight
        lb[i] *= ineq_weight
        ub[i] *= ineq_weight
 
    # Solve CVP
    target = vector([(lb[i] + ub[i]) // 2 for i in range(num_ineq)])
    result = Babai_CVP(mat, target)
 
    for i in range(num_ineq):
        if (lb[i] <= result[i] <= ub[i]) == False:
            print("Fail : inequality does not hold after solving")
            break
    
        # recover x
    fin = None
 
    if DET != 0:
        mat = mat.transpose()
        fin = mat.solve_right(result)
    
    ## recover your result
    return result, applied_weights, fin
 
 
SIG1 = [(12122920644857436418668108677431446821511965161835906257619686170008223981633617118848536864333256883344783807472533, 14197268540776373741177673820089672023976732299858030846681305575389640921071188098294211283607291412628404706330635), (30023311263693682916692119631904793161812704258670063725046946028381482586508452744969994191586576481159969039892535, 16094000621518284822857020964974522983541224425681758135622160784082988267314022122458996489586892811938506732931748), (20274365333087648992099914855887452427265725062234768121150756210734918282305324594709095440941680006674472249980168, 26128948049631412381227970242480771408976962602375493955244402440727109476811862753343673422200707132102306861245065), (30768939097894626895378677401324579041720728810052060616179712179254924186139940391745214635086621700092451846257475, 23800973758418165064781275855199658315920145808589994209139192398347876290686870300287776343940629270010735723235385), (28473557828088061979399196473136471402585047600303142695341163640729652130707043952255899907766676152597539289628315, 28281625820520087035698954279133768588017050298800453267610958044101108252535161164763310762642756504428205563108030), (961118250385917764507600420510572217848406774402919254807074729943580199634194943936928534369937371624710732726857, 24031640471683802687061395705285266808842836983869848057857017127967668008272515010890509063551366550912420338902834), (19370494654235267454217217719890760732479633443331393690560476118111139682942513564572505092689607226193201989778575, 2433781820944268337733283393291854175920938847482642777771696759267025446311242119383222969981818996711424713151752), (30779090043894032830605276175884042975994811516472755795216312382846355682168692296678880256197033821390044997147420, 4893123418105561169402880287889300261310663472852291300562230045024356786173678817075957809203454759484532173136896), (14643705489977528788970058117566828771249298225825962912655208159781673578193298484890200020885473583280037544119578, 15935318488540400173648065087608623889419958306790544362968141852933585912044021990423536612481693468915965522445032), (26190847735254363003436975683906714419695452818227446664219556609524851687182160032913188662574521358473164521270318, 1593531527201615623099098664942415943763347197253061444470827851943278116759392933621884906245655648264221554908273), (2444983458103763169338770323724579409115782087673217289810500838726321984003897473707801517318376539252731600634354, 31519693975000372684536588360058886155393128374920715958105917368560178529829092541542334254564649031015390295526257), (5539202944379041047645815730619570855915700610921747198866014997007285622810384696777658611658354790466198556409538, 20332957999843652613921660609152489318731466697459198872422541589848932160246010821103577261742306246402279741839395), (29969504934312616092773577215293054327868412131595687908164133237389228991764362661689008330244463167067377417804848, 23502790732595477415220062415069646202303453814634558339724957279860279173977141614843448086419994681526804050994011), (28663099246038192816273570466053103880330161954725039364215397713591731084208919109404788115439838323705057354906183, 32343362746546345028906807296090845637927648209201182279186066312617262402540993950717856425293636562311369826695241), (37811425966842340383821228402925951424928841073943712670686829246012732634532778206829440348798738360996829177934659, 1512161086988707363568355555539355341485927942150807857139424735463213909258176919376930783632168090029799006962452), (6779019396487335250176376177316480940562897505935292947586838966405847326392683369310422331267556304950213385562403, 21277628400501469478914168423023057684740585069176201105893608414023541256985765180901007757435611069875893412465586), (6366948926057872251073324724715646697709396244107534411996999604518484325522941417643164680481781327650121512161589, 31835229197999276237723592037000880402276309404799202930304320555417861589116989270114086456362377584676026798317441), (15281845709607491920369813817013377362178255708702641554534892473368410191641487999506001924287614983557554388444790, 2984115935788221541188290047888309109458147722093547866020985007410124451071701982135991689832422756636714734848410), (17261327950609380032505415413729345506837563477802335104261903199945292046286371909764527605537844250765520460420883, 4414083024903566067346682354660036193755195663970474589205389345245255956774402052618861533800845720100684618788066), (23285217326555475016519552330905568382923977489456237456732496253903350233528472100890947226393609572097915969599580, 15864787645844524123645508552473833769050437498168559566442342764983309617043514215685980718642756051823094216138112), (38735613502207617543460798902089924117030110156904845492417889885452926231509412677457364662728826603870166089048783, 2764799580566369130997255183073579096790304637375189258729225097121531798414933779603126159724061297478107963529944), (34397686468933908386713398593117199247477408535310063872486364205758893481567076156685158122992765644664863620408441, 32278070177934959080616216483052122171696315094028362684579162316990518944414668141213923548802330689237360305444057), (36888596144580310076666982554379754727579693141157953039821763246320596624002076072694376360349327605151628461938344, 20359599307803961599163637268447617008934461534173375543520973121462531279483793982707344429872033956688432496029494), (35731945369165024527067708422190934453114426930189147171662677061124488912009487138831725596607769036223677431254394, 38690463610329621441610277699868091296837875356478232771729649752351130839647804626642276143604085382240751091874980), (23677628634176723569940322462564200990434883563619558260828733247431579872437268289228719660272457754577432647629267, 5694960089075991074464290708570332306998548315951489339220678741537951501152608587055469175810163056202380723484162), (36183304484234246866110911449167537754372333309427114844147387618829024530231991189605158113348204109845980352696465, 23965168344478037213105641624609514777278543321778037076016154890855496855531577133265749426868642365368798849451496), (33162978581198415974999091637775219015609843478885981431365405627376986149964493390352996432902431398214990453120700, 17522675770165519045405383886383499046920674272323023864859028070652034097791735019059447013185908178315975726718027), (37977524287531621731269652998518444039221788561001084681446374543680582455529006667074181965831283556770601026406412, 34014871750340380154692206012455554620218508761966344769331999972401940089831171697348255247018267326994810496665301), (1507013781859412581460229968016871686472000162722420853292672399595213588246897578540619347856535893357627270900677, 7123198841569413454577310078272821534024280579100722414329202844057424863366193509058084349838170744321137899380851), (16162098325755207229063189997383396611921725235544867443071126936768120496007100174087010708793986788501933456531117, 35843125491563878831891747420494968566047358046579202101829199006631647636438358745741154644883785641557638179703196), (27146246587667190740076698462480327352334872042637035686499133830505424921309618795732649623443166432157485441206513, 29374852723618836996041990307719900335299612538156861129617267376582701400599574166091116228943846822827095705431420), (20318873596559259511055531147506382540328039101211632617939893607230146992770755366357547004154440123877927279562805, 21880244506505391597381900288791130929029500377960791610120410522262499720103003893165761379437860585723438454338357), (2677089679217144714677235060642211123498261589343453643587089980258267670810054471717380695130400677765718942750715, 22811216118007709181671732510261424038689262085998138698823325592895788252084744051591190795979078528619437443272430), (28242261012068041277293540110291951864968606243755362285072828317158908834811289543798540567848975185502994215611619, 28337300861435742639020944587343125537033416178222051556584188414720653042082343068603170738957875834942311839398955), (21313784566242236288558209540398728358450102518073033970974355085249250643681779922552823541265620185702575612865123, 25973923581441774490467725510310356393118571760442289368631380634139185801852675014798484820655377425355874214608838), (3972247474338783322467875314927935482812576258324764658865475177091575186850519760736477068863287011253657979695035, 1949243324150001215851803463575673078965313534368782887187770074096642168523503805499517384914614086023503127806847), (1151944487736036555640946065337093366220353301888076465796765130037778971904962274932934887966419998200175365995781, 19564575441055199178132952897543045993451659948447588920651596150288550414960098453945167530353880987093029030638144), (34162335734397557091228494111777449419659314364130585745202913773828419992559542465196157154618586692393424347136785, 34816069361672535828713924897177961374080352312052306803897119805834580104455380505473277752161016451540002438069017), (6214420518977400720115040915606936189332457649954029722703185627542783153439822172938794340141280694328697860997151, 35036609860976357406366810820445499231048373436931375253989834911997779342195269560660560149275988782146654615055395), (17932296848485476028307829364900722350664622103067434376880482465660776884118027615894824834062520974562950696190800, 25284454559391441356742861992714899157880349238554132025565451660342323497911181209889041052025003714876311648649308), (16729838562359475474212958363183560420250559702291016364521051500450026103395443198630456476103970943753669154249375, 32346909821898954875794104426207252965578694675212598600013619876939291316966520281348030524571180602992351937324549), (18383357524600760202019477696462766408564829389632201092711392752822975200725339011191785469174324590811632757501470, 36650204800420829652120261290123142229312040551658496656556239024215868372978503733453573308931372634821353503537954), (12679474326846184225965528024726547768506690550379875402442700592477187625032566343282886015393973299453970347716666, 31594434445787142355786158780673084733603186104893515951267587710628733125154787164728421585888101421671404571441460), (1460155946173513465605000753006943939473815980031454177632679861455928714118380298806901823644725063756743440478323, 28595065903087426074566358753005915622433302916683368431103530322432724436087166807363512661383021500064699866636573), (1712191697812545578149205758294464160112058894608923583568724616471266315677289849142337215940784518880963429394123, 15549321728923260877275319522523938368845573355479005888471636555747793775030205015093656278438688710952666664504896), (27247850567913925982695067834491518101584714379758703325384826250084810338850873054903173768682909886315224820151843, 18441987213600418235028717811172592400392968984874201495657937932256496057636260779718506455774046512049959224326533), (23125206105423712170494578086460408200155706950388584751758217770641881139847092343076320949651253557057860975699290, 617384558916714490913646402391877958626488085682864653677413549966260928717156654411337297014822767990795093863229), (10309859796084513086949474325745742289943652601164042295798749216013816749262406978527658506169631041432182034483264, 3401470346181096624340649421457463749621102267436616681750603386976006189520143441710738979453350404845158395485486), (16368609105601996512123657503983976901814846135585476552914466414979175179581723778823773810904335136988607343388641, 12887327683770298631686858909410191002874101297863064763857850276211374735131663350575035482893318627486961140493060), (12597783086712780955829102511325977339556480314456317226084059427852975744410298400466570369739729859822682094743763, 18143629657739573817392351951162537846408025200449845703036545707816887229856135678162116712273281752461460773286157), (18149765203212365095922365541429595804115110638460797557247425663278065057761683694963435074306083146559748910820933, 4623808735710466757897562443056494514986872251154643072124080945722371896930429940197336707416267350592331887509370), (36685770489292450862829854673422281288659959443468144451918042753101522158121942740628396053876144087903556902670459, 25427602196870003078247382997147130945403862270376348600679340464766087619183853473530884327535652383782148396318369), (26400994935887323685812785588779777604807033818459784383379336636723016041989131355813709350621150638600337397745755, 35441443644761879722810537983899640132591168390041946180094287752185744760148684344825560100034902852843703022913572), (21549464322285949487974060839290414317291085580470644413175603703659811599686802128539665387707492575120952990974169, 27426668476821276280862019979056999027369355304092859933896625743859680072036382523929860072977660288769061968841056), (17945055270149004672174407200101186426733019188557222629374387229166321253248131455944582958258851086680992327717775, 22763432714358352994467634787642451136567944768237186044385733037319457391071748311079692136983455628393624590912773), (19679372898006128640291583077178951435604248960537272688952385068434563933226836358777706619530975918926211454093254, 22558450199634522395989325930989798822306499440080795289426594476903491433232767149595712438138190142613146382805102), (5053808002622613648696016012235196453213394765089545993472533920762659290879000238284401142373566610359754334503119, 25596265678131212259962460250737224350948937567171043241527736952385125964273084970352617767438577469728391374901104), (35021535942876477664620323193569084612777266590551110729944867045139787961246598034847607119451282633173220627617528, 24412900363309066203864154425415165066253353692376637520978763141267068333052991517573772819303004361631432100082761), (30382344157317014521174359938595199590313101376532894077961655976102849666994412986977757526700903573837979050569748, 36380054077835016119489703494179753668737802402599719907220000486624011084909818429478518718710302969894134810399414), (23392455319924374624407363218414017792726341637348154289368001919553092631539423722056128035028761955761251335231397, 24615969593765671009089175669046441351199855489516238368580612855661905474214253402259306074086838224100682009493110), (39043410087571658849777088723644840444773112471772958075589595817236649732325361138357268471190048890890922330173113, 24256166337102519478716198099822063504670413826816008063467295625641151486658627000887001654580846329391802379723304), (25198309246276017483121163348865597630643532403493815715878126594393814779012937502862557889192295110821475991529943, 31183736084868762605705341491981967451872193027043779034558377529784073696083378450370565887268611112401715464692322), (21490370993563026264971775993182460905215869236047670304210535706894812928914407971234995821500730800223031598266257, 30524538483293986209920139400952501355824771895617776073345360374702907548949007510552008565834914052456239691889902), (37366673614850776444692939328421732388527123695286819437966655615675408069366910860035074204029318799945903064048527, 17779215295739572760353458898043288811931339150166396214780752407992014275252723707803456409767620788479105600423376), (23880907135038389168803046756901468214206189168117058906553768830712533102670877117203361468021971439264847643087559, 36554798683087533081747521419888907675190192122029480300791517998074362122003489313160167552894436296245959628579534), (1839816617790796393877679129129689526692744195784843313918019394276687774692559082426410650970115204065124516740192, 33280887100325540541044876347841631022975706016854603366960877001893277240119020663116400162762880357011028194015505), (37860238532878533314237881709991803144640720532159211259802653676233680439794809051955788290617724291896314228484287, 2079530852252634619529204167324028013909690544367420298080750988365566999876311319237386168370876748621061304030325), (33076401294910426866408725898185517353797089714631638085904654063741185770239407827102674966897738352568845852795461, 32388782563029207071708238813265723145823101733798639269010838632868478704546695027802504168693070745244529700498871), (19664630416995907039268499340971147354543906991316471257330973370399289180202716179184726176333997501833047008445188, 15010332454096306874561434765152776137424843532232617982537812287828972466131420109345949260515569323587248864746943), (25871769372685370569925822425693820620619794598214474123600511253778185796962172073208206762818745309605540739100621, 12733332659612677892428319839726866498876500931386736309794894873372522229292842342178191364595143966422220824826073), (12769045455084894273436527159204816902432305644017210629296787933904295785281457448881044929402038399496940189044093, 11594689177180251431669445510565369712938818714831055440921516382728285369019679675944135089038247905820859659761517), (1865703770871313754195006900013207845562542245675070113698481870088723236246390202799490489472079377268354306242668, 5125550573798542551697831171912361478992101952449490976854228951650529010822626202419835861052330070344633285976669), (37096662612327463148937337171394483039720908237996642157433470567568444060739072904671016601404440533704833919544285, 4790007747398249736115034551686542360219836448905259482276520130644298771477774260329772071196479778643314968168876), (31170630741028077467666117690922124046397732731173001565911078911132891410318903435039074418130660922292175028485161, 36700267333965429842826985729957565986107482356086995641315664499740118242353501066703906197210995388334971341587044), (16429305562010070045918008502995674904932019310071872766389089174936173832847431470110417157600205840910967654695105, 13348678473612360711357762565221644167552517488898971900250507563637477504294039445796012121832852740292220571524010), (36814999620410624650408927593101102311832288601200212772521220280747373268407838162653769833122342138193850888479316, 21678377395564601107395386759737337329969405189315349034054067649380849056748928922052454754064625128419150919292053), (37080204662579811419723925250553811343118062800721020347850990442377486549932418090303179252403198539322519694444276, 15821341762768738218228176979267566826815656142437698746345759451195866137662375460664107143767858376489559348158119), (31900665212807794653067892050991087787174739879112603157270515722601016232361976337248279931832041244757837789022461, 11910037530034363325480855721128870881334951395240192762039726365170413466292618778748338552446589898886095541743053), (22713234938446144853039935121713734891074107932043602957345904095128407091303028830418630224869359322276067322228220, 37648033797699949313050109414984677478246381964295991074283362304879984221990727828373537248000765921622593274507531), (26966642227721045071442724645484661519368889576738311756067876287666319883156972945382104473351822669036919304411830, 33837552398136675647634120649336283866568054003022435569393484219100126804419072284913749466938666527692475735307495)]
SIG2 = [(1049639883029709557497416807885448950887522866921671928450292553333188509467250311602354191758381412870243165308138, 34790284668131148498252310249426530965492667679223859021102993403672099203069041205214172414075756555276490789178956), (3085218467051892206002417901865728576393577451338770207618129262272350718747277968031614020531383301753358875936613, 35069145156217342955289020258826302551823920792084376060949622353808056721610402437441970841628302496074418474626297), (24094905265337534276165828047859782238987431219303883218554480297297861668847922558928617159973811943649844468445020, 9328776074819457901331657355801560516363178058099225535915537394781684440774078985119798155365962514386879323530606)]
 
 
p = 39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319
a = -3
b = 27580193559959705877849011840389048093056905856361568521428707301988689241309860865136260764883745107765439761230575
curve = EllipticCurve(GF(p), [a, b])
n = 39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643
Z_n = GF(n)
gx = 26247035095799689268623156744566981891852923491109213387815615900925518854738050089022388053975719786650872476732087
gy = 8325710961489029985546751289520108179287853048861315594709205902480503199884419224438643760392947333078086511627871
G = curve(gx, gy)
 
# ks == z1 + r * d mod n
# (k1 + z1 * 2^128 + k3 * 2^256)s == z1 + r * d mod n
# k1 + z1 * 2^128 + k3 * 2^256 == s^-1 (z1 + r * d) mod n
# k1 + z1 * (2^128 - s^-1) + k3 * 2^256 - s^-1 r d == 0 mod n
# -2^128 <= z1 * (2^128 - s^-1) + k3 * 2^256 - s^-1 r d mod n <= 0
 
num_sig = 20
M = Matrix(ZZ, 2 * num_sig + 2, 2 * num_sig + 2)
lb = [0] * (2 * num_sig + 2)
ub = [0] * (2 * num_sig + 2)
 
for i in range(num_sig):
    r, s = SIG1[i]
    M[0, i] = ((1 << 128) - inverse(s, n)) % n 
    M[1, i] = (- r * inverse(s, n)) % n 
    M[2 + i, i] = 1 << 256
    M[2 + num_sig + i, i] = n 
    lb[i] = - (1 << 128)
    ub[i] = - 1
 
for i in range(num_sig):
    M[2 + i, num_sig + i] = 1
    lb[num_sig + i] = 1
    ub[num_sig + i] = 1 << 128
 
M[0, 2 * num_sig] = 1
lb[2 * num_sig] = 1
ub[2 * num_sig] = 1 << 128
 
M[1, 2 * num_sig + 1] = 1
lb[2 * num_sig + 1] = 1
ub[2 * num_sig + 1] = n 
 
result, applied_weights, fin = solve(M, lb, ub)
flag1 = long_to_bytes(int(fin[1] % n))
z1 = int(fin[0] % n)
d = int(fin[1] % n)
 
predictor = MT19937Predictor()
 
for i in range(80):
    r, s = SIG1[i]
    k = ((z1 + r * d) * inverse(s, n)) % n
    k1 = k & ((1 << 128) - 1)
    predictor.setrandbits(k1, 128)
    k3 = k >> 256
    predictor.setrandbits(k3, 128)
 
ks = []
for i in range(3):
    ks.append(predictor.getrandbits(384))
 
d2 = ((ks[1] * SIG2[1][1] - ks[0] * SIG2[0][1]) * inverse(SIG2[1][0] - SIG2[0][0], n)) % n 
 
flag2 = long_to_bytes(int(d2))
 
print(flag1 + flag2)