第十讲线性反馈移位寄存器

秒速五厘米 2023-03-02 04:58 73阅读 0赞

# 1 反馈移位寄存器(Feedback shift register，FSR) #

移位寄存器是流密码产生密钥流的一个主要组成部分。

GF(2)上一个n级反馈移位寄存器由n个二元存储器与一个反馈函数![f(a\_1,a\_2,...,a\_n)][f_a_1_a_2_..._a_n]组成，如下图所示。

![20200727180102465.png][]

### 反馈移位寄存器的状态 ###

在任一时刻，这些级的内容构成该反馈移位寄存器的状态，每一状态对应于GF(2)上的一个n维向量，共有![2^n][2_n]种可能的状态。

每一时刻的状态可用n维向量 ![(a\_1 ,a\_2 ,...,a\_n )][a_1 _a_2 _..._a_n]表示，其中 ![a\_i][a_i] 是第 i 级存储器的内容。

### 反馈函数 ###

初始状态由用户确定。

反馈函数![f(a\_1 ,a\_2 ,...,a\_n )][f_a_1 _a_2 _..._a_n]是n元布尔函数，即函数的自变量和因变量只取0和1这两个可能的值。

函数中的运算有逻辑与、逻辑或、逻辑补等运算。

### 反馈移位寄存器的例子 ###

如图是一个3级反馈移位寄存器，其初始状态为![(a\_1 ,a\_2 ,a\_3 )=(1,0,1)][a_1 _a_2 _a_3 _1_0_1]，输出可由右表给出。

![20200727180527774.png][]

![\\newline a\_4=f(a\_1,a\_2,a\_3)=a\_1a\_2\\bigoplus a\_3=0\\bigoplus 1=1 \\newline a\_5=f(a\_2,a\_3,a\_4)=a\_2a\_3\\bigoplus a\_4=0\\bigoplus 1=1 \\newline...][newline a_4_f_a_1_a_2_a_3_a_1a_2_bigoplus a_3_0_bigoplus 1_1 _newline a_5_f_a_2_a_3_a_4_a_2a_3_bigoplus a_4_0_bigoplus 1_1 _newline...]

# 2 线性反馈移位寄存器LFSR（linear feedback shift register） #

![20200727181538730.png][]

### LFSR的反馈函数 ###

![20200727181628661.png][]

线性反馈移位寄存器：实现简单、速度快、有较为成熟的理论，成为构 造密钥流生成器的最重要的部件之一。

### LFSR的实例 ###

![20200727182808135.png][]

### 密钥流的周期 ###

![20200727182857585.png][]

### LFSR的性质 ###

![20200727183221105.png][]

[f_a_1_a_2_..._a_n]: https://private.codecogs.com/gif.latex?f%28a_1%2Ca_2%2C...%2Ca_n%29
[20200727180102465.png]: /images/20230208/2b8113a82a4249fe9bb84d5d9fb98be7.png
[2_n]: https://private.codecogs.com/gif.latex?2%5En
[a_1 _a_2 _..._a_n]: https://private.codecogs.com/gif.latex?%28a_1%20%2Ca_2%20%2C...%2Ca_n%20%29
[a_i]: https://private.codecogs.com/gif.latex?a_i
[f_a_1 _a_2 _..._a_n]: https://private.codecogs.com/gif.latex?%5Cbg_red%20f%28a_1%20%2Ca_2%20%2C...%2Ca_n%20%29
[a_1 _a_2 _a_3 _1_0_1]: https://private.codecogs.com/gif.latex?%28a_1%20%2Ca_2%20%2Ca_3%20%29%3D%281%2C0%2C1%29
[20200727180527774.png]: /images/20230208/09a52faea4364ad88c704a71ae946922.png
[newline a_4_f_a_1_a_2_a_3_a_1a_2_bigoplus a_3_0_bigoplus 1_1 _newline a_5_f_a_2_a_3_a_4_a_2a_3_bigoplus a_4_0_bigoplus 1_1 _newline...]: https://private.codecogs.com/gif.latex?%5Cnewline%20a_4%3Df%28a_1%2Ca_2%2Ca_3%29%3Da_1a_2%5Cbigoplus%20a_3%3D0%5Cbigoplus%201%3D1%20%5Cnewline%20a_5%3Df%28a_2%2Ca_3%2Ca_4%29%3Da_2a_3%5Cbigoplus%20a_4%3D0%5Cbigoplus%201%3D1%20%5Cnewline...
[20200727181538730.png]: https://img-blog.csdnimg.cn/20200727181538730.png
[20200727181628661.png]: https://img-blog.csdnimg.cn/20200727181628661.png
[20200727182808135.png]: https://img-blog.csdnimg.cn/20200727182808135.png
[20200727182857585.png]: https://img-blog.csdnimg.cn/20200727182857585.png
[20200727183221105.png]: https://img-blog.csdnimg.cn/20200727183221105.png