第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 流密码(序列密码)的基本概念 明文: 密钥: 密文: 加密变换: 解密变换:

3 加法流密码体制模型

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

5 存储器 存储器 存储器 存储器 图2 GF(2)上的n级反馈移位寄存器

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

7 初始状态由用户确定。 反馈函数f(a1,a2,…,an)是n元布尔函数，即函数的自变量和因变量只取0和1这两个可能的值。 函数中的运算有逻辑与、逻辑或、逻辑补等运算。

8 例 图3 是一个3级反馈移位寄存器，其初始状态为(a1,a2,a3)=(1,0,1)，输出可由表2.2求出。
1 表2.2 一个3级反馈移位寄存器的状态和输出 图3 一个3级反馈移位寄存器 即输出序列为 …，周期为4。

9 线性反馈移位寄存器LFSR（linear feedback shift register）
GF(2)上的n级线性反馈移位寄存器

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

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

12 总是假定c1,c2,…,cn中至少0，否则 f(a1,a2,…,an)≡0。 总是假定cn=1。
LFSR输出序列的性质：完全由其反馈函数决定。 n级LFSR状态数：最多有2n个。 n级LFSR的状态周期：  2n-1。 输出序列的周期=状态周期， 2n-1。 选择合适的反馈函数可使序列的周期达到最大值 2n-1，周期达到最大值的序列称为m序列。

13 an+k=c1an+k-1 c2an+k-2 … cnak (*) p(x)=1+c1x+…＋cn-1xn-1＋cnxn
2.3 线性移位寄存器的一元多项式表示 设n级线性移位寄存器的输出序列满足递推关系 an+k=c1an+k-1 c2an+k … cnak (*) 用延迟算子 D(Dak=ak-1) 作为未定元，给出的反馈多项式为： p(D)=1+c1D+…＋cn-1Dn-1＋cnDn 这种递推关系 可用一个一元高次多项式 p(x)=1+c1x+…＋cn-1xn-1＋cnxn 表示，称这个多项式为LFSR的特征多项式或特征多项式。 记2n-1个非零序列的全体为G(p(x))

14 定义2.1 给定序列{ai}，幂级数 称为该序列的生成函数。

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

16 证明： 在等式 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) (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 移项整理

17 (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 移项整理

18 定理2.2 p(x)|q(x)的充要条件是G(p(x))G(q(x))。
证明 (1)必要性：若p(x)|q(x)，可设q(x)=p(x)r(x)，因此 所以若{ai}∈G(p(x))，则{ai}∈G(q(x))，即G(p(x))G(q(x))。

19 上述定理说明可用n级LFSR产生的序列，也可用级数更多的LFSR来产生。
(2)充分性： 上述定理说明可用n级LFSR产生的序列，也可用级数更多的LFSR来产生。

20 定义2.2 设p(x)是GF(2)上的多项式，使p(x)|(xp-1)的最小p称为p(x)的周期或阶。

21 定理2.3 若序列{ai}的特征多项式p(x)定义在GF(2)上，p是p(x)的周期，则{ai}的周期r|p。 证明：

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

23 下面讨论特征多项式满足什么条件时，LFSR的输出序列为m序列。

24 定理2.4 设p(x)是n次不可约多项式，周期为m，序列{ai}∈G(p(x))，则{ai}的周期为m。
证明：设{ai}的周期为r，由定理2.3有r|m，所以r≤m。 设A(x)为{ai}的生成函数，A(x)=(x) / p(x)，即p(x)A(x)=(x)≠0，(x)的次数不超过n-1。而 A(x)=∑aixi-1=a1+a2x+…+arxr-1 +xr(a1+a2x+…+arxr-1) +(xr)2(a1+a2x+…+arxr-1)+… =a1+a2x+…+arxr-1/(1-xr) =a1+a2x+…+arxr-1/(xr-1)

25

26 定理2.5 n级LFSR产生的序列有最大周期2n-1的必要条件是其特征多项式为不可约的。
证明：设n级LFSR产生的序列周期达到最大2n-1。反证法：设特征多项式为p(x)，若p(x)可约，可设为p(x)=g(x)h(x)，其中g(x)不可约，且次数k<n。由于G(g(x))G(p(x))，而G(g(x))中序列的周期一方面不超过2k-1，另一方面又等于2n-1，这是矛盾的，所以p(x)不可约。（证毕） 该定理的逆不成立，即LFSR的特征多项式为不可约多项式时，其输出序列不一定是m序列。

27 ak=ak-1ak-2ak-3ak-4(k≥4)
例2.4 f(x)=x4+x3+x2+x+1为GF(2)上的不可约多项式，这可由x,x+1,x2+x+1都不能整除f(x)得到。以f(x)为特征多项式的LFSR的输出序列可由 ak=ak-1ak-2ak-3ak-4(k≥4) 和给定的初始状态求出，设初始状态为0001，则输出序列为 …，周期为5，不是m序列。

28 定义2.3 若n次不可约多项式p(x)的阶为 2n-1，则称p(x)是n次本原多项式。

29 定理2.6 设{ai}∈G(p(x))，{ai}为m序列的充要条件是p(x)为本原多项式。
证明：若p(x)是本原多项式，则其阶为2n-1，得{ai}的周期等于2n-1，即{ai}为m序列。 反之，若{ai}为m序列，即其周期等于2n-1，由定理2.5知p(x)是不可约的。由定理2.3知{ai}的周期2n-1整除p(x)的阶，而p(x)的阶不超过2n-1，所以p(x)的阶为2n-1，即p(x)是本原多项式。（证毕）

30 {ai}为m序列的关键在于p(x)为本原多项式，n次本原多项式的个数为
(2n-1)/n 其中为欧拉函数。已经证明，对于任意的正整数n，至少存在一个n次本原多项式。所以对于任意的n级LFSR，至少存在一种连接方式使其输出序列为m序列。

31 例2.5 设p(x)=x4+x+1，由于p(x)|(x15-1)，但不存在小于15的常数l，使得p(x)|(xl-1)，所以p(x)的阶为15。p(x)的不可约性可由x,x+1,x2+x+1都不能整除p(x)得到，所以p(x)是本原多项式。 若LFSR以p(x)为特征多项式，则输出序列的递推关系为 ak=ak-1ak-4(k≥4) 若初始状态为1001，则输出为 … 周期为24-1=15，即输出序列为m序列。

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

33 为讨论序列的随机性，先讨论随机序列的一般特性。
游程: 设{ai}=(a1a2a3…)为0、1序列，例如 ，其前两个数字是00，称为0的2游程；接着是11，是1的2游程；再下来是0的1游程和1的3游程。

34 定义2.4：GF(2)上周期为T的序列{ai}的自相关函数定义为
当τ=0时，R(τ)=1；当τ≠0时，称R(τ)为异相自相关函数。

35 Golomb对伪随机周期序列提出了应满足的如下3个随机性公设：
① 在序列的一个周期内，0与1的个数相差至多为1。 ② 在序列的一个周期内，长为i的游程占游程总数的1/2i (i=1,2,…)，且在等长的游程中0的游程个数和1的游程个数相等。 ③ 异相自相关函数是一个常数。 ①说明{ai}中0与1出现的概率基本上相同; ②说明0与1在序列中每一位置上出现的概率相同; ③意味着通过对序列与其平移后的序列做比较，不能给出其他任何信息。

36 从密码系统的角度看，一个伪随机序列还应满足下面的条件：
① {ai}的周期相当大。 ② {ai}的确定在计算上是容易的。 ③ 由密文及相应的明文的部分信息，不能确定整个{ai}。

37 m序列满足Golomb的3个随机性公设。 定理2.7 GF(2)上的n长m序列{ai}具有如下性质： ① 在一个周期内，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}的自相关函数为

38 证明： ① 在n长m序列的一个周期内，除了全0状态外，每个n长状态（共2n-1个）都恰好出现一次，这些状态中有2n-1个在a1位是1，其余2n-1-2n-1=2n-1-1个状态在a1位是0。
对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。

39 由于寄存器中不会出现全0状态，所以不会出现0的n游程，但必有一个1的n游程，而且1的游程不会更大，因为若出现1的n+1游程，就必然有两个相邻的全1状态，但这是不可能的。这就证明了1的n游程必然出现在如下的串中： 当这n+2位通过移位寄存器时，便依次产生以下状态：

40 由于 ， 这两个状态只能各出现 一次，所以不会有1的n-1游程。
由于 ， 这两个状态只能各出现 一次，所以不会有1的n-1游程。 0的n-1游程只有一个: 于是在一个周期内，总游程数为

41 ③ {ai}是周期为2n-1的m序列，对于任一正整数τ(0<τ<2n-1)，{ai}+{ai+τ}在一个周期内为0的位的数目正好是序列{ai}和{ai+τ}对应位相同的位的数目。

42 有限域上的二元加法流密码是目前最为常用的流密码体制，设滚动密钥生成器是线性反馈移位寄存器，产生的密钥是m序列。

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

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

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

46 做矩阵 而 则

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

48 即 而

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

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

51 二元序列的线性复杂度: 指生成该序列的最短LFSR的级数。

52 Geffe序列生成器由3个LFSR组成，其中LFSR2作为控制生成器使用，如图2.12所示。

53 设LFSRi的特征多项式分别为ni次本原多项式，且ni 两两互素
图2.12 Geffe序列生成器 则Geffe序列的周期= 线性复杂度=

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

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

56 图2.14 J-K触发器

57

58 利用J-K触发器的非线性序列生成器见图2.15。
{ak} :m级m序列 {bk}:n级m序列

59 当m与n互素且a0+b0=1时，序列{ck}的周期为(2m-1)(2n-1)。

60 例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。

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

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

63 图2.16 Pless生成器

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

65 图2.17 最简单的钟控序列生成器

66 假设LFSR1和LFSR2分别输出序列{ak}和{bk}，其周期分别为p1和p2。假设钟控序列{ck}的周期为p，可得如下关系：

67 f1(x): {ak} 的极小特征多项式, GF(2)上m次本原
f2(x): {bk}的极小特征多项式, GF(2)上n次本原 且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) 极小特征多项式:

68 例 设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的变化情况如下：

69 {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,…

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

71 实际应用中，可以用上述最基本的钟控序列生成器构造复杂的模型，具体构造方式可参阅有关文献。

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

73 第2章重点 流密码的加密和解密过程； 线性反馈移位寄存器及一元多项式表示； m序列具有伪随机性； m序列的破译方法；
非线性序列：Geffe生成器，J-K触发器，Pless生成器，钟控序列生成器。