Noisy Chinese remaindering

本文主要介绍 noisy Chinese remaindering 问题，以及在SekaiCTF中的一道相关的题目。

问题重述

Problem (Noisy Chinese remaindering): 令 $0\le N\le B$，且 $p_1,\cdots,p_n$是互素的整数。给定$n$个集合$S_1,\cdots,S_n$，其中$S_i=\{r_{i,j}\}_{1\le j\le m}$ 包括$N\bmod p_i$和$m-1$个噪声（$\Z_{p_i}$中随机整数），要求恢复$N$，已知解是唯一的。

求解思路

令$P=\prod_{i=1}^np_i$，$L_i\equiv1(\bmod p_i)$ 且 $L_i\equiv0(\bmod\prod_{j\neq i}p_j)$，那么根据中国剩余定理，

$N\equiv\sum\limits_{i=1}^n(N\bmod p_i)L_i\;(\bmod P)$

再线性化这个问题，令$\delta_{i,j}=1$当 $N\equiv r_{i,j}\;(\bmod p_i)$，否则等于0. 那么可以得到：

$N\equiv\sum\limits_{i=1}^n\sum\limits_{j=1}^m\delta_{i,j}r_{i,j}L_i\;(\bmod P)$

这其实是说 $N$ 是 $r_{i,j}L_i$ 的一个小的子集和。

如果按下面的方式造格子：

$L=\begin{pmatrix}P&0&\ldots&\ldots&0\\r_{1,1}L_1&B&0&\ldots&0\\r_{1,2}L_1&0&B&\ddots&\vdots\\\vdots&\vdots&\ddots&\ddots&0\\r_{n,m}L_n&0&\ldots&0&B\end{pmatrix}$

那么可以验证，

$(k,\delta_{1,1},\delta_{1,2},\cdots,\delta_{n,m})L=(N,\delta_{1,1}B,\delta_{1,2}B,\ldots,\delta_{n,m}B)$

并且目标向量被期望是最短向量。

SekaiCTF Noisier CRC

import secrets
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256
from flag import FLAG


isIrreducible = [True for i in range(1 << 17)]

def init():
	for f in range(2, 1 << 17):
		if isIrreducible[f]:
			ls = [0] # store all multiples of polynomial `f`
			cur_term = f
			while cur_term < (1 << 17):
				ls = ls + [x ^ cur_term for x in ls]
				cur_term <<= 1

			for g in ls[2:]:  # the first two terms are 0, f respectively
				isIrreducible[g] = False

def getCRC16(msg, gen_poly):
	assert (1 << 16) <= gen_poly < (1 << 17)  # check if deg = 16
	msglen = msg.bit_length()

	msg <<= 16
	for i in range(msglen - 1, -1, -1):
		if (msg >> (i + 16)) & 1:
			msg ^= (gen_poly << i)

	return msg

def oracle(secret, gen_poly):
	l = int(13.37)
	res = [secrets.randbits(16) for _ in range(l)] 
	res[secrets.randbelow(l)] = getCRC16(secret, gen_poly)
	return res


def main():
	init()  # build table of irreducible polynomials

	key = secrets.randbits(512)
	cipher = AES.new(sha256(long_to_bytes(key)).digest()[:16], AES.MODE_CTR, nonce=b"12345678")
	enc_flag = cipher.encrypt(FLAG)
	print(f"Encrypted flag: {enc_flag.hex()}")

	used = set({})

	for _ in range(int(133.7)):
		gen_poly = int(input("Give me your generator polynomial: "))
		assert (1 << 16) <= gen_poly < (1 << 17)  # check if deg = 16
		if not isIrreducible[gen_poly]:
			print("Invalid polynomial")
			exit(1)

		if gen_poly in used:
			print("No cheating")
			exit(1)

		used.add(gen_poly)

		print(oracle(key, gen_poly))

main()

题目允许我们传133个不同数，并且都得对应一个次数16的不可约多项式$f_i(x)$。然后计算CRC16(key, $f_i(x)$)，并添加12个噪声给我们。需要恢复key。

这里首先要注意计算CRC16相当于一次代数运算。我们将一个数看成是一个多项式，是将这个数进行二进制表示，对应于一个多项式的系数。CRC16(key, $f_i(x)$)等价于计算 $key(x)*x^{16}(\bmod f_i(x))$对应的数。

但我们依然可以建立起类似下面的方程组：

$N\equiv\sum\limits_{i=1}^n\sum\limits_{j=1}^m\delta_{i,j}r_{i,j}L_i\;(\bmod P)$

但不一样的是，对$r_{i,j}L_i$ 模 $P$ 后进行乘以$\delta_{i,j}$求和方程最高次数不增。因此如果不考虑最后512项，求和后的多项式系数都必须为0，从而建立起线性方程组。需要注意的是，$\sum\limits_{j=1}^m\delta_{i,j}\equiv 1(\bmod 2)$ 可以多增加$n$个方程。

最后在方程的解空间里爆破求解。

exp written by shallow:

from pwn import *
from functools import reduce
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256
# context.log_level = 'debug'
io = remote('chals.sekai.team','3006')

io.recvuntil(b'Encrypted flag: ')
flag = io.recvline()[:-1]
PR.<x> = PolynomialRing(GF(2))
def to_poly(m):
    temp = bin(m)[2:]
    temp = [int(i) for i in temp][::-1]
    return PR(temp)
def to_bin(m):
    temp = list(m)[::-1]
    temp = [str(i) for i in temp]
    return int(''.join(temp) , 2)
def getres(p):
    io.recvuntil(b'generator polynomial: ')
    io.sendline(str(p).encode())
    res = eval(io.recvline()[:-1])
    return res
def find_prime():
    plist = []
    for i in range(2**16 , 2**17):
        temp = to_poly(i)
        if temp.is_irreducible():
            plist.append(i)
    return plist

pnum = 133
plist = find_prime()[:pnum]

datalist = []
for i in range(133):
    datalist.append(getres(plist[i]))

plist = [to_poly(i) for i in plist]

data1 = []
for i in range(133):
    temp = [(to_poly(j) * inverse_mod(x^16 , plist[i])%plist[i]) for j in datalist[i]]
    data1.append(temp)

datalist = data1

from functools import reduce

pmul = reduce(lambda x, y: x * y, plist)

def to_vec(data , p):
    temp = data * (pmul//p) * inverse_mod(pmul//p , p) % pmul
    return vector(GF(2) , (list(temp) + [0] * (16*pnum - len(list(temp))))[513:])

keysize = 512
eqnum = 16*pnum - keysize - 1
error = 13
M = Matrix(GF(2) , 0 , eqnum)
for i in range(pnum):
    for j in range(error):
        v = to_vec(datalist[i][j] , plist[i])
        M = M.stack(v)
M2 = Matrix(GF(2), pnum*error , pnum)
for i in range(pnum):
    for j in range(error):
        M2[i*error+j , i] = 1

M1 = block_matrix([[M , M2]])
v = vector(GF(2) ,[0]*(eqnum) + [1]*pnum)

vlist = M1.left_kernel().matrix()
solv = M1.solve_left(v)

def check_sol(v):
    res = []
    for i in range(133):
        temp = [i for i in v[i*13:i*13+13]]
        if temp.count(1) == 1:
            res.append(temp.index(1))
        else:
            return None
    return res 

def getsol(vlist , solv):
    vlen = vlist.nrows()
    for i in range(2**vlen):
        temp = solv
        choice = i
        for j in range(vlen):
            if choice & 1:
                temp += vlist[j]
            choice //= 2
        res = check_sol(temp)
        if res != None:
            return res

res = getsol(vlist , solv)
key = 0
for i in range(133):
    a = datalist[i][res[i]]
    p = plist[i]
    key += a* (pmul//p) * inverse_mod(pmul//p , p) % pmul

print(key)
print(flag)

key = to_bin(key)

cipher = AES.new(sha256(long_to_bytes(key)).digest()[:16], AES.MODE_CTR, nonce=b"12345678")
enc_flag = bytes.fromhex(flag.deocde())
flag = cipher.decrypt(enc_flag)
print(flag)