《第3章-第1讲伪随机数发生器与单向散列函数》由会员分享，可在线阅读，更多相关《第3章-第1讲伪随机数发生器与单向散列函数（30页珍藏版）》请在金锄头文库上搜索。
1、第三章 安全业务及其实现方法,第一讲 伪随机数发生器与单向散列函数,第一部分 伪随机序列发生器,随机数在网络安全算法中的应用,（1）鉴别方案：序列号，临时密钥,（2）会话密钥的产生：种子密钥的生成，会话密钥的生成,（3）公钥密钥的产生,密码算法上对随机数的要求？,（4）用于生成序列密码（流密码）的密钥流,一、基本概念,（1）它是满足伪随机性，这表明它通过了我们所能找到的所有 随机性统计检验。,（2）它是不可预测的。即使给出产生序列的算法或硬件和所有以前产生的比特流的全部知识，也不可能通过计算来预测下一个随机比特应是什么。,（3）它不能可靠地重复产生。如果你用完全同样的输入对序列产生器操作两次（
2、至少与人所能做到的最精确的一样），你将得到两个不相关的随机序列。,密码学上安全的伪随机数生成器必须满足下面（1）（2）条件,如果一个随机序列产生器具有下面的第三条性质，它就是真正随机的：,二、伪随机数生成器,1、线性反馈移位寄存器,一个反馈移位寄存器（FSR）由两个部分组成：移位寄存器和反馈函数（feed back function）。移位寄存器是一个位序列，其长度用位表示，每次需要一个位，移位寄存器中所有的位右移一个位，新的最左端的位根据寄存器中的其它位计算得到，输出位一般是寄存器的最低有效位。移位寄存器的周期是指输出序列从开始到重复的长度,最简单的反馈移位寄存器是线性反馈移位寄存器（LFS
3、R），反馈函数是寄存器中某些位的异或运算，即是上的一个多项式，为了能达到最大周期（m序列）应该是上的一个本原多项式,1、线性反馈移位寄存器,例子：3级线性反馈移位寄存器,第0时刻 0 0 1,产生序列为：1001110和一个全零序列,优点：随机统计特性好，速度快 缺点：线性复杂度低，容易受攻击,使用：作为其它生成器的驱动，即生成种子密钥,2、基于密码算法的随机数产生器,ANSIX9.17伪随机数产生器,EDE,EDE,EDE,K1K2,Vi+1,Vi,Ri,DTi,第i阶段开始的种子,第i阶段的日期,每个阶段使用的DES密钥,下一阶段的种子,输出的随机数,3、基于大数因子分解的发生器BBS产生
4、器,密码强度最强，基于大整数分解困难性,选择p,q,满足p=q=3 mod 4, n=pq。选随机数s，s和n互素X0s2 mod nFor i=1 to do Xi=Xi-12 mod n;Bi=Xi mod 2 Bi为产生的随机数序列,(1)该发生器有一特殊性质，为了得到第i位不用去迭代前面的i-1位,（2）对左右都是不可预测的。,速度比较慢。,注意：不使用于序列密码加密，适用于对安全性要求高的应用 程序，例如密钥产生 。,优点：,缺点：,使用,的更多低位，可以使用,位,加速方法 ：,第二部分 单向散列函数,单向散列函数：Hash Function，哈希函数、杂凑函数将任意长度的消息M映射
5、成一个固定长度散列值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)满足很难。（抗强抗攻击性）,还要求：能用于任何大小的消息；能产生定长输出； 实现：单向散列函数是建立在压缩函数之上的：,MD表示消息摘要(Message Di
6、gest),单向散列函数输入： 给定一任意长度的消息输出： 长为m的散列值。 压缩函数的输入：消息分组和前一分组的输出(对第一个函数需初始化向量IV)；输出： 到该点的所有分组的散列，即分组Mi的散列为 hi=f (Mi, hi1) 循环： 该散列值和下一轮的消息分组一起作为压缩函数下一轮的输入，最后一分组的散列就是整个消息的散列。,(一) MD5 算 法,1、算法MD5对输入的任意长度消息产生128位散列值：,MD5算法五个步骤：1) 附加填充位2) 附加长度3) 初始化MD缓冲区4) 按512位的分组处理5) 输出,1) 附加填充位填充消息，使其长度为一个比512的倍数小于64位的数。幻灯
7、片 25填充方法：在消息后面填充一位1，然后填充所需数量的0。填充位的位数从1512。2) 附加长度将原消息长度的64位表示附加在填充后的消息后面。当原消息长度大于264时，用消息长度mod 264填充。（5123216）,3) 初始化MD缓冲区初始化用于计算消息摘要的128位缓冲区，由四个32位寄存器A、B、C、D表示：A: 01 23 45 67B: 89 ab cd efC: fe dc ba 98D: 76 54 32 10(按低位字节在前的顺序存放),4) 按512位的分组处理输入消息MD5的主循环，包括四轮，每个循环都以当前的正在处理的512比特分组Yq和128比特缓冲值ABCD为
8、输入，然后更新缓冲内容。,压缩函数,四轮的操作类似，每轮16次：,MD5的一次操作,四轮操作的不同之处在于每轮使用的非线性函数不同，分别为(其输入/输出均为32位字)：F(X,Y,Z) = (XY) (X) Z)G(X,Y,Z) = (XZ)(Y (Z)H(X,Y,Z) = XYZI(X,Y,Z) = Y(X (Z)其中，表示按位与；表示按位或；表示按位反；表示按位异或。,MD5对每512bit按照下列算法进行处理,(1) 把Yi分为16个32比特分组M0、M1、M15，其中，M0为最左边的32bit。(2) Let AA =A，BB =B，CC =C，DD =D(3) for i =0 to
9、 15 do (第一轮)Temp=B + (A + F(B,C,D) + Mj + Tj) sj ;A =D; B =temp; C =B; D = C;endfor j =16 to 31 do （第二轮）Temp= B + (A + G(B,C,D) + M(1+(j-16)*5)%16 + Tj) sj ;A =D; B =temp; C =B; D = C;End,for j =32 to 47 do （第三轮）Temp= B + (A + H(B,C,D) + M(5+(i-32)*3%16 + Tj) sj ;A =D; B =temp; C =B; D = C;endfor j
10、=48 to 63 do （第四轮）Temp= B + (A + I(B,C,D) + M(0+(i-48)*7%16 + Tj) sj ;A =D; B =temp; C =B; D = C;end,(4) Let A = A + AA ，B = B + BB，C = C + CC，D = D + DD,5）输出在处理完Yn后，128位的消息摘要为A、B、C、D级联的结果。,（二）安全散列函数(SHA),1 算法SHA是美国NIST和NSA共同设计的安全散列算法(Secure Hash Algorithm)，用于数字签名标准DSS(Digital Signature Standard)。修改
11、版SHA1于1995年作为美国联邦信息处理标准公告发布。SHA1的输入： 度小于264位的消息输出：160位的消息摘要。,图 SHA1算法,1) 填充消息将消息填充为512位的整数倍，填充方法和MD5完全相同。幻灯片 16 2) 初始化缓冲区SHA要用到两个缓冲区，均有五个32位的寄存器。第一个缓冲区：A、B、C、D、E；第二个缓冲区：H0、H1、H2、H3、H4。 运算过程中还用到一个标记为W0、W1、W79的80个32位字序列和一个单字的缓冲区TEMP。在运算之前，初始化Hj：,H0 = 0x67452301 H1 = 0xEFCDAB89 H2 = 0x98BADCFE H3 = 0x1
12、0325476 H4 = 0xC3D2E1F0,3) 按512位的分组处理输入消息SHA运算主循环包括四轮，每轮20次操作。逻辑函数序列f0、f1、f79，每个逻辑函数的输入为三个32位字，输出为一个32位字：ft (B,C,D) = (BC) (BD) (0t19)ft (B,C,D) = BCD (20t39)ft (B,C,D) = (BC) (BD) (CD) (40t59)ft (B,C,D) = BCD (60t79)还用到常数字序列K0、K1、K79：Kt = 0x5A827999 (0t19)， Kt = 0x6ED9EBA1 (20t39)Kt = 0x8F1BBCDC (4
13、0t59)，Kt = 0xCA62C1D6 (60t79),SHA算法按如下步骤处理每个字块Mi：(1) 把Mi分为16个字W0、W1、W15，其中，W0为最左边的字。(2) for t =16 to 79 dolet Wt =(Wt3 Wt8 Wt14 Wt16)1(3) Let A =H0，B =H1，C =H2，D =H3，E =H4(4) for t =0 to 79 doTEMP = (A5)+ft (B, C, D)+E +Wt +Kt ;E =D; D =C; C =(B30); B = A; A = TEMP;(5) Let H0 =H0 +A, H1 =H1 +B, H2 =H2 +C, H3 =H3 +D, H4 =H4 +E,4) 输出在处理完Mn后，160位的消息摘要为H0、H1、H2、H3、H4级联的结果。,SHA1与MD5的比较 SHA1是在MD4的基础上开发的。,表 SHA-1与MD5的比较,
