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 | # R 为初始状态,mask 为掩码 |
性质
LFSR 寄存器的空间状态受限于寄存器位数最大只能达到 $2^{n}$,去除初始状态之后有 $2^{n}-1$ 即可到达循环节。
>> 度长为 $m$ 的 LFSR 可产生的最大周期序列长度为 $2^{m}-1$.
选取最大不可约多项式进行验证:
1 | #-*- coding: utf-8 -*- |
运行结果: