1
0
0
1
1010 1101 0110 0011 1001
0
17
LFSR
举例
1111 0111 1011 0101 → → → → → → → → → → 1 1 1 1 0 1 0 1 1 0
0
1
0
0
1010 1101 0110 0011 1001 0100
0
18
LFSR
举例
1111 0111 1011 0101 → → → → → → → → → → → 1 1 1 1 0 1 0 1 1 0 0
LFSR的周期
上例周期为15 不同的LFSR周期不一定相同
举例：反馈函数仅引入b1，则周期最大为4
阶为n的LFSR的最大周期为2n-1 周期主要与反馈函数有关
26
LFSR的周期
已经证明：当反馈函数是本原多项式时， 周期达到最大为2n-1 本原多项式定义
若阶为n的多项式P(x)能够整除xt+1，其中t = 2n-1，且对于任何d < 2n-1且d| 2n-1 ，P(x)不能 整除xd+1，则称P(x)为本原多项式
41
序列密码的评价标准
周期 统计特性 线性复杂度（局部线性复杂度） 混淆与扩散 非线性特性
42
真随机序列
信息源
电磁辐射，热噪声，人机交互等
不能用于加密，可以用于生成密钥
43
1
1000 1100 1110
LFSR
举例
1111 0111 1011 0101 → → → → → → → → → → → → → → → 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0
24
1
1
1
1
1010 1101 0110 0011 1001 0100 0010 0001
0
1000 1100 1110 1111
n
6
LFSR
线性反馈移位寄存器
7
LFSR
举例
4位，b1和b4参与反馈
b4 b3 b2 b1
8
LFSR
举例
1111 → 1
1
1
1
1
0
9
LFSR
举例
1111 0111 → → 1 1
0
1
1
1
1
10
LFSR
举例
1111 0111 1011 → → → 1 1 1
1
0
1
1
0
11
LFSR
举例
1111 0111 1011 0101 → → → → 1 1 1 1
大整数N＝PQ，其中P，Q是模4余3的素数，N的 分解未知。随机选择一个与N互素的整数x0作为种 子，迭代用下面的方式产生： xi+1=xi2 mod N 然后取出xi+1的低位log log N比作为序列的第i+1次 输出。Log N＝1024， 2048等 速度比前面的LFSR相对慢一些，但比RSA或BM 发生器快得多。 是可以证明安全的，即如果大整数分解是困难的， 那么BBS发生器的输出是无法预测的。统计特性 也非常好。主要用于高安全性环境，例如生成系 统的主密钥等。
配合方式
多路输出
异或，门限，异步内积，其他线性函数
选择输出
Geffe：2选1，n选1 Jennings：组合选择
31
利用LFSR构造序列密码
配合方式
停走产生器
2选1交替走 Beth-Piper异步停走 对称停走 Gollmann级联停走
消耗产生器
输出/不输出控制位，自消耗/联合消耗
收缩产生器
32
实例
0
1
01Leabharlann 112LFSR
举例
1111 0111 1011 0101 → → → → → 1 1 1 1 0
1
0
1
0
1010
1
13
LFSR
举例
1111 0111 1011 0101 → → → → → → 1 1 1 1 0 1
1
1
0
1
1010 1101
0
14
LFSR
举例
1111 0111 1011 0101 → → → → → → → 1 1 1 1 0 1 0
22
1
1
0
0
1010 1101 0110 0011 1001 0100 0010 0001
1
1000 1100
LFSR
举例
1111 0111 1011 0101 → → → → → → → → → → → → → → → 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0
23
1
1
1
0
1010 1101 0110 0011 1001 0100 0010 0001
0
0
1
0
1010 1101 0110 0011 1001 0100 0010
0
19
LFSR
举例
1111 0111 1011 0101 1010 → → → → → → → → → → → → 1 1 1 1 0 1 0 1 1 0 0 1
0
0
0
1
1101 0110 0011 1001 0100 0010 0001
第4讲 序列密码
授课：伍前红 Chinacrypt2008@, 辅导：周红亮 zhouhl2002@
序列密码
线性同余产生器 LFSR（Linear Feedback Shift Register）:线 性反馈移位寄存器 LFSR与序列密码 序列密码实例 序列密码与其他密码 真随机源
36
其它序列密码
非线性反馈移位寄存器
反馈函数为非线性函数
例如：组合逻辑函数
问题：周期不容易确定，甚至可能退化
37
其它序列密码
无移位寄存器的序列密码
RC4，1987, Ron Rivest
植入密钥
Si = i ( i = 0,1,…,255) j=0 i = 0 to 255
j=( j+Si+Ki) mod 256 SWAP(Si, Sj)
A5算法
GSM手机与基站的信道加密 3个LFSR，周期分别为19，22，23 多路输出：异或 停走方式
若输出是3个1或3个0则全走，否则两个相同的走， 不相同的停
33
实例
Mush算法
两个LFSR
每个数据单元（寄存器）包含32bits，反馈函数采 用算术加：
Ai = ( Ai-55 + Ai-24 ) mod 232 Bi = ( Ai-52 + Ai-19 ) mod 232
本原多项式一定是不可约多项式
27
LFSR的周期
通过本原多项式设计反馈函数
去掉本原多项式中的最高次数项系数1 以剩余各项的次数作为编号，将移位寄存器中 相应编号在本原多项式中系数为1的寄存器的 1 内容取出进行异或，获得反馈值，最终输入到 反馈移位寄存器中 移位寄存器中的寄存器从右向左编号，最靠近 输出端的寄存器编号1，对应本原多项式的0次 项
Benlekamp-Massey方法截获2n位密钥，即可计算出 LFSR的当前状态，从而生成LFSR密钥流，破解密文
采用多个周期互素的LFSR相互配合，将各自的输 出非线性组合作为输出序列，增强安全性 相关免疫函数：寻求序列输出和序列发生器内部 LFSR的关系，利用工具主要线性代数
30
利用LFSR构造序列密码
2
线性同余产生器
工作方式：Xn=aXn–1+b mod m 序列周期的概念 线性同余产生器的最大周期为m–1（b与m互素） 速度快 统计特征非常好，然而可以预测，因而不能用于 密码设计 仍在用，主要用于编码或作为其它不需要安全性 的随机数发生器
3
LFSR
LFSR＝移位寄存器＋反馈函数 移位寄存器：一个二进制序列 如果有n位，则成为n位移位寄存器
4
LFSR
反馈函数：寄存器中特定位的异或，这些 位的列表称为一个选择序列，也称为 Fibobnacci结构
5
LFSR
线性反馈移位寄存器（LFSR）
22
n
1
1
密码学要求：输出序列周期足够长，统计特征好， 不可预测 n位的LFSR最大周期为2n–1，这样的序列称为m序 列。 反馈函数使用非线性函数，n位的非线性反馈移位 寄存器最大周期可达 22 1，这样的序列称为M序列。
38
RC4
产生密钥流
i=j=0 loop
i=(i+1) mod 256 j=(j+Si) mod 256 t=(Si+Sj) mod 256 Ki=St
39
序列密码与其他密码
利用对称密码或其他强密码，经常更换序 列密码的密钥 利用其他安全的密码设计序列密码
DES RSA BBS
40
BBS发生器
1
20
LFSR
举例
1111 0111 1011 0101 → → → → → → → → → → → → → 1 1 1 1 0 1 0 1 1 0 0 1 0
1
0
0
0
1010 1101 0110 0011 1001 0100 0010 0001
1
1000
21
LFSR
举例
1111 0111 1011 0101 → → → → → → → → → → → → → → 1 1 1 1 0 1 0 1 1 0 0 1 0 0
0
1
1
0
1010 1101 0110
0
15