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

密码学Cryptology 计算机学院 黄玉划 hyuhua2k@163.com 办公室：北门A12号楼116教学内容 第1章 引论 第2章 古典密码学 第3章 流密码算法与伪随机数产生器 第4章 分组密码算法 第5章 分组密码算法的工作模式 第6章 单向散列(Hash)函数 第7章 公钥密码算法与数字签名算法 第8章 认证与密钥交换协议 第3章 流密码算法与伪随机数产生器 密码算法可分为两类：对称算法和非对称算法。对称算法又称单密钥算法，可分为两类：序列密码算法和分组密码算法。序列密码算法通过将明（密）文同密码流逐位相异或进行加（解）密,其特点是实现简单，速度一般比较快，错误传播少或没有。分组密码算法则将明（密）文分组通过一对互逆密码算法来进行分组加（解）密。 第3章 流密码算法(续) 序列密码也称为流密码，密钥序列也称为密钥流。 序列密码加密的基本原理是：用一个随机序列与明文序列进行异或来产生密文。 流密码是将明文划分成字符（单个字母），或其编码的基本单元（0, 1数字），字符分别与密钥流作用进行加密，解密时以同步产生的同样的密钥流实现。 设计序列密码体制的关键就是要设计一种产生密钥序列的方法。 “一次一密”的随机密钥序列密码体制在理论上是不可以破译的。 产生序列密码中的密钥序列的一种主要工具是移位寄存器。 第3章 流密码算法——移位寄存器 移位寄存器是流密码产生密钥流的一个主要组成部分。GF(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)=cnat⊕cn-1at+1⊕…⊕c1an+t-1 其中常数ci=0或1(总是假定cn=1),⊕是模2加法。ci=0或1可用开关的断开和闭合来实现,如图所示。 第3章 流密码算法——线性反馈移位寄存器(续) n级线性反馈移位寄存器最多有2n个不同的状态。若其初始状态为0，则其状态恒为0。若其初始状态非0，则其后继状态不会为0。因此n级线性反馈移位寄存器的状态周期≤2n-1。其输出序列的周期T与状态周期相等，也≤2n-1。只要选择合适的反馈函数便可使序列的周期达到最大值2n-1，周期达到最大值的序列称为m序列。 第3章 流密码算法——LFSR的特征多项式 设n级线性移位寄存器的输出序列满足递推关系an+t=cnat⊕cn-1at+1⊕…⊕c1an+t-1 这种递推关系可用一个一元高次多项式P(x)=1+c1x+…＋cn-1xn-1＋cnxn表示，称这个多项式为LFSR的特征多项式。 定理 n级LFSR产生的序列有最大周期2n-1的必要条件是其特征多项式为不可约的。 若n次不可约多项式p(x)的阶为2n-1，则称p(x)是n次本原多项式。 定理 设{ai}∈G(p(x))，{ai}为m序列的充要条件是p(x)为本原多项式。 第3章 流密码算法（续） 从密码系统的角度看，一个伪随机序列还应满足下面的条件： ① {ai}的周期相当大。 ② {ai}的确定在计算上是容易的。 ③ 由密文及相应的明文的部分信息，不能确定整个{ai}。 注：LFSR不能直接作为流密码算法。 第3章 流密码算法—— RC4算法 RC4算法是由RSA公司的Ron Rivest设计的序列密码算法。在WLAN(无线局域网)必威体育官网网址机制中，IEEE802.11的初期标准就是采用了RC4算法。 假设密钥为key，密钥长度为Lk字节；输出密钥流为ks，所需输出长度为len，则RC4算法可表示为ks = RC4(key, Lk)，其过程可分为三步： 第3章 流密码算法—— RC4算法步骤 1）初始化(Initialization)：j = 0; For i = 0 to 255 { s[i] = i ; k[i] = key[i mod Lk]; } 2）密钥编排算法(KSA) For i = 0 to 255 { j = ( j + s[i] + k[i]) mod 256; tmp2 = s[i]; s[i] = s[j]; s[j] = tmp2; } 第3章 流密码算法—— RC4算法步骤（续） 3）伪随机数产生(PRNG)算法：i = j = 0; for tmp = 0 to len-1 { i = (i + 1) mod 256; j = (j + s[i]) mod 256; tmp2 = s[