encryption - 如何找到抽取的 LFSR 的多项式？

Question

我知道，如果您抽取线性反馈移位寄存器生成的系列，您会得到一个新系列和一个新多项式。例如，如果您对由多项式 x4+x+1 的 LFSR 生成的系列中的每五个元素进行采样，您将获得由 x2+x+1 生成的系列。我可以通过蛮力找到第二个多项式 (x2+x+1)，这对于低阶多项式来说很好。然而，对于高阶多项式，暴力破解所需的时间变得不合理。

所以问题是:是否有可能通过分析找到抽取多项式？

Answer 1

最近看了这篇文章，看到你的问题就想到了，希望能帮到你。:oÞ

给定 GF(q) 上的一个本原多项式，可以通过抽取从初始多项式获得的 LFSR 序列来获得另一个本原多项式。这在下面的代码中进行了演示。

K := GF(7); C := PrimitivePolynomial(K, 2); C; D^2 + 6*D + 3 In order to generate an LFSR sequence, we must first multiply this polynomial by a suitable constant so that the trailing coefficient becomes 1.

C := C * Coefficient(C,0)^-1; C; 5*D^2 + 2*D + 1 We are now able to generate an LFSR sequence of length 72 - 1. The initial state can be anything other than [0, 0].

t := LFSRSequence (C, [K| 1,1], 48); t; [ 1, 1, 0, 2, 3, 5, 3, 4, 5, 5, 0, 3, 1, 4, 1, 6, 4, 4, 0, 1, 5, 6, 5, 2, 6, 6, 0, 5, 4, 2, 4, 3, 2, 2, 0, 4, 6, 3, 6, 1, 3, 3, 0, 6, 2, 1, 2, 5 ] We decimate the sequence by a value d having the property gcd(d, 48)=1.

t := Decimation(t, 1, 5); t; [ 1, 5, 0, 6, 5, 6, 4, 4, 3, 1, 0, 4, 1, 4, 5, 5, 2, 3, 0, 5, 3, 5, 1, 1, 6, 2, 0, 1, 2, 1, 3, 3, 4, 6, 0, 3, 6, 3, 2, 2, 5, 4, 0, 2, 4, 2, 6, 6 ] B := BerlekampMassey(t); B; 3*D^2 + 5*D + 1 To get the corresponding primitive polynomial, we multiply by a constant to make it monic.

B := B * Coefficient(B, 2)^-1; B; D^2 + 4*D + 5 IsPrimitive(B); true