# Writeup for Crypto Problems in CyBRICS CTF 2019

## Zakukozh

### Script

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 `````` ``````from Crypto.Util.number import GCD, inverse # d^-1(x) = a^-1 (x - b) % 256 pre = [0x89, 0x50, 0x4e] post = [0x60, 0x09, 0xeb] for a in range(256): if GCD(a,256)!=1: continue inv_a = inverse(a, 256) for b in range(256): q = 1 for i in range(3): if (inv_a * (post[i] - b) ) % 256 != pre[i]: q=0 break if(q): print(a, b) # 15, 89 ``````

 ``````1 2 3 4 5 6 7 8 9 `````` ``````a = 15 inv_a = 239 b = 89 with open("zakukozh.bin", "rb") as f1: t = f1.read() with open("flag.png", "wb") as f2: for c in t: p = inv_a * (c - b) % 256 f2.write(bytes[p]) ``````

## Fast Crypto

### 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 `````` ``````import json from tqdm import tqdm from egcd import egcd from pathlib import Path import sys def get_next(a, power, N): b = a ** power % N return b, b % 256 if not Path('public.key').exists(): print("Key file not found") exit(1) if len(sys.argv) != 3: print("Usage: python3 cryptor.py ") exit(1) try: key = json.loads(Path('public.key').open().read()) data = Path(sys.argv[1]).open('rb').read() except Exception as e: print("Error during keyfile load: {}".format(e)) exit(1) else: seed = int(input("Input seed value (int16): ")) if seed < 0 or seed > 2**16: print("Invalid seed. Encryption may be too slow.") exit(1) power = int(input("Input power value (2-16): ")) if power < 2 or power > 16: print("Invalid power. Encryption may be too slow.") exit(1) if egcd(power, key['N'])[0] != 1: print("Invalid power value") exit(1) # calculate offset for _ in range(key['O']): seed = get_next(seed, power, key['N'])[0] with Path(sys.argv[2]).open('wb') as w: for i in tqdm(range(len(data))): seed, bt = get_next(seed, power, key['N']) w.write(bytes([data[i] ^ bt])) ``````

• seed: [0, 2**16]
• power: [2, 16]
• 先对seed做`key['O']=31337`幂模运算。
• 再用seed的低8-bit来和数据异或（也就是相当于一个`stream cipher`）。

`seed``power`都是随机的，后面所有东西都是由这两个随机数决定的。

``````N = 73882271767225067628282422302548400069735434660808564149855701357643617388546710750167259617348302921921308565033188464703728096338599435641707966042336489111486646451993143053931136428343207443971020988133537590763029595507074481482058514976650388077801669364711731111970923913958083815347282871017052613916475670517
O = 31337
``````

`sage`factor`N`:

 ``````1 2 3 `````` ``````def get_next(a, power, N): b = a ** power % N return b, b % 256 ``````

 `````` 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 `````` ``````from tqdm import tqdm N = 73882271767225067628282422302548400069735434660808564149855701357643617388546710750167259617348302921921308565033188464703728096338599435641707966042336489111486646451993143053931136428343207443971020988133537590763029595507074481482058514976650388077801669364711731111970923913958083815347282871017052613916475670517 O = 31337 raw = [82, 73, 70, 70] enc = [0x46, 0x83, 0x49, 0x44] head = [] for i in range(8): head.append(raw[i] ^ enc[i]) # head = [20, 202, 15, 2, 239, 26, 199, 210] # brute-force for power in range(2, 17): print(power) for s in tqdm(range(2**16+1)): seed = s for _ in range(O): seed = pow(seed, power, N) q = 1 for i in range(4): seed = pow(seed, power, N) bt = seed & 255 if bt != head[i]: q = 0 break if(q): print(s, power) ``````

O轮pow()，也就是相当于直接幂`power**O`，可以改写成`pow(seed, power**O, N)`。但是`2**31337`已经是个超级无敌变态大的数字了，这里应该还可以再优化一下。

 `````` 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 `````` ``````from tqdm import tqdm N = 73882271767225067628282422302548400069735434660808564149855701357643617388546710750167259617348302921921308565033188464703728096338599435641707966042336489111486646451993143053931136428343207443971020988133537590763029595507074481482058514976650388077801669364711731111970923913958083815347282871017052613916475670517 phi_N = 73518206147262443676837361159127776505334808540008666455558114391523228702493449359589995596913129043911224919282022228135566170964663692657377830877081156633758852294230067854975206472518946297562604445162853306974953289714803969929459936619828333107726452353102277743999390152590440267776000000000000000000000000000 O = 31337 raw = [82, 73, 70, 70] enc = [0x46, 0x83, 0x49, 0x44] head = [] for i in range(8): head.append(raw[i] ^ enc[i]) # head = [20, 202, 15, 2, 239, 26, 199, 210] # brute-force for power in range(2, 17): print(power) for s in tqdm(range(2**16+1)): seed = s seed = pow(seed, pow(power, O, phi_N), N) q = 1 for i in range(4): seed = pow(seed, power, N) bt = seed & 255 if bt != head[i]: q = 0 break if(q): print(s, power) ``````

（注意换行那边）

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 `````` ``````from tqdm import tqdm power = 7 seed = 4485 N = 73882271767225067628282422302548400069735434660808564149855701357643617388546710750167259617348302921921308565033188464703728096338599435641707966042336489111486646451993143053931136428343207443971020988133537590763029595507074481482058514976650388077801669364711731111970923913958083815347282871017052613916475670517 phi_N = 73518206147262443676837361159127776505334808540008666455558114391523228702493449359589995596913129043911224919282022228135566170964663692657377830877081156633758852294230067854975206472518946297562604445162853306974953289714803969929459936619828333107726452353102277743999390152590440267776000000000000000000000000000 O = 31337 seed = pow(seed, pow(power, O, phi_N), N) with open("enc.wav", "rb") as fin: data = fin.read() with open("flag.wav", "wb") as fout: for i in tqdm(range(len(data))): seed = pow(seed, power, N) bt = seed & 255 fout.write(bytes([data[i] ^ bt])) ``````

### Summary

• 了解到了`wav`文件的一些基本格式。
• 学到了一手`from tqdm import tqdm`，可以进度条显示。
• 看来，密码题还是需要爆破啊。
• 学到了一点算法的optimization
• 听力有待提升。