menu badmonkey's blog
more_vert
chevron_right 首页 » Math » 正文
从一道re题看有限域乘法
2020-05-11 | Math | 暂无评论 | 214 次阅读 | 1005字

从一道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}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*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}*t1_{ij} $$

于是根据矩阵乘法的性质可以得到

$$ input*(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

快速幂

发表评论
暂无评论
textsms
account_circle
email
link
arrow_back 上一篇
arrow_forward 下一篇