无线通信安全-03第三讲 序列密码的设计与分析 (2)

无线通信安全
18
线性反馈移位寄存器
显然，一个n阶线性反馈移位寄存器序列 a0,a1, a2,…,an,… 满足递推关系式 an+t=c1 an+t -1 + c2 an+t -2 + … + cn at，t≥0。 其中c1, c2,..., cn称为反馈系数，也叫抽头系数。
无线通信安全
19
线性反馈移位寄存器
无线通信安全
26
m序列是伪随机序列的证明
由于寄存器中不会出现全0状态，所以不会出 现0的n游程，但必有一个1的n游程，而且1的游 程不会更大，因为若出现1的n+1游程，就必然有 两个相邻的全1状态，但这是不可能的。这就证明 了1的n游程必然出现在如下的串中：
0 11 1 0
n个1
当这n+2位通过移位寄存器时，便依次产生 以下状态：



看起来是随机的 不可预测性 不能重复产生

如果采用完全相同的输入对序列发生器操作两 次，将得到两个不相关的随机序列
目的： 产生具有随机数统计特性，并且不可再现的数。
无线通信安全
5
1. 序列的随机性

看起来是随机的 不可预测性

即使给出产生序列的算法或硬件和所有以前 产生的位序列的全部知识，也不可能通过计 算来预测下一个随机位是什么
定义：周期为2n-1的LFSR序列称为m序 列。 随机性如何？ m序列的特点：



长周期 m序列是伪随机序列 [定理]
如何生成？


结论
m序列是我们要寻找的序列。
无线通信安全
24
m序列的特性
[定理] GF(2)上的n长m序列{ai}具有如下性质： ① 0,1平衡性：在一个周期内，0、1出现的次数 分别为2n-1-1和2n-1。 ②游程特性：在一个周期内，总游程数为2n-1； 对1≤i≤n-2，长为i的游程有2n-i-1个，且0、1游程 各半；长为n-1的0游程一个，长为n的1游程一 个。 ③ {ai}的自相关函数为


非线性反馈移位寄存器的序列密码

非线性反馈移位寄存器序列 利用进位寄存器反馈的移位寄存器 非线性前馈序列
2
无线通信安全
典型序列密码算法——A5算法
本章目标



了解序列随机性的基本概念 重点：Golomb随机性公设 了解线性反馈移位寄存器的基本概念 m序列的基本概念及其随机性的讨论 LFSR的软件实现 m序列密码的破译 非线性反馈移位寄存器的序列密码 掌握A5算法的基本原理
1 11
1 0
r-游程 1≤r≤n-2
0的游程 2n-r-2
1的游程 2n-r-2
游程 2n-r-1
占总游程比 1/2r
r=n-1
r=n
1
0
0
1
1
1
1/2r
1/2n-1
r>n
无线通信安全
0
0
0
0
28
所以，m序列满足第二公设。
m序列是伪随机序列的证明
③ Golomb第三公设：{ai}是周期为2n-1的m序列， 对于任一正整数τ(0<τ<2n-1)，{ai}+{ai+τ}在 一个周期内为0的位的数目正好是序列{ai}和 {ai+τ}对应位相同的位的数目。 设序列{ai}满足递推关系： ah+n=c1ah+n-1 c2ah+n-2 … cnah 故ah+n+τ=c1ah+n+τ-1 c2ah+n+τ-2 … cnah+τ ah+n ah+n+τ=c1(ah+n-1 ah+n+τ-1) c2(ah+n-2 ah+n+τ-2) … cn(ah ah+τ)


线性移位寄存器LFSR、 非线性移位寄存器NLFSR、 有限自动机、 线性同余等方法 混沌密码序列技术。
这些方法都是通过一个种子（有限长）产生具有足够长 周期的、良好随机性的序列，在传递、存储序列时，只 需传递、存储生成器的方法和种子。
无线通信安全
13
2. 线性移位寄存器的结构与设计
移位寄存器与移位寄存器序列 n阶反馈移位寄存器 m序列及其随机性 LFSR的软件实现
《无线通信安全》
第三讲 序列密码的设计与分析
计算机学院 李晖
lihuill@bupt.edu.cn
无线通信安全
北京邮电大学 1
主要内容

序列的随机性 线性反馈移位寄存器


线性移位寄存器的一元多项式表示 m序列的伪随机性 m序列密码的破译 序列的线性复杂度 B-M算法

Βιβλιοθήκη Baidu
线性反馈移位寄存器的分析方法
2n1 1 2n1 1 R n n 2 1 2 1
（证毕）
无线通信安全
30
线性移位寄存器的特征多项式
设LFSR的反馈系数为c1, c2,..., cn，即： an+k=c1 an+k-1 + c2 a n+k-2 + … + cn ak，i=0，1，2，…。 (1) 可以用一个一元高次多项式来表示：
无线通信安全
29
m序列是伪随机序列的证明
令bj=aj aj+τ，由递推序列{ai}可推得 递推序列{bi}，{bi}满足 bh+n=c1bh+n-1 c2bh+n-2 … cnbh {bi}也是m序列。为了计算R(τ)，只要 用{bi}在一个周期中0的个数减去1的个数， 再除以2n-1，即

如果一个GF(q)上的n阶反馈移位寄存器的反馈 函数形如：
f（x1,x2,…,xn-1,xn）= cn x1 + cn-1 x2 + … + c1 xn，
其中ci∈GF(q)，1≤i≤n，则称其为线性反馈 移位寄存器，用LFSR（Linear Feedback Shift Register）表示；否则，称其为非线性反馈移位 寄存器，用NLFSR（Nonlinear Feedback Shift Register）表示。
[例2]
移入 单元1 0 0 0 1 0 1 0 0 0 1 0 1 单元2 1 0 0 0 1 0 1 0 0 0 1 0 单元3 0 1 0 0 0 1 0 1 0 0 0 1 单元4 1 0 1 0 0 0 1 0 1 0 0 0 输出 1 0 1 0 0 0 1 0 1 0 0 0
16
并行加载 输入
显然，R(np)= 1，（ n = 0，1，2，…，）这称为同相自相关 函数 ；当τ≠np时，称R(τ)为异相自相关函数。nτ就是延迟时 间τ后的序列与原序列在一个周期内相同比特的个数，反映了 序列比特的均匀分布特性。如果nτ是一个常数，则说明分布 完全均匀，也就是说，通过这种平移比较得不到任何其它信 息。
无线通信安全
6
1. 序列的随机性

看起来是随机的

满足伪随机序列的Golomb三条公设

0和1的个数相等 r游程基本上占游程总数的1/2r 异相自相关函数是一个常数

能通过我们所能找到的所有随机性统计检验
无线通信安全
7
1. 序列的随机性
[定义] 在序列{ki | i=1，2，…}的周期为p，在它 的一个周期kl+1，kl+2，…，kl+p中，如果： km≠km+1= km+2=…= km+r≠km+r +1， l+1≤m+1<m+r≤l+p，则（km+1， km+2，…， km+r） 称为序列的一个r-游程（run）。 例： 设{ai}=(a1a2a3…)为0、1序列，例如00110111， 其前两个数字是00，称为0的2游程；接着是11， 是1的2游程；再下来是0的1游程和1的3游程。

无线通信安全
14
2.1 移位寄存器与移位寄存器序列
Parallel load
1
Shift in
0
1
0
0
1
0
1
Shift out

一个8位移位寄存器
Parallel load
0
Shift in
1
0
1
0
0
1
0
Shift out

无线通信安全
移入一个0以后的寄存器内容
15
2.1 移位寄存器与移位寄存器序列
3
无线通信安全
1. 序列的随机性
序列密码中必须解决的问题是： 密钥流的质量（随机性）如何刻画？如 何保证？ 无限长密钥流如何产生？ 合法用户如何很容易地获得或再生该密 钥流？加密、解密如何同步？
无线通信安全
4
1. 序列的随机性
数学描述：
随机变量序列ξ1ξ2…ξi…，其中ξi（i = 1，2，…）是相 互独立的、等概率取值0，1的随机变量。
②说明0与1在序列中每一位置上出现的概率相同; ③意味着通过对序列与其平移后的序列做比较，不能 给出其他任何信息。
无线通信安全
10
1. 序列的随机性
从密码系统的角度看，一个伪随机序列 还应满足下面的条件： ① {ai}的周期相当大。 ② {ai}的确定在计算上是容易的。 ③ 由密文及相应的明文的部分信息，不能确 定整个{ai}。
解：输出序列为101111000100110 1011110001 00110…。
可见该序列具有周期15， 是否序列都是周期的呢？
无线通信安全
22
[定理1 ]

n级线性反馈移位寄存器的输出序列是周 期的，周期最大为2n-1。 证明
密码设计者感兴趣序列 是什么？

无线通信安全
23
2.3 m序列及其随机性
并行加载 输入
0
1
0
1
输出
解：由图 可知反馈移位寄存器的阶数是4， 其反馈函数是：f（x1,x2,x3,x4）= x1 + x3 从表 7.2.1可知其输出序列为101000 101000…，周期为6。
无线通信安全
21
线性反馈移位寄存器

设n=4，s0=（1,0,1,1），f（x1,x2,x3,x4）= x1 + x2，计算输出序列。
无线通信安全
8
1. 序列的随机性
[定义] 设序列{ki | i=1，2，…}的周期为p，令nτ=
#{i | 1≤i≤p，ki = ki +τ}， dτ= #{i | 1≤i≤p，ki ≠ ki +τ}，
则R(τ) =
n d p
，τ = 0，1，2，…称为序列{ki |
i=1，2，…}的自相关函数。
无线通信安全
9
1. 序列的随机性
Golomb随机性公设： ① 在序列的一个周期内，0与1的个数相差至多为1。 ② 在序列的一个周期内，长为i的游程占游程总数的 1/2i (i=1,2,…)，且在等长的游程中0的游程个数和1的 游程个数相等。 ③ 异相自相关函数是一个常数。
①说明{ai}中0与1出现的概率基本上相同;
1, 0 R 1 n , 0 2 2 n 2 1
无线通信安全
25
m序列是伪随机序列的证明
证明： ① Golomb第一公设：在n长m序列的一个周期内， 除了全0状态外，每个n长状态（共有2n-1个）都恰 好出现一次，这些状态中有2n-1个在a1位是1，其余 2n-1-2n-1=2n-1-1个状态在a1位是0。 ②Golomb第二公设：对n=1,2，易证结论成立。 对n>2，当1≤i≤n-2时，n长m序列的一个周期内， 长为i的0游程数目等于序列中如下形式的状态数目： 100…01*…*，其中n-i-2个*可任取0或1。这种状 态共有2n-i-2个。同理可得长为i的1游程数目也等于 2n-i-2，所以长为i的游程总数为2n-i-1。
0 0
0
1
0
1
输出
1 0 1 0 0 0
带反馈的移位寄存器
1 0 1 0
无线通信安全
2.2 n阶反馈移位寄存器
xn xn-1
... ...
x2
x1
输出
f（x1,x2,…,xn-1,xn）
几个术语 反馈移位寄存器的状态 初始状态 反馈移位寄存器序列 状态序列
无线通信安全
17
线性反馈移位寄存器的定义

在线性反馈移位寄存器中总是假定 c1,c2,…,cn中至少有一个不为0，否则 f(a1,a2,…,an)≡0，这样的话，在n个脉冲 后状态必然是00…0，且这个状态必将一 直持续下去。 一般对于n级线性反馈移位寄存器，总是 假定cn=1。
20

无线通信安全
线性反馈移位寄存器

写出例2的反馈函数，当初始状态为1010时， 求输出序列的周期？
无线通信安全
11
1. 序列的随机性 [例1]

讨论序列：
1010 1110 1100 0111 1100 1101 0010 000 1010 1110 1100 0111 1100 1101 0010 000…
的随机性。
无线通信安全
12
小结

寻找生成一个具有良好随机特性密码序 列的方法：

0 11 1 11 1
n 1个1
n个1
11 1 0
n 1个1
无线通信安全
27
m序列是伪随机序列的证明
由于 ， n 1个1 这两个状态只 n 1个1 能各出现一次，所以不会有1的n-1游程。 于是在一个周期内，总游程数为
1 1 2n i 1 2n 1
i 1 n2
0 11