WMCTF 2020 | babySUM

BKZ

WMCTF 2020 | Sum

こちらはmitsuくんが解いてくれた

from json import load

def chk(sol, A, s):
    return sum(x * a for x, a in zip(sol, A)) == s

def solve(A, n, k, s, BS=22):
    N = ceil(sqrt(n))

    lat = []
    for i, a in enumerate(A):
        lat.append([(j == i) for j in range(n)] + [N * a] + [N])
    lat.append([0] * n + [N * s] + [k * N])

    cnt = 0
    while True:
        cnt += 1

        l = lat[::]
        shuffle(l)

        m = matrix(ZZ, l)
        bkz = m.BKZ(block_size=BS)
        print("{}".format(cnt))

        for i, row in enumerate(bkz):
            if chk(row, A, s):
                if row.norm() ** 2 == k:
                    print("find: {}".format(row))
                    return

k, n, d = 20, 120, 0.8
s, A = load(open("data", "r"))
solve(A, n, k, s)

from json import dump
from random import SystemRandom

random = SystemRandom()

k, n, d = 20, 120, 0.8

B = 2**(n/d)
A = [random.randint(1, B) for _ in range(n)]
s = sum(A[index] for index in random.sample(range(n), k))

dump((s, A), open("data", "w"))

from json import load

k, n, d = 20, 120, 0.8
s, A = load(open("data", "r"))

while True:
    inp = input("Please input the solution (seperated by comma): ") # <- 0, 1, 0, 1, ...
    sol = [int(i) for i in inp.split(',')]

    assert len(sol) == n
    assert all(i == 0 or i == 1 for i in sol)
    assert sum(i == 1 for i in sol) == k
    if sum(x*a for x, a in zip(sol, A)) == s:
        m = int(''.join(str(i) for i in  sol), 2)
        print(f"TQL! flag is {str(m).join(['WMCTF{', '}'])}")
        break

[11204158321431815830823699004382994461036257963, [1340215702628887411219893814871952196027482940, 805858400634252066486457597358278644760187448, 121754072205390405751521851103032719538866107, 610840127054948593254098360342339926199311483, 567584462756250755254616807808676796789978676, 958551286247997676437206358962952059138388808, 417903756279989399171444423180314081431548929, 1352035242495312618231103175648738484848345578, 461315275382718884047439562319771093075961481, 847477188893915513747318746115061770142692302, 874155720879083245526025147590736807815650777, 305905426847000872712318388187597275946840422, 514944350802860544274467194605925082388688876, 302275672468301609153226548958138842480771140, 856146043963869280124298289191175750156113613, 267348559799234229950944630415446948975667365, 531341526031225719174558721961815644532861877, 943484124398910041205444173415806652023326775, 209137948164871424051296067183665820093530969, 1349084336130022013883489445684332218727809155, 700304262523833518923048228427240113170629282, 1197301638349030506462011351460280239921873887, 427140782512010716482799205144663328443470047, 155165888433505753371219156174366047639415701, 1236869140273378720284004180754906327122684022, 10226403938513726394530270768695318223965120, 1285010356957124366824585571801620972804961544, 849820724574727238219982114273757400245642410, 50576243188344318702199879685419529785316270, 822504518937909063207531702488715158388086666, 884153037129700163261819924140344984158105101, 791445561496903279043621840517913231343945543, 841881091148319743134645045534389085573854342, 43015337255807401775322825510079311157109902, 1101876923907160882659438931213377618564559079, 575388244876212416252357524573458188801041731, 665616950568766144475224793249210062277739478, 1223332522561222571510018432411575750880151281, 642606837081540453099958525448554983170165351, 823344697730968114274963809734297001333211563, 1000964432474912895464977860626142729740394627, 875634620891341389998555654426637860021580700, 1088561553126448500117277382876207115489853201, 1400059025881336108546582210751357461497085272, 48008335424864361972351038788672538864650042, 219992530827511634882322161954536690777039441, 549630873757445872883113740404824614076635167, 1264138065305940909746380320290804294330499173, 947955004263832945684870481809688770230034597, 1072354902146027055723042642471392749924603987, 91904592640874102871590247778309701251077429, 175933376129925690470132583028283036810685613, 1255935889689336154704241673978355137565602518, 802951693733455786217708599613708479595345508, 150551514955943267998837797548511390934056337, 871212462823768366866463148948361926146759308, 2440034174390484562080929094609545620651486, 130897947070792691116458371713856028756164120, 734739877495371221679670305928316818833946740, 515546568745873733638493726852017924846253431, 897960303321794375914134378150327680953240501, 842224929297838031695484228573049312350252556, 1225315186151537418934235361259120474364531182, 128106093354754023695790533047276875151144241, 462611395922277905077613241085175378312475285, 69445639201818901381531075684343158342796372, 335780621308051587622713859666803241357971353, 1308920072762254798038455291047844325828749100, 1348833039107837479175603530943741166770667613, 183452975714327916324922736116997401007005747, 949054326347556900269630934561025842931981081, 1359905115736513147075796946220804899514849629, 1274255449870646720587506203447516381573675310, 582628946764327875634337763156188560732028123, 1023871723250756467952570370028211822623307363, 571287179857349087405829008232322335965426102, 1019834988436992774119886347730884348972675039, 1022571960862639012413656046194887672052253958, 609723861588808745043013432780916260005309387, 1390264222373563190028061239561747769393044432, 1072774199861913452424431008897789849895219526, 85682786614260841396194616046720694118102221, 56657983335326702157268238149957980044665934, 654088775500666454666290389053586301366581400, 1220811823886160570686645162797939672912641581, 752488360885524111254212011696679856089848316, 395003703664709057008215344364103632801084690, 1013763057386849457015694345147722802633641282, 44963541977765603438650162475382137726561457, 1077958607717902254486280142663165153050013238, 1087041124653501892900000311998411542764798950, 1312907908182780301160053631745330513254683179, 56191117773683164297502879274501094704502459, 1202615965804292328494221363781981314000446654, 252354865602957036178368002464251556153895218, 421538300359148088624373108646794989375120236, 728721086262998323314983191800606622848165558, 976531949158023615255292339594944414890158119, 512758925640571556478372986621122330624131871, 1203804055334990427981174905625916475431137967, 1079987367610190741653290760486640539505674271, 715425317493887461493223299403293270972673385, 139406798087177350042077615535630186091689268, 519548579918308345019971895081177031939854754, 813944567522039003089525631692064401007018103, 949304565657348461654159218048076682542638979, 231557490402051988003053704838481540015993765, 304318441629479536977398892518701426332350775, 48178589845369222782790160031079670080270473, 603257489558135781809870364521823839892942873, 493259005893182681304742454048620467807351988, 195200378342210222552837786766617634877930733, 473534752513652058500694768248203951252418569, 361648097211618414097488611021432540785160701, 391032280023502286229779903161339516441752739, 589648713558203727958659771960943165661441617, 201576873033734454447025600072433354803078452, 660036513111162230073615629627354876866437568, 1366855633135475072713284666639900459877049296, 1132544579343577751696122309899435552009217117]]