crypto_方程组思想应用-先知社区

文章分为两部分，一部分是lfsr，另一部分是结式

lfsr

lfsr是一类线性寄存器，不了解的话可以查看我的另一篇文章'CTF_Crypro_PRNG浅析'

lfsr就是在fsr的基础上确保了用来生成新的数值的反馈函数是一个与b1，b2,......,bn-1，bn，这n个数值都相关的线性函数,也就是n元一次方程这样子,当然也就可以使用方程组的方法来解出题目

原理

把整个线性寄存的过程写为如下形式

a_1

x_1 mod 2 + a_2

x_2 mod 2 +……+ a_n

x_n mod 2 = a_{n+1}

a_2

x_1 mod 2 + a_3*x_2 mod 2 +……+ a_{n+1}

x_n mod 2 = a_{n+2}

a_n

x_1 mod 2 + a_{n+1}*x_2 mod 2 +……+ a_{2n-1}*x_n mod 2 = a_{2n}

可以明显地看出这就是一个方程组，所以只要知道mask(x_1

x_n),输入序列(a_1

a_n),输出序列(a_{n+1}~a_{2n})之中的的两个部分就可以得出剩余的一个部分的值从而得到flag

例题

分析

题目给出了504个输出序列，且mask的值为256，那就意味着如下方所示的一个结构：

这时我们已知可以爆破出最后8位数值，也就2^8 = 256种可能，然后再按照列方程组的方式将输入序列、输出序列列入，然后解这个256元一次函数得到256个可能的mask值

然后筛选得到一个有意义的mask字符串，估计就是flag了

exp

结式

知识点

结式（Resultant）是用于判断两个多项式是否存在公共根的工具。对于多项式 f(x) 和 g(x)，结式 Res(f,g,x) 是一个关于多项式系数的行列式，当且仅当 f 和 g 有公共根时其值为零

在密码类题目里面，结式主要用于消去变量，将多变量方程组转化为单变量方程，从而求解。在SageMath中可直接调用 f.resultant(g, x) 计算结式，不嫌麻烦的话通过西尔维斯特矩阵构造行列式计算

结式的通俗解释

结式是一个用来判断两个多项式是否有共同根的工具。简单来说，假设你有两个关于 x 的多项式f(x) 和 g(x)，它们的系数可以组成一个特殊的矩阵（叫做西尔维斯特矩阵），这个矩阵的行列式就是结式。

结式的值有两种情况：1.如果结式为0：说明 f(x) 和 g(x) 有共同的根。2.结式不为0：说明 f(x) 和 g(x) 无共同的根。

也即：结式为0 → 两个多项式有共同根 → gcd 不是 1。结式不为0 → 两个多项式没有共同根 → gcd 是 1。

例题

因为没找到适合的例题就自己口胡了一道

题目

分析

给定两个多项式 f(x, y) 和 g(x, y)，以及一个密文 c，其中：

f(x, y) = x^2 + y^2 - 1

g(x, y) = x^3 + y^3 - 2

密文 c 是通过某个与 x 和 y 相关的密钥生成的。目标是求解 x 和 y 的值，并恢复明文

解答