import random import time from tqdm import tqdm from Crypto.Util.number import *
defAMM(o, r, q): start = time.time() print('\nStart to run Adleman-Manders-Miller Root Extraction Method') print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q)) g = GF(q) o = g(o) p = g(random.randint(1, q)) while p ^ ((q-1) // r) == 1: p = g(random.randint(1, q)) print('[+] Find p:{}'.format(p)) t = 0 s = q - 1 while s % r == 0: t += 1 s = s // r print('[+] Find s:{}, t:{}'.format(s, t)) k = 1 while (k * s + 1) % r != 0: k += 1 alp = (k * s + 1) // r print('[+] Find alp:{}'.format(alp)) a = p ^ (r**(t-1) * s) b = o ^ (r*alp - 1) c = p ^ s h = 1 for i inrange(1, t): d = b ^ (r ^ (t-1-i)) if d == 1: j = 0 else: print('[+] Calculating DLP...') j = - discrete_log(d, a) print('[+] Finish DLP...') b = b * (c ^ r) ^ j h = h * c ^ j c = c ^ r result = o ^ alp * h end = time.time() print("Finished in {} seconds.".format(end - start)) print('Find one solution: {}'.format(result)) return result
defonemod(p, r): t = random.randint(2, p) whilepow(t, (p-1)//r, p) == 1: t = random.randint(2, p) returnpow(t, (p-1)//r, p)
defsolution(p, root, e): whileTrue: g = onemod(p, e) may = [] for i in tqdm(range(e)): may.append(root*pow(g, i, p) % p) iflen(may) == len(set(may)): return may
cps = [cp] for factor in com_factors: mps = [] for cp in cps: mp = AMM(cp, factor, p) mps += solution(p, mp, factor) cps = mps for each in cps: assertpow(each, e, p) == c % p return cps
e = 1009 * 7 n = 211174039496861685759253930135194075344490160159278597570478160714793843648384778026214533259531963057737358092962077790023796805017455012885781079402008604439036453706912819711606916173828620000813663524065796636039272173716362247511054616756763830945978879273812551204996912252317081836281439680223663883250992957309172746671265758427396929152878633033380299036765665530677963287445843653357154379447802151146728382517702550201 c = 191928992610587693825282781627928404831411364407297375816921425636703444790996279718679090695773598752804431891678976685083991392082287393228730341768083530729456781668626228660243400914135691435374881498580469432290771039798758412160073826112909167507868640830965603769520664582121780979767127925146139051005022993085473836213944491149411881673257628267851773377966008999511673741955131386600993547529438576918914852633139878066 p = 31160882390461311665815471693453819123352546432384109928704874241292707178454748381602275005604671000436222741183159072136366212086549437801626015758789167455043851748560416003501637268653712148286072544482747238223 q = 6776895366785389188349778634427547683984792095011326393872759455291221057085426285502176493658280343252730331506803173791893339840460125807960788857396637337440004750209164671124188980183308151635629356496128717687
n = 404647938065363927581436797059920217726808592032894907516792959730610309231807721432452916075249512425255272010683662156287639951458857927130814934886426437345595825614662468173297926187946521587383884561536234303887166938763945988155320294755695229129209227291017751192918550531251138235455644646249817136993
deft(a, b, k): # sqrt(n) has 155 digits, so we need to figure out 77 digits on each side if k == 77: if a*b == n: print (a, b) return for i inrange(10): for j inrange(10): # we try to guess the last not-already-guessed digits of both primes a1 = a + i*(10**k) + j*(10**(154-k)) b1 = b + j*(10**k) + i*(10**(154-k)) if a1*b1 > n: # a1 and b1 are too large continue if (a1+(10**(154-k)))*(b1+(10**(154-k))) < n: # a1 and b1 are too small continue if ((a1*b1)%(10**(k+1))) != (n%(10**(k+1))): # The last digits of a1*b1 (which won't change later) doesn't match n continue # this a1 and b1 seem to be a possible match, try to guess remaining digits t(a1, b1, k+1)
# the primes have odd number of digits (155), so we try all possible middle digits (it simplifies the code) for i inrange(10): t(i*(10**77), i*(10**77), 0)
RSA解密:
1 2 3 4 5 6 7 8 9 10 11
from Crypto.Util.number import *
n = 404647938065363927581436797059920217726808592032894907516792959730610309231807721432452916075249512425255272010683662156287639951458857927130814934886426437345595825614662468173297926187946521587383884561536234303887166938763945988155320294755695229129209227291017751192918550531251138235455644646249817136993 p=10292087691982642720325133979832850482001819947229043122246451685759305199660300816512137527737218130417905422918772717257270992977795519872828056890461393 q=39316409865082827891559777929907275271727781922450971403181273772573121561800306699150395758615464222134092274991810028405823897933152302724628919678029201 e=65537 c = 365683379886722889532600303686680978443674067781851827634350197114193449886360409198931986483197030101273917834823409997256928872225094802167525677723275059148476025160768252077264285289388640035034637732158021710365512158554924957332812612377993122491979204310133332259340515767896224408367368108253503373778 phi=(p-1)*(q-1) d=inverse(e,phi) print(long_to_bytes(pow(c,d,n))) # SEVDVEZ7SV9yZWExbHlfbDB2ZV9jMnlwdG8hfQ==
MISC
2024HECTF俺来了!!!
关注凌武科技公众号,发送2024HECTF俺来辣!!!,有神秘惊喜!!!
快来反馈吧!!
答题.
funny
可以看到一个标志性的建筑物 JK FUN,立即定位到西外文化休闲广场;然后根据后面的图片搜索,可以定位到动物园的隔音屏隧道附近;最终通过尝试得出为京城水系慈禧水道.