第13讲-序列密码2

阶数最小的LFSR可能是退化的，此时
a
(N)
且
（f N ( x)） lN
B-M算法是一个迭代算法。 0级LFSR以f(x)=1为联结多项式，且全零序列仅
由0级线性移位寄存器产生。
B-M 算 法
定义：设 a
(N)
(a 0 a1 ...a N 1 ) 是GF(2)上的一个长
度为N的序列。能产生 a ( N ) 并且阶数最小的线性移 位寄存器的阶数称为
序列密码的安全性取决于密钥流的安全性，要求
密钥流序列有良好的随机性，以使密码分析者对它无
法预测。即使截获其中一段，也无法推测后面是什么。 如果密钥流是周期的，要做到完全随机是困难的，
严格地说，这样的序列不可能做到随机。
只能要求截获比周期短的一段时不会泄露更多信 息，这样的序列称为伪随机序列。
( x) 不可约，不一定能生成m序列。
上节回顾
移位寄存器序列的三种表示方法:
ห้องสมุดไป่ตู้
• 线性递推式（反馈函数）： at+n=c1at+n-1+c2at+n-2+…+cnat ,t>=0 • 联结多项式： f(x)=1+c1x+c2x2+…+cnxn • 状态转移矩阵： 满足： st+1=stTf
m序列的伪随机性
N
递推关系 ： aN a0
a1
a N -1
aN 2
…
a0
输出
这样的多项式是没有多大意义的.
B-M 算 法
我们需要找到一个阶数尽可能小的移位寄存器，使之生 成a
(N)
(a0 a1...aN 1 )
B-M 迭 代 算 法
B-M 算 法
设 a ( N ) (a0 a1...aN 1 ) 是GF(2)上一段长度为N的序 列， f N ( x) 是一个能产生该序列并且阶数最小的 LFSR的联结多项式。l N 是该序列的阶数，称二元组
第六章 序列密码与移位寄存器
——伪随机序列的生成
数学与统计学学院 贾小英 2013.03
主要内容
序列密码简介
线性反馈移位寄存器序列 m序列的伪随机性
B-M 算法 线性移位寄存器的非线性组合
上节回顾
移位寄存器序列的三种表示方法:
• 线性递推式（反馈函数）： • 联结多项式：
at+n=c1at+n-1+c2at+n-2+…+cnat ,t>=0 f(x)=1+c1x+c2x2+…+cnxn 满足： st+1=stTf
密码分析的角度： 已知一段序列，怎样构造一个阶数尽可能小的线 性移位寄存器来产生该序列
研究一段序列可以由什么样的多项式来生成
B-M 算 法
问：任意给定一段长为N的序列 a ( N ) (a0 a1...aN 1 ) 是否都可以找到一个多项式生成该序列？ 答案是肯定的。 联结多项式： f N ( x) 1 x
此时，
f n 1 ( x) f n ( x) x
nm
f m ( x),
ln1 max{ ln , n 1 ln }
B-M 算 法
例：设a(10)=(0001101111)是二元域
GF(2)上的一个长度为10的序列，求其
线性综合解。
解：
B-M 算 法
定理：设 a
(N)
(a0 a1...aN 1 ) 是二元域GF(2)上的
• 状态转移矩阵：
上节回顾
n阶m序列:周期为 2n
1.
1 的序列
极小多项式（可以生成该序列的次数最低的多项式）
GF(2)上任一周期序列的极小多项式存在且唯一 2. 序列的周期等于生成这条序列的极小多项式的周期 3. 一个多项式生成的非零序列都是m序列，那么这个多项式一 定不可约。反之，若 f 4. 本原多项式
2
n i 2
个。
m序列的伪随机性
m序列的随机性
(3)
a

的自相关函数为：
0； 1 Ra ( ) 1 n n 0 2 1 2 1
达到最佳值。 m序列满足Golomb随机性三假设。
m序列的伪随机性
需要说明的是： Golomb随机性假设只是随机性的必要条件。一个
n0 1
l1 l2 ... ln0 0, ln0 1 n0 1
B-M 算 法
B-M算法描述
2）利用递推关系进行迭代，直到序列最后一位。
假设序列前n位的线性综合解已求出
f1 ( x), l1 , f 2 ( x), l2 ,... f n ( x), ln
序列。
主要内容
序列密码简介
线性反馈移位寄存器序列 m序列的伪随机性
B-M 算法 线性移位寄存器的非线性组合
B-M 算 法
序列密码中，对移位寄存器的研究主要有两个角度： 密码设计的角度：
利用阶数尽可能小的线性移位寄存器来产生周期 尽可能长并且随机性能良好的序列；（m序列）
研究多项式能产生什么样的序列
m序列的伪随机性
怎样衡量一条序列的随机性？
分布特性；
游程特性； 相关特性； 游程：游程就是指连续的0或1序列。
011…110
1游程
100…001
0游程
m序列的伪随机性
定义：设 的序列
a (a0 a1a2 ...)

是GF(2)上一个周期为T
1 T 1 ai ai Ra ( ) (1) (1) ,0 T 1. T i 0
—0与1在序列的每个位置上出现的概率基本相同。
异相自相关函数是一个常数。
—对序列及对其平移后的序列做比较，不能给出任何信息。
Ｇolomb称满足这三条假设的序列伪噪声序列（伪随机序列）。
m序列的伪随机性
m序列的随机性 设
a

是GF(2)上一个n阶m序列。则
(1)在一个周期内，0和1出现的次数接近相等。
f N ( x)，l N 为序列 a ( N ) 的线性综合解。
约定0阶LFSR的联结多项式为f(x)=1，产生长度为n
的全零序列。
已知一段序列，求取生成该序列的多项式的过 程，又被称为LFSR序列的综合。
B-M 算 法
B-M算法描述
（1）找出第一个不为0的位，并给出该位之前全零序列的表达式。

记这两段中相同的位数为A，不同的位数为D。则
A D Ra ( ) T
自相关函数反映一个周期内平均每位的相同程度。
m序列的伪随机性
Golomb随机性三假设： 在序列的一个周期内，0和1的个数相差至多为1。
— 0与1出现的概率基本相同。
在序列的一个周期内，长为i的游程占游程总数的 1/2i, 且在等长的游程中，0游程和1游程个数相等 。

称为序列的自相关函数。
0 时， Ra ( ) 1. 0 时， Ra ( ) 称为序列的异自相关函数。

m序列的伪随机性
等价定义： 设
a (a0 a1a2 ...) 是GF(2)上一个周期为T的序列。 (a0 a1a2 ...aT ) 是其中的一个周期子段。 (a a 1a 2 ...a T ) 也是其中的一个周期子段。
a( N )
的线性复杂度。记为：
C (a ( N ) )
。
无穷周期序列
a

的线性复杂度定义为能产生
a
且阶数最小的LFSR的阶数。
B-M 算 法
定理：设
a (a 0 a1 ...a N 1 )

是GF(2)上的一个无

穷周期序列。其线性复杂度
C (a ) l
。如果知道

a

的任意连续 2l 位，即可确定 多项式。
a ( N ) (a 0 a1 ...a N 1 )，设n0是满足 a 0 a1 ... a n0 1 0, an0 1 的非负整数。取 d 0 d 1 ... d n0 1 0, d n 1 0
对于给定的序列
f1 ( x) f 2 ( x) ... f n0 ( x) 1, f n0 1 ( x) 1 x
设
f n ( x) 1 c1 x c2 x ...cl x
2
l
计算
d n an c1an1 c2 an2 ... cl anl
B-M 算 法
B-M算法描述 若
若
d n 0, 则 f n1 ( x) f n ( x), ln1 ln d n 1, 则存在非负整数m,满足 lm lm1 lm2 ... ln
(N)
一个长度为N的序列。a
作为B-M算法的输入， 一定是 a ( N )
则B-M算法的输出 f N ( x)，l N
的线性综合解。
B-M 算 法
B-M算法的几点说明： 设 f N ( x)，l N 是B-M算法求出的线性综合解。
lN 。这是因为产生 则 （f N ( x)）
伪随机序列应满足Golomb假设，但仅满足相应标准
的周期序列并不一定能满足密码学的应用。 m序列完全满足Golomb假设，但m序列是高度可 预测的，对于n级的m序列，只需要知道连续2n位， 利用B-M算法或解线性方程组的方法就可以以O（n2）
的计算复杂度预测该序列任一位的值。
m序列的伪随机性
从密码系统的角度看，一个伪随机序列还应该满足： 周期足够大 确定该序列在计算上是容易的； 由密文及对应的明文的部分信息，不能确定整个
0出现的次数为 2
1出现的次数为
n 1
1 次。
次。
2
n 1
m序列的伪随机性
m序列的随机性
(2)在一个周期内，游程总数为
和1游程各占一半。
2
n 1
，其中0游程
当 n 2 时，游程分布如下 (1 i n 2)：
- 长为i的0游程和1游程都有
- 长为n-1的0游程有1个。 - 长为n的1游程有1个。
a

并求出 a
的极小
B-M 算 法
以上定理说明：
如果序列密码中密钥序列的线性复杂度较低，则相
应的密码体制是很不安全的。 n阶m序列的线性复杂度是n。即如果知道连续2n 位，就可利用B-M算法求得该序列的极小多项式。 m序列虽然具有良好的随机性能，但并不适合直接 作为密钥序列来使用。