《第3章_单向散列函数.》由会员分享，可在线阅读，更多相关《第3章_单向散列函数.（51页珍藏版）》请在金锄头文库上搜索。
1、Network and Information Security,第3章 单向散列函数,3.1 单向散列函数概述 3.2 MD5算法 3.3 SHA-1算法 3.4 消息认证码(MAC) 3.5 对单向散列函数的攻击,Network and Information Security,随着以Internet为基础的电子商务技术的迅猛发展,以公钥密码、数字签名等为代表的加密安全技术已成为研究的热点。 单向散列函数是数字签名中的一个关键环节,可以大大缩短签名时间并提高安全性,另外在消息完整性检测,内存的散布分配,软件系统中帐号口令的安全存储单向散列函数也有重要应用。,Network and Info
2、rmation Security,3.1 单向散列函数概述,所谓的单向散列函数(Hash Function，又称哈希函数、杂凑函数)，是将任意长度的消息M映射成一个固定长度散列值h(设长度为m)的函数H： h=H(M) 散列函数要具有单向性，则必须满足如下特性： 给定M，很容易计算h。 给定h，根据H(M)=h反推M很难。 给定M，要找到另一消息M并满足H(M)=H(M)很难。 在某些应用中，单向散列函数还需要满足抗碰撞(Collision)的条件：要找到两个随机的消息M和M，使H(M)=H(M)很难。,Network and Information Security,Hash函数的良好性质,
3、（ 1 ）广泛的应用性 Hash函数能用于任何大小的消息。 （ 2 ） 定长输出 将消息集合中的任意长度的消息映射为长度为的消息摘要。 （ 3 ） 实现性 对Hash函数的一个非常重要的要求是简单易实现性。 （ 4 ） 单向性质 要求Hash函数是单向函数。给定h值，求信息M （是一对多的关系） ，只有通过枚举，在现有的计算环境下是不可行的。,Network and Information Security,（ 5 ） 抗弱对抗性 确定与x有相同位数的y,使H(x)=H(y), 在现有的计算环境下是不可行的。 （ 6 ） 抗强对抗性 找到两个不同位数信息x,y,使H(x)=H(y)，在现有的计
4、算环境下是不可行的。 注：以上两种，哪一种更容易找？ （ 7 ） 独立性 哈希函数值“不依赖输入信息”，从某种程度上说是由算法决定的。 （ 8 ）抗近冲突 Hash函数满足独立性，输入信息某一位的变化，应该引起平均一半的输出位的变化。 （9 ） 安全性 在很广泛的条件下, Hash值()的分布是均匀分布的.,Network and Information Security,散列函数工作模式,图3-1 单向散列函数工作模式,Network and Information Security,3.2.1 算法 MD表示消息摘要(Message Digest)。MD5是MD4的改进版，该算法对输入的任
5、意长度消息产生128位散列值(或消息摘要) 。MD5算法可用图3-2表示。,3.2 MD5 算 法,Network and Information Security,图3-2 MD5算法,1) 附加填充位,2) 附加长度64,3) 初始化MD缓冲区,5) 输出,4) 按512位的分组处理输入消息,Network and Information Security,由上图可知，MD5算法包括以下五个步骤。 1) 附加填充位 首先填充消息，使其长度为一个比512的倍数小64位的数。填充方法：在消息后面填充一位1，然后填充所需数量的0。填充位的位数从1512。 填充消息长度=512-(k+64) mo
6、d 512 2) 附加长度 将原消息长度的64位表示附加在填充后的消息后面。当原消息长度大于264时，用消息长度mod 264填充。这时，总长度恰好是512的整数倍。令M0 1N1为填充后消息的各个字(每字为32位)，N是16的倍数。,Network and Information Security,3) 初始化MD缓冲区 初始化用于计算消息摘要的128位缓冲区。这个缓冲区由四个32位寄存器A、B、C、D表示。寄存器的初始化值为(按低位字节在前的顺序存放)： A: 01 23 45 67 B: 89 ab cd ef C: fe dc ba 98 D: 76 54 32 10 4) 按512位
7、的分组处理输入消息 这一步为MD5的主循环，包括四轮，如图3-3所示。每个循环都以当前的正在处理的512比特分组Yq和128比特缓冲值ABCD为输入，然后更新缓冲内容。,Network and Information Security,图3-3 单个512比特分组的MD5主循环处理,Network and Information Security,图3-3中，四轮的操作类似，每一轮进行16次操作。各轮的操作过程如图3-4所示。,图3-4 MD5某一轮的1次执行过程,j:015, i:164(共四轮， 每一轮用的都不同),Network and Information Security,四轮操作
8、的不同之处在于每轮使用的非线性函数不同，在第一轮操作之前，首先把A、B、C、D复制到另外的变量a、b、c、d中。这四个非线性函数分别为(其输入/输出均为32位字)： F(X,Y,Z) = (X Y) (X) Z) G(X,Y,Z) = (X Z) (Y (Z) H(X,Y,Z) = X Y Z I(X,Y,Z) = Y (X (Z) 其中， 表示按位与； 表示按位或；表示按位反； 表示按位异或。,Network and Information Security,此外，由图3-4可知，这一步中还用到了一个有64个元素的表T164，Ti=232abs(sin(i)，i的单位为弧度。 根据以上描述，
9、将这一步骤的处理过程归纳如下： for i = 0 to N/161 do /* 每次循环处理16个字，即512字节的消息分组*/ /*把A存为AA，B存为BB，C存为CC，D存为DD*/ AA = A BB = B CC = C DD = D,Network and Information Security,/* 第一轮*/ /* 令abcd k s i表示操作 b = b + (a + F(b,c,d) + Mk + Ti) s) 其中，Ys表示Y循环左移s位*/ /* 完成下列16个操作*/ ABCD 0 7 1 DABC 1 12 2 CDAB 2 17 3 BCDA 3 22 4 A
10、BCD 4 7 5 DABC 5 12 6 CDAB 6 17 7 BCDA 7 22 8 ABCD 8 7 9 DABC 9 12 10 CDAB 10 17 11 BCDA 11 22 12 ABCD 12 7 13 DABC 13 12 14 CDAB 14 17 15 BCDA 15 22 16,Network and Information Security,/* 第二轮*/ /*令abcd k s i表示操作 b = b + (a + G(b,c,d) + Mk + Ti) s)*/ /*完成下列16个操作*/ ABCD 1 5 17 DABC 6 9 18 CDAB 11 14
11、19 BCDA 0 20 20 ABCD 5 5 21 DABC 10 9 22 CDAB 15 14 23 BCDA 4 20 24 ABCD 9 5 25 DABC 14 9 26 CDAB 3 14 27 BCDA 8 20 28 ABCD 13 5 29 DABC 2 9 30 CDAB 7 14 31 BCDA 12 20 32,Network and Information Security,/*第三轮*/ /*令abcd k s t表示操作 b= b + (a + H(b,c,d) + Mk + Ti) s)*/ /*完成以下16个操作*/ ABCD 5 4 33 DABC 8
12、11 34 CDAB 11 16 35 BCDA 14 23 36 ABCD 1 4 37 DABC 4 11 38 CDAB 7 16 39 BCDA 10 23 40 ABCD 13 4 41 DABC 0 11 42 CDAB 3 16 43 BCDA 6 23 44 ABCD 9 4 45 DABC 12 11 46 CDAB 15 16 47 BCDA 2 23 48,Network and Information Security,/*第四轮*/ /*令abcd k s t表示操作 b = b + (a + I(b,c,d) +Mk + Ti) s) */ /*完成以下16个操作*
13、/ ABCD 0 6 49 DABC 7 10 50 CDAB 14 15 51 BCDA 5 21 52 ABCD 12 6 53 DABC 3 10 54 CDAB 10 15 55 BCDA 1 21 56 ABCD 8 6 57 DABC 15 10 58 CDAB 6 15 59 BCDA 13 21 60 ABCD 4 6 61 DABC 11 10 62 CDAB 2 15 63 BCDA 9 21 64 A = A + AA B = B + BB C = C + CC D = D + DD end /*i循环*/,Network and Information Security
14、,5) 输出 由A、B、C、D四个寄存器的输出按低位字节在前的顺序(即以A的低字节开始、D的高字节结束)得到128位的消息摘要。 以上就是对MD5算法的描述。MD5算法的运算均为基本运算，比较容易实现且速度很快。,Network and Information Security,3.2.2 举例,我们以求字符串“abc”的MD5散列值为例来说明上面描述的过程。“abc”的二进制表示为01100001 01100010 01100011。 1填充消息 消息长24，先填充1位1，然后填充423位0，再用消息长24，即0x00000000 00000018填充，则： M0=61626380 M1=0
15、0000000 M2=00000000 M3=00000000 M4=00000000 M5=00000000 M6=00000000 M7=00000000 M8=00000000 M9=00000000 M10=00000000 M11=00000000 M12=00000000 M13=00000000 M14=00000000 M15=00000018 2初始化 A:01 23 45 67 B:89 ab cd ef C:fe dc ba 98 D:76 54 32 10 3主循环 利用3.2.1节中描述的过程对字块1（本例只有一个字块）进行处理。变量a、b、c、d每一次计算后的中间值不再详细列出。 4输出 消息摘要=90015098 3cd24fb0 d6963f7d 28e17f72,Network and Information Security,3.3 安全散列函数(SHA-1),3.3.1 算法 SHA是美国NIST和NSA共同设计的安全散列算法(Secure Hash Algorithm)，用于数字签名标准DSS(D
