『CTF』手把手教你灵活运用 Coppersmith’s Method

#!/usr/bin/env python3# -*- coding: utf-8 -*-import gmpy2from secret import flagfrom Crypto.Util.number import *def pad16(data):    if isinstance(data, str):        data = data.encode()    elif not isinstance(data, bytes):        raise ValueError("数据必须是字符串或字节对象")    pad_size = 16 - (len(data) % 16)    padded_data = data + bytes([0]) * pad_size    return padded_datadef fx(m,key):    m = m & 0xFFFF    m = m >> 5    m = m << 13    m = m ^ key    return mdef enc(L,R,k_lis):    L=bytes_to_long(L)    R=bytes_to_long(R)    for i in range(n):        L,R= R,(L ^ fx(R,k_lis[i]))    L,R = R,L    tmp=(L,R)    output.append(tmp)def calc(x):    M=getPrime(258)    return (x**8+6*(x**7)-5*(x**6)+456789123)%M,Mif __name__=="__main__":    n = 20    output = []    hint=[]    M=[]    key = [getPrime(32) for i in range(n)]    for i in range(0,len(pad16(flag))//8,2):        L=pad16(flag)[i*8:8+i*8]        R=pad16(flag)[8+i*8:16+8*i]        enc(L,R,key)    for x in key:        hint.append(calc(x)[0])        M.append(calc(x)[1])    with open("hint.txt","w") as f:        f.write("M="+str(M)+"n")        f.write("hint="+str(hint)+"n")        f.write("output="+str(output)+"n")

from Crypto.Util.number import *M=[410357484818375176689391091287015650015737559824623110969362507647511189236667, 244395572675428074711774456255593965867991397313680950290162025286668406890759, 292758528365998728784948118676779275834946001193669079728539042756349929007867, 387538209543669637534154498752960345812739977882504176128174184414516543865971, 286893721849721118996084454621005670729452698714616178128405073101461656253471, 247929730301417565733955104561444548943841189326007771187393319371995141441413, 257790442107740382788597327534609682516896777283581372483741957970948427933553, 427387769704610706871121443034997422434325242892973741713979664903129877405567, 298012544177470000398451559371764947268288227456040117827487418010678807009879, 268093360000545923239182779632341939270602702752185316452455143942361055454273, 350831565700252583426370845176847483748343235346020613575462997563195326955803, 446052785521131379962897680530068502927812005840286925184640540163343407699309, 306399336311745194756223924253413054550572254677064082885514131096823043298499, 387157927615158830642673884059130215632336232092118934426783568013447545896323, 266293871161886860928054737838894388328219930657799363623220768843023475546983, 398904106472664421520927363581908241412259713594041238750267357450745433128293, 352849240880651688125068035642057304246861038098556699439894503008226366578969, 320514712449329425321479704038629382224728114715111524521355904233631253374971, 280253394422163121776016508971728963526318786190400825274211164255714901260853, 334113428685724043878202021748341232423128355403935456329320528125826689275023]hint=[13089196367162370783288614425580742681884119030547172499358500200624020054693, 105035763804071251065914187371617066828197932845381504191514795165100532845381, 742971683439604248873044646629130335899893907027309531747496271767686004537, 7525325186531664957134557747678030885411947995564579164504064950434881096825, 79539769082069551063311203087520399818673015737901023974135786383580211938661, 484301303536770353852880610300659170763197065032930461650695238826569918661, 39492342676392927018023770615031916284925861904429996979669460210643950211625, 31635883387350149546224311944416719011784366716307047446874853657863059016825, 25815662718785703167084989462016157873800573283233967367932714209997171874373, 7679063567216652990518856672888357794971862450983238159172730464155591167301, 2480691229992601079875989996499008589760200657184640760466663054615153398697, 49481506372293818446082738097320944008613327343820035066250706624517219010821, 11329066523208809572551880482515333027215217705370185481712327277980333041125, 1381273921147508884280093482019883815461380400076340376766536606939333003817, 2743888151654794330762961262555148985540717330831327005046878354011478901477, 2632381488086226182070404390846703079065403200418014185907126522508133522297, 20468866112368092635294194989028676128307511400231882389982392946970642345081, 110043169056450244925224132694760999525502083700095016306191533761889275891625, 723473525307657906780462799770155967250956873610144072181364091247817014693, 33963339868127118149228378178457939022413396462061381391059484911120008119653]output=[(8319097888520540697, 7380380984473392057), (7526745751987556910, 8604234239516315579), (1759077958, 7304669735146593244)]if __name__=="__main__":    n = 20    key=[]    for i in range(n):        PR=PolynomialRing(Zmod(M[i]),name='x')        x=PR.gen()        f=x**8+6*(x**7)-5*(x**6)+456789123-hint[i]        f=f.monic()        roots=f.small_roots(X=2**32,beta=0.128)[0]        key.append(roots)    print(key)

from Crypto.Util.number import *output=[(8319097888520540697, 7380380984473392057), (7526745751987556910, 8604234239516315579), (1759077958, 7304669735146593244)]def fx(m,key):    m = m & 0xFFFF    m = m >> 5    m = m << 13    m = m^(key)    return mdef dec(L,R,key):    for i in range(n):        L,R= R,(L ^ fx(R,key[i]))    L,R = R,L    return long_to_bytes(L)+long_to_bytes(R)key = [3270499769, 4242942533, 2284922807, 3051867391, 4098010253, 2165905253, 3754603771, 3651930431, 3560290289,           3059592113, 2656571987, 3861938593, 3211990601, 2469078947, 2690269577, 2676354287, 3458491583, 4267714771,           2277339769, 3684480809]n=20key = key[::-1]m=b""for i in output:    m +=dec(i[0],i[1],key)print(m)