###### tags: `writeups`
# Writeup for Fast Crypto in CyBRICS
## Description
意思就是说，这是一个*very modern*的加密算法，试着凭借一个*secret message*来解密这个*WAV*文件。
## Analysis
加密脚本：
```python
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 <filename_in> <filename_out>")
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`都是随机的，后面所有东西都是由这两个随机数决定的。
先提取`key`再说。
```
N = 73882271767225067628282422302548400069735434660808564149855701357643617388546710750167259617348302921921308565033188464703728096338599435641707966042336489111486646451993143053931136428343207443971020988133537590763029595507074481482058514976650388077801669364711731111970923913958083815347282871017052613916475670517
O = 31337
```
出于直觉，验证了一下N和O是否为质数。发现O是个质数，但是N不是。
用`sage`来*factor*`N`:
都是一些比较小的质数。
想了想从N出发应该如何crack这个加密算法。31337轮**幂模**后，`seed`肯定巨大无比，再来取低位做`stream cipher`的`key`，这个好像真的crack不了。
一个比较奇怪的地方是，它的那个幂模运算居然是：
```python
def get_next(a, power, N):
b = a ** power % N
return b, b % 256
```
为什么不用*python*自带的基于快速幂（猜测，但多半就是了）的`pow()`函数呢？这样先乘方，再取余的算法实在是需要太大的运算量了。
未果，睡了一会儿。
---
醒来的时候，感觉可以用`brute-force`，2**16才只是65536，再加上`power`的15种可能，总共就65536*15=983040种可能，爆破起来肯定很快（后面可以看到，快不快还是要取决于算法的`optimization`）。
顺着它的思路写脚本：
```python
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)
```
**说明一下**：前面关于`raw, enc, head`的一段。题目提示加密前的文件格式是`.wav`，去找了一下`wav`文件的开头，是以`RIFF`为开头的前4个byte数据，记为`raw`；再对加密后文件开头的4个byte（记为`enc`）分别异或，得到的结果`head`应当为`stream key`的前4个byte，以此作为验证的依据。这里4个byte数据已经足够了，因为256^4=4294967296 >> 983040=2^16*15。
可是这个脚本跑起来却很慢：
这可能要跑一天才能跑完，开多进程可以快一些，但总的来说，还是要需要**小时**级别的时间。
思考应当如何**优化算法**。回过头来看代码时，发现O轮那个循环实在是有点费时间，每次都需要31337次pow()，即使是快速幂也顶不住啊。
O轮pow()，也就是相当于直接幂`power**O`，可以改写成`pow(seed, power**O, N)`。但是`2**31337`已经是个超级无敌变态大的数字了，这里应该还可以再优化一下。
幂模，联想到了**欧拉定理**`pow(a, phi(n), n) = 1`。也就是说，那个幂其实是个周期性的东西，`pow(a, k*phi(n)+b, n) = pow(a, b, n)`，可以对幂`mod phi(n)`，结果仍然不变。
再回到这题，前面分析到，`N`不是一个质数并且能够被轻易地质因数分解。那么，计算`phi(N)`就是一个很简单的事情了。
有了`phi(N)`，就还能再改写成`pow(seed, pow(power, O, phi_N), N)`，这就快多了。
```python
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)
```
这相比之前，简直就像火箭一样快。修改power的值，手动多进程了一下，很快就跑出来了：
（注意换行那边）
所以`seed=4485, power=7`。
接着就是*decode*了
```python
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]))
```
打开解密后的`wav`文件，一开始还听不出来，多听了好几遍(吐槽一下这个文本转语音)，才听出来`The flag is cybrics bracket b l u m underscore b l u m underscore crypto rear bracket`，也就是`cybrics{blum_blum_crypto}`。提交，正确!
## Summary
- 了解到了`wav`文件的一些基本格式。
- 学到了一手`from tqdm import tqdm`，可以进度条显示。
- 看来，密码题还是需要爆破啊。
- 学到了一点算法的*optimization*。
- 听力有待提升。
Sign in with Wallet
Connect another wallet