从一道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$

算法流程

1. 初始化D为$00\cdots00$
2. 考察B的LSB即$b_0$是否为1,如果是1则令$D = D+A$(相当于竖式乘法的乘数最后一位为1时的操作
3. 令B左移一位变成$0b_{n-2}\cdots b_2 b_1$(相当于为下一次竖式乘法做准备，即遍历乘数的每一位判断当前是否需要向D加上A
4. 令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$。
5. 如果上一步的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，但是仍然能感觉到两者间的联系，希望随着学习的深入能够探究两者真正的联系。。

参考链接

Finite_field_arithmetic

快速幂