06密码学--序列密码

本章主要讲述了序列密码,其中包括序列密码的概念:同步流密钥,自同步流密钥;反馈移位寄存器:线性反馈移位寄存器LFSR,基于LFSR的密钥流生成器等;其他序列密码介绍:RC4,SEAL2.0,混沌序列;伪随机比特/序列:真随机数生成,PRNG生成,CSPRNG生成,统计测试。
展开查看详情

1.密码学 导论˙第 6 章 序列 密码 李卫海

2.本章内容 密码学导论 -- 中国科学技术大学 2

3.第一节 序列密码的概念 密码学导论 -- 中国科学技术大学 3

4.序列密码 , 又 称流密码 ,它逐个比特处理信息 典型流密码体制 使用 (伪)随机数序列 做加密密钥流 加密、解密算法 加密密钥流与明文流按比特异或 C i = M i  StreamKey i 密钥 K 密钥 K 伪随机数发生器 k 加密 伪随机数发生器 k 解密 明文码流 M 明文码流 M 密文码流 C 密码学导论 -- 中国科学技术大学 4

5.明文信息中的统计特征被流密钥的随机性所掩盖 加密算法极为简单!! 加解密简单,速率极快 密钥流严格不可重复使用 已知明文攻击可以轻易获得密钥流 关键在设计一个好的伪随机数发生器 设计优良的流密码可以具有与分组密码相当的安全性 密码学导论 -- 中国科学技术大学 5

6.流密码的一些设计准则 密码学导论 -- 中国科学技术大学 6

7.多数流密码的基本构造模块为 反馈移位寄存器 FSR 特别是 线性反馈移位寄存器 LFSR 寄存器存储当前状态,流密码有时也称为状态密码 流密码通常可分为同步和自同步两类 同步流密钥 : 通信双方需要密钥严格同步 同步被破坏时,密文无法解密 自同步流密钥 : 同步被破坏时,可以自动重建,正确解密 密码学导论 -- 中国科学技术大学 7

8.同步流密钥 反馈移位寄存器: σ i+1 =f( σ i , k) σ 是寄存状态( σ 0 为初始状态,可由密钥 k 确定) z i 是加密密钥流: z i =g( σ i , k) 密文: c i =h( z i , m i ) f g σ i h σ i+1 z i k m i σ i h -1 g z i σ i f σ i σ i+1 k m i c i 密码学导论 -- 中国科学技术大学 8

9.性质: 严格要求同步 必须同步,才能保证双方使用相同的密钥位 需要在密文中嵌入特殊记号,用于同步检测 或利用明文的冗余进行检测 若密文在传输中发生插入或删除,或双方时钟不同步,会导致同步丢失 同步丢失后必须重建同步,包括状态重置、同步记号检测 无错误传播 密文字母错误,不影响其它字母的正确解密 主动攻击 在密文中插入或删除字符,破坏同步 有选择的改变密文字符,观察对明文的影响 f g σ i h σ i+1 z i k m i σ i h -1 g z i σ i f σ i σ i+1 k m i c i 密码学导论 -- 中国科学技术大学 9

10.自同步流密钥 反馈移位寄存器: σ i =f(c i-t ,c i-t+1 ,…,c i-1 ) 初始状态 σ 0 =( c -t ,c -t+1 ,…,c -1 ) 非保密 z i 是加密密钥流: z i =g( σ i , k) 密文: c i =h( z i , m i ) g h z i k m i h -1 g z i k m i c i … … … … σ i σ i 密码学导论 -- 中国科学技术大学 10

11.性质: 自同步 状态仅依赖以前的 t 个密文。同步丢失时,再接收 t 个密文即可自动恢复同步 有限的错误传播 当单个密文出错(或插入、删除)时,除当前明文字符错误外,之后最多会有 t 个解密明文错误 主动攻击 对密文的修改,会引发后面一些字符解密错误,增加了被解密器发现的可能性 自同步特性使得解密器发现主动攻击的可能性降低,因而需要附加技术来保证数据完整性 明文统计扩散 每个明文字符会影响其后的整个密文 g h z i k m i h -1 g z i k m i c i … … … … σ i σ i 密码学导论 -- 中国科学技术大学 11

12.第二节 反馈移位寄存器 密码学导论 -- 中国科学技术大学 12

13.一、线性反馈移位寄存器 LFSR 优点: 非常适合于硬件实现 可以产生大周期序列 可以产生具有良好统计性质的序列 易于利用代数方法对其进行分析 密码学导论 -- 中国科学技术大学 13

14.L 级 LFSR 由 0,1, …,L-1 共 L 个级(或延迟单元)和一个时钟构成 控制信号 c i 时钟用于控制数据的移动。每个时钟周期内执行下述操作 输出 第 0 级; 各级向下一级移位 反馈信号输入第 L-1 级 级 0 级 1 级 L-2 级 L-1 … … … c L c L-1 c 2 c 1 s j 输出 密码学导论 -- 中国科学技术大学 14

15.定义 :如前图的长为 L 的 LFSR 可记为 (L,C(D)) ,其中 C(D)=1+c 1 D+c 2 D 2 +…+ c L D L ∈GF (2 D ) 为 联结多项式 若 C(D) 的次数为 L (即 c L =1) ,则称此 LFSR 为 非奇异 的 各级的初始值 [s L-1 ,…,s 1 ,s 0 ] 称为该 LFSR 的 初始状态 初始状态为 [s L-1 ,…,s 1 ,s 0 ] 的 LFSR ,输出序列 s=s 0 ,s 1 ,… 为 s j =(c 1 s j-1 +c 2 s j-2 +…+ c L s j -L ) mod 2, j≥L 密码学导论 -- 中国科学技术大学 15

16.例: LFSR<4,1+D+D 4 > ,初始状态 [0,1,1,0] 输出为 s=0,1,1,0,0,1,0,0,0,1,1,1,1,0,1,… 周期 15 级 0 级 1 级 2 级 3 输出 t 级 3 级 2 级 1 级 0 t 级 3 级 2 级 1 级 0 t 级 3 级 2 级 1 级 0 0 0 1 1 0 5 0 0 0 1 10 0 1 1 1 1 0 0 1 1 6 1 0 0 0 11 1 0 1 1 2 1 0 0 1 7 1 1 0 0 12 0 1 0 1 3 0 1 0 0 8 1 1 1 0 13 1 0 1 0 4 0 0 1 0 9 1 1 1 1 14 1 1 0 1 密码学导论 -- 中国科学技术大学 16

17.矩阵表示 广义线性序列发生器: s j + c 1 s j-1 +c 2 s j-2 +…+ c L s j -L =0, j≥ L c i 为任意数 字 联结 矩阵 密码学导论 -- 中国科学技术大学 17

18.LFSR<L,C(D)) 的每一个输出序列(任何非零初始状态)是 周期的 ,当且仅当联结多项式 C(D) 的次数为 L 。 对奇异 LFSR ,除去开始的固定有限项后,是周期的 例: LFSR<4,1+D+D 2 > ,初始状态 [1,0,0,0] 输出为 s= 0,0 ,0,1,1,0,1,1 后面仅讨论非奇异 LFSR 级 0 级 1 级 2 级 3 输出 密码学导论 -- 中国科学技术大学 18

19.LFSR 输出序列的周期 若 C(D) 在 GF(2 L ) 上是不可约的,则每一个非零初始状态都可以产生一个 周期为 N 的输出序列。其中 N 是满足下述性质的最小正整数: C(D) 能够整除 1+D N (注意, N 总是的 2 L -1 因子) 若 C(D) 是本原多项式(即生成元),则每一 个非零初始状态都 可以产生具有 最大周期为 2 L -1 的输出序列。此 LFSR 称为 最大长度 LFSR ,输出序列称为 m 序列 。 密码学导论 -- 中国科学技术大学 19

20.常用移位寄存器序列 m 序列: 最长线性移位寄存器序列 Gold 序列: 两个级数相同(码长相同)的 m 序列的输出的异或 M 序列: 最长非线性移位寄存器序列。周期 2 L 密码学导论 -- 中国科学技术大学 20

21.m 序列 的 长度为 k( k≤L ) 的模型分布几乎是均匀的。即若 s 是长为 L 的 LFSR 生成的 m 序列,设 k(1≤k≤L) 为整数, s 是 s 的长为 2 L +k-2 的任意子序列,则: s 的每个长度为 k 的非零子序列恰好出现 2 L-k 次 长度为 k 的零子序列恰好出现 2 L-k -1 次。 密码学导论 -- 中国科学技术大学 21 k L-k

22.线性复杂度 无穷序列 s=s 0 ,s 1 ,,s 2 ,… 有限序列 s n =s 0 ,s 1 ,,s 2 ,…,s n-1 若某 LFSR 在某初始状态下输出序列的前 n 项为 s n 的话,则称该 LFSR 生成有限序列 s n 可以设想用 LFSR 来描述序列的复杂程度 LFSR 是线性的,因此它描述的是线性的复杂程度 密码学导论 -- 中国科学技术大学 22

23.无穷二元序列 s 的 线性复杂度 L(s) 定义为 : 若 s 为零序列,即 s=0,0,0,… ,则 L(s)= 0 若 没有 LFSR 能够生成 s ,则 L(s)= ∞ 否则 , L(s) 就为生成 s 的最短 LFSR 的 长度 有限二元序列 s n 的 线性复杂度 L( s n ) 定义为: 生成以 s n 为开始的二元序列的最短 LFSR 的长度 设 L N 表示子序列 s N =s 0 ,s 1 ,,s 2 ,…,s N-1 的线性复杂度,则序列 L 1 ,L 2 ,… 称为 s 的 线性复杂度轮廓 密码学导论 -- 中国科学技术大学 23

24.线性复杂度的性质 :令 s 和 t 都为二元序列 对任意 n≥1 ,子序列 s n 的线性复杂度满足 0≤L( s n )≤n 若 s 的周期为 N ,则 L(s)≤N L( s n )=0 ,当且仅当 s n 是长度为 n 的零序列 L( s n )=n ,当且仅当 s n =0,0,0,…,0,1 L( s  t )≤L(s)+L(t) 线性复杂度轮廓的性质 : 若 j> i ,则 L j ≥L i 若 L N+1 >L N ,则 L N ≤N/2 若 L N+1 >L N ,则 L N+1 +L N =N+1 密码学导论 -- 中国科学技术大学 24

25.Berlekamp -Massey 算法 求解最小阶数 L 及相应的 C(x) ,使之满足 s j + c 1 s j-1 +c 2 s j-2 +… c L s j -L =0, j=L,L+1,…,N-1 序列 s 1 ,s 2 ,…, s N 多项式 C(x)=1+c 1 x+c 2 s 2 +…+ c L s L 若以上算法定义在模 2 多项式运算中,即为求解线性复杂度及联结多项式的算法。 定义 d=s k +c 1 s k-1 +c 2 s k-2 +…+ c L s k -L 为迭代到第 k 轮时的下一步离差。即第 k-1 轮迭代结果对 s k 的预测与实际 s k 的差。 密码学导论 -- 中国科学技术大学 25

26.B-M 算法: j 表示 当前已迭代轮数, B(x) 和 b 分别表示当 L 最后一次更新前的 C(x) 和 d , m 表示当 L 更新后的轮数 密码学导论 -- 中国科学技术大学 26

27.密码学导论 -- 中国科学技术大学 27 s a+m s a+m-1 s a+m-2 … s a+1 s a s a-1 s a-2 … s a -L’ … s a -L 1 B 1 B 2 … B L’ 1 C 1 C 2 … C L j=a 时更新了线性复杂度 L 和联接多项式 C(x), 置 m=0

28.密码学导论 -- 中国科学技术大学 28 s a+m s a+m-1 s a+m-2 … s a+1 s a s a-1 s a-2 … s a -L’ … s a -L 1 B 1 B 2 … B L’ 1 C 1 C 2 … C L 1 C 1 C 2 … C m C m+1 … C L j=a 时更新了线性复杂度 L 和联接多项式 C(x), 置 m=0 j= a+m 时,下一步离差 d≠0

29.密码学导论 -- 中国科学技术大学 29 s a+m s a+m-1 s a+m-2 … s a+1 s a s a-1 s a-2 … s a -L’ … s a -L 1 B 1 B 2 … B L’ 1 C 1 C 2 … C L 1 C 1 C 2 … C m C m+1 … C L j=a 时更新了线性复杂度 L 和联接多项式 C(x), 置 m=0 j= a+m 时,下一步离差 d≠0