Intended Solution to Crypto Problems in NCTF 2019

Crypto

Keyboard[123pt 72solvers]

Description

==Difficulty: intuitive==

The plaintext is a string of meaningful lowercase letters, without whitespace.

Please submit the result with "NCTF{}" wrapped.

==Author: Soreat_u==


Analysis

ooo yyy ii w uuu ee uuuu yyy uuuu y w uuu i i rr w i i rr rrr uuuu rrr uuuu t ii uuuu i w u rrr ee www ee yyy eee www w tt ee


q -> 1
w -> 2
e -> 3
r -> 4
t -> 5
y -> 6
u -> 7
i -> 8
o -> 9


Exploit

 1 2 3 4 5 6 7 8 9  cipher = 'ooo yyy ii w uuu ee uuuu yyy uuuu y w uuu i i rr w i i rr rrr uuuu rrr uuuu t ii uuuu i w u rrr ee www ee yyy eee www w tt ee' s = ' qwertyuiop' d = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'] for part in cipher.split(' '): # print(part) count = len(part) num = s.index(part[0]) print(d[num][count - 1], end='') 

Sore[667pt 6solvers]

Description

==Difficulty: easy==

Can you break the “unbreakable” cipher?

==Author: Soreat_u==


Exploit

NCTF{vlbeunuozbpycklsjXlfpaq}

babyRSA[526pt 10solvers]

Description

==Difficulty: baby==

I forget the modulus. Can you help me recover it?

==Author: Soreat_u==


Analysis

$$\phi(n) \approx n, e = 65537, d < n$$ 所以 $$k < e = 65537$$ 只需穷举小于65537且能整除$ed - 1$的所有$k$，即可得到所有可能的$\phi(n)$

Exploit

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24  #!/usr/bin/python2 from Crypto.Util.number import * import gmpy2 e = 65537 d = 19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913 c = 5382723168073828110696168558294206681757991149022777821127563301413483223874527233300721180839298617076705685041174247415826157096583055069337393987892262764211225227035880754417457056723909135525244957935906902665679777101130111392780237502928656225705262431431953003520093932924375902111280077255205118217436744112064069429678632923259898627997145803892753989255615273140300021040654505901442787810653626524305706316663169341797205752938755590056568986738227803487467274114398257187962140796551136220532809687606867385639367743705527511680719955380746377631156468689844150878381460560990755652899449340045313521804 kphi = e*d - 1 for k in range(1, e): if kphi % k == 0: phi = kphi // k root = gmpy2.iroot(phi, 2)[0] for p in range(root - 2000, root + 2000): if phi % (p-1) == 0: break else: continue break q = phi//(p-1) + 1 m = pow(c, d, p*q) print(long_to_bytes(m)) # 'NCTF{70u2_nn47h_14_v3ry_gOO0000000d}' 

childRSA[213pt 38solvers]

Description

==Difficulty: baby==

==Author: Soreat_u==


Introduction

An Introduction to Mathematical Cryptography书中说到：

Analysis

smooth有什么坏处呢？

Pollard的厉害之处就在于此，他发现，如果p-1正好是一些很小的质数的乘积，那么p-1就能整除$n!$，其中$n$是一个不太大的数。

Exploit

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17  from Crypto.Util.number import * def Pollard_p_1(N): a = 2 while True: f = a # precompute for n in range(1, 80000): f = pow(f, n, N) for n in range(80000, 104729+1): f = pow(f, n, N) if n % 15 == 0: d = GCD(f-1, N) if 1 < d < N: return d print(a) a += 1 

 1 2  n = 1592519204764870135... print( Pollard_p_1(n) ) 

  1 2 3 4 5 6 7 8 9 10 11 12 13  from Crypto.Util.number import * n = 1592519204764870135... c = 5744608257563538066... p = 5075332621067110585... q = n // p assert(p*q == n) d = inverse(0x10001, (p-1)*(q-1)) m = pow(c, d, n) print(long_to_bytes(m)) # b'NCTF{Th3r3_ar3_1ns3cure_RSA_m0duli_7hat_at_f1rst_gl4nce_appe4r_t0_be_s3cur3}' 

Reverse[909pt 2solvers]

Description

==Difficulty: easy==

DES has a very bad key schedule.

==Author: Soreat_u==


Introduction

leak出的Kn[10]应该是第11组子密钥$K_{11}$。

PERMUTED CHOICE 2是一个56 bits -> 48 bits的置换。可以穷举被truncated的8bits，逆一下对$K_{11}$的PERMUTED CHOICE 2即可返回到C11 D11

Exploit

  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  from base64 import b64decode from itertools import product from DES import * # https://github.com/soreatu/Cryptography/blob/master/DES.py guess_8bit = list(product(range(2), repeat=8)) not_in_PC2 = [9,18,22,25,35,38,43,54] def re_PC2(sbkey): # 48-bit -> 56-bit res = [0]*56 for i in range(len(sbkey)): res[PC_2_table[i]-1] = sbkey[i] return res # ok def guess_CiDi10(sbkey, t): res = re_PC2(sbkey) for i in range(8): res[not_in_PC2[i]-1] = guess_8bit[t][i] return res # ok def guess_allsbkey(roundkey, r, t): sbkey = [[]]*16 sbkey[r] = roundkey CiDi = guess_CiDi10(roundkey, t) Ci, Di = CiDi[:28], CiDi[28:] for i in range(r+1,r+16): Ci, Di = LR(Ci, Di, i%16) sbkey[i%16] = PC_2(Ci+Di) return sbkey # ok def long_des_enc(c, k): assert len(c) % 8 == 0 res = b'' for i in range(0,len(c),8): res += DES_enc(c[i:i+8], k) return res def try_des(cipher, roundkey): for t in range(256): allkey = guess_allsbkey(roundkey, 10, t) plain = long_des_enc(cipher, allkey[::-1]) if plain.startswith(b'NCTF'): print(plain) if __name__ == "__main__": cipher = b64decode(b'm0pT2YYUIaL0pjdaX2wsxwedViYAaBkZA0Rh3bUmNYVclBlvWoB8VYC6oSUjfbDN') sbkey10 = [0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1] try_des(cipher, sbkey10) # b'NCTF{1t_7urn3d_0u7_7h47_u_2_g00d_@_r3v3rs3_1snt}' 

easyRSA[909pt 2solvers]

Description

==Difficulty: simple==

We can do RSA decryption even if e and phi(n) are not coprime.

Hint: m has exactly 24196561 solutions :)

Hint2: https://stackoverflow.com/questions/6752374/cube-root-modulo-p-how-do-i-do-this

Hint3: https://arxiv.org/pdf/1111.4877.pdf

==Author: Soreat_u==


Exploit

• 先用Adleman-Manders-Miller rth Root Extraction MethodGF(p)GF(q)上对ce次根，分别得到一个解。大概不到10秒。
• 然后去找到所有的0x1336primitive nth root of 1，乘以上面那个解，得到所有的0x1337个解。大概1分钟。
• 再用CRTGF(p)GF(q)上的两组0x1337个解组合成mod n下的解，可以得到0x1337**2==24196561mod n的解。最后能通过check的即为flag。大概十几分钟。

exp.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 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  import random import time # About 3 seconds to run def AMM(o, r, q): start = time.time() print('\n----------------------------------------------------------------------------------') print('Start 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 in range(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 def findAllPRoot(p, e): print("Start to find all the Primitive {:#x}th root of 1 modulo {}.".format(e, p)) start = time.time() proot = set() while len(proot) < e: proot.add(pow(random.randint(2, p-1), (p-1)//e, p)) end = time.time() print("Finished in {} seconds.".format(end - start)) return proot def findAllSolutions(mp, proot, cp, p): print("Start to find all the {:#x}th root of {} modulo {}.".format(e, cp, p)) start = time.time() all_mp = set() for root in proot: mp2 = mp * root % p assert(pow(mp2, e, p) == cp) all_mp.add(mp2) end = time.time() print("Finished in {} seconds.".format(end - start)) return all_mp c = 10562302690541901187975815594605242014385201583329309191736952454310803387032252007244962585846519762051885640856082157060593829013572592812958261432327975138581784360302599265408134332094134880789013207382277849503344042487389850373487656200657856862096900860792273206447552132458430989534820256156021128891296387414689693952047302604774923411425863612316726417214819110981605912408620996068520823370069362751149060142640529571400977787330956486849449005402750224992048562898004309319577192693315658275912449198365737965570035264841782399978307388920681068646219895287752359564029778568376881425070363592696751183359 p = 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059 q = 112213695905472142415221444515326532320352429478341683352811183503269676555434601229013679319423878238944956830244386653674413411658696751173844443394608246716053086226910581400528167848306119179879115809778793093611381764939789057524575349501163689452810148280625226541609383166347879832134495444706697124741 e = 0x1337 cp = c % p cq = c % q mp = AMM(cp, e, p) mq = AMM(cq, e, q) p_proot = findAllPRoot(p, e) q_proot = findAllPRoot(q, e) mps = findAllSolutions(mp, p_proot, cp, p) mqs = findAllSolutions(mq, q_proot, cq, q) print mps, mqs def check(m): h = m.hex() if len(h) & 1: return False if h.decode('hex').startswith('NCTF'): print(h.decode('hex')) return True else: return False # About 16 mins to run 0x1337^2 == 24196561 times CRT start = time.time() print('Start CRT...') for mpp in mps: for mqq in mqs: solution = CRT_list([int(mpp), int(mqq)], [p, q]) if check(solution): print(solution) print(time.time() - start) end = time.time() print("Finished in {} seconds.".format(end - start)) 

2019.12.04更新：

2020.08.11更新：

AMM算法中计算离散对数部分有些问题，已修改，但还未测试。

Summary

p, q都是预先用下面这个函数生成的，保证了e | p-1, e | q-1

 1 2 3 4 5 6 7 8  import random from Crypto.Util.number import * def gen(): p = e * random.getrandbits(1012) + 1 while not isPrime(p): p = e * random.getrandbits(1012) + 1 return p 

flag后面填充了一段杂乱的字符串，是为了增加flag转成整数后的位数。不然位数太低，算出GF(p)GF(q)里2组0x1337个解，取交集就可以得到flag了。位数增加后，就必须要算24196561CRT才能得到flag，可能需要个十几分钟来跑。

LCG[667pt 6solvers]

Description

==Difficulty: interesting==

nc 139.129.76.65 60001

The script to pass proof of work is provided in the link.

Have fun :>

==Author: Soreat_u==


Introduction

https://zeroyu.xyz/2018/11/02/Cracking-LCG/ 里，作者详细地描述了4种针对各种参数已知情况的攻击。本题就是基于这篇文章而出的。

Exploit

  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 122 123 124 125 126  # python2 import hashlib import primefac from pwn import * from Crypto.Util.number import * host, port = '', 10000 r = remote(host, port) # context.log_level = 'debug' def proof_of_work(): print '[+] Proof of work...' r.recvuntil('hexdigest() = ') digest = r.recvline().strip() r.recvuntil("s[:7].encode('hex') =") prefix = r.recvline().strip().decode('hex') # s = r.recvline().strip() for suffix in range(256**3): guess = prefix + long_to_bytes(suffix, 3) if hashlib.sha256(guess).hexdigest() == digest: print '[+] find: ' + guess.encode('hex') break r.recvuntil("s.encode('hex') = ") # r.sendline(s) r.sendline(guess.encode('hex')) def solve1(N, a, b, n1): return (n1 - b) * inverse(a, N) % N def solve2(N, a, n1, n2): b = (n2 - n1 * a) % N return solve1(N, a, b, n1) def solve3(N, n1, n2, n3): a = (n3 - n2) * inverse(n2 - n1, N) % N return solve2(N, a, n1, n2) def solve4(n1, n2, n3, n4, n5, n6): t1 = n2 - n1 t2 = n3 - n2 t3 = n4 - n3 t4 = n5 - n4 t5 = n6 - n5 N = GCD(t3*t1 - t2**2, t5*t2 - t4*t3) factors = primefac.factorint(N) while not isPrime(N): for prime, order in factors.items(): if prime.bit_length() > 128: continue N = N / prime**order return solve3(N, n1, n2, n3) def challenge1(): print '[+] Solving challenge1...' r.recvuntil('lcg.N = ') N = int(r.recvline().strip()) r.recvuntil('lcg.a = ') a = int(r.recvline().strip()) r.recvuntil('lcg.b = ') b = int(r.recvline().strip()) r.recvuntil('lcg.next() = ') next1 = int(r.recvline().strip()) init_seed = solve1(N, a, b, next1) r.recvuntil('lcg.seed = ') r.sendline(str(init_seed)) def challenge2(): print '[+] Solving challenge2...' r.recvuntil('lcg.N = ') N = int(r.recvline().strip()) r.recvuntil('lcg.a = ') a = int(r.recvline().strip()) r.recvuntil('lcg.next() = ') next1 = int(r.recvline().strip()) r.recvuntil('lcg.next() = ') next2 = int(r.recvline().strip()) init_seed = solve2(N, a, next1, next2) r.recvuntil('lcg.seed = ') r.sendline(str(init_seed)) def challenge3(): print '[+] Solving challenge3...' r.recvuntil('lcg.N = ') N = int(r.recvline().strip()) r.recvuntil('lcg.next() = ') next1 = int(r.recvline().strip()) r.recvuntil('lcg.next() = ') next2 = int(r.recvline().strip()) r.recvuntil('lcg.next() = ') next3 = int(r.recvline().strip()) init_seed = solve3(N, next1, next2, next3) r.recvuntil('lcg.seed = ') r.sendline(str(init_seed)) def challenge4(): print '[+] Solving challenge4...' r.recvuntil('lcg.next() = ') next1 = int(r.recvline().strip()) r.recvuntil('lcg.next() = ') next2 = int(r.recvline().strip()) r.recvuntil('lcg.next() = ') next3 = int(r.recvline().strip()) r.recvuntil('lcg.next() = ') next4 = int(r.recvline().strip()) r.recvuntil('lcg.next() = ') next5 = int(r.recvline().strip()) r.recvuntil('lcg.next() = ') next6 = int(r.recvline().strip()) init_seed = solve4(next1, next2, next3, next4, next5, next6) r.recvuntil('lcg.seed = ') r.sendline(str(init_seed)) proof_of_work() challenge1() challenge2() challenge3() challenge4() r.interactive()