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

第三章 安全业务及其实现方法第一讲 伪随机数发生器与单向散列函数第一部分 伪随机序列发生器随机数在网络安全算法中的应用（ 1）鉴别方案：序列号，临时密钥（ 2）会话密钥的产生：种子密钥的生成，会话密钥的生成（ 3）公钥密钥的产生密码算法上对随机数的要求？（ 4）用于生成序列密码（流密码）的密钥流一、基本概念（ 1）它是满足伪随机性，这表明它通过了我们所能找到的所有 随机性统计检验。（ 2）它是不可预测的。即使给出产生序列的算法或硬件和所有以前产生的比特流的全部知识，也不可能通过计算来预测下一个随机比特应是什么。（ 3）它不能可靠地重复产生。如果你用完全同样的输入对序列产生器操作两次（至少与人所能做到的最精确的一样），你将得到两个不相关的随机序列。 密码学上安全的伪随机数生成器必须满足下面（ 1）（ 2）条件如果一个随机序列产生器具有下面的第三条性质，它就是 真正随机 的：二、伪随机数生成器1、线性反馈移位寄存器一个反馈移位寄存器（ FSR）由两个部分组成： 移位寄存器和反馈函数 （ feed back function）。移位寄存器是一个位序列，其长度用位表示，每次需要一个位，移位寄存器中所有的位右移一个位，新的最左端的位根据寄存器中的其它位计算得到，输出位一般是寄存器的最低有效位。移位寄存器的周期是指输出序列从开始到重复的长度 最简单的反馈移位寄存器是 线性反馈移位寄存器 （LFSR）， 反馈函数 是寄存器中某些位的异或运算，即是上的 一个多项式 ，为了能达到最大周期（ m序列 ）应该是上的一个 本原多项式 1、线性反馈移位寄存器例子： 3级线性反馈移位寄存器第 0时刻 0 0 1 产生序列为： 1001110 和一个全零序列 优点 ：随机统计特性好，速度快缺点 ：线性复杂度低，容易受攻击使用 ：作为其它生成器的驱动，即生成种子密钥2、基于密码算法的随机数产生器ANSIX9.17伪随机数产生器EDEEDEEDEK1K2Vi+1ViRiDTi第 i阶段开始的种子第 i阶段的日期每个阶段使用的 DES密钥下一阶段的种子1 iKiKiiKiKiDTEDEREDEVDTEDEVEDER=+输出的随机数3、基于大数因子分解的发生器 BBS 产生器密码强度最强，基于大整数分解困难性选择 p,q,满足 p=q=3 mod 4, n=pq。选随机数 s， s和 n互素X0 s2 mod nFor i=1 to do Xi=Xi-12 mod n;Bi=Xi mod 2Bi为产生的随机数序列(1)该发生器有一特殊性质，为了得到第 i位不用去迭代前面的 i-1位 （ 2）对左右都是不可预测的。速度比较慢。注意 ：不使用于序列密码加密，适用于对安全性要求高的应用 程序，例如密钥产生 。优点：缺点：使用 的更多低位，可以使用 位 加速方法 ：第二部分 单向散列函数单向散列函数： Hash Function，哈希函数、杂凑函数将任意长度的消息 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) 满足很难。（抗强抗攻击性）还要求 ：能用于任何大小的消息；能产生定长输出；实现：单向散列函数是建立在压缩函数之上的：MD表示消息摘要 (Message Digest),单向散列函数输入： 给定一任意长度的消息输出： 长为 m的散列值。压缩函数的输入：消息分组和前一分组的输出 (对第一个函数需初始化向量 IV)；输出： 到该点的所有分组的散列，即分组 Mi的散列为hi=f (Mi, hi1)循环： 该散列值和下一轮的消息分组一起作为压缩函数下一轮的输入，最后一分组的散列就是整个消息的散列。(一 ) MD5 算 法 1、算法MD5对输入的任意长度消息产生 128位散列值：MD5算法五个步骤：1) 附加填充位2) 附加长度3) 初始化 MD缓冲区4) 按 512位的分组处理5) 输出1) 附加填充位填充消息，使其长度为一个比 512的倍数小于 64位的数。 幻灯片 25填充方法：在消息后面填充一位 1，然后填充所需数量的 0。填充位的位数从 1 512。2) 附加长度将原消息长度的 64位表示附加在填充后的消息后面。当原消息长度大于 264时，用消息长度 mod 264填充。（ 512 3216）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为输入，然后更新缓冲内容。 压缩函数四轮的操作类似，每轮 16次：MD5的一次操作四轮操作的不同之处在于每轮使用的非线性函数不同，分别为 (其输入 /输出均为 32位字 )：F(X,Y,Z) = (XY) ( X) Z)G(X,Y,Z) = (XZ)(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) Let AA =A， BB =B， CC =C， DD =D(3) for i =0 to 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;Endfor 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 =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 + DD5）输出在处理完 Yn后， 128位的消息摘要为 A、 B、 C、 D级联的结果。（二）安全散列函数 (SHA) 1 算法SHA是美国 NIST和 NSA共同设计的安全散列算法(Secure Hash Algorithm)， 用于数字签名标准 DSS(Digital Signature Standard)。修改版 SHA1于 1995年作为美国联邦信息处理标准公告发布。SHA1的输入： 度小于 264位的消息输出：160位的消息摘要。图 SHA1算法 1) 填充消息将消息填充为 512位的整数倍，填充方法和 MD5完全相同。 幻灯片 162) 初始化缓冲区SHA要用到两个缓冲区，均有五个 32位的寄存器。第一个缓冲区： A、 B、 C、 D、 E；第二个缓冲区： H0、 H1、 H2、 H3、 H4。运算过程中还用到一个标记为 W0、 W1、 、 W79的 80个 32位字序列和一个单字的缓冲区 TEMP。在运算之前，初始化 Hj： H0 = 0x67452301 H1 = 0xEFCDAB89H2 = 0x98BADCFE H3 = 0x10325476H4 = 0xC3D2E1F0 3) 按 512位的分组处理输入消息SHA运算主循环包括四轮，每轮 20次操作。逻辑函数序列 f0、 f1、 、 f79，每个逻辑函数的输入为三个 32位字，输出为一个 32位字：ft (B,C,D) = (BC) (BD) (0t19)ft (B,C,D) = B C D (20t39)ft (B,C,D) = (BC) (BD) (CD) (40t59)ft (B,C,D) = B C D (60t79)还用到常数字序列 K0、 K1、 、 K79：Kt = 0x5A827999 (0t19)， Kt = 0x6ED9EBA1 (20t39)Kt = 0x8F1BBCDC (40t59)， 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