第3章-第1讲-伪随机数发生器与单向散列函数-优质课件

第三章安全业务及其实现方法第一讲伪随机数发生器与单向散列函数第一部分伪随机序列发生器随机数在网络安全算法中的应用（1）鉴别方案：序列号，临时密钥（2）会话密钥的产生：种子密钥的生成，会话密钥的生成（3）公钥密钥的产生密码算法上对随机数的要求？（4）用于生成序列密码（流密码）的密钥流一、基本概念（1）它是满足伪随机性，这表明它通过了我们所能找到的所有随机性统计检验。（2）它是不可预测的。即使给出产生序列的算法或硬件和所有以前产生的比特流的全部知识，也不可能通过计算来预测下一个随机比特应是什么。（3）它不能可靠地重复产生。如果你用完全同样的输入对序列产生器操作两次（至少与人所能做到的最精确的一样），你将得到两个不相关的随机序列。密码学上安全的伪随机数生成器必须满足下面（1）（2）条件如果一个随机序列产生器具有下面的第三条性质，它就是真正随机的：二、伪随机数生成器1、线性反馈移位寄存器一个反馈移位寄存器（FSR）由两个部分组成：移位寄存器和反馈函数（feedbackfunction）。移位寄存器是一个位序列，其长度用位表示，每次需要一个位，移位寄存器中所有的位右移一个位，新的最左端的位根据寄存器中的其它位计算得到，输出位一般是寄存器的最低有效位。移位寄存器的周期是指输出序列从开始到重复的长度最简单的反馈移位寄存器是线性反馈移位寄存器（LFSR），反馈函数是寄存器中某些位的异或运算，即是上的一个多项式，为了能达到最大周期（m序列）应该是上的一个本原多项式1、线性反馈移位寄存器例子：3级线性反馈移位寄存器第0时刻001产生序列为：1001110……和一个全零序列优点：随机统计特性好，速度快缺点：线性复杂度低，容易受攻击使用：作为其它生成器的驱动，即生成种子密钥2、基于密码算法的随机数产生器ANSIX9.17伪随机数产生器EDEEDEEDE＋＋K1K2Vi+1ViRiDTi第i阶段开始的种子第i阶段的日期每个阶段使用的DES密钥下一阶段的种子]][[]][[1iKiKiiKiKiDTEDEREDEVDTEDEVEDER==+输出的随机数3、基于大数因子分解的发生器——BBS产生器密码强度最强，基于大整数分解困难性选择p,q,满足p=q=3mod4,n=p×q。选随机数s，s和n互素X0＝s2modnFori=1to∞do{Xi=Xi-12modn;Bi=Ximod2}Bi为产生的随机数序列(1)该发生器有一特殊性质，为了得到第i位不用去迭代前面的i-1位（2）对左右都是不可预测的。速度比较慢。注意：不使用于序列密码加密，适用于对安全性要求高的应用程序，例如密钥产生。优点：缺点：ix2logn使用的更多低位，可以使用位加速方法：第二部分单向散列函数单向散列函数：HashFunction，哈希函数、杂凑函数将任意长度的消息M映射成一个固定长度散列值h的函数：h=H(M)，其中，h的长度为m。用途：消息认证、数字签名。散列函数要具有单向性，则必须满足如下特性：（1）有效性给定M，很容易计算h，便于软硬件实现。（2）单向性给定h，根据H(M)=h反推M很难。（3）弱抗碰撞性（弱攻击性）给定M，找到另一M’满足H(M)=H(M’)很难。在某些应用中，单向散列函数还需要满足抗碰撞(Collision)的条件：要找到两个随机的消息M和M’，使H(M)=H(M’)满足很难。（抗强抗攻击性）还要求：能用于任何大小的消息；能产生定长输出；实现：单向散列函数是建立在压缩函数之上的：消息分组1消息分组2压缩函数压缩函数IV……消息分组n填充位压缩函数函数值MD表示消息摘要(MessageDigest),单向散列函数输入：给定一任意长度的消息输出：长为m的散列值。压缩函数的输入：消息分组和前一分组的输出(对第一个函数需初始化向量IV)；输出：到该点的所有分组的散列，即分组Mi的散列为hi=f(Mi,hi−1)循环：该散列值和下一轮的消息分组一起作为压缩函数下一轮的输入，最后一分组的散列就是整个消息的散列。(一)MD5算法1、算法MD5对输入的任意长度消息产生128位散列值：L×512bit＝N×32bit消息Kbit100…0填充位消息长度(Kmod264)Y0512bit512HMD5Y1512HMD5CV1128128IV512bit……YL－1512HMD5128位消息摘要128512bitCVL－1MD5算法五个步骤：1)附加填充位2)附加长度3)初始化MD缓冲区4)按512位的分组处理5)输出1)附加填充位填充消息，使其长度为一个比512的倍数小于64位的数。幻灯片25填充方法：在消息后面填充一位1，然后填充所需数量的0。填充位的位数从1～512。2)附加长度将原消息长度的64位表示附加在填充后的消息后面。当原消息长度大于264时，用消息长度mod264填充。（512＝32×16）3)初始化MD缓冲区初始化用于计算消息摘要的128位缓冲区，由四个32位寄存器A、B、C、D表示：A:01234567B:89abcdefC:fedcba98D:76543210(按低位字节在前的顺序存放)4)按512位的分组处理输入消息MD5的主循环，包括四轮，每个循环都以当前的正在处理的512比特分组Yq和128比特缓冲值ABCD为输入，然后更新缓冲内容。压缩函数四轮的操作类似，每轮16次：c＋＋＋s＋非线性函数bdaMjT[i]cbdaMD5的一次操作四轮操作的不同之处在于每轮使用的非线性函数不同，分别为(其输入/输出均为32位字)：F(X,Y,Z)=(X^Y)ˇ((～X)^Z)G(X,Y,Z)=(X^Z)ˇ(Y^(～Z))H(X,Y,Z)=X＋Y＋ZI(X,Y,Z)=Y＋(Xˇ(～Z))其中，^表示按位与；ˇ表示按位或；～表示按位反；＋表示按位异或。MD5对每512bit按照下列算法进行处理(1)把Yi分为16个32比特分组M0、M1、…、M15，其中，M0为最左边的32bit。(2) LetAA=A，BB=B，CC=C，DD=D(3) fori=0to15do(第一轮)Temp=B+((A+F(B,C,D)+M[j]+T[j])s[j];A=D;B=temp;C=B;D=C;end forj=16to31do（第二轮）Temp=B+((A+G(B,C,D)+M[(1+(j-16)*5)%16]+T[j])s[j];A=D;B=temp;C=B;D=C;End forj=32to47do（第三轮）Temp=B+((A+H(B,C,D)+M[(5+(i-32))*3%16]+T[j])s[j];A=D;B=temp;C=B;D=C;end forj=48to63do（第四轮）Temp=B+((A+I(B,C,D)+M[(0+(i-48))*7%16]+T[j])s[j];A=D;B=temp;C=B;D=C;end(4) LetA=A+AA，B=B+BB，C=C+CC，D=D+DD5）输出在处理完Yn后，128位的消息摘要为A、B、C、D级联的结果。（二）安全散列函数(SHA)1算法SHA是美国NIST和NSA共同设计的安全散列算法(SecureHashAlgorithm)，用于数字签名标准DSS(DigitalSignatureStandard)。修改版SHA–1于1995年作为美国联邦信息处理标准公告发布。SHA–1的输入：度小于264位的消息输出：160位的消息摘要。L×512bit＝N×32bit消息Kbit100…0填充位消息长度(Kmod264)Y0512bit512HSHAY1512HSHACV1160160IV512bit……YL－1512HSHA160位消息摘要160512bitCVL－1图SHA–1算法1)填充消息将消息填充为512位的整数倍，填充方法和MD5完全相同。幻灯片162)初始化缓冲区SHA要用到两个缓冲区，均有五个32位的寄存器。第一个缓冲区：A、B、C、D、E；第二个缓冲区：H0、H1、H2、H3、H4。运算过程中还用到一个标记为W0、W1、…、W79的80个32位字序列和一个单字的缓冲区TEMP。在运算之前，初始化{Hj}：H0=0x67452301H1=0xEFCDAB89H2=0x98BADCFEH3=0x10325476H4=0xC3D2E1F03)按512位的分组处理输入消息SHA运算主循环包括四轮，每轮20次操作。逻辑函数序列f0、f1、…、f79，每个逻辑函数的输入为三个32位字，输出为一个32位字：ft(B,C,D)=(B^C)ˇ(~B^D)(0≤t≤19)ft(B,C,D)=B＋C＋D(20≤t≤39)ft(B,C,D)=(B^C)ˇ(B^D)ˇ(C^D)(40≤t≤59)ft(B,C,D)=B＋C＋D(60≤t≤79)还用到常数字序列K0、K1、…、K79：Kt=0x5A827999(0≤t≤19)，Kt=0x6ED9EBA1(20≤t≤39)Kt=0x8F1BBCDC(40≤t≤59)，Kt=0xCA62C1D6(60≤t≤79)SHA算法按如下步骤处理每个字块Mi：(1)把Mi分为16个字W0、W1、…、W15，其中，W0为最左边的字。(2) fort=16to79doletWt=(Wt−3Wt−8Wt−14Wt−16)1(3) LetA=H0，B=H1，C=H2，D=H3，E=H4(4) fort=0to79doTEMP=(A5)+ft(B,C,D)+E+Wt+Kt;E=D;D=C;C=(B30);B=A;A=TEMP;(5) LetH0=H0+A,H1=H1+B,H2=H2+C,H3=H3+D,H4=H4+E4)输出在处理完Mn后，160位的消息摘要为H0、H1、H2、H3、H4级联的结果。SHA–1与MD5的比较SHA–1是在MD4的基础上开发的。表SHA-1与MD5的比较SHA-1MD5Hash值长度160bit128bit分组处理长512bit512bit步数80(4×20)64(4×16)最大消息长≤264bit不限非线性函数3(第2、4轮相同)4常数个数464