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

密码学Cryptology计算机学院黄玉划[e-mail]办公室：北门A12号楼11613675155711教学内容第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公司的RonRivest设计的序列密码算法。在WLAN(无线局域网)保密机制中，IEEE802.11的初期标准就是采用了RC4算法。假设密钥为key，密钥长度为Lk字节；输出密钥流为ks，所需输出长度为len，则RC4算法可表示为ks=RC4(key,Lk)，其过程可分为三步：第3章流密码算法——RC4算法步骤1）初始化(Initialization)：j=0;Fori=0to255{s[i]=i;k[i]=key[imodLk];}2）密钥编排算法(KSA)Fori=0to255{j=(j+s[i]+k[i])mod256;tmp2=s[i];s[i]=s[j];s[j]=tmp2;}第3章流密码算法——RC4算法步骤（续）3）伪随机数产生(PRNG)算法：i=j=0;fortmp=0tolen-1{i=(i+1)mod256;j=(j+s[i])mod256;tmp2=s[i];s[i]=s[j];s[j]=tmp2;t=(s[i]+s[j])mod256;ks[tmp]=s[t];}第3章流密码算法——RC4算法性能由RC4算法过程可知，RC4算法是通过将密钥key周期扩展为256字节来产生伪随机数的，没有体现出密钥长度的区别，例如RC4(key,Lk)=RC4(key||key,2*Lk)（||表示串联）。另外，统计测试表明，RC4算法具有相关密钥产生相似输出的缺陷。为此，有人提出了RC4的一种变形算法RC4*，其算法过程ks=RC4*(key,Lk)为：第3章流密码算法——RC4*算法步骤1）初始化(Initialization)：j=0;i0=0;j0=0;Fori=0to255{s[i]=i;k[i]=key[imodLk];}2）密钥编排算法(KSA)Fori=0to255{j=(j+s[i]+k[i])mod256;i0=(i0+s[i])mod256;j0=(j0+s[j])mod256;tmp2=s[i];s[i]=s[j];s[j]=tmp2;}第3章流密码算法——RC4*算法步骤（续）3）伪随机数产生(PRNG*)算法：i=i0;j=j0;fortmp=0tolen-1{i=(i+C)mod256;j=(j+s[i])mod256;tmp2=s[i];s[i]=s[j];s[j]=tmp2;t=(s[i]+s[j])mod256;ks[tmp]=s[t];}第3章流密码算法——RC4*算法性能RC4*算法也是通过将密钥key周期扩展为256字节来产生伪随机数的，没有体现出密钥长度的区别，即RC4*(key,Lk)=RC4*(key||key,2*Lk)。统计测试表明，RC4*算法的伪随机性比RC4有所改善，不过也存在相关密钥产生相似输出的缺陷。另外，RC4*算法与RC4相比，速度明显下降。SNOW2(ISO/IEC18033-4:2006)St+15St+11St+5St+2Stα-1αR1SR2有限状态机kSNOW2SNOW2算法逻辑结构简洁，运算速度较快，已被采纳为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个64位字组成。分组密钥编排/Hash消息扩展AES：w[i]=S(w[i-1])⊕w[i-4]SHA1：w[t]=(w[t-3]⊕w[t-8]⊕w[t-14]⊕w[t-16])1SHA2：W[t]=F6(W[t–2])+W[t–7]+F5(W[t–15])+W[t–16]非线性循环移位寄存器(NRSR)...输出ai(m比特)计数加1⊕×ai+n-1(m比特)ai+1(imodm)2i+1ai+n={[(ai+n-1j)⊕ai]+1}mod2mai+n={[(b×ai+n-1)⊕(aij)]+1}mod2m非线性循环移位寄存器特点(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双核CPU、2GB内存、WinXP、C语言），NRSR速度为700MB/s。SNOW2采用的LFSR速度为630MB/s。SHA1和SHA256的消息扩展算法速度都小于400MB/s。对于A5算法采用的LFSR，就算同时并行32个LFSR，实测效率也很低。第3章作业1、请写出RC4*的算法过程，并说明RC4和RC4*算法的区别。2、请写出用分组密码算法构造流密码算法的两种模式步骤。Ｐ28，习题，3,6.