# LITCTF 2021

## 7 More Caesar Salads (397 solves, 106 pts)

Here’s an easy Crypto problem, try to decipher mshn{Dlsjvtl_Av_Jyfwavnyhwof}

很明顯是 Caesar cipher，直接丟 dcode.fr

:::success
flag{Welcome_To_Cryptography}
:::

## Zzz (241 solves, 110 pts)

Oh no, somebody shuffled the alphabet, can you help us restore the message? Note that the flag is not wrapped with flag{}, so you will have to do that yourself.

題目直接表明是 Substitution cipher，再次丟 dcode.fr XD

:::success
flag{HOW_DO_YOU_KNOW_YOU_ARE_NOT_SLEEPING }
:::

## RSA Improved (161 solves, 116 pts)

The standard RSA only uses 2 prime factors, way too insecure. Let’s improve it by using more factors! More is better, ...right?

from Crypto.Util.number import getPrime
import math

# string to decimal
pt = int(open('flag.txt','rb').read().hex(),16);

primes = [];
n = 1
# euler totient
phi = 1
# public key
e = 65537

while math.log2(n) < 640:
	primes.append(getPrime(32));
	n *= (primes[-1]);
	phi *= (primes[-1] - 1);

# No duplicates
assert(len(primes) == len(list(set(primes))));
# private key
d = pow(e,-1,phi);
# cipher text
ct = pow(pt,e,n);

def decrypt(ct):
	# decode ciphertext for plaintext
	pt = pow(ct,d,n);
	# convert decimal back to string
	return bytes.fromhex(hex()[2:]).decode("utf-8");

print("n = " + str(n));
print("e = 65537");
print("ct = " + str(ct))

可以看到它的 $n$ 是由一堆 32-bits 的質數組成，他們小到直接用 factordb 就會找到所有因數 ...

from output import *
from factordb.factordb import FactorDB

f = FactorDB(n)

f.connect()
primes = f.get_factor_list()

phi = 1

for p in primes:
	phi *= (p-1)

pt = pow(ct, pow(e, -1, phi), n)

from Crypto.Util.number import long_to_bytes

flag = long_to_bytes(pt)
print(flag)

## Geometry is Fun! (104 solves, 126 pts)

通靈題 ... 聽說是將所有三角形面積算出來，拼起來就是 flag 了 ...

## Scottish Flag (87 solves, 131 pts)

Was is it Scottish or British? Oh who remembers these days

import random
import binascii
import math
import sympy


def d(x0,x1,y0,y1):
    return (x0-y0)**2 + (x1-y1)**2

class PRNG:
    def __init__(self,seed0,seed1):
        self.seed0 = seed0;
        self.seed1 = seed1;
        self.L = 1;

    # Returns a random number between [0,x)
    def rand(self,x0,x1):
        return d(self.seed0, self.seed1, x0, x1)


def str2Dec(str):
    return int(binascii.hexlify(str.encode("utf-8")),16);

flag = open('flag.txt','rb').read().decode("utf-8");
flag0 = flag[:len(flag) // 2];
flag1 = flag[len(flag) // 2:len(flag)];

ct0 = str2Dec(flag0);
ct1 = str2Dec(flag1);

g = PRNG(ct0,ct1);
a0 = 1000000000000000000;
a1 = random.randint(0,1000000000000000000);

print(g.rand(0,a0));
print(g.rand(a1,0));
print(g.rand(a1,a0));

所以我們有以下三條等式： $$ \begin{align} g(0, a_0) &= x^2 +\left(y-a_0\right)^2 \\ g(a_1, 0) &= \left(x-a_1\right)^2 +y^2 \\ g(a_1, a_0) &= \left(x-a_1\right)^2 +\left(y-a_0\right)^2 \end{align} $$

其中 $a_0$ 是已知的。後兩式相減得到 $y$ 的一次方程式 $$2a_0y-a_0^2 = g(a_1, 0) - g(a_1, a_0), \quad y = \frac{g(a_1, 0) - g(a_1, a_0) + a_0^2}{2a_0}$$ 代回第一條就可以得到 $x$，$$x = \sqrt{g(0, a_0)-\left(y-a_0\right)^2}$$

from output import *

### a = x^2+(y-a0)^2
### b = (x-a1)^2+y^2
### c = (x-a1)^2+(y-a0)^2

a0 = 1000000000000000000

y = (b - c + a0 ** 2) // (2 * a0)

from decimal import *

getcontext().prec = 3000

x = int(Decimal(a - (y-a0) ** 2) ** (Decimal(1)/Decimal(2)))

import binascii

flag1 = binascii.unhexlify(hex(x)[2:])
print(flag1)

flag2 = binascii.unhexlify(hex(y)[2:])
print(flag2)

:::success
flag{6r1t15h_cr0s5_mak35_g00d_pro6I3m}
:::

## Leftovers (53 solves, 152 pts)

Leftovers are bad, but I guess at least they help the environment by not wasting food.

import random
import binascii
import math
import sympy

random.seed(1337)

class PRNG:
	def __init__(self,seed):
		self.seed = seed;
		self.L = 1;

	# Returns a random number between [0,x)
	def rand(self,x):
		return self.seed % sympy.prevprime(x);

def str2Dec(str):
	return int(binascii.hexlify(str.encode("utf-8")),16);

flag = open('flag.txt','rb').read().decode("utf-8");
ct = str2Dec(flag);

NUMBER_OF_DIGITS = 128;
assert(math.log10(ct) <= 128)

g = PRNG(ct);
res = [];

for i in range(12):
	x = random.randint(1,4e10);
	res.append(g.rand(x));

print(res);

這隻程式有先固定 random seed，因此迴圈中的 $x$ 是固定的，從而 PRNG 回傳的是 flag 除以一個已知的 $p$ 的餘數。用 CRT 就能找到 $$x \pmod{\prod_{i=1}^{12}{p_i}}$$ 已知 flag 有 128 位數，我們必須要有 $$10^{128} \le x + k\prod_{i=1}^{12}{p_i} < 10^{129}$$

import random
import sympy

random.seed(1337)

primes = []
product = 1

for i in range(12):
	x = random.randint(1, 4e10)
	primes.append(sympy.prevprime(x))
	product *= primes[-1]

from output import *

crt = 0

for p, r in zip(primes, res):
	crt += (r * pow(product // p, -1, p) * (product // p))
	crt %= product

for i in range(12):
	assert crt % primes[i] == res[i]

from Crypto.Util.number import long_to_bytes

for _ in range(50000):
	try:
		flag = long_to_bytes(crt + _ * product)
		if b"flag" in flag:
			print(flag)
	except:
		continue

:::success
flag{ch1nese_f00d_l3ft0v3r_th30r3m_1s_v3ry_d3l1c10u5}
:::

## Merkle-Heavenwoman (19 solves, 227 pts)

Do you know that you can make a cryptosystem from the knapsack problem?

import random
import math

def makeKey(n):
	privKey = [random.randint(1,4 ** n)];
	for i in range(1,n):
		privKey.append(random.randint(2 * privKey[-1],4 ** (n + i)));

	q = random.randint(privKey[-1] + 1,2 * privKey[-1]);
	r = random.randint(privKey[-1] + 1,2 * privKey[-1]);

	pubKey = [];
	for i in range(0,n):
		if(i < (n // 2)):
			pubKey.append(privKey[i] ^ q);
		else:
			pubKey.append(privKey[i] ^ r);

	return privKey,q,r,pubKey;

def enc(msg,pubKey):
	n = len(pubKey);
	cipher = 0;
	i = 0;
	a = 0;
	b = 0;
	for bit in msg:
		cipher ^= (int(bit) * pubKey[i]);
		if(i < (n // 2)):
			a ^= int(bit);
		else:
			b ^= int(bit);
		i += 1;

	return a,b,bin(cipher)[2:];

def dec(msg,privKey,q,r,a,b):
	msg ^= (q * a) ^ (r * b);
	pt = "";
	n = len(privKey)
	for i in range(n - 1,-1,-1):
		highestBit = 1 << (int)(math.log2(privKey[i]));
		pt = ('0','1')[(msg & highestBit) != 0] + pt;
		msg ^= ((msg & highestBit) != 0) * privKey[i];
	return bytes.fromhex(hex(int(pt,2))[2:]).decode("utf-8");

flag = open('flag.txt','rb').read();
binary = bin(int(flag.hex(),16))[2:];
keyPair = makeKey(len(binary));
print(keyPair[3]);
ct = enc(binary,keyPair[3]);
print(int(ct[2],2));

這題是 Merkle-Hellman 的變形，唯一的區別是 pubKey[i] 都沒有 mod 一個大質數。又因為 2*privKey[i] < privKey[i+1]，當我們將 pubKey 們用二進位表示時，能夠根據 pubKey[i] 與 pubKey[i+1] 第一個不一樣的 bit 決定 q 或 r 對應的 bit 值。如此一來，我們便能夠輕易地取得偽 privKey，從而解密。

from output import *
import math

highest_bit = 0

for key in public_key:
	highest_bit = max(highest_bit, int(math.log2(key)) + 1)

### Goal: find q, r such that 2 * (public_key[i] ^ q) < 2 * public_key[i+1]

n = len(public_key) # n % 2 == 1

public_key = public_key[::-1]

current_i = 0
current_bit = 1 << highest_bit

q = 0

while current_i < n - n // 2:

	### Find the first different bit

	if public_key[current_i] & current_bit != public_key[current_i + 1] & current_bit:
		if public_key[current_i] & current_bit == 0:
			q ^= current_bit			
		
		current_i += 1
	else:
		if public_key[current_i] & current_bit == current_bit:
			q ^= current_bit

	current_bit = current_bit // 2

r = 0 

for i in range(highest_bit, int(math.log2(current_bit)), -1):

	test_bit = 1 << i

	if public_key[current_i] & test_bit == test_bit:
		r ^= test_bit

while current_i < n - 1:

	if public_key[current_i] & current_bit != public_key[current_i + 1] & current_bit:
		if public_key[current_i] & current_bit == 0:
			r ^= current_bit

		current_i += 1
	else:
		if public_key[current_i] & current_bit == current_bit:
			r ^= current_bit

	current_bit = current_bit // 2
	

for i in range(n):

	if i < n - n // 2:
		public_key[i] = public_key[i] ^ q
	else:
		public_key[i] = public_key[i] ^ r

for i in range(n - 1):
	assert public_key[i] > 2 * public_key[i+1]

def dec(msg, privKey, q, r, a, b):
	msg ^= (q * a) ^ (r * b);
	pt = "";
	n = len(privKey)
	for i in range(n - 1,-1,-1):
		highestBit = 1 << (int)(math.log2(privKey[i]));
		pt = ('0','1')[(msg & highestBit) != 0] + pt;
		msg ^= ((msg & highestBit) != 0) * privKey[i];
	return bytes.fromhex(hex(int(pt,2))[2:]).decode("utf-8");

public_key = public_key[::-1]

for a in range(2):
	for b in range(2):
		try:
			flag = dec(ct, public_key, q, r, a, b)
			print(flag)
		except:
			pass

:::success
flag{why_n0t_u53_nph4rd_f0r_3ncypt10n}
:::

## Filter Collector (9 solves, 303 pts)

I look cute in Instagram Filters. Let’s try to collect some more
nc filtercollector.litctf.live 1337

#!/usr/bin/python3
from Crypto.Util.number import getPrime
import random
import math
import cmath

Welcome = "Instagram filters are fun, aren't they?"
print(Welcome);

flag = int(open('flag.txt','rb').read().hex(),16);
print(flag)
k = 7
p = int(input("Input your favorite mod: "));
assert(p * p < flag);

# Divides tot randomly into n parts
def get_partition(tot,n):
	partitions = [tot];
	for i in range(n - 1):
		partitions.append(random.randint(0,tot));
	partitions.sort()
	for i in range(n - 1,0,-1):
		partitions[i] -= partitions[i - 1];
	return partitions

def gen_poly(partitions,n):
	poly = [];
	cnt = 0
	for i in range(n):
		if(i % k == 0):
			poly.append(partitions[cnt]);
			cnt += 1;
		else:
			poly.append(random.randint(0,p - 1));
	assert(cnt == len(partitions));
	return poly

def hash(poly,x):
	res = 0;
	for i,c in enumerate(poly):
		res += c * pow(x,i,p) % p;
	return res % p;

partitions = get_partition(flag,(199 // k) + 1);
poly = gen_poly(partitions,200);
for i in range(k):
	x = int(input("Input the a number: "));
	y = hash(poly,x);
	print("The hash of the number under your mod filter is " + str(y));

由代碼可知，server 會生成一個 $199$ 次的多項式 $$f(x) = \sum\limits_{i=0}^{199}a_{i}x^{i}$$ 滿足 $$a_0+a_7+\cdots+a_{196} = flag$$ 而我們能夠做的事情是給定 $p$ 跟 $x_1, x_2, \dots, x_7$，然後拿到 $f\left(x_1\right), f\left(x_2\right), \dots, f\left(x_7\right)$ 模 $p$ 的值。這有沒有模 $p$ 其實沒什麼差，我們就是要代所有的 $7$ 次方根進去，然後線性組合會得到 $flag$ 模 $p$。
假設 $g$ 是非 $1$ 的 $7$ 次方根，那麼 $$0 = g^7 - 1 = \left(g-1\right)\left(\sum\limits_{i=0}^{6}{g^{i}}\right) \rightarrow \sum\limits_{i=0}^{6}{g^{i}} = 0 $$ 因此 $$\sum\limits_{i=1}^{7}f(g^{i}) = \sum\limits_{i=0}^{199}a_{i}\left(\sum\limits_{j=1}^{7}{g^{ij}}\right) = 7*flag$$
因為有規定 $p^2 < flag$，我們要連到 server 數次拿到 $flag$ 模 $p$ 的值。

from pwn import *
from Crypto.Util.number import isPrime, long_to_bytes

primes = []
generators = []

for p in range(7001, 14001, 7): 
	if isPrime(p):
		for i in range(2, p):
			if pow(i, 7, p) == 1:
				primes.append(p)
				_ = [pow(i, j, p) for j in range(7)]
				generators.append(_)
				break
		continue

res = []

for p, g in zip(primes, generators):
	r = process("filter_collector.py")
	r.recvuntil("favorite mod: ")
	r.sendline(str(p))
	
	residues = []

	for i in range(7):
		r.recvuntil("Input the a number: ")
		r.sendline(str(g[i]))
		r.recvuntil("filter is ")
		residues.append(int(r.recvline().strip()))

	r.close()

	_ = (sum(residues) * pow(7, -1, p)) % p

	res.append(_)

product = 1

for p in primes:
	product *= p

crt = 0

for p, r in zip(primes, res):
	crt += r * pow(product // p, -1, p) * (product // p)
	crt %= product

flag = long_to_bytes(crt)
print(flag)

:::success
flag{w3_mu5t_un1t3_th3_r00t5_t0g3th3r}
:::

## Tree Hash (9 solves, 303 pts)

#!/usr/bin/python3
from sympy import prevprime
from random import randint
import sys

#init

sys.setrecursionlimit(1000)

#constants

n = 100
m = prevprime(n ** (n - 2))
k = 65537
w = randint(1, n)

mx = 80 #less than log256(m)
flagkey = b"This piece of text is the flag key wow omg!"

flag = open("./flag.txt", "r").read()

#hash funcs

def hexToStr(s):
    try:
        return bytes.fromhex(s).rstrip(b'\x00')
    except:
        return ""

def strToInt(s):
    return int.from_bytes(s, "little")
    
def intHash(x):
    return pow(x, k, m)

def intToArray(x):
    a = []
    for i in range(n - 2):
        a.append(x % n)
        x //= n
    return a

def arrayToTree(a):
    d = [0] * n
    for i in a:
        d[i] += 1

    a.append(a[-1])

    j, l = 0, 0
    e = []
    for i in a:
        while d[j] != 0 or i == j:
            j += 1
        if d[l] != 0 or i == l:
            l = j
        
        e.append((i, l))

        d[i] -= 1
        d[l] -= 1

        if d[i] == 0 and i < j:
            l = i

    return e

def dfs(g, c, p):
    ret = c
    for i in g[c]:
        if i != p:
            ret = max(ret, dfs(g, i, c))

    return ret

def treeHash(e):
    g = [[] for i in range(n)]

    for i in e:
        g[i[0]].append(i[1])
        g[i[1]].append(i[0])

    ret = 1
    for i in e:
        ret *= (dfs(g, i[0], i[1]) + dfs(g, i[1], i[0]) + w)

    return ret

def H(s):
    x = strToInt(s)
    y = intHash(x)
    a = intToArray(y)
    e = arrayToTree(a)
    return treeHash(e)

#interaction

print("Welcome to my TreeHash generator.")
print(f"You can input any string of length up to {mx} chars, and I'll give you its hash!")
print("Note: trailing null bytes are stripped.\n")

print("I am testing its security, so if you can generate a collision with the flag key I'll give you the flag!")
print(f"The flag key is: {str(flagkey)[1:]}\n")

while(1):
    s = input("Input a hex encoded string: ")
    print('')

    s = hexToStr(s)

    if len(s) == 0:
        print("Invalid hex format.\n")
        continue

    if len(s) > mx:
        print("String length too large.\n")
        continue

    print(f"String {str(s)[1:]} has hash: \n{H(s)}\n")

    if s == flagkey:
        print("This is just the flag key smh.\n")
    elif H(s) != H(flagkey):
        print("The string is not a collision.\n")
    else:
        print("Wtmoo you found a collision!")
        print(f"The flag is: {flag}")
        break

我們的目標是求出 $s$ 使得 $$H(s)=H(flag\_key)$$ 一個很直覺的想法是讓 $$dfs(g, i[0], i[1]) = dfs(g, i'[0], i'[1]), dfs(g, i[1], i[0]) = dfs(g, i'[1], i'[0])$$ 不難發現 $dfs$ 是去算將 $cp$ 這條邊砍掉後，$c$ 的連通塊中最大的下標。因此兩個 $dfs$ 代表的是將某條邊砍掉後，兩個連通塊中個別最大的下標。因此問題便轉換成，給定 $n-1$ 組 $\{(a_i, b_i)\}$，我們是否能找到一棵樹使得，依次砍掉 $n-1$ 條邊，蒐集兩個連通塊個別最大的下標組成的數對，它們形成的集合恰恰好是 $\{(a_i, b_i)\}$

不妨假設 $a_i \le a_{i+1} < b_j = n-1$，現在考慮一棵像竹子的樹，且將 $n$ 放在最右邊，我們希望由左而右砍掉邊，左邊最大的數恰恰是 $a_i$。作法很簡單，如果 $a_{i-1} < a_i$，我們就把 $a_i$ 直接放上去；否則，用隨便一個沒用過的小數字替代 $a_{i-1}$ 這個點，然後把 $a_{i-1}$ 接回去。

### Construct a path-like tree such that the corresponding 
### treehash equals to that of flag key

cnt, d, parent ,visited = [0] * n, [0] * n, [0] * n, [False] * n

for i in a:
	cnt[i] += 1
	
j, prev, y = 0, -1, -1

for i in range(n-1):
		
	if cnt[i] > 0:
		if prev != -1:
			d[i] += 1
			d[prev] += 1
    		parent[prev] = i
		else:
			y = i	# record the leaf with least ind

		prev = i
		cnt[i] -= 1
		visited[i] = True

	tmp = []

	while cnt[i] > 0:
		while visited[j]:
			j += 1
	
		tmp.append(j)

		cnt[i] -= 1
		visited[j] = True

	shuffle(tmp)

	for v in tmp:
		d[v] += 1
		d[prev] += 1
		parent[prev] = v

		prev = v 

d[prev] += 1
d[n - 1] += 1
parent[prev] = n - 1
parent[n - 1] = -1

下一個挑戰是將樹轉回陣列，那這邊它在做的其實是 Prufer code，

Prufer = []

j = y # the leaf with least ind

for i in range(n - 2):

    x = parent[j]
    Prufer.append(x)

    d[x] -= 1

    # if y becomes a leaf with ind_y < ind_x, then it must be the next leaf with least ind
    if d[x] == 1 and x < y: 
        j = x
    else:
        y += 1

        while d[y] != 1:
            y += 1
			
        j = y

最後將 Prufer 這個陣列轉回字串

res = 0

for i, j in enumerate(Prufer):
	res += j * (n ** i)

num = pow(res, pow(k, -1, m - 1), m)

s = num.to_bytes((7 + num.bit_length()) // 8, 'little')

payload = s.hex()

注意到題目有要求 $s$ 不能太長，所以上述的做法才會隨機 shuffle 準備加入的小數字，讓最終換回來的 $num$ 不會太大。

:::success
flag{crypt0_1s_b4s1c4lly_cp_4nyw4y}
:::

## The Oracle's Prophecy (1 solves, 463 pts)

似乎是 AES-PCBC Adjacent Swap Attack，之後有空再研究。