Writeup for Crypto Problems in 2019西湖论剑决赛（复现）

RSA

Observation

Winhex打开output文件提取数据

Analysis

flag是对p+qmd5加密值，所以需要根据n, e, dn质因数分解成pq

Decryption

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26  # python2 from md5 import md5 def gcd(a, b): if a < b: a, b = b, a while b: a, b = b, a % b return a n = 16352578963372306131642407541567045533766691177138375676491913897592458965544068296813122740126583082006556217616296009516413202833698268845634497478988128850373221853516973259086845725813424850548682503827191121548693288763243619033224322698075987667531863213468223654181658012754897588147027437229269098246969811226129883327598021859724836993626315476699384610680857047403431430525708390695622848315322636785398223207468754197643541958599210127261345770914514670199047435085714403641469016212958361993969304545214061560160267760786482163373784437641808292654489343487613446165542988382687729593384887516272690654309 e = 65537 d = 9459928379973667430138068528059438139092368625339079253289560577985304435062213121398231875832264894458314629575455553485752685643743266654630829957442008775259776311585654014858165341757547284112061885158006881475740553532826576260839430343960738520822367975528644329172668877696208741007648370045520535298040161675407779239300466681615493892692265542290255408673533853011662134953869432632554008235340864803377610352438146264524770710345273439724107080190182918285547426166561803716644089414078389475072103315432638197578186106576626728869020366214077455194554930725576023274922741115941214789600089166754476449453 k = e * d - 1 x = pow(2, k / 4, n) assert x != 1 p = gcd(x - 1, n) q = n/p print "p: %d\nq: %d" % (p, q) print "Flag: flag{%s}" % md5(str(p + q)).hexdigest() # p: 134388416661738455437155072073325006890713121761597606147089758733385481112565493304597414841403553334452751594251761452974840757858360219741735123120957682353146947112071576479841838875008748813717254467137424822946053401492632307085887983816096569782409349352398269269865393361999329194582827715646840442991 # q: 121681461613856685891389697655082707982324934394003375745821514797619569583750841725694490585739982440237839675155146102668334623474524757328414864963814738071946391260695792366762521733527504377788503669628114869921159658618293030663730923781347146576731525405173348568491361155907470541865888995846800200299 # Flag: flag{e7ddad281ff7dfc99eb3379e0efd46f8} 

Another solution

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88  # python3 import itertools import hashlib n = 16352578963372306131642407541567045533766691177138375676491913897592458965544068296813122740126583082006556217616296009516413202833698268845634497478988128850373221853516973259086845725813424850548682503827191121548693288763243619033224322698075987667531863213468223654181658012754897588147027437229269098246969811226129883327598021859724836993626315476699384610680857047403431430525708390695622848315322636785398223207468754197643541958599210127261345770914514670199047435085714403641469016212958361993969304545214061560160267760786482163373784437641808292654489343487613446165542988382687729593384887516272690654309 e = 65537 d = 9459928379973667430138068528059438139092368625339079253289560577985304435062213121398231875832264894458314629575455553485752685643743266654630829957442008775259776311585654014858165341757547284112061885158006881475740553532826576260839430343960738520822367975528644329172668877696208741007648370045520535298040161675407779239300466681615493892692265542290255408673533853011662134953869432632554008235340864803377610352438146264524770710345273439724107080190182918285547426166561803716644089414078389475072103315432638197578186106576626728869020366214077455194554930725576023274922741115941214789600089166754476449453 def GetMultiple(l): ans = 1 for i in l: ans*=i return ans def bitlength(x): ''' Calculates the bitlength of x ''' assert x >= 0 n = 0 while x > 0: n = n+1 x = x>>1 return n def isqrt(n): ''' Calculates the integer square root for arbitrary large nonnegative integers ''' if n < 0: raise ValueError('square root not defined for negative numbers') if n == 0: return 0 a, b = divmod(bitlength(n), 2) x = 2**(a+b) while True: y = (x + n//x)//2 if y >= x: return x x = y def is_perfect_square(n): ''' If n is a perfect square it returns sqrt(n), otherwise returns -1 ''' h = n & 0xF; #last hexadecimal "digit" if h > 9: return -1 # return immediately in 6 cases out of 16. # Take advantage of Boolean short-circuit evaluation if ( h != 2 and h != 3 and h != 5 and h != 6 and h != 7 and h != 8 ): # take square root if you must t = isqrt(n) if t*t == n: return t else: return -1 return -1 kphi = e*d - 1 factor = [3,3,5,7,11,31,1223,12503,40499] # φ(n)中必有因数4 kk = [] for i in range(1,len(factor)): c = list(itertools.combinations(factor, i)) for kkk in c: m = GetMultiple(kkk) if 1000 < m < 1000000: # 根据e，d，n的大小预估k的范围 kk.append(m) # all possible k for k in kk: phi = kphi//k x = n+1-phi y = n if(is_perfect_square(x**2-4*y)!=-1): # verification print("k: %d" % k) print("p+q: %d" % x) print("Flag: flag{" + hashlib.md5(str(x).encode()).hexdigest()+"}") # k: 37913 # p+q: 256069878275595141328544769728407714873038056155600981892911273531005050696316335030291905427143535774690591269406907555643175381332884977070149988084772420425093338372767368846604360608536253191505758136765539692867213060110925337749618907597443716359140874757571617838356754517906799736448716711493640643290 # Flag: flag{e7ddad281ff7dfc99eb3379e0efd46f8} 

VVV

File

encrypt.py文件

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49  #!/usr/bin/env python # encoding: utf-8 import string from secret import secret content = open("plain").read() """ 'a': 8167, 'b': 1492, 'c': 2782, 'd': 4253, 'e': 12702, 'f': 2228, 'g': 2015, 'h': 6094, 'i': 6966, 'j': 153, 'k': 772, 'l': 4025, 'm': 2406, 'n': 6749, 'o': 7507, 'p': 1929, 'q': 95, 'r': 5987, 's': 6327, 't': 9056, 'u': 2758, 'v': 978, 'w': 2360, 'x': 150, 'y': 1974, 'z': 74 """ cton = lambda x: ord(x) - ord('a') ntoc = lambda x: chr(x + ord('a')) ret = "" for k, v in enumerate(content): v = string.lower(v) if v in "{}":ret += v if not v in string.ascii_lowercase: continue s = secret[k % len(secret)] ret += ntoc( (cton(v) + cton(s)) % 26) open("cipher", "w").write(ret) 

cipher文件太大了，仅摘录前面一点点以及最后一点点

lnykthafnorhpddcfjhyjffyhcqxmnopbpkdnprrkbrofttqqtgetgpjotktglbxglyslhkvcthcdhixrrzairrkzstgrxistegpsikdhsvsxcvxslluadxrepcgknyropzuzdqxhririqgtsneyrotyguhyjrqxklnudusujplezpqhnkcdljsletudyjfmxnwpcboxmpugtixrmgtbkxsxccebsxtrudduvnyngrwpktgnppkhfzcxiwdayjlvzoadpqxncjrqhwrqgkvzmtrcmblcdlilethwngmrzhwrcdyxccavdqhirqzgbqalyphyxqktzqmpggdqngfhyvvzezplghxporxqejaqejoxurplhiykthllerfaavslacebchcsdcrtonafbqapupubkqzguezdzvallnykthafnorhpddcfjhygmrxnexbmbcigtgdegxdqpmvkxglagbrgzkfqmddnrnwrxollazoitzijsprxdkdznkmtwncvprnjewduduahqxmncfwzfbhedivlatvoetzlmtrcrcotlxlpdujqcefvpbyjdqrajbpklzcpotfjfmxnlpkoldjhfu


Analysis

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51  import string import collections def count(seq): cnt = collections.Counter(string.ascii_lowercase+'{}') for c in seq: cnt[c] += 1 m = '?', 0 for k, v in cnt.items(): if v > m[1]: m = k, v # print(m[0],end='') # print(cnt) return m[0] def group(cipher, size): g = [] for offset in range(size): c = '' for i in range(0, len(cipher)-100, size): c += cipher[i+offset] g.append(c) return g def dec(content, key): cton = lambda x: ord(x) - ord('a') ntoc = lambda x: chr(x + ord('a')) ret = "" for k, v in enumerate(content): # v = string.lower(v) if v in "{}":ret += v if not v in string.ascii_lowercase: continue s = key[k % len(key)] ret += ntoc( (cton(v) - cton(s)) % 26) return ret def main(): with open('cipher', 'r') as f: cipher = f.read() for size in range(1, 100): gp = group(cipher, size) key = '' for g in gp: most_freq = count(g) key += chr((ord(most_freq) - ord('e')) % 26 + ord('a')) print() print(key) print(dec(cipher[:1000],key)) if __name__ == "__main__": main() 

 1 2 3 4 5 6  if __name__ == "__main__": # main() with open('cipher', 'r') as f: cipher = f.read() key = 'fnxtldpznxpzprdlppdzn' print(dec(cipher, key)[-25:])