第2章 流密码 2.1 流密码的基本概念 2.2 线性反馈移位寄存器 2.3 线性移位寄存器的一元多项式表示 2.4 m序列的伪随机性

Presentation on theme: "第2章 流密码 2.1 流密码的基本概念 2.2 线性反馈移位寄存器 2.3 线性移位寄存器的一元多项式表示 2.4 m序列的伪随机性"— Presentation transcript:

1 第2章 流密码 2.1 流密码的基本概念 2.2 线性反馈移位寄存器 2.3 线性移位寄存器的一元多项式表示 2.4 m序列的伪随机性
第2章 流密码 2.1 流密码的基本概念 2.2 线性反馈移位寄存器 2.3 线性移位寄存器的一元多项式表示 2.4 m序列的伪随机性 2.5 m序列密码的破译 2.6 非线性序列 习题

2 2.1 流密码的基本概念 流密码的基本思想: 密钥:k 产生一个密钥流:z=z0 z1…， 明文串:x=x0 x1 x2…
2.1 流密码的基本概念 流密码的基本思想: 密钥:k 产生一个密钥流:z=z0 z1…， 明文串:x=x0 x1 x2… 加密： y=y0 y1 y2…=Ez0(x0)Ez1(x1)Ez2(x2)…。 密钥流发生器f： zi=f(k,σi)， σi是加密器中的记忆元件（存储器）在时刻i的状态，f是由密钥k和σi产生的函数。

3 分组密码与流密码的区别就在于有无记忆性 流密码的滚动密钥z0=f(k,σ0)由函数f、密钥k和指定的初态σ0完全确定。 此后，由于输入加密器的明文可能影响加密器中内部记忆元件的存储状态， σi(i>0)可能依赖于k，σ0，x0，x1，…，xi-1等参数。

4 图2.1 分组密码和流密码的比较

5 σi独立于明文字符的叫做同步流密码，否则叫做自同步流密码。
同步流密码 流密码: 同步流密码和自同步流密码 σi独立于明文字符的叫做同步流密码，否则叫做自同步流密码。 在同步流密码中，由于zi=f(k,σi)与明文字符无关，因而此时密文字符yi=Ezi(xi)也不依赖于此前的明文字符。因此，可将同步流密码的加密器分成密钥流产生器和加密变换器两个部分。

6 图2.2 同步流密码体制模型

7 图2.3 加法流密码体制模型 二元加法流密码是目前最为常用的流密码体制，其加密变换可表示为yi=zi xi。

8 一次一密密码是加法流密码的原型。事实上，如果（即密钥用作滚动密钥流），则加法流密码就退化成一次一密密码。
实际使用中，密码设计者的最大愿望是设计出一个滚动密钥生成器，使得密钥经其扩展成的密钥流序列具有如下性质：极大的周期、良好的统计特性、抗线性分析、抗统计分析。

9 2.1.2 有限状态自动机 有限状态自动机是具有离散输入和输出（输入集和输出集均有限）的一种数学模型，由以下3部分组成：
有限状态自动机 有限状态自动机是具有离散输入和输出（输入集和输出集均有限）的一种数学模型，由以下3部分组成： ① 有限状态集S={ si | i=1,2,…,l }。 ② 有限输入字符集A1={ A(1)j| j=1,2,…,m}和有限输出字符集A2={A(2)k |k=1,2,…,n}。 ③ 转移函数A(2)k=f1(si, A(1)j )，sh=f2(si, A(1)j) 即在状态为si，输入为A(1)j时，输出为A(2)k，而状态转移为sh。

10 有限状态自动机可用有向图表示，称为转移图。
转移图的顶点对应于自动机的状态，若状态si在输入A(1)i时转为状态sj，且输出一字符A(2)j，则在转移图中，从状态si到状态sj有一条标有(A(1)i, A(2)j)的弧线

11

12 图2.4 有限状态自动机的转移图

13 若输入序列为A(1)1 A(1)2 A(1)1 A(1)3 A(1)3 A(1)1，
初始状态为s1， 则得到状态序列 s1s2s2s3s2s1s2 输出字符序列 A(2)1 A(2)1 A(2)2 A(2)1 A(2)3 A(2)1

14 2.1.3 密钥流产生器 密钥流产生器: 参数为k的有限状态自动机，
密钥流产生器 密钥流产生器: 参数为k的有限状态自动机， 一个输出符号集Z、一个状态集∑、两个函数φ和ψ以及一个初始状态σ0组成。 状态转移函数φ:σi→σi+1，将当前状态σi变为一个新状态σi+1， 输出函数ψ:σi→zi，当前状态σi变为输出符号集中的一个元素zi。

15 图2.5 作为有限状态自动机的密钥流生成器

16 关键:φ和ψ，使得输出序列z满足密钥流序列z应满足的几个条件，并且要求在设备上是节省的和容易实现的。为了实现这一目标，必须采用非线性函数。
采用线性的φ和非线性的ψ时，将能够进行深入的分析并可以得到好的生成器。 可将这类生成器分成驱动部分和非线性组合部分. 驱动部分控制生成器的状态转移，并为非线性组合部分提供统计性能好的序列； 非线性组合部分要利用这些序列组合出满足要求的密钥流序列。

17 图2.6 密钥流生成器的分解

18 图2.7 常见的两种密钥流产生器

19 2.2 线性反馈移位寄存器 移位寄存器是流密码产生密钥流的一个主要组成部分。
GF(2)上一个n级反馈移位寄存器由n个二元存储器与一个反馈函数f(a1,a2,…,an)组成，如图2.8所示。 图2.8 GF(2)上的n级反馈移位寄存器 2.2 线性反馈移位寄存器

20 每一存储器称为移位寄存器的一级，在任一时刻，这些级的内容构成该反馈移位寄存器的状态，每一状态对应于GF(2)上的一个n维向量，共有2n种可能的状态。每一时刻的状态可用n长序列
a1,a2,…,an 或n维向量 (a1,a2,…,an) 表示，其中ai是第i级存储器的内容。

21 初始状态由用户确定， 当第i个移位时钟脉冲到来时，每一级存储器ai都将其内容向下一级ai-1传递，并计算f(a1,a2,…,an)作为下一时刻的an。 反馈函数f(a1,a2,…,an)是n元布尔函数，即n个变元a1,a2,…,an可以独立地取0和1这两个可能的值，函数中的运算有逻辑与、逻辑或、逻辑补等运算，最后的函数值也为0或1。

22 例2.2 图2.9是一个3级反馈移位寄存器，其初始状态为(a1,a2,a3)=(1,0,1)，输出可由表2.2求出。
图2.9 一个3级反馈移位寄存器

23 表2.2 一个3级反馈移位寄存器 的状态和输出 状态（a1,a2,a3) 输出 1

24 f(a1,a2,…,an) =cna1cn-1a2…c1an
即输出序列为 …，周期为4。 如果f(a1,a2,…,an)是a1,a2,…,an的线性函数，则称之为线性反馈移位寄存器LFSR（linear feedback shift register）。此时f可写为 f(a1,a2,…,an) =cna1cn-1a2…c1an 其中常数ci=0或1，是模2加法。ci=0或1可用开关的断开和闭合来实现，如图2.10所示。

25 图2.10 GF(2)上的n级线性反馈移位寄存器

26 an+t=cnatcn-1at+1…c1an+t-1
线性反馈移位寄存器因其实现简单、速度快、有较为成熟的理论等优点而成为构造密钥流生成器的最重要的部件之一。

27 例2.3 图2.11是一个5级线性反馈移位寄存器，其初始状态为（a1,a2,a3,a4,a5）=(1,0,0,1,1)，可求出输出序列为
… 周期为31。 图2.11 一个5级线性反馈移位寄存器

28 在线性反馈移位寄存器中总是假定c1,c2,…,cn中至少有一个不为0，否则f(a1,a2,…,an)≡0，这样的话，在n个脉冲后状态必然是00…0，且这个状态必将一直持续下去。
若只有一个系数不为0，设仅有cj不为0，实际上是一种延迟装置。 一般对于n级线性反馈移位寄存器，总是假定cn=1。

29 n级线性反馈移位寄存器的状态周期小于等于2n-1。
周期达到最大值的序列称为m序列。

30 an+k=c1an+k-1 c2an+k-2 … cnak (*) p(x)=1+c1x+…＋cn+1xn-1＋cnxn
2.3 线性移位寄存器的一元多项式表示 设n级线性移位寄存器的输出序列{ai}满足递推关系 an+k=c1an+k-1 c2an+k … cnak (*) 对任何k>=1成立。这种递推关系可用一个一元高次多项式 p(x)=1+c1x+…＋cn+1xn-1＋cnxn 表示，称这个多项式为LFSR的特征多项式或特征多项式。

31 记2n-1个非零序列的全体为G(p(x))。 定义2.1 给定序列{ai}，幂级数
设n级线性移位寄存器对应于递推关系(*)，由于ai∈GF(2) (i =1, 2,…, n)，所以共有2n组初始状态，即有2n个递推序列，其中非恒零的有2n-1个， 记2n-1个非零序列的全体为G(p(x))。 定义2.1 给定序列{ai}，幂级数 称为该序列的生成函数。

32 定理2.1 设p(x)=1+c1x+…+cn-1xn-1+cnxn是GF(2)上的多项式，G(p(x))中任一序列{ai}的生成函数A(x)满足：
A(x)=(x)/p(x) 其中 =(a1+a2x+…+anxn-1)+c1x(a1+a2x+…+an-1xn-2) +c2x2(a1+a2x+…+an-2xn-3)+…+cn-1xn-1a1

33 证明： 在等式 an+1=c1anc2an-1…cna1 an+2=c1an+1c2an…cna2 … 两边分别乘以xn,xn+1,…，再求和，可得 A(x)-(a1+a2x+…+anxn-1) =c1x[A(x)-(a1+a2x+…+an-1xn-2)] +c2x2[A(x)-(a1+a2x+…+an-2xn-3)]+…+cnxnA(x)

34 移项整理得 (1+c1x+…+cn-1xn-1+cnxn)A(x) =(a1+a2x+…+anxn-1)+c1x(a1+a2x+…+an-1xn-2) +c2x2(a1+a2x+…+an-2xn-3)+…+cn-1xn-1a1 即 (证毕) 注意在GF(2)上有a+a=0。

35 A(x)=(x)/p(x)=[(x)r(x)]/[p(x)r(x)]=(x)r(x)/q(x)
定理2.2 p(x)|q(x)的充要条件是G(p(x))G(q(x))。 证明：若p(x)|q(x), 可设q(x)=p(x)r(x)，因此 A(x)=(x)/p(x)=[(x)r(x)]/[p(x)r(x)]=(x)r(x)/q(x) 所以若{ai}∈ G(p(x)), 则{ai}∈ G(q(x)), 即G(p(x))  G(q(x))。

36 反之，若G(p(x))G(q(x)),则对于多项式(x)，存在序列{ai}∈ G(p(x))以A(x)=(x) / p(x)为生成函数。特别地，对于多项式(x)=1，存在序列
{ai}∈ G(p(x)) 以1 / p(x)为生成函数。由于 G(p(x))  G(q(x)), 序列{ai}∈ G(q(x)), 所以存在函数r(x)，使得{ai}的生成函数也等于r(x) / q(x)，从而1/p(x)= r(x) / q(x)，即q(x)=p(x)r(x)，所以p(x)|q(x). (证毕) 上述定理说明可用n级LFSR产生的序列，也可用级数更多的LFSR来产生。

37 定义2.2 设p(x)是GF(2)上的多项式，使p(x)|(xp-1)的最小p称为p(x)的周期或阶。
定理2.3 若序列{ai}的特征多项式p(x)定义在GF(2)上，p是p(x)的周期，则{ai}的周期r | p。 证明：由p(x)周期的定义得p(x)|(xp-1), 因此存在q(x)，使得xp-1=p(x)q(x)，又由p(x)A(x)=(x)可得p(x)q(x)A(x)=(x)q(x)， 所以(xp-1)A(x)=(x)q(x)。由于q(x)的次数为 p-n，(x)的次数不超过n-1，所以(xp-1)A(x)的次数不超过(p-n)+(n-1)=p-1。将(xp-1)A(x)写成 xp A(x)- A(x),可看出对于任意正整数i都有ai+p=ai。 设p=kr+t,0≤t<r，则ai+p=ai+kr+t=ai+t=ai，所以t=0，即r | p。（证毕）

38 n级LFSR输出序列的周期r不依赖于初始条件，而依赖于特征多项式p(x)。我们感兴趣的是LFSR遍历2n-1个非零状态，这时序列的周期达到最大2n-1，这种序列就是m序列。
显然对于特征多项式一样，而仅初始条件不同的两个输出序列，一个记为{a(1)i}，另一个记为{a(2)i}，其中一个必是另一个的移位，即存在一个常数k，使得 a(1)i=a(2)k+i, i=1, 2,… 下面讨论特征多项式满足什么条件时，LFSR的输出序列为m序列。

39

40

41

42

43

44

45

46

47

48

49 小结 序列的周期整除特征多项式的周期 若特征多项式是不可约的，则序列的周期等于特征多项式的周期 序列有最大周期  特征多项式是不可约的
序列有最大周期  特征多项式是不可约的 序列有最大周期   特征多项式是本原多项式

50 2.4 m序列的伪随机性 流密码的安全性取决于密钥流的安全性，要求密钥流序列有好的随机性，以使密码分析者对它无法预测。也就是说，即使截获其中一段，也无法推测后面是什么。如果密钥流是周期的，要完全做到随机性是困难的。严格地说，这样的序列不可能做到随机，只能要求截获比周期短的一段时不会泄露更多信息，这样的序列称为伪随机序列。

51

52

53

54

55

56

57

58

59

60 2.5 m序列密码的破译 有限域上的二元加法流密码（如图2.3）是目前最为常用的流密码体制，
设滚动密钥生成器是线性反馈移位寄存器，产生的密钥是序列。又设Sh和Sh+1是序列中两个连续的n长向量，其中

61 设序列{ai}满足线性递推关系： 可表示为

62 或Sh+1=M·Sh，其中 又设敌手知道一段长为2n的明密文对，即已知

63 于是可求出一段长为2n的密钥序列 其中 , 由此可推出线性反馈移位寄存器连续的n+1个状态：

64 做矩阵 而 若X可逆，则

65 下面证明X的确是可逆的。 因为X是由S1,S2,…,Sn作为列向量，要证X可逆，只要证明这n个向量线性无关。 由序列递推关系： 可推出向量的递推关系：

66 设m(m≤n+1)是使S1,S2,…,Sm线性相关的最小整数，即存在不全为0的系数l1,l2,…,lm，其中不妨设l1=1，使得
对于任一整数i有

67 由此又推出密钥流的递推关系： 即密钥流的级数小于m。若m≤n，则得出密钥流的级数小于n，矛盾。所以m=n+1，从而矩阵X必是可逆的。

68 例2.6 设敌手得到密文串 和相应的明文串 ， 得密钥流为 。进一步假定敌手还知道密钥流是使用5级线性反馈移位寄存器产生的，那么敌手可分别用密文串中的前10个比特和明文串中的前10个比特建立如下方程

69 即 而

70 从而得到 所以 密钥流的递推关系为

71 2.6 非线性序列 密钥流生成器可分解为驱动子系统和非线性组合子系统。 驱动子系统常用一个或多个线性反馈移位寄存器来实现，
2.6 非线性序列 密钥流生成器可分解为驱动子系统和非线性组合子系统。 驱动子系统常用一个或多个线性反馈移位寄存器来实现， 非线性组合子系统用非线性组合函数F来实现。

72 为了使密钥流生成器输出的二元序列尽可能复杂，应保证其周期尽可能大、线性复杂度和不可预测性尽可能高，因此常使用多个LFSR来构造二元序列，称每个LFSR的输出序列为驱动序列，显然密钥流生成器输出序列的周期不大于各驱动序列周期的乘积，因此，提高输出序列的线性复杂度应从极大化其周期开始。 二元序列的线性复杂度指生成该序列的最短LFSR的级数，最短LFSR的特征多项式称为二元序列的极小特征多项式。

73 Geffe序列生成器由3个LFSR组成，其中LFSR2作为控制生成器使用 图2.12 Geffe序列生成器图

74 当LFSR2输出1时，LFSR2与LFSR1相连接；当LFSR2输出0时，LFSR2与LFSR3相连接。
若设LFSRi的输出序列为{a(i)k} (i=1,2,3)，则输出序列{bk}可以表示为

75 Geffe序列生成器也可以表示为图2.13的形式，其中LFSR1和LFSR3作为多路复合器的输入，LFSR2控制多路复合器的输出。设LFSRi的特征多项式分别为ni次本原多项式，且ni两两互素，则Geffe序列的周期为 线性复杂度为

76 图2.13 多路复合器表示的Geffe序列生成器

77 Geffe序列的周期实现了极大化，且0与1之间的分布大体上是平衡的。

78 J-K触发器 J-K触发器如图2.14所示，它的两个输入端分别用J和K表示，其输出ck不仅依赖于输入，还依赖于前一个输出位ck-1，即 其中x1和x2分别是J和K端的输入。由此可得J-K触发器的真值表，如表2.3。

79 图2.14 J-K触发器 图2.15 利用J-K触发器的非线性序列生成器

80 在图2.15中，令驱动序列{ak}和{bk}分别为m级和n级m序列，则有
如果令c-1=0，则输出序列的最初3项为 当m与n互素且a0+b0=1时，序列{ck}的周期为 (2m-1)(2n-1)。

81 例2.7 令m=2, n=3，两个驱动m序列分别为 {ak}=0,1,1,… 和 {bk}=1,0,0,1,0,1,1,… 于是，输出序列{ck}是0,1,1,0,1,0,0,1,1,1,0,1,0,1,0,0,1,0,0,1,0,…, 其周期为(22-1)(23-1)=21。

82 由表达式ck=(ak+bk)ck-1+ak可得
因此，如果知道{ck}中相邻位的值ck-1和ck，就可以推断出ak和bk中的一个。而一旦知道足够多的这类信息，就可通过密码分析的方法得到序列{ak}和{bk}。为了克服上述缺点，Pless提出了由多个J-K触发器序列驱动的多路复合序列方案，称为Pless生成器。

83 Pless生成器 Pless生成器由8个LFSR、4个J-K触发器和1个循环计数器构成，由循环计数器进行选通控制，如图2.16所示。假定在时刻t输出第t(mod 4)个单元，则输出序列为 a0b1c2d3a4b5d6

84 图2.16 Pless生成器

85 钟控序列最基本的模型是用一个LFSR控制另外一个LFSR的移位时钟脉冲，如图2.17所示。 图2.17 最简单的钟控序列生成器
钟控序列生成器 钟控序列最基本的模型是用一个LFSR控制另外一个LFSR的移位时钟脉冲，如图2.17所示。 图2.17 最简单的钟控序列生成器

86 假设LFSR1和LFSR2分别输出序列{ak}和{bk}，其周期分别为p1和p2。当LFSR1输出1时，移位时钟脉冲通过与门使LFSR2进行一次移位，从而生成下一位。当LFSR1输出0时，移位时钟脉冲无法通过与门影响LFSR2。因此LFSR2重复输出前一位。假设钟控序列{ck}的周期为p，可得如下关系： 其中

87 又设{ak}和{bk}的极小特征多项式分别为GF(2)上的m和n次本原多项式f1(x)和f2(x)，且m|n。因此，p1=2m-1, p2=2n-1。又知w1=2m-1， 因此
gcd(w1, p2)=1，所以p=p1p2=(2m-1)(2n-1)。 此外，也可推导出{ck}的线性复杂度为n(2m-1)，极 小特征多项式为

88 例2.8 设LFSR1为3级m序列生成器，其特征多项式为f1(x)=1+x+x3。设初态为a0=a1=a2=1，于是输出序列为{ak}=1,1,1,0,1,0,0,…。
又设LFSR2为3级m序列生成器，且记其状态向量为σk，则在图2.17的构造下σk的变化情况如下：

89 {ck}的周期为(23-1)2=49，在它的一个周期内，每个σk恰好出现7次。
设f2(x)=1+x2+x3为LFSR2的特征多项式，且初态为b0=b1=b2=1，则{bk}=1,1,1,0,0,1,0，…。 由σk的变化情况得 {ck}=1,1,1,0,0,0,0,0, 1,0,1,1,1,1,1, 1,0,0,0,1,1,1, 0,1,1,1,1,1,1, 0,0,1,1,0,0,0, 1,1,1,1,0,0,0, 0,1,0,0,1,1,…

90 {ck}的极小特征多项式为1+x14 + x21，其线性复杂度为3·（23-1）=21，图2.18是其线性等价生成器。
图2.18 一个钟控序列的线性等价生成器

91 设计一个性能良好的序列密码是一项十分困难的任务。最基本的设计原则是“密钥流生成器的不可预测性”，它可分解为下述基本原则：
① 长周期。 ② 高线性复杂度。 ③ 统计性能良好。 ④ 足够的“混乱”。 ⑤ 足够的“扩散”。 ⑥ 抵抗不同形式的攻击。

92 习题 2-1 3级线性反馈移位寄存器在c3=1时可有4种线性反馈函数，设其初始状态为(a1,a2,a3)=(1,0,1)，求各线性反馈函数的输出序列及周期。 2-2 设n级线性反馈移位寄存器的特征多项式为p(x)，初始状态为(a1,a2,…,an-1,an)=(00…01)，证明输出序列的周期等于p(x)的阶。 2-3 设n=4, ，初始状态为(a1,a2,a3,a4)=(1,1,0,1)，求此非线性反馈移位寄存器的输出序列及周期。

93 2-4 已知流密码的密文串1010110110和相应的明文串0100010001，而且还已知密钥流是使用3级线性反馈移位寄存器产生的，试破译该密码系统。
2-5 设J-K触发器中{ak}和{bk}分别为3级和4级m序列，且 {ak}= … {bk}= … 求输出序列{ck}及周期。

94 2-6 设基本钟控序列产生器中{ak}和{bk}分别为2级和3级m序列，且{ak}=101101…
{bk}= …求输出序列{ck}及周期。