CryptoCTF 2023 easy分类团队解题writeup

这次 easy 分类偏简单，

不过由于配合得不是很好，所以在实战中会有部分题目卡壳的情况

不过还好能有其他人也帮忙看一看，所以马上就能够解围

Did it!

题目描述

记 $n = 127$，$N=\{0, 1, 2, \ldots, n-1\}$，有随机的未知 $K \subseteq N$，且 $|K| \le 20$。

有至多 12 次的机会，输入一个集合 $A \subseteq N$，且 $|A| \le 20$，返回结果

$\{x_0^2 \bmod n + r_0, x_1^2 \bmod n + r_1, \ldots\}$

对于所有 ${x_i \in A - K}$

其中 $r_i \in \{0, 1\}$ 为一个关于 $x_i$ 的随机数。

如果输入的 $A = K$，则得到 flag。

我的解答

也就是说，有至多 11 次的机会去得到结果，然后就要猜出 $K$ 来。

因为 $n$ 是素数，所以对于结果中的每一组 $x_i^2 \bmod n + r_i$，都可以枚举 $r_i$，通过开平方求得可能的 $x_i$。然后再用 $A$ 减去这些 $x_i$ 构成的集合，就得到 $K$ 中可能包含的元素。

另外，我们把输入的 $A$ 元素个数弄小一点，以减小下面的情况出现的概率：

$x_i^2 \bmod n + r_i = k_j^2 \bmod n + r_i'$

如果不幸地，上式成立的话，我们就会错误地把 $A \cap K$ 中的元素 $k_j$ 也当作 $A-K$ 中的元素给移除掉，其中 $r_i’$ 为我们上面枚举的 $r_i$。因为至多 12 次机会去得到结果，所以每次猜测的集合大小至多为 $\lceil127/12\rceil = 11$。即使是这样，也有很大概率弄不出所有的 20 个数，也要通过诸如赌 $K$ 在生成的过程中生成一样的数，从而导致 $|K|<20$ 来增大能求出的概率。（当然不排除能有将 $\{0, 1, \ldots, 127\}$ 进行科学地划分以避免上述情形出现的手法，但是能通过碰概率猜出 $K$ 就咸鱼了）

代码如下：

from pwn import *
from sage.all import *

class Gao:
    def __init__(self):
        # self.conn = process(['python3', 'another.py'])
        self.conn = remote('01.cr.yp.toc.tf', 11337)
        self.ans = set()
        self.Zp = Zmod(127)
    
    def gao_guess(self, subset):
        self.conn.sendline(','.join(str(x) for x in subset))
        self.conn.recvuntil('+ DID = ')
        res = eval(self.conn.recvline())
        A_minus_K = []
        for y in res:
            for r in [0, 1]:
                x2 = self.Zp(y - r)
                x_list = x2.nth_root(2, all=True)
                A_minus_K.extend(map(ZZ, x_list))
        
        self.ans |= set(subset) - set(A_minus_K)
    
    def gao(self):
        my_guess = list(range(127))
        shuffle(my_guess)
        my_guess_batch = [my_guess[i:i+20] for i in range(0, len(my_guess), 11)] # 12 # 20
        print(f'{len(my_guess_batch) = }')
        for A in my_guess_batch:
            self.gao_guess(A)
        print(f'{len(self.ans) = }')
        self.conn.sendline(','.join(str(x) for x in self.ans))
        self.conn.recvline()
        res = self.conn.recvline()
        self.conn.close()
        if b'Too' in res:
            return False
        else:
            print(res)
            return True

if __name__ == '__main__':
    while True:
        g = Gao()
        res = g.gao()
        if res:
            break

得到 flag 为：

1	CCTF{W4rM_Up_CrYpt0_Ch4Ll3n9e!!}

再次尝试：将 $N$ 进行划分为两两不交的子集 $N_0, N_1, N_2, \ldots, N_{11}$，使得

$|N_i| \le 20$ 对于 $i = 0, 1, \dots, 11$
不存在 $x_i, x_i’ \in N_i, r_i, r_i’ \in \{0, 1\}$，使

$x_i^2 \bmod n + r_i = x_i'^2 \bmod n + r_i'$

因此可以做一个很简单的贪心：对于 $x = 0, 1, \dots, n-1$：

尝试放到第 $i$ 个集合 $N_i$ 里面
如果 $|N_i| = 20$，那么就不能放到这个集合里面
计算 $x^2 \bmod n$ 和 $x^2 \bmod n + 1$，如果这两个值都不和 $N_i$ 所有值的平方和平方加一冲突，那么就能把 $x$ 加到这个集合里面
否则就不能放到这个集合里面
如果不能放到第 $i$ 个集合 $N_i$ 里面，那么就尝试放到第 $i+1$ 个集合 $N_{i+1}$ 里面。

贪心构造划分的代码如下：

t = 12
n = 127

A_list = [[] for i in range(t)]
A_char_list = [set() for i in range(t)]

for i in range(n):
    for j in range(t):
        if (len(A_list[j]) == 20):
            continue
        for offset in [0, 1]:
            s = pow(i, 2, n) + offset
            if (s in A_char_list[j]):
                break
        else:
            A_list[j].append(i)
            for offset in [0, 1]:
                s = pow(i, 2, n) + offset
                A_char_list[j].add(s)
            break
    else:
        raise Exception('GG')

print(A_list)

将得到的划分结果应用在猜测中：

from pwn import *
from sage.all import *

class Gao:
    def __init__(self):
        # self.conn = process(['python3', 'another.py'])
        self.conn = remote('01.cr.yp.toc.tf', 11337)
        self.ans = set()
        self.Zp = Zmod(127)
    
    def gao_guess(self, subset):
        self.conn.sendline(','.join(str(x) for x in subset))
        self.conn.recvuntil('+ DID = ')
        res = eval(self.conn.recvline())
        A_minus_K = []
        for y in res:
            for r in [0, 1]:
                x2 = self.Zp(y - r)
                x_list = x2.nth_root(2, all=True)
                A_minus_K.extend(map(ZZ, x_list))
        
        self.ans |= set(subset) - set(A_minus_K)
    
    def gao(self):
        my_guess_batch = [
            [0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 19, 20, 21, 22, 23],
            [1, 12, 17, 18, 24, 25, 26, 27, 28, 29, 30, 31, 32, 34, 35, 36, 37, 38, 39, 40],
            [33, 41, 42, 43, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 59, 60, 62, 63, 87],
            [44, 56, 57, 58, 61, 65, 67, 68, 72, 73, 74, 78, 79, 80, 81, 82, 84, 85, 88, 89],
            [64, 66, 69, 70, 71, 86, 90, 91, 92, 93, 95, 96, 97, 98, 99, 100, 101, 102, 103, 105],
            [75, 76, 77, 83, 94, 104, 107, 108, 109, 110, 111, 112, 114, 115, 116, 117, 118, 119, 120, 122],
            [106, 113, 121, 123, 124, 125, 126]
        ]
        for A in my_guess_batch:
            self.gao_guess(A)
        print(f'{len(self.ans) = }')
        self.conn.sendline(','.join(str(x) for x in self.ans))
        self.conn.recvline()
        res = self.conn.recvline()
        self.conn.close()
        if b'Too' in res:
            return False
        else:
            print(res)
            return True

if __name__ == '__main__':
    while True:
        g = Gao()
        res = g.gao()
        if res:
            break

就能不用多次尝试就能猜出集合 $K$ 来。

Suction

题目描述

RSA 中，$N=pq$，但是 $p, q$ 仅有 128 位。

题目给出的 $(N, e, c)$ 的后 8 位均未知，且 $e$ 为 16 位素数。

求明文 $m$。

我的解答

所以就是嗯枚举就行了。

枚举 $N$ 的后 8 位，并尝试分解。如果能分解成 2 个 128 位素数之积，那么可能就是 $N$。注意 $N$ 为两个奇素数之积，必为奇数
枚举 $e$ 的后 8 位，如果是素数，并且 $e$ 与 $\phi(N)$ 互素，那么可能就是 $e$。注意 $e$ 为奇素数
枚举 $c$ 的后 8 位，如果解密的 $m$ 满足可见字符的条件，那么可能就是 $m$

不过对 256 位的 $N$ 进行分解这个时间是一个玄学的东西，需要挂着跑一阵子。

枚举 $N$ 的代码：

from tqdm import trange

PKEY = 55208723145458976481271800608918815438075571763947979755496510859604544396672

bitsequence = f'{PKEY:b}'
N, e = bitsequence[:-8], bitsequence[-8:]
print(len(N))

N, e = map(lambda x: int(x, 2), (N, e))

for i in trange(2^7):
    N_ = N * 2^8 + 2 * i + 1
    fac = factor(N_)
    if (len(fac) == 2):
        for p, alpha in fac:
            if (p.nbits() != 128) or (alpha != 1):
                break
        else:
            print('AOLIGEI!!!')
            print(f'{N_ = }')
            print(f'{fac = }')

得到 $N$ 以及分解：

1 2	N_ = 55208723145458976481271800608918815438075571763947979755496510859604544396613 fac = 188473222069998143349386719941755726311 * 292926085409388790329114797826820624883

继续枚举可能的加密指数 $e$ 和密文 $c$，并对解出来的明文 $m$ 作检验：

from tqdm import trange

PKEY = 55208723145458976481271800608918815438075571763947979755496510859604544396672

bitsequence = f'{PKEY:b}'
N, e = bitsequence[:-8], bitsequence[-8:]
print(len(N))

N, e = map(lambda x: int(x, 2), (N, e))

N = 55208723145458976481271800608918815438075571763947979755496510859604544396613
p, q = 188473222069998143349386719941755726311, 292926085409388790329114797826820624883

e_list = []

for i in range(2^7):
    e_ = e * 2^8 + 2 * i + 1
    if is_prime(e_) and gcd(e_, p-1) == 1 and gcd(e_, q-1) == 1:
        e_list.append(e_)

from Crypto.Util.number import *

ENC = 127194641882350916936065994389482700479720132804140137082316257506737630761

for i in trange(2^8):
    c = ENC * 2^8 + i
    for e_ in e_list:
        d_ = inverse_mod(e_, (p-1)*(q-1))
        m = pow(c, d_, N)
        msg = long_to_bytes(int(m))
        if (all(32 <= x < 128 for x in msg)):
            print(f'{msg = }')

并补上 flag 的格式，得到 flag 为：

1	CCTF{6oRYGy&Dc$G2ZS}

Blue Office

题目描述

题目基于流密钥。

题目先将流密钥 d 作 reseed 变换，再将明文 msg 的第 c 个字节和密钥 d 作异或生成密文：

while c < l:
    d = reseed(d)
    enc += (msg[c] ^ ((d >> 16) & 0xff)).to_bytes(1, 'big')
    c += 1

reseed 变换实现如下：

1 2	def reseed(s): return s * 214013 + 2531011

给密文 enc，试恢复明文 msg。

我的解答

因为这里 d 实际被拿去作异或的部分只有第 16-23 位，而且 reseed 函数是线性的，所以整个系统关于 d 模 $2^{24}$ 是等价的。

所以只需枚举初始随机数 d 在 $[0, 2^{24})$ 范围内，然后判断明文 msg 是否均为可见字符即可。

代码如下：

enc = b'b0cb631639f8a5ab20ff7385926383f89a71bbc4ed2d57142e05f39d434fce'
enc = bytes.fromhex(enc.decode())

from tqdm import trange

def reseed(s):
    return s * 214013 + 2531011

def encrypt(s, msg):
    assert s <= 2**32
    c, d = 0, s
    enc, l = b'', len(msg)
    while c < l:
        d = reseed(d) # linear
        enc += (msg[c] ^ ((d >> 16) & 0xff)).to_bytes(1, 'big')
        c += 1
    return enc

for seed in trange(2 ** 24):
    flag = encrypt(seed, enc)
    if (all(32 < x < 128 for x in flag)):
        print(f'flag = {flag}')

解得 flag 为：

1	CCTF{__B4ck_0r!F1c3__C1pHeR_!!}