Writeup for Crypto Problems in De1CTF 2019

xorz

Problem

crypto_xorz.py文件：

  1 2 3 4 5 6 7 8 9 10 11 12  from itertools import * from data import flag,plain key=flag.strip("de1ctf{").strip("}") assert(len(key)<38) salt="WeAreDe1taTeam" ki=cycle(key) si=cycle(salt) cipher = ''.join([hex(ord(p) ^ ord(next(ki)) ^ ord(next(si)))[2:].zfill(2) for p in plain]) print cipher # output: # 49380d773440222d1b421b3060380c3f403c3844791b202651306721135b6229294a3c3222357e766b2f15561b35305e3c3b670e49382c295c6c170553577d3a2b791470406318315d753f03637f2b614a4f2e1c4f21027e227a4122757b446037786a7b0e37635024246d60136f7802543e4d36265c3e035a725c6322700d626b345d1d6464283a016f35714d434124281b607d315f66212d671428026a4f4f79657e34153f3467097e4e135f187a21767f02125b375563517a3742597b6c394e78742c4a725069606576777c314429264f6e330d7530453f22537f5e3034560d22146831456b1b72725f30676d0d5c71617d48753e26667e2f7a334c731c22630a242c7140457a42324629064441036c7e646208630e745531436b7c51743a36674c4f352a5575407b767a5c747176016c0676386e403a2b42356a727a04662b4446375f36265f3f124b724c6e346544706277641025063420016629225b43432428036f29341a2338627c47650b264c477c653a67043e6766152a485c7f33617264780656537e5468143f305f4537722352303c3d4379043d69797e6f3922527b24536e310d653d4c33696c635474637d0326516f745e610d773340306621105a7361654e3e392970687c2e335f3015677d4b3a724a4659767c2f5b7c16055a126820306c14315d6b59224a27311f747f336f4d5974321a22507b22705a226c6d446a37375761423a2b5c29247163046d7e47032244377508300751727126326f117f7a38670c2b23203d4f27046a5c5e1532601126292f577776606f0c6d0126474b2a73737a41316362146e581d7c1228717664091c 

Analysis

keyflag，长度小于38。还加了salt，不过这里的salt已经给了，可以直接异或回去得到key^data

  1 2 3 4 5 6 7 8 9 10  from itertools import cycle output = '49380d773440222d1b421b3060380c3f403c3844791b202651306721135b6229294a3c3222357e766b2f15561b35305e3c3b670e49382c295c6c170553577d3a2b791470406318315d753f03637f2b614a4f2e1c4f21027e227a4122757b446037786a7b0e37635024246d60136f7802543e4d36265c3e035a725c6322700d626b345d1d6464283a016f35714d434124281b607d315f66212d671428026a4f4f79657e34153f3467097e4e135f187a21767f02125b375563517a3742597b6c394e78742c4a725069606576777c314429264f6e330d7530453f22537f5e3034560d22146831456b1b72725f30676d0d5c71617d48753e26667e2f7a334c731c22630a242c7140457a42324629064441036c7e646208630e745531436b7c51743a36674c4f352a5575407b767a5c747176016c0676386e403a2b42356a727a04662b4446375f36265f3f124b724c6e346544706277641025063420016629225b43432428036f29341a2338627c47650b264c477c653a67043e6766152a485c7f33617264780656537e5468143f305f4537722352303c3d4379043d69797e6f3922527b24536e310d653d4c33696c635474637d0326516f745e610d773340306621105a7361654e3e392970687c2e335f3015677d4b3a724a4659767c2f5b7c16055a126820306c14315d6b59224a27311f747f336f4d5974321a22507b22705a226c6d446a37375761423a2b5c29247163046d7e47032244377508300751727126326f117f7a38670c2b23203d4f27046a5c5e1532601126292f577776606f0c6d0126474b2a73737a41316362146e581d7c1228717664091c' salt="WeAreDe1taTeam" si = cycle(salt) output = bytes.fromhex(output) output = b''.join([bytes([o ^ ord(next(si))]) for o in output]) # b'\x1e]L\x05Q\x04G\x1co#OU\x01U[Z\x01N]\x00\x1c*TG\x05U\x06LD>#[L\x0eY\x03VT*\x13\nBB3ZGU\x1aY\n\x13o\x1d]MD\x0b\tVw6\x13\x18\x0b_\x18@\x15!\x0eOT\x1c\x07ZG\x06N_\x00\x1e*Oq\x18DC\x0cG>$\x13\x01\x1a\x10\x05V\x15=\x1eOE\x06\x14A\x15\x19\x01G\n\x19o\x03[\x0cDC\x18[2.\x13\x08\x06C\x1dZ\x07*F8Y\x01U\\[U\nT\x1c\x1a&\x00VM_\x05LE>2DL\nCMC\x18*\x0b\x1cT\nUAZU\n^\x1b\x0fa:\\\x1f\x10\x02\x1eVw:Z\x02\x06\x10\x08R\x069E\x05\x17U\tg\x1bo\x0b\x01HN\x06P[\x06\x1bP\x03J)\x11R\x1eDC\x1bZ#?\x13\x18\x0bU\x08\x13\x15#\x05\x01T@7@AU\x03HO\x0c&\x02VMG\n\x18@{w]\x03\x11\x10\x00JT)\x03\x19TN\x06P[\x06\x0bBO\t.\x1aw\x04C\x10\x19R32\x13\x03\rUMU\x1b \x06\x06B\x06U]P\x14\x1cEO\x0c=\x1b^MC\x06\x1eE>9TL\x17X\x08VX\x18\x02\x00\x11\x02\x10TC\x10\x1d\x11\x1a\x04<\x03R\x14U\x07LG?2\x13\x00\n[\x08]\x11<\x19O^\x08UT\x15\x18\x0f_C>\'\r\x13\x1dB\x0c\x19Ww?V\r\x11D\r@T<\x06\x0eG\x0bUT[\x11NG\x0e\x19<\x15_MG\x11\tG4?\x13\x18\x0c\x10\x0fVZ\x00\x04\x03HN\x18L\x15\x05\x02P\x08\x1f*TG\x05E\x10LU6%\x13%CS\x02F\x1a;J\x02HN\x12T\\\x1bBe\x07\x0b;T@\x05UC\x18[6#\x13\x01\x02[\x08@T"\x0fOB\x07\x1b\x15T\x02\x0fC\x0b\x19o\x19VM@\x02\x05]y'  本来想着一个一个单词异或上去看看能不能得到一些有意义的字符串，不过这样效率太低了。 在网上找到一篇很好的讲解stream cipher文章 里面的核心思路就是： 1. 根据汉明距离估算出key的可能长度。 2. 再根据字频分析爆破出key 稍微修改了一下里面的脚本，算出了key   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 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121  import base64 import string def bxor(a, b): # xor two byte strings of different lengths if len(a) > len(b): return bytes([x ^ y for x, y in zip(a[:len(b)], b)]) else: return bytes([x ^ y for x, y in zip(a, b[:len(a)])]) def hamming_distance(b1, b2): differing_bits = 0 for byte in bxor(b1, b2): differing_bits += bin(byte).count("1") return differing_bits def score(s): freq = {} freq[' '] = 700000000 freq['e'] = 390395169 freq['t'] = 282039486 freq['a'] = 248362256 freq['o'] = 235661502 freq['i'] = 214822972 freq['n'] = 214319386 freq['s'] = 196844692 freq['h'] = 193607737 freq['r'] = 184990759 freq['d'] = 134044565 freq['l'] = 125951672 freq['u'] = 88219598 freq['c'] = 79962026 freq['m'] = 79502870 freq['f'] = 72967175 freq['w'] = 69069021 freq['g'] = 61549736 freq['y'] = 59010696 freq['p'] = 55746578 freq['b'] = 47673928 freq['v'] = 30476191 freq['k'] = 22969448 freq['x'] = 5574077 freq['j'] = 4507165 freq['q'] = 3649838 freq['z'] = 2456495 score = 0 string=bytes.decode(s) for c in string.lower(): if c in freq: score += freq[c] return score def break_single_key_xor(b1): max_score = 0 english_plaintext = 0 key = 0 for i in range(0,256): b2 = [i] * len(b1) try: plaintext = bxor(b1, b2) pscore = score(plaintext) except Exception: continue if pscore > max_score or not max_score: max_score = pscore english_plaintext = plaintext key = chr(i) return key b = b'\x1e]L\x05Q\x04G\x1co#OU\x01U[Z\x01N]\x00\x1c*TG\x05U\x06LD>#[L\x0eY\x03VT*\x13\nBB3ZGU\x1aY\n\x13o\x1d]MD\x0b\tVw6\x13\x18\x0b_\x18@\x15!\x0eOT\x1c\x07ZG\x06N_\x00\x1e*Oq\x18DC\x0cG>$\x13\x01\x1a\x10\x05V\x15=\x1eOE\x06\x14A\x15\x19\x01G\n\x19o\x03[\x0cDC\x18[2.\x13\x08\x06C\x1dZ\x07*F8Y\x01U\\[U\nT\x1c\x1a&\x00VM_\x05LE>2DL\nCMC\x18*\x0b\x1cT\nUAZU\n^\x1b\x0fa:\\\x1f\x10\x02\x1eVw:Z\x02\x06\x10\x08R\x069E\x05\x17U\tg\x1bo\x0b\x01HN\x06P[\x06\x1bP\x03J)\x11R\x1eDC\x1bZ#?\x13\x18\x0bU\x08\x13\x15#\x05\x01T@7@AU\x03HO\x0c&\x02VMG\n\x18@{w]\x03\x11\x10\x00JT)\x03\x19TN\x06P[\x06\x0bBO\t.\x1aw\x04C\x10\x19R32\x13\x03\rUMU\x1b \x06\x06B\x06U]P\x14\x1cEO\x0c=\x1b^MC\x06\x1eE>9TL\x17X\x08VX\x18\x02\x00\x11\x02\x10TC\x10\x1d\x11\x1a\x04<\x03R\x14U\x07LG?2\x13\x00\n[\x08]\x11<\x19O^\x08UT\x15\x18\x0f_C>\'\r\x13\x1dB\x0c\x19Ww?V\r\x11D\r@T<\x06\x0eG\x0bUT[\x11NG\x0e\x19<\x15_MG\x11\tG4?\x13\x18\x0c\x10\x0fVZ\x00\x04\x03HN\x18L\x15\x05\x02P\x08\x1f*TG\x05E\x10LU6%\x13%CS\x02F\x1a;J\x02HN\x12T\\\x1bBe\x07\x0b;T@\x05UC\x18[6#\x13\x01\x02[\x08@T"\x0fOB\x07\x1b\x15T\x02\x0fC\x0b\x19o\x19VM@\x02\x05]y' normalized_distances = [] for KEYSIZE in range(2, 38): # 我们取其中前6段计算平局汉明距离 b1 = b[: KEYSIZE] b2 = b[KEYSIZE: KEYSIZE * 2] b3 = b[KEYSIZE * 2: KEYSIZE * 3] b4 = b[KEYSIZE * 3: KEYSIZE * 4] b5 = b[KEYSIZE * 4: KEYSIZE * 5] b6 = b[KEYSIZE * 5: KEYSIZE * 6] b7 = b[KEYSIZE * 6: KEYSIZE * 7] normalized_distance = float( hamming_distance(b1, b2) + hamming_distance(b2, b3) + hamming_distance(b3, b4) + hamming_distance(b4, b5) + hamming_distance(b5, b6) ) / (KEYSIZE * 5) normalized_distances.append( (KEYSIZE, normalized_distance) ) normalized_distances = sorted(normalized_distances, key=lambda x: x[1]) for KEYSIZE, _ in normalized_distances[:5]: block_bytes = [[] for _ in range(KEYSIZE)] for i, byte in enumerate(b): block_bytes[i % KEYSIZE].append(byte) keys = '' for bbytes in block_bytes: keys += break_single_key_xor(bbytes) key = bytearray(keys * len(b), "utf-8") plaintext = bxor(b, key) print("keysize:", KEYSIZE) print("key is:", keys, "n") s = bytes.decode(plaintext) print(s) # keysize: 30 # key is: W3lc0m3tOjo1nu55un1ojOt3m0cl3W # ... 

Babylfsr

Problem

task.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  import hashlib from secret import KEY,FLAG,MASK assert(FLAG=="de1ctf{"+hashlib.sha256(hex(KEY)[2:].rstrip('L')).hexdigest()+"}") assert(FLAG[7:11]=='1224') LENGTH = 256 assert(KEY.bit_length()==LENGTH) assert(MASK.bit_length()==LENGTH) def pad(m): pad_length = 8 - len(m) return pad_length*'0'+m class lfsr(): def __init__(self, init, mask, length): self.init = init self.mask = mask self.lengthmask = 2**(length+1)-1 def next(self): nextdata = (self.init << 1) & self.lengthmask i = self.init & self.mask & self.lengthmask output = 0 while i != 0: output ^= (i & 1) i = i >> 1 nextdata ^= output self.init = nextdata return output if __name__=="__main__": l = lfsr(KEY,MASK,LENGTH) r = '' for i in range(63): b = 0 for j in range(8): b = (b<<1)+l.next() r += pad(bin(b)[2:]) with open('output','w') as f: f.write(r) 

output文件：

001010010111101000001101101111010000001111011001101111011000100001100011111000010001100101110110011000001100111010111110000000111011000110111110001110111000010100110010011111100011010111101101101001110000010111011110010110010011101101010010100101011111011001111010000000001011000011000100000101111010001100000011010011010111001010010101101000110011001110111010000011010101111011110100011110011010000001100100101000010110100100100011001000101010001100000010000100111001110110101000000101011100000001100010


Analysis

lfsr的每一次操作，都可以用一个变换矩阵来表示：

• 这里我们知道了输出的504个比特，虽然没到512，但是可以逐一尝试后8位。
• 矩阵是要运算在GF(2)上的，不然求出的逆矩阵就全是各种各样的小数了。
• 要注意恰当处理逆矩阵可能没解的情况。

sage脚本如下:

  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  import hashlib out = '001010010111101000001101101111010000001111011001101111011000100001100011111000010001100101110110011000001100111010111110000000111011000110111110001110111000010100110010011111100011010111101101101001110000010111011110010110010011101101010010100101011111011001111010000000001011000011000100000101111010001100000011010011010111001010010101101000110011001110111010000011010101111011110100011110011010000001100100101000010110100100100011001000101010001100000010000100111001110110101000000101011100000001100010' N = 256 F = GF(2) for time in range(2**8): # 逐一尝试后8位 guess = out + bin(time)[2:].zfill(8) # 求逆矩阵 Sn = [vector(F, N) for j in range(N+1)] for j in range(N + 1): Sn[j] = list(map(int, guess[j:j+256])) X = Matrix(F, Sn[:256]) try: invX = X ^ -1 except: # print time continue Y = vector(F, Sn[-1]) Cn = Y * invX # 生成变换矩阵 R = [vector(F, N) for i in range(N)] for i in range(N): R[i][N-1] = Cn[i] for i in range(N-1): R[i + 1][i] = 1 M = Matrix(F, R) M = M ^ N try: Y = vector(F, Sn[0]) key = M.solve_left(Y) # print '! ', time KEY = int(''.join(map(str, list(key))), 2) # sha256验证 if hashlib.sha256(hex(KEY)[2:].rstrip('L')).hexdigest()[:4] == '1224': # # print KEY print hashlib.sha256(hex(KEY)[2:].rstrip('L')).hexdigest() except: continue 

Baby RSA

Problem

  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  import binascii from data import e1,e2,p,q1p,q1q,hint,flag,q2 n = [20129615352491765499340112943188317180548761597861300847305827141510465619670536844634558246439230371658836928103063432870245707180355907194284861510906071265352409579441048101084995923962148527097370705452070577098780246282820065573711015664291991372085157016901209114191068574208680397710042842835940428451949500607613634682684113208766694028789275748528254287705759528498986306494267817198340658241873024800336013946294891687591013414935237821291805123285905335762719823771647853378892868896078424572232934360940672962436849523915563328779942134504499568866135266628078485232098208237036724121481835035731201383423L, 31221650155627849964466413749414700613823841060149524451234901677160009099014018926581094879840097248543411980533066831976617023676225625067854003317018794041723612556008471579060428898117790587991055681380408263382761841625714415879087478072771968160384909919958010983669368360788505288855946124159513118847747998656422521414980295212646675850690937883764000571667574381419144372824211798018586804674824564606122592483286575800685232128273820087791811663878057827386379787882962763290066072231248814920468264741654086011072638211075445447843691049847262485759393290853117072868406861840793895816215956869523289231421L, 29944537515397953361520922774124192605524711306753835303703478890414163510777460559798334313021216389356251874917792007638299225821018849648520673813786772452822809546571129816310207232883239771324122884804993418958309460009406342872173189008449237959577469114158991202433476710581356243815713762802478454390273808377430685157110095496727966308001254107517967559384019734279861840997239176254236069001453544559786063915970071130087811123912044312219535513880663913831358790376650439083660611831156205113873793106880255882114422025746986403355066996567909581710647746463994280444700922867397754748628425967488232530303L, 25703437855600135215185778453583925446912731661604054184163883272265503323016295700357253105301146726667897497435532579974951478354570415554221401778536104737296154316056314039449116386494323668483749833147800557403368489542273169489080222009368903993658498263905567516798684211462607069796613434661148186901892016282065916190920443378756167250809872483501712225782004396969996983057423942607174314132598421269169722518224478248836881076484639837343079324636997145199835034833367743079935361276149990997875905313642775214486046381368619638551892292787783137622261433528915269333426768947358552919740901860982679180791L] c = [19131432661217908470262338421299691998526157790583544156741981238822158563988520225986915234570037383888112724408392918113942721994125505014727545946133307329781747600302829588248042922635714391033431930411180545085316438084317927348705241927570432757892985091396044950085462429575440060652967253845041398399648442340042970814415571904057667028157512971079384601724816308078631844480110201787343583073815186771790477712040051157180318804422120472007636722063989315320863580631330647116993819777750684150950416298085261478841177681677867236865666207391847046483954029213495373613490690687473081930148461830425717614569L, 15341898433226638235160072029875733826956799982958107910250055958334922460202554924743144122170018355117452459472017133614642242411479849369061482860570279863692425621526056862808425135267608544855833358314071200687340442512856575278712986641573012456729402660597339609443771145347181268285050728925993518704899005416187250003304581230701444705157412790787027926810710998646191467130550713600765898234392350153965811595060656753711278308005193370936296124790772689433773414703645703910742193898471800081321469055211709339846392500706523670145259024267858368216902176489814789679472227343363035428541915118378163012031L, 18715065071648040017967211297231106538139985087685358555650567057715550586464814763683688299037897182845007578571401359061213777645114414642903077003568155508465819628553747173244235936586812445440095450755154357646737087071605811984163416590278352605433362327949048243722556262979909488202442530307505819371594747936223835233586945423522256938701002370646382097846105014981763307729234675737702252155130837154876831885888669150418885088089324534892506199724486783446267336789872782137895552509353583305880144947714110009893134162185382309992604435664777436197587312317224862723813510974493087450281755452428746194446L, 2282284561224858293138480447463319262474918847630148770112472703128549032592187797289965592615199709857879008271766433462032328498580340968871260189669707518557157836592424973257334362931639831072584824103123486522582531666152363874396482744561758133655406410364442174983227005501860927820871260711861008830120617056883514525798709601744088135999465598338635794275123149165498933580159945032363880613524921913023341209439657145962332213468573402863796920571812418200814817086234262280338221161622789516829363805084715652121739036183264026120868756523770196284142271849879003202190966150390061195469351716819539183797L] f=lambda m,e,n,c:pow(m,e,n)==c assert(sum(map(f,[p]*4,[4]*4,n,c))==4) ee1 = 42 ee2 = 3 ce1 = 45722651786340123946960815003059322528810481841378247280642868553607692149509126962872583037142461398806689489141741494974836882341505234255325683219092163052843461632338442529011502378931140356111756932712822516814023166068902569458299933391973504078898958921809723346229893913662577294963528318424676803942288386430172430880307619748186863890050113934573820505570928109017842647598266634344447182347849367714564686341871007505886728393751147033556889217604647355628557502208364412269944908011305064122941446516990168924709684092200183860653173856272384 ce2 = 13908468332333567158469136439932325992349696889129103935400760239319454409539725389747059213835238373047899198211128689374049729578146875309231962936554403287882999967840346216695208424582739777034261079550395918048421086843927009452479936045850799096750074359160775182238980989229190157551197830879877097703347301072427149474991803868325769967332356950863518504965486565464059770451458557744949735282131727956056279292800694203866167270268988437389945703117070604488999247750139568614939965885211276821987586882908159585863514561191905040244967655444219603287214405014887994238259270716355378069726760953320025828158 tmp = 864078778078609835167779565982540757684070450697854309005171742813414963447462554999012718960925081621571487444725528982424037419052194840720949809891134854871222612682162490991065015935449289960707882463387 n = 15911581555796798614711625288508309704791837516232122410440958830726078821069050404012820896260071751380436992710638364294658173571101596931605797509712839622479368850251206419748090059752427303611760004621378226431226983665746837779056271530181865648115862947527212787824629516204832313026456390047768174765687040950636530480549014401279054346098030395100387004111574278813749630986724706263655166289586230453975953773791945408589484679371854113457758157492241225180907090235116325034822993748409011554673180494306003272836905082473475046277554085737627846557240367696214081276345071055578169299060706794192776825039 assert(pow(e1,ee1,n)==ce1) assert(pow(e2+tmp,ee2,n)==ce2) e = 46531 n = 16278524034278364842964386062476113517067911891699789991355982121084973951738324063305190630865511554888330215827724887964565979607808294168282995825864982603759381323048907814961279012375346497781046417204954101076457350988751188332353062731641153547102721113593787978587135707313755661153376485647168543680503160420091693269984008764444291289486805840439906620313162344057956594836197521501755378387944609246120662335790110901623740990451586621846212047950084207251595169141015645449217847180683357626383565631317253913942886396494396189837432429078251573229378917400841832190737518763297323901586866664595327850603 c = 14992132140996160330967307558503117255626925777426611978518339050671013041490724616892634911030918360867974894371539160853827180596100892180735770688723270765387697604426715670445270819626709364566478781273676115921657967761494619448095207169386364541164659123273236874649888236433399127407801843412677293516986398190165291102109310458304626261648346825196743539220198199366711858135271877662410355585767124059539217274691606825103355310348607611233052725805236763220343249873849646219850954945346791015858261715967952461021650307307454434510851869862964236227932964442289459508441345652423088404453536608812799355469 hint=int(binascii.hexlify(hint),16) assert(q1p*q1q==n) assert(q1p

第一段

 1 2 3 4  n = ... c = ... f=lambda m,e,n,c:pow(m,e,n)==c assert(sum(map(f,[p]*4,[4]*4,n,c))==4) 

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21  #!/usr/env/python2 from Crypto.Util.number import * import gmpy2 def CRT(mi, ai): assert (isinstance(mi, list) and isinstance(ai, list)) M = reduce(lambda x, y: x * y, mi) ai_ti_Mi = [a * (M / m) * inverse(M / m, m) for (m, a) in zip(mi, ai)] return reduce(lambda x, y: x + y, ai_ti_Mi) % M n = [20129615352491765499340112943188317180548761597861300847305827141510465619670536844634558246439230371658836928103063432870245707180355907194284861510906071265352409579441048101084995923962148527097370705452070577098780246282820065573711015664291991372085157016901209114191068574208680397710042842835940428451949500607613634682684113208766694028789275748528254287705759528498986306494267817198340658241873024800336013946294891687591013414935237821291805123285905335762719823771647853378892868896078424572232934360940672962436849523915563328779942134504499568866135266628078485232098208237036724121481835035731201383423, 31221650155627849964466413749414700613823841060149524451234901677160009099014018926581094879840097248543411980533066831976617023676225625067854003317018794041723612556008471579060428898117790587991055681380408263382761841625714415879087478072771968160384909919958010983669368360788505288855946124159513118847747998656422521414980295212646675850690937883764000571667574381419144372824211798018586804674824564606122592483286575800685232128273820087791811663878057827386379787882962763290066072231248814920468264741654086011072638211075445447843691049847262485759393290853117072868406861840793895816215956869523289231421, 29944537515397953361520922774124192605524711306753835303703478890414163510777460559798334313021216389356251874917792007638299225821018849648520673813786772452822809546571129816310207232883239771324122884804993418958309460009406342872173189008449237959577469114158991202433476710581356243815713762802478454390273808377430685157110095496727966308001254107517967559384019734279861840997239176254236069001453544559786063915970071130087811123912044312219535513880663913831358790376650439083660611831156205113873793106880255882114422025746986403355066996567909581710647746463994280444700922867397754748628425967488232530303, 25703437855600135215185778453583925446912731661604054184163883272265503323016295700357253105301146726667897497435532579974951478354570415554221401778536104737296154316056314039449116386494323668483749833147800557403368489542273169489080222009368903993658498263905567516798684211462607069796613434661148186901892016282065916190920443378756167250809872483501712225782004396969996983057423942607174314132598421269169722518224478248836881076484639837343079324636997145199835034833367743079935361276149990997875905313642775214486046381368619638551892292787783137622261433528915269333426768947358552919740901860982679180791] c = [19131432661217908470262338421299691998526157790583544156741981238822158563988520225986915234570037383888112724408392918113942721994125505014727545946133307329781747600302829588248042922635714391033431930411180545085316438084317927348705241927570432757892985091396044950085462429575440060652967253845041398399648442340042970814415571904057667028157512971079384601724816308078631844480110201787343583073815186771790477712040051157180318804422120472007636722063989315320863580631330647116993819777750684150950416298085261478841177681677867236865666207391847046483954029213495373613490690687473081930148461830425717614569, 15341898433226638235160072029875733826956799982958107910250055958334922460202554924743144122170018355117452459472017133614642242411479849369061482860570279863692425621526056862808425135267608544855833358314071200687340442512856575278712986641573012456729402660597339609443771145347181268285050728925993518704899005416187250003304581230701444705157412790787027926810710998646191467130550713600765898234392350153965811595060656753711278308005193370936296124790772689433773414703645703910742193898471800081321469055211709339846392500706523670145259024267858368216902176489814789679472227343363035428541915118378163012031, 18715065071648040017967211297231106538139985087685358555650567057715550586464814763683688299037897182845007578571401359061213777645114414642903077003568155508465819628553747173244235936586812445440095450755154357646737087071605811984163416590278352605433362327949048243722556262979909488202442530307505819371594747936223835233586945423522256938701002370646382097846105014981763307729234675737702252155130837154876831885888669150418885088089324534892506199724486783446267336789872782137895552509353583305880144947714110009893134162185382309992604435664777436197587312317224862723813510974493087450281755452428746194446, 2282284561224858293138480447463319262474918847630148770112472703128549032592187797289965592615199709857879008271766433462032328498580340968871260189669707518557157836592424973257334362931639831072584824103123486522582531666152363874396482744561758133655406410364442174983227005501860927820871260711861008830120617056883514525798709601744088135999465598338635794275123149165498933580159945032363880613524921913023341209439657145962332213468573402863796920571812418200814817086234262280338221161622789516829363805084715652121739036183264026120868756523770196284142271849879003202190966150390061195469351716819539183797] p4 = CRT(n, c) print p4 # 146068806215073497344459876631371603884129554507314987227041386431864296983800292232765852493230146632246223391161616274352995602128509562953556195654254929572680238155614318159006433172894208760309766144817665852858474274746295434459658946786114485553768622540321693696983334739989582184316792317376817587284066141025953893816735983622448994863347051427279673308801466174898201800602688359956097373676655607179834345973775227535147398518523539179261883968140504230643073698857288314127486345168652339309386405706576632120711116391426300160476076254612138216623537070845645803721685414583459545099925250474009703135469241079408739336592005949980987466671054020054633554508243871664072158338203090563533576053886607251476483441992750608537110739543678599105838456537686029895264928334606913181627024815548789841726411333636163152202116487198575625907392074866811580053962217284776220330628233642351622897902940633662074194963147661868086182955886918339487179905557899816215131118989868243555958033477834658657082003718410617182774845820310639577794302769424451100567749840744304334325501306470124397022077759031911677326433654909824518845224227308515695216456907499080502091628962571645468099748573164070147303131348996440422701533681L res = gmpy2.iroot(p4, 4) print res # (mpz(109935857933867829728985398563235455481120300859311421762540858762721955038310117609456763338082237907005937380873151279351831600225270995344096532750271070807051984097524900957809427861441436796934012393707770012556604479065826879107677002380580866325868240270494148512743861326447181476633546419262340100453), True) p = res[0] 

第二段

 1 2 3 4 5 6 7 8  ee1 = 42 ee2 = 3 ce1 = 45722651786340123946960815003059322528810481841378247280642868553607692149509126962872583037142461398806689489141741494974836882341505234255325683219092163052843461632338442529011502378931140356111756932712822516814023166068902569458299933391973504078898958921809723346229893913662577294963528318424676803942288386430172430880307619748186863890050113934573820505570928109017842647598266634344447182347849367714564686341871007505886728393751147033556889217604647355628557502208364412269944908011305064122941446516990168924709684092200183860653173856272384 ce2 = 13908468332333567158469136439932325992349696889129103935400760239319454409539725389747059213835238373047899198211128689374049729578146875309231962936554403287882999967840346216695208424582739777034261079550395918048421086843927009452479936045850799096750074359160775182238980989229190157551197830879877097703347301072427149474991803868325769967332356950863518504965486565464059770451458557744949735282131727956056279292800694203866167270268988437389945703117070604488999247750139568614939965885211276821987586882908159585863514561191905040244967655444219603287214405014887994238259270716355378069726760953320025828158 tmp = 864078778078609835167779565982540757684070450697854309005171742813414963447462554999012718960925081621571487444725528982424037419052194840720949809891134854871222612682162490991065015935449289960707882463387 n = 15911581555796798614711625288508309704791837516232122410440958830726078821069050404012820896260071751380436992710638364294658173571101596931605797509712839622479368850251206419748090059752427303611760004621378226431226983665746837779056271530181865648115862947527212787824629516204832313026456390047768174765687040950636530480549014401279054346098030395100387004111574278813749630986724706263655166289586230453975953773791945408589484679371854113457758157492241225180907090235116325034822993748409011554673180494306003272836905082473475046277554085737627846557240367696214081276345071055578169299060706794192776825039 assert(pow(e1,ee1,n)==ce1) assert(pow(e2+tmp,ee2,n)==ce2) 

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24  def iroot(c, n, i): for k in range(0, 10000000): a, b = gmpy2.iroot(c + k * n, i) if b == 1: print a break else: print 'None' ee1 = 42 ee2 = 3 ce1 = 45722651786340123946960815003059322528810481841378247280642868553607692149509126962872583037142461398806689489141741494974836882341505234255325683219092163052843461632338442529011502378931140356111756932712822516814023166068902569458299933391973504078898958921809723346229893913662577294963528318424676803942288386430172430880307619748186863890050113934573820505570928109017842647598266634344447182347849367714564686341871007505886728393751147033556889217604647355628557502208364412269944908011305064122941446516990168924709684092200183860653173856272384 ce2 = 13908468332333567158469136439932325992349696889129103935400760239319454409539725389747059213835238373047899198211128689374049729578146875309231962936554403287882999967840346216695208424582739777034261079550395918048421086843927009452479936045850799096750074359160775182238980989229190157551197830879877097703347301072427149474991803868325769967332356950863518504965486565464059770451458557744949735282131727956056279292800694203866167270268988437389945703117070604488999247750139568614939965885211276821987586882908159585863514561191905040244967655444219603287214405014887994238259270716355378069726760953320025828158 tmp = 864078778078609835167779565982540757684070450697854309005171742813414963447462554999012718960925081621571487444725528982424037419052194840720949809891134854871222612682162490991065015935449289960707882463387 n = 15911581555796798614711625288508309704791837516232122410440958830726078821069050404012820896260071751380436992710638364294658173571101596931605797509712839622479368850251206419748090059752427303611760004621378226431226983665746837779056271530181865648115862947527212787824629516204832313026456390047768174765687040950636530480549014401279054346098030395100387004111574278813749630986724706263655166289586230453975953773791945408589484679371854113457758157492241225180907090235116325034822993748409011554673180494306003272836905082473475046277554085737627846557240367696214081276345071055578169299060706794192776825039 iroot(ce1, n, ee1) # 15218928658178 iroot(ce2, n, ee2) # 864078778078609835167779565982540757684070450697854309005171742813414963447462554999012718960925081621571487444725528982424037419052194840720949809891134854871222612682162490991065015935449290342499311738517 e1 = 15218928658178 e2 = 864078778078609835167779565982540757684070450697854309005171742813414963447462554999012718960925081621571487444725528982424037419052194840720949809891134854871222612682162490991065015935449290342499311738517 - tmp # 381791429275130 

第三段

 1 2 3 4 5 6 7  e = 46531 n = 16278524034278364842964386062476113517067911891699789991355982121084973951738324063305190630865511554888330215827724887964565979607808294168282995825864982603759381323048907814961279012375346497781046417204954101076457350988751188332353062731641153547102721113593787978587135707313755661153376485647168543680503160420091693269984008764444291289486805840439906620313162344057956594836197521501755378387944609246120662335790110901623740990451586621846212047950084207251595169141015645449217847180683357626383565631317253913942886396494396189837432429078251573229378917400841832190737518763297323901586866664595327850603 c = 14992132140996160330967307558503117255626925777426611978518339050671013041490724616892634911030918360867974894371539160853827180596100892180735770688723270765387697604426715670445270819626709364566478781273676115921657967761494619448095207169386364541164659123273236874649888236433399127407801843412677293516986398190165291102109310458304626261648346825196743539220198199366711858135271877662410355585767124059539217274691606825103355310348607611233052725805236763220343249873849646219850954945346791015858261715967952461021650307307454434510851869862964236227932964442289459508441345652423088404453536608812799355469 hint=int(binascii.hexlify(hint),16) assert(q1p*q1q==n) assert(q1p

q1q = 127587319253436643569312142058559706815497211661083866592534217079310497260365307426095661281103710042392775453866174657404985539066741684196020137840472950102380232067786400322600902938984916355631714439668326671310160916766472897536055371474076089779472372913037040153356437528808922911484049460342088835693
q1p = 127587319253436643569312142058559706815497211661083866592534217079310497260365307426095661281103710042392775453866174657404985539066741684196020137840472950102380232067786400322600902938984916355631714439668326671310160916766472897536055371474076089779472372913037040153356437528808922911484049460342088834871


 1 2 3 4 5 6 7  phi = (q1p - 1) * (q1p - 1) d = gmpy2.invert(e, phi) hint = pow(c, d, n) import binascii print binascii.unhexlify(hex(hint)[2:].strip('L')) # 'orz...you.found.me.but.sorry.no.hint...keep.on.and.enjoy.it!' 

第四段

 1 2 3 4 5 6  flag=int(binascii.hexlify(flag),16) q1=q1p c1 = 262739975753930281690942784321252339035906196846340713237510382364557685379543498765074448825799342194332681181129770046075018122033421983227887719610112028230603166527303021036386350781414447347150383783816869784006598225583375458609586450854602862569022571672049158809874763812834044257419199631217527367046624888837755311215081173386523806086783266198390289097231168172692326653657393522561741947951887577156666663584249108899327053951891486355179939770150550995812478327735917006194574412518819299303783243886962455399783601229227718787081785391010424030509937403600351414176138124705168002288620664809270046124 c2 = 7395591129228876649030819616685821899204832684995757724924450812977470787822266387122334722132760470911599176362617225218345404468270014548817267727669872896838106451520392806497466576907063295603746660003188440170919490157250829308173310715318925771643105064882620746171266499859049038016902162599261409050907140823352990750298239508355767238575709803167676810456559665476121149766947851911064706646506705397091626648713684511780456955453552020460909638016134124590438425738826828694773960514221910109473941451471431637903182205738738109429736425025621308300895473186381826756650667842656050416299166317372707709596 assert(c1==pow(flag,e1,p*q1)) assert(c2==pow(flag,e2,p*q2)) 

 1 2  gcd(e1, p - 1) == 14 gcd(e1, q1 - 1) == 2 

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16  p = 109935857933867829728985398563235455481120300859311421762540858762721955038310117609456763338082237907005937380873151279351831600225270995344096532750271070807051984097524900957809427861441436796934012393707770012556604479065826879107677002380580866325868240270494148512743861326447181476633546419262340100453 q1 = 127587319253436643569312142058559706815497211661083866592534217079310497260365307426095661281103710042392775453866174657404985539066741684196020137840472950102380232067786400322600902938984916355631714439668326671310160916766472897536055371474076089779472372913037040153356437528808922911484049460342088834871 c1 = 262739975753930281690942784321252339035906196846340713237510382364557685379543498765074448825799342194332681181129770046075018122033421983227887719610112028230603166527303021036386350781414447347150383783816869784006598225583375458609586450854602862569022571672049158809874763812834044257419199631217527367046624888837755311215081173386523806086783266198390289097231168172692326653657393522561741947951887577156666663584249108899327053951891486355179939770150550995812478327735917006194574412518819299303783243886962455399783601229227718787081785391010424030509937403600351414176138124705168002288620664809270046124 e1 = 15218928658178 c1q = c1 % q1 phiq = q1 - 1 dq = gmpy2.invert(e1/2, phiq) m2 = pow(c1, dq, q1) iroot(m2, q1, 2) # 3597756982424788530654510857179372044113434920098110365668160220641544533784058353001736221836299987936893 import binacsii m2 = 3597756982424788530654510857179372044113434920098110365668160220641544533784058353001736221836299987936893 print binascii.unhexlify(hex(m2)[2:].strip('L')) # de1ctf{9b10a98b-71bb-4bdf-a6ff-f319943de21f} 

OK，得到flag:de1ctf{9b10a98b-71bb-4bdf-a6ff-f319943de21f}