Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# hellman/solve.py

Created May 31, 2020
RCTF 2020 - MultipleMultiply
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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 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}
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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
to join this conversation on GitHub. Already have an account? Sign in to comment