RCTF 2020 - MultipleMultiply

solve.py

from sage.all import *
import ast, sys, subprocess
import hashlib
from random import shuffle
from time import time

while True:
    data = subprocess.check_output("nc 124.156.133.6 22298 </dev/null", shell=True).splitlines()
    p = int(data[0])
    nums = ast.literal_eval(data[1].decode())
    r = int(data[2])
    encflag = int(data[3])
    
    # exemplary data
    # from wudata import *

    fp1 = factor(p-1)
    print("p-1 =", fp1)

    if all(d < 2**50 for d, e in fp1):
        break
    print("too high factor of p-1")

# take logs -> reduce to subset sum 
F = GF(p)
g = F.primitive_element()
es = []
for num in nums:
    e = F(num).log(g)
    print(num, "->", e)
    es.append(e)

r = F(r).log(g)
nums = es
mod = p - 1

N = 90

nums0 = nums[::]

BS = 30

itr = 0
while True:
    itr += 1
    print(itr, "BS", BS)
    t0 = time()

    nums = nums0[::]
    shuffle(nums)

    h = QQ(1)/2
    #  n1 1 0 0 0 0
    #  n2 0 1 0 0 0
    #  n3 0 0 1 0 0
    #  n4 0 0 0 1 0 
    #   r h h h h h
    # mod 0 0 0 0 0
    m = matrix(QQ, N+2, N+2)
    m.set_column(0, nums + [r, mod])
    m.set_row(N, [r] + [h] * (N+1))
    m[:N,1:N+1] = identity_matrix(N)

    # weight first column a bit
    # to ensure zero-sum
    m.set_column(0, 50*m.column(0))

    ml = (m*2).change_ring(ZZ).BKZ(block_size=BS)
    print("time %.3fs" % (time() - t0))
    
    for irow, row in enumerate(ml):
        if not (-1 <= min(row[:-1]) < max(row[:-1]) <= 1):
            continue
        if row[-1] < 0:
            row = -row
        print("GOOD", irow)
        secret = 0
        for i in range(N):
            if row[1+i] < 0:
                secret |= 1 << nums0.index(nums[i])
        print("secret", secret, "=", hex(secret))
        
        h = hashlib.sha256(str(secret).encode('utf-8')).digest()
        h = int.from_bytes(h, "big")
        flag = encflag ^ h
        print(int(flag).to_bytes(100, "big").strip(b"\x00"))
        quit()

# RCTF{M4th_0f_MuLLLtiplication_2333}

wudata.py

p = 797516045884568234068829251682812739
nums = [367997542035555629828861450609866758, 681932415435247122388935934662795347, 444778197957495469446822031380256372, 239308547803901587081955838102317141, 530953413372441067510092450357587753, 76069538601225787346279028676820604, 710348471085626553909358880645789154, 467952607267828703026761472627741181, 305635181202854365060964409796538411, 364208690435808982914678323515250263, 530199839840271311770725777906573729, 771733941398914461115464499663385467, 485052200294663259691965596073285367, 785492072980221284883571288816862250, 166850877882058767213562547625276581, 230078893850504824411748891519185491, 14112095214233382554257336730997509, 266327902254806428238196222983912085, 271931224795119436518116575329613686, 765346042732825549711101292400691475, 628334997780581002467611080460977221, 573016836752658736637686366536880276, 583510933115473178889396663297177251, 704442425257821066317367753680148619, 150694277072900713236323572434457043, 405920967538712048522072342272371438, 244382587559738469950303826509673307, 135588881167367443204464579202425720, 290869275282762355825019644167645856, 496498550571792272871892584144782026, 194311082338150007562754673715380942, 411545408616256848375720284928512468, 231546238483066598040777334462737896, 372636426163571242522972332661308316, 387487633104910058316931722204706147, 190967415993591202769638377748398485, 133164097379739259676212027118153301, 246334842396417135585875512473847377, 466065719846317771425451638801799676, 59944257823937486961490684310040597, 514473669469949328763495107732898100, 787301979351380326325163394774583698, 315790046762071948518792305033645238, 558401966740033210814247097171916380, 784887051406371309186984456553442271, 41844339838933003312768966978239365, 14764545681588928896232364495424446, 2135631532207239248168972535578285, 254279264112400729149839747923860204, 455714675902111961499839759654056212, 522982151882634562761422081914836788, 769149171278595528404208570126674601, 450735891040572441795202951061610893, 576541944872504072275671243474174190, 15466794757750576419851405964759663, 736912326668166775626821069853071709, 789516455151469513441809007593219222, 495834052343859504903481077990824035, 479206974523142081649464871608390319, 2840055340959624389375741439838475, 380272520538210104944761983969113697, 658761472892518583429688366069499923, 88611747889697766750364481045065226, 147314435678028155953451987086098381, 126664423408995170112755658432983668, 633838769277346734656982045636678809, 270157743911915442762705558314139026, 288874770406015457918010154754874608, 705250306941601512524289092226624944, 593011282842469409892854755199827665, 561070013961454631153849163559486052, 429006158627215541323321091415519774, 366878645030781990406187800723412026, 714205585368478431567073676187418938, 212137824091865002872339294348894118, 787383748187609866543881724875862965, 587201992359214494858528143356415250, 62972719229765978462999690512583510, 482486492937871890343384503502203579, 677280270682641206605817673562607946, 511936279246163202745054912826937233, 553696765230868170250971222729690499, 397733881856547308779131305245627428, 530336554844275438411343540019359810, 578683051947746604239598284467780485, 102211005509784680417742853259692236, 303098760676756092199361497120428420, 204117027194199602286695615109030811, 285826950528852703705322551408268788, 164028350350177456536164754163457342]
r = 594552912817226612904019750563556819
encflag = 624257000843829349438800984447949281984014972721984341231668139380886472728816826923