从一道re题看有限域乘法
前些天正好恰逢五一假期，一起跟Venom打了De1CTF(全程被带飞。做了几道简单的密码题，难题肝不动)。在比赛过程中re爷爷有一道题目解到一半，需要求解一个很诡异的方程，一开始Vanish师傅，Re爷爷和我都以为是个lfsr的方程组。但是我试了一下没有解出来，后来V神迅速解了出来(V神牛批），我也就没有再看。赛后看V神的脚本的时候，仔细看了看好像跟lfsr没啥太大关系，重新看了一遍题目中的信息，突然回想了起来之前草草看过的有限域乘法，于是便有了这篇文章。(本来投的是安全客，结果投的人太多了，没过审，就放这里叭。。
有限域的意义
元素数量有限的域，其中较为常用的有限域为Galois field，元素的数量为 $p^n$ ，记作$GF(p^n)$，其中$p$为素数，在实际应用中通常选择以2为底数，构造有限域$GF(2^n)$，这和二进制在计算机中的广泛应用有关，比如AES中就涉及到了$GF(2^8)$上的运算，我们知道在二元域中，加法运算和减法运算都可以视作异或运算，乘法被视作与运算。其实在有限域上的多项式商环的运算也是极其重要的，总之有限域对于密码学来说算的上是基石。
有限域上的多项式的表示形式
对于形如$GF(2^n)$的有限域，其中多项式$a_{n-1}\cdot x^{n-1}+\cdots a_1x+a_0$的二进制表示形式为$a_{n-1}a_{n-2}\cdots a_0$其中$a_i \in {0,1}$
多项式的加法，减法运算
多项式$A:a_{n-1}x^{n-1}+\cdots a_1x+a_0$
多项式$B:b_{n-1}x^{n-1}+\cdots b_1x+b_0$
多项式$D=A+B$，
即$(a_{n-1}+b_{b-1})x^{n-1}+\cdots (a_1+b1)x+(a_0+b_0)$
例如在$GF(2^8)$上$(x^6+x^4+x+1)+(x^7+x^6+x^3+x)$
等价于$x^7+2x^6+x^4+x^3+2x+1$
即$x^7+x^4+x^3+1$
有限域上多项式商环的乘法运算
总体思想类似于快速幂取模的感觉，建议不熟悉快速幂取模的读者先了解一下快速幂
设$GF(2^n)$上的多项式商环的模数多项式为$C:c_nx^n+c_{n-1}x^{n-1}+\cdots c_1x+c_0$，其二进制形式为$c_{n-1}c_{n-2}\cdots c_1 c_0$
多项式$A:a_{n-1}x^{n-1}+\cdots a_1x+a_0$,其二进制表示形式为$a_{n-1}a_{n-2}\cdots a_1 a_0$
多项式$B:b_{n-1}x^{n-1}+\cdots b_1x+b_0,$其二进制表示形式为$b_{n-1}b_{n-2}\cdots b_1 b_0$
设$D=A \cdot B$,其二进制表示形式为$d_{n-1}d_{n-2}\cdots d_1 d_0$
算法流程
- 初始化D为$00\cdots00$
- 考察B的LSB即$b_0$是否为1,如果是1则令$D = D+A$(相当于竖式乘法的乘数最后一位为1时的操作
- 令B左移一位变成$0b_{n-2}\cdots b_2 b_1$(相当于为下一次竖式乘法做准备，即遍历乘数的每一位判断当前是否需要向D加上A
- 令A右移一位变成$a_{n-1}a_{n-2}\cdots a_1 a_00$,记此时的A的MSB为carry，然后保留低n位形成新的$A:a_{n-2}a_{n-3}\cdots a_00$(右移相当于乘多项式A乘了一个x，理解快速幂的话很好理解这一步的右移,保留carry是为了取模运算的准备，保留低n位是因为最终结果一定小于$x^n$。
- 如果上一步的carry为1，说明上一步运算时需要取模的运算，但是由于已经去掉了MSB所以当前的A已经小于$x^n$只需要减去低n位的C即可$A = A-C’$即$(a_{n-2}\oplus c_{n-1})(a_{n-3}\oplus c_{n-2}) \cdots (a_0\oplus c_1) (0\oplus c_0)$,反之不需要进行取模运算
De1CTF 2020 little elves
根据逆向爷爷的信息，可以得到如下脚本(完整脚本详见Github：
# # -*- coding:utf-8 -*-
def main():
t1 = ... # 44*44 矩阵
t2 = ... # 1*44 数组
input = '1' * 44 # 44 位的flag
for i in range(44):
ch3 = 0
for j in range(44):
ch1 = input[j]
ch2 = t1[i][j]
for k in range(8):
if ch2 & 1:
ch3 ^= ch1
flag = ch1 & 0x80
ch1 = (ch1 << 1) & 0xff
if flag:
ch1 ^= 0x39
ch2 >>= 1
print i
assert (ch3 == t2[i])
print 'end.'
主要逻辑在最内层的循环
for k in range(8):
if ch2 & 1:
ch3 ^= ch1
flag = ch1 & 0x80
ch1 = (ch1 << 1) & 0xff
if flag:
ch1 ^= 0x39
ch2 >>= 1
这里的ch2相当于多项式B，ch1相当于多项式A,ch3相当于D,flag相当于carry，0x39相当于C的低8位。于是这个for循环构成了一个在$GF(2^8)$的模$x^8+x^5+x^4+x^3+1$的多项式乘法。其中满足
$$
t2_{i} = \sum_{j=0}^n input_{j} \cdot 1_{ij}
$$
于是根据矩阵乘法的性质可以得到
$$
input \cdot (t1)^{T} = t2
$$
不过需要注意的是，所有的乘法，加法运算都是在有限域上进行的。于是可以使用sage快速求解，脚本如下:
F.<x> = GF(2^8,modulus=[1,0,0,1,1,1,0,0,1])
mt = .... # 初始的44*44矩阵
t = ... # 初始的1*44 矩阵
#构造多项式矩阵
for i in range(44):
for j in range(44):
mt[i][j] = F(mt[i][j].bits())
# 构造多项式向量
for i in range(44):
t[i] = F(t[i].bits())
# 矩阵转置
MT = matrix(F, mt).T
# t2向量
TT = matrix(F, t)
# input 向量
inp = MT.solve_left(TT)
flag = [i.integer_representation() for i in inp[0].list()]
print("".join([chr(i) for i in flag]))
完整脚本详见Github
未完待续
虽然这道题并不是LFSR，但是仍然能感觉到两者间的联系，希望随着学习的深入能够探究两者真正的联系。。