《第3章-第1讲 伪随机数发生器与单向散列函数.ppt》由会员分享，可在线阅读，更多相关《第3章-第1讲 伪随机数发生器与单向散列函数.ppt（30页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章第三章 安全业务及其实现方法安全业务及其实现方法第一讲第一讲 伪随机数发生器与单向散列函数伪随机数发生器与单向散列函数第一部分第一部分 伪随机序列发生器伪随机序列发生器随机数在网络安全算法中的应用（1）鉴别方案：序列号，临时密钥（2）会话密钥的产生：种子密钥的生成，会话密钥的生成（3）公钥密钥的产生密码算法上对随机数的要求？（4）用于生成序列密码（流密码）的密钥流一、基本概念一、基本概念 （1）它是满足伪随机性，这表明它通过了我们所能找到的所有 随机性统计检验。（2）它是不可预测的。即使给出产生序列的算法或硬件和所有以前产生的比特流的全部知识，也不可能通过计算来预测下一个随机比特应是什么
2、。（3）它不能可靠地重复产生。如果你用完全同样的输入对序列产生器操作两次（至少与人所能做到的最精确的一样），你将得到两个不相关的随机序列。密码学上安全的伪随机数生成器必须满足下面（密码学上安全的伪随机数生成器必须满足下面（1）（）（2）条件）条件 如果一个随机序列产生器具有下面的第三条性质，它就是真正随机真正随机的：二、伪随机数生成器二、伪随机数生成器1、线性反馈移位寄存器、线性反馈移位寄存器 一个反馈移位寄存器（FSR）由两个部分组成：移位寄存器和移位寄存器和反馈函数反馈函数（feed back function）。移位寄存器是一个位序列，其长度用位表示，每次需要一个位，移位寄存器中所有的位
3、右移一个位，新的最左端的位根据寄存器中的其它位计算得到，输出位一般是寄存器的最低有效位。移位寄存器的周期是指输出序列从开始到重复的长度 最简单的反馈移位寄存器是线性反馈移位寄存器线性反馈移位寄存器（LFSR），反馈函数反馈函数是寄存器中某些位的异或运算，即是上的一个多项式一个多项式，为了能达到最大周期（m序列序列）应该是上的一个本原多项式本原多项式 1、线性反馈移位寄存器、线性反馈移位寄存器例子：例子：3级线性反馈移位寄存器级线性反馈移位寄存器第0时刻 0 0 1 产生序列为：1001110和一个全零序列 优点优点：随机统计特性好，速度快缺点缺点：线性复杂度低，容易受攻击使用使用：作为其它生成
4、器的驱动，即生成种子密钥2 2、基于密码算法的随机数产生器、基于密码算法的随机数产生器ANSIX9.17伪随机数产生器EDEEDEEDEK1K2Vi+1ViRiDTi第第i阶段开始的种子阶段开始的种子第第i阶段的日期阶段的日期每个阶段使用的每个阶段使用的DES密钥密钥下一阶段的种子下一阶段的种子1iKiKiiKiKiDTEDEREDEVDTEDEVEDER=+输出的随机数输出的随机数3、基于大数因子分解的发生器、基于大数因子分解的发生器BBS产生器产生器密码强度最强，基于大整数分解困难性选择p,q,满足p=q=3 mod 4,n=pq。选随机数s，s和n互素 X0s2 mod n For i=
5、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。用途：消息认证、数字签名。散列函数要具有单向性，则必须满
6、足如下特性：散列函数要具有单向性，则必须满足如下特性：（1）有效性）有效性 给定M，很容易计算h，便于软硬件实现。（2）单向性）单向性 给定给定h h，根据根据H(M)=hH(M)=h反推反推M M很难很难。（3）弱抗碰撞性（弱攻击性）弱抗碰撞性（弱攻击性）给定M，找到另一M满足H(M)=H(M)很难。在在某某些些应应用用中中，单单向向散散列列函函数数还还需需要要满满足足抗抗碰碰撞撞(Collision)的的条条件件：要找到两个随机的消息M和M，使H(M)=H(M)满足很难。（抗强抗攻击性）（抗强抗攻击性）还要求还要求：能用于任何大小的消息；能用于任何大小的消息；能产生定长输出；能产生定长输出
7、；实现：实现：单向散列函数是建立在压缩函数之上的：单向散列函数是建立在压缩函数之上的：MD表示消息摘要(Message Digest),单向散列函数 输入：给定一任意长度的消息输出：长为m的散列值。压缩函数的输入：消息分组和前一分组的输出(对第一个函数需初始化向量IV)；输出：到该点的所有分组的散列，即分组Mi的散列为hi=f(Mi,hi1)循环：该散列值和下一轮的消息分组一起作为压缩函数下一轮的输入，最后一分组的散列就是整个消息的散列。(一一)MD5 算算 法法 1、算法、算法MD5对输入的任意长度消息产生对输入的任意长度消息产生128位散列值：位散列值：MD5算法五个步骤：算法五个步骤：1
8、)附加填充位2)附加长度3)初始化MD缓冲区4)按512位的分组处理5)输出 1)附加填充位附加填充位 填充消息，使其长度为一个比填充消息，使其长度为一个比512的倍数小于的倍数小于64位的数。位的数。幻灯片幻灯片 25填填充充方方法法：在在消消息息后后面面填填充充一一位位1，然然后后填填充充所所需需数数量量的的0。填填充充位位的位数从的位数从1512。2)附加长度附加长度 将原消息长度的将原消息长度的64位表示附加在填充后的消息后面。位表示附加在填充后的消息后面。当原消息长度大于当原消息长度大于264时，用消息长度时，用消息长度mod 264填充。填充。（5123216）3)初始化初始化MD
9、缓冲区缓冲区 初初始始化化用用于于计计算算消消息息摘摘要要的的128位位缓缓冲冲区区，由由四四个个32位寄存器位寄存器A、B、C、D表示：表示：A:01234567 B:89abcdef C:fedcba98 D:76543210(按低位字节在前的顺序存放按低位字节在前的顺序存放)4)按按512位的分组处理输入消息位的分组处理输入消息 MD5的主循环，包括四轮，每个循环都以当前的正在处理的512比特分组Yq和128比特缓冲值ABCD为输入，然后更新缓冲内容。压缩函数压缩函数四轮的操作类似，每轮四轮的操作类似，每轮16次：次：MD5的一次操作的一次操作 四轮操作的不同之处在于每轮使用的非线性函数
10、不同，分别为(其输入/输出均为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 15 do (第一轮)Temp=B+(A+F(B,C,D)+Mj+Tj)sj;A=D;B=temp;C=B;D=C;end for j=16
11、 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;end for 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
12、后，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要用
13、到两个缓冲区，均有五个要用到两个缓冲区，均有五个32位的寄存器。位的寄存器。第一个缓冲区：第一个缓冲区：A、B、C、D、E；第二个缓冲区：第二个缓冲区：H0、H1、H2、H3、H4。运算过程中还用到一个标记为运算过程中还用到一个标记为W0、W1、W79的的80个个32位字序列和一个位字序列和一个单字的缓冲区单字的缓冲区TEMP。在运算之前，初始化。在运算之前，初始化Hj：H0=0 x67452301 H1=0 xEFCDAB89H2=0 x98BADCFE H3=0 x10325476H4=0 xC3D2E1F0 3)按按512位的分组处理输入消息位的分组处理输入消息 SHA运算主循环包括四轮
14、，每轮运算主循环包括四轮，每轮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=0 x5A827999 (0t19)，Kt=0 x6ED9EBA1(20t39)Kt=0 x8F1BBCDC(40t59)，Kt=0 xCA62C1D6 (60
15、t79)SHA算法按如下步骤处理每个字块Mi：(1)把Mi分为16个字W0、W1、W15，其中，W0为最左边的字。(2)for t=16 to 79 do let Wt=(Wt3 Wt8 Wt14 Wt16)1 (3)Let A=H0，B=H1，C=H2，D=H3，E=H4 (4)for t=0 to 79 do TEMP=(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+E4)输出 在处理完Mn后，160位的消息摘要为H0、H1、H2、H3、H4级联的结果。SHA1与与MD5的比较的比较SHA1是在是在MD4的基础上开发的。的基础上开发的。表SHA-1与MD5的比较SHA-1MD5Hash值长度160bit128bit分组处理长512bit512bit步数80(420)64(416)最大消息长264bit不限非线性函数3(第2、4轮相同)4常数个数464