密码学c3流密码算法与伪随机数产生器

1、密码学Cryptology计算机学院 黄玉划办公室：北门A12号楼11613675155711教学内容第1章 引论第2章 古典密码学第3章 流密码算法与伪随机数产生器第4章 分组密码算法第5章 分组密码算法的工作模式第6章 单向散列(Hash)函数第7章 公钥密码算法与数字签名算法第8章 认证与密钥交换协议第3章 流密码算法与伪随机数产生器密码算法可分为两类：对称算法和非对称算法。对称算法又称单密钥算法，可分为两类：序列密码算法和分组密码算法。序列密码算法通过将明（密）文同密码流逐位相异或进行加（解）密,其特点是实现简单，速度一般比较快，错误传播少或没有。分组密码算法则将明（密）文分组通过一对

2、互逆密码算法来进行分组加（解）密。 第3章 流密码算法(续)序列密码也称为流密码流密码，密钥序列也称为密钥流密钥流。 序列密码加密的基本原理是：用一个随机随机序列与明文明文序列进行异或来产生密文。流密码是将明文划分成字符（单个字母），或其编码的基本单元（0, 1数字），字符分别与密钥流作用进行加密，解密时以同步产生的同样的密钥流实现。 设计序列密码体制的关键就是要设计一种产生密钥序密钥序列列的方法。“一次一密”的随机密钥序列密码体制在理论上是不可以破译的。产生序列密码中的密钥序列的一种主要工具是移位寄移位寄存器存器。第3章 流密码算法移位寄存器移位寄存器是流密码产生密钥流的一个主要组成部分。G

3、F(2)上一个n级反馈移位寄存器由n个二元存储器与一个反馈函数f(a1,a2,an)组成，如图所示。第3章 流密码算法线性反馈移位寄存器(LFSR)如果移位寄存器的反馈函数f (a1,a2,an)是a1,a2,an的线性函数,则称之为线性反馈移位寄存器(LFSR)。此时输出序列an+t=f(at,at+1,an+t-1)=cnatcn-1at+1c1an+t-1其中常数ci=0或1(总是假定cn=1),是模2加法。ci=0或1可用开关的断开和闭合来实现,如图所示。第3章 流密码算法线性反馈移位寄存器(续)n级线性反馈移位寄存器最多有2n个不同的状态。若其初始状态为0，则其状态恒为0。若其初始状

4、态非0，则其后继状态不会为0。因此n级线性反馈移位寄存器的状态周期2n-1。其输出序列的周期T与状态周期相等，也2n-1。只要选择合适的反馈函数便可使序列的周期达到最大值2n-1，周期达到最大值的序列称为m序列。第3章 流密码算法LFSR的特征多项式设n级线性移位寄存器的输出序列满足递推关系an+t=cnatcn-1at+1c1an+t-1这 种 递 推 关 系 可 用 一 个 一 元 高 次 多 项 式P(x)=1+c1x+cn-1xn-1cnxn表示，称这个多项式为LFSR的特征多项式。定理定理 n级LFSR产生的序列有最大周期2n-1的必必要条件要条件是其特征多项式为不可约的。若n次不可

5、约多项式p(x)的阶为2n-1，则称p(x)是n次本原多项式。定理定理 设aiG(p(x)，ai为m序列的充要条件充要条件是p(x)为本原多项式。第3章 流密码算法（续）从密码系统的角度看，一个伪随机序列还应满足下面的条件： ai的周期相当大。 ai的确定在计算上是容易的。 由密文及相应的明文的部分信息，不能确定整个ai。注：LFSR不能直接作为流密码算法。第3章 流密码算法 RC4算法RC4算法是由RSA公司的Ron Rivest设计的序列密码算法。在WLAN(无线局域网)保密机制中，IEEE802.11的初期标准就是采用了RC4算法。假设密钥为key，密钥长度为Lk字节；输出密钥流为ks，

6、所需输出长度为len，则RC4算法可表示为ks = RC4(key, Lk)，其过程可分为三步： 第3章 流密码算法 RC4算法步骤1）初始化(Initialization)：j = 0;Fori = 0 to 255 si = i ; ki = keyi mod Lk; 2）密钥编排算法(KSA)Fori = 0 to 255 j = ( j + si + ki) mod 256; tmp2 = si; si = sj; sj = tmp2; 第3章 流密码算法 RC4算法步骤（续）3）伪随机数产生(PRNG)算法：i = j = 0;fortmp = 0tolen-1 i = (i + 1

7、) mod 256; j = (j + si) mod 256; tmp2 = si; si = sj; sj = tmp2; t = (si + sj) mod 256; kstmp = st; 第3章 流密码算法 RC4算法性能由RC4算法过程可知，RC4算法是通过将密钥key周期扩展为256字节来产生伪随机数的，没有体现出密钥长度的区别，例如RC4(key, Lk) = RC4(key|key, 2*Lk)（|表示串联）。另外，统计测试表明，RC4算法具有相关密钥产生相似输出的缺陷。为此，有人提出了RC4的一种变形算法RC4*，其算法过程ks=RC4*(key, Lk)为： 第3章 流密

8、码算法 RC4*算法步骤1）初始化(Initialization)：j = 0; i0 = 0; j0 = 0;Fori = 0 to 255 si = i ; ki = keyi mod Lk; 2）密钥编排算法(KSA)Fori = 0 to 255 j = ( j + si + ki) mod 256; i0 = (i0+si) mod 256; j0 = ( j0+sj) mod 256; tmp2 = si; si = sj; sj = tmp2; 第3章 流密码算法 RC4*算法步骤（续）3）伪随机数产生(PRNG*)算法： i = i0; j = j0;fortmp = 0tol

9、en-1 i = (i + C) mod 256; j = (j + si) mod 256; tmp2 = si; si = sj; sj = tmp2; t = (si + sj) mod 256; kstmp = st; 第3章 流密码算法 RC4*算法性能RC4*算法也是通过将密钥key周期扩展为256字节来产生伪随机数的，没有体现出密钥长度的区别，即RC4*(key, Lk) = RC4*(key|key, 2*Lk)。统计测试表明，RC4*算法的伪随机性比RC4有所改善，不过也存在相关密钥产生相似输出的缺陷。另外，RC4*算法与RC4相比，速度明显下降。SNOW2 (ISO/IEC

10、 18033-4: 2006) St+15 St+11St+5St+2 St-1R1SR2有限状态机kSNOW2SNOW2算法逻辑结构简洁，运算速度较快，已被采纳为3GPP加密标准。 SNOW2由1个线性反馈移位寄存器(LFSR)和1个有限状态机组成，状态机采用AES的思想。SNOW2的密钥编排比RC4、SEAL和HC256快，但比AES慢。SNOW2的缺点是：(1) SNOW2不能直接扩展成64位字算法，要更换不可约多项式。(2)内存需求较大。SNOW2有6个表，其中2个用于LFSR，4个S盒用于状态机，每个表由256个32位字组成。如果扩展成64位字算法，需要8个以上S盒，每个S盒由256

11、个64位字组成。 分组密钥编排/Hash消息扩展AES：wi=S(wi-1) wi-4 SHA1：wt = (wt-3 wt-8 wt-14 wt-16 )1SHA2： Wt = F6(Wt 2) + Wt 7 + F5 (Wt 15) + Wt 16 非线性循环移位寄存器非线性循环移位寄存器(NRSR) 输 出 a i ( m 比 特 ) 计 数 加 1 a i + n - 1 ( m 比 特 )a i + 1 ( i mod m ) 2 i + 1 ai+n = ( a i + n -1 j ) ai + 1 mod 2m ai+n = ( bai+n-1) (ai j ) + 1 mod

12、 2m 非线性循环移位寄存器特点非线性循环移位寄存器特点(1) 周期更大、安全性更高。n级LFSR的最大周期为2n-1；n级NLFSR的最大周期为2n。由于运算不固定，NRSR周期大于(2m)n（m为字长）。对于周期达到最大的LFSR，其输出状态1 2n-1是绝对均匀的；对于周期达到最大的NLFSR，其输出状态0 2n-1是绝对均匀的，遍历了所有状态才会重复。测试表明，NRSR产生的输出是伪随机均匀的。因此，NRSR的不可预测性和安全性优于(N)LFSR。NRSR的初值不受限，可以全为0。对于SHA1和SHA2的消息扩展算法，如果分组消息全为0，则扩展消息也全为0。 非线性循环移位寄存器特点非线性循环移位寄存器特点(2) 多平台适应性更灵活。(N)LFSR软件实现慢，解决的办法是并行m个(N)LFSR（m一般取平台的位数），相当于字长为m比特，但最大周期还是小于等于2n，除非象SNOW2一样采用模2m的本原多项式，最大周期才小于等于(2m)n。此时一般需要空间存储反馈系数表。对于不同的字长m和不同的级数n，(N)LFSR要寻找不同的反馈模式。不管字长m和级数n为多大，NRSR存在固定的反馈模式，无须寻找达到最大周期的反馈模式，可以直接适应各种平台，包括将来128位以上的平台。 非线性循环移位寄存器特点非线性循环移位寄存器特点(3) 效率更高。在32位平台下（2.4GHz双