由于我正在寻找 Python 中的 LFSR 实现,因此我偶然发现了这个主题。但是,我发现根据我的需要,以下内容更准确:
def lfsr(seed, mask):
result = seed
nbits = mask.bit_length()-1
while True:
result = (result << 1)
xor = result >> nbits
if xor != 0:
result ^= mask
yield xor, result
上述 LFSR 生成器基于 GF(2 k ) 模演算 (GF = Galois Field )。刚刚完成了代数课程,我将用数学的方式来解释这一点。
让我们以 GF(2 4 ) 为例,它等于 {a 4 x 4 + a 3 x 3 + a 2 x 2 + a 1 x 1 + a 0 x 0 | a 0 , a 1 , ..., a 4 ∈ Z 2 }(澄清一下,Z n = {0,1,...,n-1} 因此 Z 2 = {0,1},即一位)。这意味着这是所有四次多项式的集合,所有因子都存在或不存在,但没有这些因子的倍数(例如,没有 2x k)。X3、 x 4 + x 3、 1 和 x 4 + x 3 + x 2 + x + 1 都是该组成员的示例。
我们将此集合模数取为四次多项式(即,P(x) ∈ GF(2 4 )),例如 P(x) = x 4 +x 1 +x 0。这种对组的模运算也表示为 GF(2 4 ) / P(x)。供您参考,P(x) 描述了 LFSR 中的“抽头”。
我们还取一个 3 次或更低阶的随机多项式(这样它就不会受到我们的模数的影响,否则我们也可以直接对其执行模数运算),例如 A 0 (x) = x 0。现在每个后续的 A i (x) 都是通过将其乘以 x 来计算的:A i (x) = A i-1 (x) * x mod P(x)。
由于我们处于有限的领域,模运算可能会产生影响,但只有当得到的 A i (x) 至少具有因子 x 4(我们在 P(x) 中的最高因子)时。请注意,由于我们正在处理 Z 2中的数字,因此执行取模运算本身只不过是通过将 P(x) 和 A i (x)中的两个值相加来确定每个 a i是 0 还是 1 (即,0+0=0、0+1=1、1+1=0,或“异或”这两个)。
每个多项式都可以写成一组位,例如 x 4 +x 1 +x 0 ~ 10011。A 0 (x) 可以看作是种子。'times x' 操作可以看作是左移操作。模运算可以看作是位掩码运算,掩码就是我们的 P(x)。
因此,上面描述的算法生成(无限流)有效的四位 LFSR 模式。例如,对于我们定义的 A 0 (x) (x 0 )和 P(x) (x 4 +x 1 +x 0 ) ,我们可以在 GF(2 4 )中定义以下第一个产生的结果(注意 A 0直到第一轮结束时才产生——数学家通常从“1”开始计数):
i Ai(x) 'x⁴' bit pattern
0 0x³ + 0x² + 0x¹ + 1x⁰ 0 0001 (not yielded)
1 0x³ + 0x² + 1x¹ + 0x⁰ 0 0010
2 0x³ + 1x² + 0x¹ + 0x⁰ 0 0100
3 1x³ + 0x² + 0x¹ + 0x⁰ 0 1000
4 0x³ + 0x² + 1x¹ + 1x⁰ 1 0011 (first time we 'overflow')
5 0x³ + 1x² + 1x¹ + 0x⁰ 0 0110
6 1x³ + 1x² + 0x¹ + 0x⁰ 0 1100
7 1x³ + 0x² + 1x¹ + 1x⁰ 1 1011
8 0x³ + 1x² + 0x¹ + 1x⁰ 1 0101
9 1x³ + 0x² + 1x¹ + 0x⁰ 0 1010
10 0x³ + 1x² + 1x¹ + 1x⁰ 1 0111
11 1x³ + 1x² + 1x¹ + 0x⁰ 0 1110
12 1x³ + 1x² + 1x¹ + 1x⁰ 1 1111
13 1x³ + 1x² + 0x¹ + 1x⁰ 1 1101
14 1x³ + 0x² + 0x¹ + 1x⁰ 1 1001
15 0x³ + 0x² + 0x¹ + 1x⁰ 1 0001 (same as i=0)
请注意,您的掩码必须在第四个位置包含“1”,以确保您的 LFSR 生成四位结果。另请注意,“1”必须出现在第零位,以确保您的比特流不会以 0000 位模式结束,或者最后一位将变为未使用(如果所有位都向左移动,您将在一个班次后的第 0 个位置也以零结束)。
并非所有 P(x) 都必然是 GF(2 k ) 的生成器(即,并非所有 k 位掩码都生成所有 2 k-1 -1 个数字)。例如,x 4 + x 3 + x 2 + x 1 + x 0生成 3 组,每组 5 个不同的多项式,或“周期 5 的 3 个周期”:0001,0010,0100,1000,1111;0011,0110,1100,0111,1110;和 0101,1010,1011,1001,1101。请注意,永远不能生成 0000,也不能生成任何其他数字。
通常,LFSR 的输出是“移出”的位,如果执行模运算,则为“1”,否则为“0”。周期为 2 k-1 -1 的 LFSR,也称为伪噪声或 PN-LFSR,遵循 Golomb 的随机性假设,即该输出位“足够”随机。
因此,这些位的序列在密码学中有它们的用途,例如在 A5/1 和 A5/2 移动加密标准或 E0 蓝牙标准中。然而,它们并不像人们想的那样安全:Berlekamp-Massey 算法可用于对 LFSR 的特征多项式(P(x))进行逆向工程。因此,强大的加密标准使用非线性 FSR或类似的非线性函数。与此相关的主题是AES 中使用的S-Box 。
请注意,我已经使用了int.bit_length()
操作。这直到 Python 2.7 才实现。
如果您只想要一个有限位模式,您可以检查种子是否等于结果,然后打破循环。
您可以在 for 循环(例如)中使用我的 LFSR 方法,for xor, pattern in lfsr(0b001,0b10011)
或者您可以重复调用.next()
方法结果的操作,每次都返回一个新(xor, result)
的 -pair。