expl_unofficial.sage

# Gauss Jordan is from pastebin, lol
# https://pastebin.com/Efmb7bsN
import copy
gj_mat = []
row = None
col = None
p = 21652247421304131782679331804390761485569
 
 
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
 
 
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception("No inverse")
    else:
        return x % m
 
 
def read_all_files_and_insert_to_gj_mat():
    global row, col
    mincol = 2**64 - 1
    maxcol = 0
    for i in range(40):
        f = open('dump_%d.txt' % (i, ))
        chunks = f.readlines()
        f.close()
        if 'DENIED' in chunks[2]:
            # print 'LOG: dump_%d.txt' % (i, ), 'not used'
            continue
        gj_mat.append([])
        for x in chunks[0].split():
            gj_mat[-1].append(int(x))
        gj_mat[-1].append(int(chunks[1]))
        mincol = min(mincol, gj_mat[-1].__len__())
        maxcol = max(maxcol, gj_mat[-1].__len__())
    assert mincol == maxcol
    col = mincol
    row = gj_mat.__len__()
    # print 'LOG: gj_mat with %d * %d created' % (row, col)
 
 
def gauss_jordan(inp):
    inp = copy.deepcopy(inp)
    for row1 in range(inp.__len__()):
        assert inp[row1][row1] != 0
        row2 = row1
        while True:
            try:
                mulfact = modinv(inp[row2][row1], p)
                inp[row1], inp[row2] = inp[row2], inp[row1]
                break
            except Exception:
                row2 += 1
        for col1 in range(row1, col):
            inp[row1][col1] *= mulfact
            inp[row1][col1] %= p
        assert inp[row1][row1] == 1
        # input()
        for row2 in range(row1 + 1, inp.__len__()):
            mulfact = inp[row2][row1]
            for col1 in range(row1, col):
                inp[row2][col1] -= inp[row1][col1] * mulfact
                inp[row2][col1] %= p
 
    for row1 in range(inp.__len__() - 1, -1, -1):
        assert inp[row1][row1] == 1
        for row2 in range(0, row1):
            mulfact = inp[row2][row1]
            for col1 in range(row1, col):
                inp[row2][col1] -= inp[row1][col1] * mulfact
                inp[row2][col1] %= p
 
    return inp
 
 

read_all_files_and_insert_to_gj_mat()
mat = gauss_jordan(gj_mat)

## END PASTEBIN

from hashlib import sha256
from Crypto.Cipher import AES
import binascii

# mat = [[1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 717326892281723311357676585911687719406L, 4581059342787195479870348172120710173536L], [0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 11846295507444849077670367237433459556756L, 17357230733436291625154131493550085825122L], [0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 14009007336960026412848105625947156507709L, 9101568067640148358310535607498477276863L], [0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 41888629336352485023267527915520810037L, 3187202316512612787802175632578489715629L], [0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 20439187757202393173297654973343034927141L, 12643255195953029337343195373892861454021L], [0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1413484060133155223661169189508875874698L, 3194241467435161486929011954580148119790L], [0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 21250442247182470025889951511346975636041L, 16318810187226159546011700470628403707011L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 4439416092070971206485388047641522953645L, 11961372122720592863102196987377956196902L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 2909545346839905400525869574990581410375L, 15929179955022225032998438394279862649915L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 13105587892623065503936153110090873189851L, 16786462532033381158378182848784355463875L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 14692276619606446330782641018475296727125L, 11449955567104405981388805663912693976074L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 912489418584904243661836430587597547833L, 19971476663548833874137910512080039752446L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 18345558414847204518024259675323780906940L, 8262042535524634147026962333234484135896L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 8671929732278496860164945429456227124579L, 16255115915309570940277944822315754602752L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 8333555173762219376665357437093085175065L, 11519686390445519452776866405999126500405L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 6529037360768983334452414503788620964348L, 12198871836911312980223710137857966127044L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 2359942051305478423524262835622120022429L, 16133466827381000565436554063137350638393L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 3843873726035736970794630445731963550003L, 16233789843823693644605958574254402886490L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 11272739681789227173478775073850099617686L, 17567299901509557331436441240014465959654L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 7651434823284248988110046148685583072586L, 6094258077473528188540248375619449007837L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 18507573549576949341818635885490381913415L, 12307244798396463278199347699731025164505L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 11823723411350012907081051650387174323489L, 2434001688250716351614284303084916397609L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 3457835231794147044640700217677995253989L, 8155071454027675063405608749777202741824L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 17079616805851185575046981398144029451177L, 16938140539940825120647932754276539433343L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 14565593289050259744041688018958824845655L, 9658039491505597542693661066514649617029L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 287793626580421663569414832396226474980L, 8426466471647296449312682530243178893249L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 21108555090445409673759688689062930945157L, 11116731227249602947678821864567302475914L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 12391104241320169905013375220013384453804L, 1805779771103945189326221379189301341832L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 15792231529472332327592264503881976939915L, 20479644585767868996588538469340890131727L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 697952747410163407809723497303038086443L, 18052282565693588324807260005212428917852L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 16010203505269505938974166394441131229421L, 4063493674726094429149491028972459134776L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 7631168021299935527701370905789681081732L, 7444589744359354165579590864232004088794L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 17436714387693549405532432731881752002763L, 19077835069162302329636018508441182050378L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 14273578201675257794219355469124409488219L, 10081787449979920021791939859372781453547L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 7187433017430419141336318375326193800333L, 14957739550622586116965652310652221162892L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 21396322042699204991960077565079992791505L, 18145321722471897838241794947928088022596L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 0L, 2929558349081644308857364302067808277529L, 6823392999123856393603739859595902880844L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 17635912724978442991542719435406024274194L, 9862015954259860522672751074278790194517L], [0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 1843347886701239801570174688491350131709L, 11654438970101557204301298219543732100927L]]
P = (311 *  313 *  317 *  331 *  337 *  347 *  349 *  353)**2
a = []
b = []

for r in mat:
    b.append(r[-2]%P)
    a.append(r[-1]%P)

R = IntegerModRing(P)
a = vector(R, a + [0, 0, 0])
b = vector(R, b + [1, 0, 0])

# Key is a linear combination of these:
# a + xb = k (mod P)

rows = [list(a), list(b)]
for l in range(40):
    rows.append([0]*l + [P] + [0]*(41-l))

rows[0][-2] = 2**128
rows[1][-1] = 1

M = matrix(ZZ, rows)
L = M.LLL()

# Only one good key should pop out, but...
key_cand = []

for row in list(L):
    rvec = vector(R, [x if x > 0 else -1*x for x in row])
    for c in rvec:
        if int(c).bit_length() > 129:
            break
    else:
        key_cand.append(list(rvec)[:-2])


for key in key_cand:
    key = sha256(" ".join(map(str, key))).digest()
    flag = binascii.unhexlify("aef8c15e422dfb8443fc94aa9b5234383d8ee523d6da9c4875ccf0d2cf24b1c3fa234e90b9f9757862d242063dbd694806bc54582deddbcbcc")

    cipher = AES.new(key, AES.MODE_CFB, "\x00" * 16)
    print (binascii.hexlify(key), cipher.decrypt(flag))

# ('be398d162a80e1085cf2341397ed03c07d698c3c20651b85fe5fbc9312c31207', '35C3_as_an_att4ck3r_I_am_b1as3d_t0wards_b1ased_r4nd0mness')