---
# System prepended metadata

title: TMUCTF 2021

---

# TMUCTF 2021

Rank: 58th
Points: 2254

## Common Factor (52 solves, 383 pts)

:::spoiler **Source Code**
```python=
from Crypto.Util.number import *
from functools import reduce


def encrypt(msg, n):
    enc = pow(bytes_to_long(msg), e, n)
    return enc


e = 65537

primes = [getPrime(2048) for i in range(5)]
n = reduce(lambda a, x: a * x, primes, 1)
print(n)

x1 = primes[1] ** 2
x2 = primes[2] ** 2
x3 = primes[1] * primes[2]
y1 = x1 * primes[2] + x2 * primes[1]
y2 = x2 * (primes[3] + 1) - 1
y3 = x3 * (primes[3] + 1) - 1
print(x2 + x3 + y1)
print(y2 + y3)

with open('flag', 'rb') as f:
    flag = f.read()
    print(encrypt(flag, n))
```
:::

從題目名稱也也能看出這題要幹嘛 :D。首先，根據定義化簡可得$$x_2+x_3+y_1 = p_2(p_1+p_2)(p_1+1)$$ 以及 $$y_2+y_3 = p_2(p_1+p_2)(p_3+1)-2$$ 因為質數都是隨機取的，所以基本上可以確定 $$p_2 = (x_2+x_3+y_1, n)$$ 另一方面，我們知道 $$p_2(p_1+p_2) \mid (x_2+x_3+y_1, y_2+y_3+2) $$ 並且他們的商是 $(p_1+1, p_3+1)$，可以預期它不會太大。直接窮舉就能得到 $p_1$，從而也知道 $p_3$。

一般來說，RSA 要完全分解才能解密，但是我們並沒有 $p_0, p_4$ 的資訊，因此就想說把它當作 $N = p_1p_2p_3$ 的 RSA (參考 CryptoCTF 2020 Three Raven)

:::spoiler **Script**
```python=
from Crypto.Util.number import *
from functools import reduce
from output import *
from math import gcd

### x2 + x3 + y1 = p2(p1 + p2)(p1 + 1)
### y2 + y3 + 2  = p2(p1 + p2)(p3 + 1) 

p2 = gcd(n, a)

assert isPrime(p2)

_ = gcd(a, b+2) // p2

for i in range(10, 30):
	if _ % i == 0:
		p1 = _ // i - p2
		if isPrime(p1) and n % p1 == 0:
			break

assert a == p2 * (p1 + p2) * (p1 + 1)

p3 = (b+2) // (p2 * (p1 + p2)) - 1

assert (b+2) == p2 * (p1 + p2) * (p3 + 1) and isPrime(p3)

fake_phi = (p1 - 1) * (p2 - 1) * (p3 - 1)

d = pow(65537, -1, fake_phi)

pt = pow(c, d, p1 * p2 * p3) 

flag = long_to_bytes(pt)
print(flag)
```
:::

:::success
TMUCTF{Y35!!!__M4Y_N0t_4lW4y5_N33d_4ll_p21M3_f4c70R5}
:::

## 435! (45 solves, 413 pts)

:::spoiler **Source Code**
```python=
import binascii
import hashlib
import sys
from Crypto.Cipher import AES

key = b'*XhN2*8d%8Slp3*v'
key_len = len(key)


def pad(message):
    padding = bytes((key_len - len(message) % key_len) * chr(key_len - len(message) % key_len), encoding='utf-8')
    return message + padding


def encrypt(message, key, iv):
    aes = AES.new(key, AES.MODE_CBC, iv)
    return aes.encrypt(message)


h = hashlib.sha256(key).hexdigest()
hidden = binascii.unhexlify(h)[:10]
message = b'CBC (Cipher Blocker Chaining) is an advanced form of block cipher encryption' + hidden

with open('flag', 'rb') as f:
    IV = f.read().strip(b'TMUCTF{').strip(b'}')
    print(binascii.hexlify(encrypt(pad(message), key, IV)))
```
:::

題目給了 AES-CBC 的部分 key，然後用 flag 當作 IV，加密一個跟 key 有關的訊息，然後密文也只有給一部分。

注意到 key 只有被遮掉三個 character，並且密文後一個半個 block 都沒被碼掉，所以能去暴搜所有可能的 key，然後看下面的等式有沒有可能成立：$$ AES_{ECB}(msg[i] \oplus block[i-1]) = block[i]  $$ 具體的方式是去看 $$ AES_{ECB}^{-1}(block[i]) \oplus msg[i] $$ 跟 $block[i-1]$ 已知的 bytes 有沒有一致。若有的話，代表是可能的 key。

:::spoiler **Find key**
```python=
import binascii
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes

key_len = 16

def pad(message):
	padding = bytes((key_len - len(message) % key_len) * chr(key_len - len(message) % key_len), encoding='utf-8')
	return message + padding

def Decrypt(c, k):
	aes = AES.new(k, AES.MODE_ECB)
	return aes.decrypt(c)

# block1 = binascii.unhexlify("************1b3*******9f43fd6634")
ind = [6, 11, 12, 13, 14, 15]
block1 = {
	6: b'\x1b',
	11: b'\x9f',
	12: b'\x43',
	13: b'\xfd',
	14: b'\x66',
	15: b'\x34'
}
block2 = binascii.unhexlify("1f3ef3fab2bbfc838b9ef71867c3bcbb")

chars = [chr(_) for _ in range(128)]

for char1 in chars:
	for char2 in chars:
		for char3 in chars:
			key = char1 + "XhN2" + char2 + "8d%8Slp3" + char3 + "v"
			key = key.encode()
			
			h = hashlib.sha256(key).hexdigest()
			hidden = binascii.unhexlify(h)[:10]
			message = b'CBC (Cipher Blocker Chaining) is an advanced form of block cipher encryption' + hidden
			message = pad(message)
			message = message[-16:]
	
			decrypted_block2 = Decrypt(block2, key)

			check = True

			for i in ind:
				_ = decrypted_block2[i] ^ block1[i][0]
				if message[i:i+1] != long_to_bytes(_):
					check = False
		
			if check:
				print("Found!")
				print(key)
```
:::

倒著解密回去就可以知道 $flag\oplus msg[0]$ 的值，也就拿到 flag 啦！

:::spoiler **Get flag**
```python=
import binascii
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes

key = b'0XhN2!8d%8Slp3Ov'
key_len = len(key)

def pad(message):
	padding = bytes((key_len - len(message) % key_len) * chr(key_len - len(message) % key_len), encoding='utf-8')
	return message + padding

h = hashlib.sha256(key).hexdigest()
hidden = binascii.unhexlify(h)[:10]
message = b'CBC (Cipher Blocker Chaining) is an advanced form of block cipher encryption' + hidden
message = pad(message)

def decrypt(c, k):
        aes = AES.new(k, AES.MODE_ECB)
        return aes.decrypt(c)

def xor_blocks(b1, b2):
	res = b''
	for x, y in zip(b1, b2):
		res += long_to_bytes(x^y)
	return res

current_block = binascii.unhexlify("1f3ef3fab2bbfc838b9ef71867c3bcbb")

for i in range(6):
	current_block = decrypt(current_block, key)

	j, k = -16 * (i+1), -16 * i
	if k:
		c = message[j: k]
	else:
		c = message[j:]

	current_block = xor_blocks(current_block, c)

print(current_block)
```
:::

:::success
TMUCTF{Y0U_D3CrYP73D_17}
:::

## Broken RSA (21 solves, 482 pts)

:::spoiler **Source Code**
```python=
from Crypto.Util.number import *

e = 65537

with open('n', 'rb') as f:
    n = int(f.read())

with open('secret', 'rb') as f:
    secret_msg = f.read()

pads = [b'\x04', b'\x02', b'\x00', b'\x01', b'\x03']

with open('out.txt', 'w') as f:
    for i in range(len(pads)):
        for j in range(len(pads)):
            msg = pads[j] * (i + 1) + b'TMUCTF' + pads[len(pads) - j - 1] * (i + 1)
            enc = pow(bytes_to_long(msg), e, n)
            f.write(str(enc) + '\n')

    enc = pow(bytes_to_long(secret_msg), e, n)
    f.write(str(enc))
```
:::

我們拿到了很多個已知明文的加密結果以及加密後的 flag，算 gcd 就能把 $n$ 給找回來，但也僅限於此。關鍵點是要去看 $n$ 的二進制，然後會發現中間有很多 $0$，頭尾看起來是形如 $$2^{k}\triangle + (2^{k}-1-\triangle) = (2^{k}-1)(\triangle+1)$$ 的東西，於是 $n$ 會被 $2^{k-1}$ 整除，剩下就輕鬆ㄌ！

:::spoiler **Script**
```python=
from Crypto.Util.number import *

with open('output.txt', 'r') as f:
	for _ in range(25):
		f.readline()

	enc = int(f.readline().strip())

from tmp import n

p = (1 << 1279) - 1
q = n // p

assert isPrime(p) and isPrime(q)

flag = pow(enc, pow(65537, -1, (p-1)*(q-1)), n)
print(long_to_bytes(flag))
```
:::

:::success
TMUCTF{Ju57_4n07h3r_R54_ch4ll3n63!_C0u1d_y0u_50lv3_17?!?}
:::

## Baby Encoder (17 solves, 489 pts)

:::spoiler **Source Code**
```python=
from Crypto.Util.number import bytes_to_long


def displace(a, base):
    res = []
    for i in range(base):
        if base + i >= len(a):
            for j in range(base - 1, i - 1, -1):
                res.append(a[j])
            return res
        res.append(a[base + i])
        res.append(a[i])
    for j in range(len(a) - 1, 2 * base - 1, -1):
        res.append(a[j])
    return res


def flag_encoder(flag):
    encoded_flag = []
    n = len(flag)
    for i in range(n):
        encoded_flag.append(ord(flag[i]) ^ ord(flag[i - 1]))
    for i in range(n):
        encoded_flag[i] ^= encoded_flag[n - i - 1]
    a = []
    for i in range(0, n, 3):
        a.append(encoded_flag[i] + encoded_flag[i + 1])
        a.append(encoded_flag[i + 1] + encoded_flag[i + 2])
        a.append(encoded_flag[i + 2] + encoded_flag[i])
    encoded_flag = a
    for i in range(1, n):
        if i % 6 == 0:
            encoded_flag = displace(encoded_flag, i)
    encoded_flag = ''.join(chr(encoded_flag[i]) for i in range(n))
    return encoded_flag


with open('flag', 'rb') as f:
    flag = f.read().decode('UTF-8')
    print(str(bytes_to_long(flag_encoder(flag).encode())))
```
:::

不難注意到 displace 是將陣列重排，我們也不用管它具體怎麼操作，把 identity 丟進去給它排，就能輕鬆的逆向回來。

:::spoiler **Reverse displace**
```python=
def rev_displace(a, base):

        identity = [i for i in range(n)]
        inv = displace(identity, base)

        res = [0 for i in range(n)]

        for _ in range(n):
                res[inv[_]] = a[_]

        return res
        
for i in range(n-1, 0, -1):
        if i % 6 == 0:
                encoded_flag = rev_displace(encoded_flag, i)
```
:::

接著是將陣列三個三個一組，然後換成兩兩相加的結果，也就是 $$ (a,b,c) \rightarrow (a+b, b+c, c+a) $$ 很明顯地，$$ (d,e,f) \rightarrow \left(\frac{d+f-e}{2},\frac{e+d-f}{2},\frac{f+e-d}{2}\right) $$ 是它的逆操作。在前一步是將陣列頭尾配對，依序給它們做 XOR，那因為 XOR 是 involution，所以直接反著 XOR 回去就能得到原本的陣列。

:::spoiler
```python=
for i in range(0, n, 3):
        encoded_flag[i] = (a[i] + a[i+2] - a[i+1]) // 2
        encoded_flag[i+1] = (a[i+1] + a[i] - a[i+2]) // 2
        encoded_flag[i+2] = (a[i+2] + a[i+1] - a[i]) // 2

for i in range(n-1, -1, -1):
        encoded_flag[i] ^= encoded_flag[n - i - 1]
```
:::

最後由於陣列是透過 flag 相鄰的字元 XOR 得來的，我們枚舉所有可能的開頭，然後看解出來的 flag 有沒有 TMUCTF 即可。

:::spoiler **Get Flag**
```python=
for c in range(128):
        possible_flag = str(chr(c))

        for i in range(1, n):
                next_char = chr(ord(possible_flag[-1]) ^ encoded_flag[i])
                possible_flag += next_char

        if "TMUCTF" in possible_flag:
                print(possible_flag)
```
:::

:::success
TMUCTF{0h!_3nc0d1n6_15_n07_4lw4y5_4_600d_1d34_70_h1d3_7h3_fl46__d0_y0u_46r33?}
:::

## Signed Flag (15 solves, 492 pts)

:::spoiler **Source Code**
```python=
from string import ascii_uppercase, ascii_lowercase, digits
from random import randrange, choice
from Crypto.PublicKey import DSA
from hashlib import sha1
from gmpy2 import xmpz, to_binary, invert, powmod, is_prime


def gen_rand_str(size=40, chars=ascii_uppercase + ascii_lowercase + digits):
    return ''.join(choice(chars) for _ in range(size))


def gen_g(p, q):
    while True:
        h = randrange(2, p - 1)
        exp = xmpz((p - 1) // q)
        g = powmod(h, exp, p)
        if g > 1:
            break
    return g


def keys(g, p, q):
    d = randrange(2, q)
    e = powmod(g, d, p)
    return e, d


def sign(msg, k, p, q, g, d):
    while True:
        r = powmod(g, k, p) % q
        h = int(sha1(msg).hexdigest(), 16)
        try:
            s = (invert(k, q) * (h + d * r)) % q
            return r, s
        except ZeroDivisionError:
            pass


if __name__ == "__main__":
    print("\n")
    print(".___________..___  ___.  __    __    ______ .___________. _______     ___     ___    ___    __  ")
    print("|           ||   \/   | |  |  |  |  /      ||           ||   ____|   |__ \   / _ \  |__ \  /_ | ")
    print('`---|  |----`|  \  /  | |  |  |  | |  ,----"`---|  |----`|  |__         ) | | | | |    ) |  | | ')
    print("    |  |     |  |\/|  | |  |  |  | |  |         |  |     |   __|       / /  | | | |   / /   | | ")
    print("    |  |     |  |  |  | |  `--'  | |  `----.    |  |     |  |         / /_  | |_| |  / /_   | | ")
    print("    |__|     |__|  |__|  \______/   \______|    |__|     |__|        |____|  \___/  |____|  |_| ")

    steps = 10
    for i in range(steps):
        key = DSA.generate(2048)
        p, q = key.p, key.q
        print("\n\nq =", q)
        g = gen_g(p, q)
        e, d = keys(g, p, q)
        k = randrange(2, q)
        msg1 = gen_rand_str()
        msg2 = gen_rand_str()
        msg1 = str.encode(msg1, "ascii")
        msg2 = str.encode(msg2, "ascii")
        r1, s1 = sign(msg1, k, p, q, g, d)
        r2, s2 = sign(msg2, k, p, q, g, d)
        print("\nsign('" + msg1.decode() + "') =", s1)
        print("\nsign('" + msg2.decode() + "') =", s2)
        if i == (steps - 1):
            with open('flag', 'rb') as f:
                flag = f.read()
                secret = flag
        else:
            secret = gen_rand_str()
            secret = str.encode(secret, "ascii")
        r3, s3 = sign(secret, k, p, q, g, d)
        print("\nsign(secret) =", s3, r3)
        h = input("\nGive me SHA1(secret) : ")
        if h == str(int(sha1(secret).hexdigest(), 16)):
            print("\nThat's right, the secret is", secret.decode())
        else:
            print("\nSorry, I cannot give you the secret. Bye!")
            break
```
:::

簡單來說，題目每次會給兩個訊息跟它們的 DSA 簽章，接著在給個簽章，問你說知不知道它簽了什麼訊息。那本身 DSA 沒有問題，有問題的是它重複使用了 nonce，也就是說我們有兩條式子：$$ \begin{align} s_1 & = k^{-1}(h_1+dr) \pmod{q} \\ s_2 & = k^{-1}(h_2+dr) \pmod{q} \end{align} $$ 於是我們有 $$ k = \frac{h_1-h_2}{s_1-s_2} \pmod{q} $$ 解得 $k$ 後，對於新的簽章 $s_3$，我們便可以很輕易地算出 $h_3$，$$ h_3 = k(s_3-s_1)+h_1 \pmod{q} $$

:::spoiler **Script**
```python=
from pwn import *
from hashlib import sha1

bb = b"\') = "
print(bb)

def connect():
	r = remote('185.235.41.166', 5000)

	return r

def sign(r):

	r.recvuntil("q = ")
	q = int(r.recvline().strip())

	r.recvuntil("sign")
	_ = r.recvline()[2:].strip().split(bb)
	
	h1 = int(sha1(_[0]).hexdigest(), 16)
	s1 = int(_[1])

	r.recvuntil("sign")
	_ = r.recvline()[2:].strip().split(bb)
	
	h2 = int(sha1(_[0]).hexdigest(), 16)
	s2 = int(_[1])

	r.recvuntil("sign(secret) = ")
	_ = r.recvline().strip().split(b" ")
	s3 = int(_[0])
	r3 = int(_[1])

	### s1 - s2 = k^-1 (h1 - h2)
	### s3 - s1 = k^-1 (h3 - h1)
	inv_k = pow(h1 - h2, -1, q) * (s1 - s2) % q
	h3 = (pow(inv_k, -1, q) * (s3 - s1) + h1) % q
	c.sendline(str(h3))

c = connect()

step = 10

for i in range(step):
	sign(c)

c.interactive()
```
:::

:::success
TMUCTF{7h15_w45_my_m1574k3__1_f0r607_7h47_1_5h0uld_n3v3r_516n_mul71pl3_m3554635_w17h_4_dupl1c473_k3y!!!}
:::