LFSR

在密码学中，流密码（Stream cipher），又译为流加密、数据流加密，是一种对称加密算法，加密和解密双方使用相同伪随机加密数据流（pseudo-random stream）作为密钥，明文数据每次与密钥数据流顺次对应加密，得到密文数据流。实践中数据通常是一个位（bit）并用异或（xor）操作加密。

该算法解决了对称加密完善保密性（perfect secrecy）的实际操作困难。完善保密性由克劳德·香农于 1949 年提出。由于完善保密性要求密钥长度不短于明文长度，故而实际操作存在困难，改由较短数据流通过特定算法得到密钥流。

伪随机密钥流（keystream）由一个随机的种子（seed）通过算法（称为：PRG，pseudo-random generator）得到，k 作为种子，则 G(k) 作为实际使用的密钥进行加密解密工作。为了保证流加密的安全性，PRG 必须是不可预测的。弱算法包括 glibc random() 函数，线性同余生成器（linear congruential generator）等。

实际序列密码使用的密钥位序列 $s_{1}, s_{2}, …$ 是通过具有某种属性的密钥流生成器得到的。一种得到长伪随机序列的简单方法就是使用线性反馈移位寄存器（LFSR）, LFSR 很容易使用硬件实现，许多序列密码都是使用 LFSR 来实现的，但不是全部。

构成

一个 LFSR 有若干时钟存储原件（触发器）和一个反馈路径组成，存储原件的数目给出了 LFSR 的度。换言之，一个拥有 m 个触发器的 LFSR 可以称为度为 m。反馈网络计算移位寄存器中某些触发器的 XOR 和，并将其作为上一个触发器的输入。

如果这里的反馈函数是线性的，我们则将其称为 LFSR，此时该反馈函数可以表示为：

$$ f(a_{1},a_{2}, …, a_{n}) = c_{1}a_{1} \oplus c_{2}a_{2} \oplus … \oplus c_{n}a_{n}$$

其中$c_{i}=0$或$1$，$⊕$表示异或（模二加）。

（例）加密过程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# R 为初始状态，mask 为掩码
def LFSR(R, mask):
    # 把 R 左移一位后低32位（即抹去 R 的最高位，然后在 R 的最低位补 0）的值赋给 output 变量
    output = (R << 1) & 0xffffffff
    # 把传入的 R 和 mask 做按位与运算，运算结果取低 32 位，将该值赋给 i 变量
    i = (R & mask) & 0xffffffff
    # 从 i 的最低位向 i 的最高位依次做异或运算，将运算结果赋给 lastbit 变量
    lastbit = 0
    while i!= 0:
        lastbit ^= (i & 1)
        i = i >> 1
    # 将 output 变量的最后一位设置成 lastbit 变量的值。
    output ^= lastbit 
    # output 即经过一轮 LFSR 之后的新序列，lastbit 即经过一轮 LFSR 之后输出的一位
    return (output, lastbit)

性质

LFSR 寄存器的空间状态受限于寄存器位数最大只能达到 $2^{n}$，去除初始状态之后有 $2^{n}-1$ 即可到达循环节。

>> 度长为 $m$ 的 LFSR 可产生的最大周期序列长度为 $2^{m}-1$.

选取最大不可约多项式进行验证：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#-*- coding: utf-8 -*-
# 本原多项式样本值 (0, 1, 3, 5, 16)
from operator import eq

def LFSR(p_x, seq):
    s = 0
    for i in p_x:
        s ^= seq[i - 1] # i - 1
    for i in range(len(seq) - 1):
        seq[i] = seq[i + 1] # seq 1,2,...,n <-
    seq[-1] = s

if __name__ == "__main__":
    # 特征多项式 P(x)
    # P_x = list(input("Please Input P(x) >> "))
    # 本源多项式
    P_x = list((0, 1, 3, 5, 16))
    p_x = P_x[1:]
    # seq = input("Please Input Sequence >> ")
    # 寄存器的初始状态 seq
    seq = [(_ % 2) for _ in range(P_x[-1])]
    cmp = [(_ % 2) for _ in range(P_x[-1])]
    cnt = 0
    while True:
        LFSR(p_x, seq)
        cnt += 1
        if eq(seq, cmp):
            print seq
            print cnt
            break

运行结果:

参看

[1] 深入分析CTF中的LFSR类题目（一）