《应用密码学》课件第6章 Hash函数(1).pptx

1、12024/3/192024/3/1912024/3/172024/3/171-通信系统典型攻击通信系统典型攻击通信系统典型攻击通信系统典型攻击22024/3/192024/3/1922024/3/172024/3/17222024/3/192024/3/1922024/3/172024/3/1722024/3/192024/3/192 2知识点：认证与认证系统认证与认证系统散列算法概述散列算法概述Hash散列算法散列算法散列算法的攻击现状散列算法的攻击现状消息认证消息认证第第6章章 认证理论与技术认证理论与技术Hash函数函数(1)32024/3/192024/3/1932024/3/172

2、024/3/17332024/3/192024/3/1932024/3/172024/3/1732024/3/192024/3/193 36.1 认证与认证系统认证与认证系统 认认证证（Authentication），又称为鉴别，认证往往是许多应用系统中安全保护的第一道设防(进入系统，先输密码)，也是防止主动攻击的重要技术。简单地说，认证是一个实体向另外一个实体证明某种声称的属性。因此，可以看出认证至少涉及到两个独立的通信实体。而认证参数一般有多种形式，如口令、标示符、密钥、信物、智能卡、指纹、视网纹等。目前广泛应用的还是目前广泛应用的还是基于密码的认证技术基于密码的认证技术，主要认证有身份认

3、证、站点认证、，主要认证有身份认证、站点认证、报文认证等。报文认证等。随着Hash函数和数字签名的发现，人们意识到保密和认证同时是信息系统安保密和认证同时是信息系统安全的两个方面全的两个方面，但它们是两个不同属性的问题，认证不能自动提供保密性，而保密性也不能自然提供认证功能。42024/3/192024/3/1942024/3/172024/3/17442024/3/192024/3/1942024/3/172024/3/174认证认证主要目的主要目的用以确保消息发送者和接收者的真实性以及消息的完整性。认证通常可分为三个子概念：消息认证（或者数据源认证）、实体认证和认证密钥建立。消息认证消息认

4、证主要涉及验证消息的某个声称属性；实体实体认证认证更多涉及验证消息发送者声称的身份；认证认证密钥密钥建立建立主要是致力于产生一条安全信道，用于后继的应用层的安全通信会话。52024/3/192024/3/1952024/3/172024/3/17552024/3/192024/3/1952024/3/172024/3/1752024/3/192024/3/195 5 认证系统原理（系统模型）认证系统原理（系统模型）认证系统原理（系统模型）认证系统原理（系统模型）认证系统模型：认证系统模型：认证系统模型：认证系统模型：由认证编码器、密钥源和认证译码器由认证编码器、密钥源和认证译码器由认证编码器、

5、密钥源和认证译码器由认证编码器、密钥源和认证译码器三部分组成。认证编码器对认证编码器对认证编码器对认证编码器对发送的消息产生认证码发送的消息产生认证码发送的消息产生认证码发送的消息产生认证码。密钥源通常预先协商、通过安全信道分配密钥密钥源通常预先协商、通过安全信道分配密钥。认证译码器认证译码器对接收到的消息进行验证对接收到的消息进行验证。消息认证过程消息认证过程消息认证过程消息认证过程:首先，首先，首先，首先，由发送方的认证编码器对发出的消息生成认证信息，然后，然后，然后，然后，将消息和认证信息一起通过公开信道发送给接收方；接收方收到消息和认证信息后，接收方收到消息和认证信息后，由认证译码器验

6、证消息的合法性，如果消息合法便接受，否则将其丢弃由认证译码器验证消息的合法性，如果消息合法便接受，否则将其丢弃。62024/3/192024/3/1962024/3/172024/3/17662024/3/192024/3/1962024/3/172024/3/1762024/3/192024/3/196 6认证的分类 根据产生认证消息不同方式，认证分为下面三类：根据产生认证消息不同方式，认证分为下面三类：（1）消息认证：用消息的密文本身充当认证信息；）消息认证：用消息的密文本身充当认证信息；（2）消息认证码）消息认证码MAC(MessageAuthenticationCode)：由以消息和密

7、钥作为由以消息和密钥作为输入的公开函数产生的认证信息。输入的公开函数产生的认证信息。（3）散列值：由以消息作为唯一输入的散列函数产生的认证信息（无需密钥）散列值：由以消息作为唯一输入的散列函数产生的认证信息（无需密钥），也称，也称“消息摘要消息摘要”或或“报文摘要报文摘要”。72024/3/192024/3/1972024/3/172024/3/17772024/3/192024/3/1972024/3/172024/3/1772024/3/192024/3/197 76.2 散列算法概述散列算法概述 散列函数是一公开函数，通常记为散列函数是一公开函数，通常记为H，用于将任意长的消息用于将任意

8、长的消息M映射为较短的、映射为较短的、固定长度的一个值作为认证符固定长度的一个值作为认证符，记为，记为H(M)，经常称函数值经常称函数值H(M)为散列值、哈希值、为散列值、哈希值、杂凑值、杂凑码或消息摘要、数字指纹。杂凑值、杂凑码或消息摘要、数字指纹。从密码角度看，散列函数也可以看作是一种单向密码体制，即它从一个明文从密码角度看，散列函数也可以看作是一种单向密码体制，即它从一个明文到密文是不可逆映射，只有加密过程，不能解密。到密文是不可逆映射，只有加密过程，不能解密。散列值是消息中所有比特的函数，因此提供了一种错误检测能力，即改变消散列值是消息中所有比特的函数，因此提供了一种错误检测能力，即改

9、变消息中任何一个比特或几个比特都会使散列值发生改变。息中任何一个比特或几个比特都会使散列值发生改变。在密码学和数据安全技术中，散列函数是实现有效、安全可靠数字签字和认证在密码学和数据安全技术中，散列函数是实现有效、安全可靠数字签字和认证的重要工具的重要工具，是安全认证协议中的重要模块。，是安全认证协议中的重要模块。82024/3/192024/3/1982024/3/172024/3/1786.2.1 6.2.1 散列算法的概念及结构散列算法的概念及结构 Hash散列函数一般模型散列函数一般模型对于散列函数对于散列函数H有下面六个要求：有下面六个要求：（1）能够接受任意长度的消息作为输入；能够

10、接受任意长度的消息作为输入；（2）能够生成较短的固定长度的输出；能够生成较短的固定长度的输出；（3）对任何消息输入都应该能够容易和快速地计算对任何消息输入都应该能够容易和快速地计算出散列值；出散列值；（4）应该是一个单向函数应该是一个单向函数难以或不可能反推。难以或不可能反推。也就是说，给定也就是说，给定H(m)，恢复恢复m在计算上是不可行的；在计算上是不可行的；（5）应该能够抵抗弱冲突，即当两个不同消息输入应该能够抵抗弱冲突，即当两个不同消息输入生成相同的输出时，就产生了冲突；生成相同的输出时，就产生了冲突；（6）应该能够抵抗强冲突，即找到两个有意义的消应该能够抵抗强冲突，即找到两个有意义的

11、消息息m1和和m2，使得使得H(m1)=H(m2)几几乎是不可能的。乎是不可能的。又称为：哈希函数、数字指纹又称为：哈希函数、数字指纹又称为：哈希函数、数字指纹又称为：哈希函数、数字指纹（Digitalfingerprint)Digitalfingerprint)、压缩、压缩、压缩、压缩（Compression)Compression)函数、紧缩函数、紧缩函数、紧缩函数、紧缩（ContractionContraction）函数）函数）函数）函数 前三条要求具有前三条要求具有前三条要求具有前三条要求具有实用性实用性实用性实用性；第第第第4 4条是条是条是条是单向性质单向性质单向性质单向性质，即给

12、定消息可以产生一个散列码，而给定散列码不可能产生对应的消，即给定消息可以产生一个散列码，而给定散列码不可能产生对应的消，即给定消息可以产生一个散列码，而给定散列码不可能产生对应的消，即给定消息可以产生一个散列码，而给定散列码不可能产生对应的消息；息；息；息；第第第第5 5条性质是保证一个给定的消息的散列码不能找到与之相同的另外的消息，即条性质是保证一个给定的消息的散列码不能找到与之相同的另外的消息，即条性质是保证一个给定的消息的散列码不能找到与之相同的另外的消息，即条性质是保证一个给定的消息的散列码不能找到与之相同的另外的消息，即防止伪造防止伪造防止伪造防止伪造；第第第第6 6条是对已知的条是

13、对已知的条是对已知的条是对已知的生日攻击生日攻击生日攻击生日攻击方法的防御能力。方法的防御能力。方法的防御能力。方法的防御能力。92024/3/192024/3/1992024/3/172024/3/1792024/3/192024/3/199 9散列函数应该满足的一般安全特性：散列函数应该满足的一般安全特性：102024/3/192024/3/19102024/3/172024/3/17102024/3/192024/3/191010 散列函数的一般结构散列函数的一般结构散列函数的一般结构散列函数的一般结构 1979年，MerKle基于数据压缩函数f建议了一个散列函数的一般结构如下图所示。M

14、D系列、SHA系列大多数散列函数都使用该结构。散列函数基本结构散列函数基本结构112024/3/192024/3/19112024/3/172024/3/17112024/3/192024/3/191111 上上图图中中，散散列列函函数数输输入入消消息息M，并并将将其其分分为为L个个固固定定长长度度的的分分组组，若若最最后后一一个个数数据据块不满足输入分组长度要求，按照一定规则进行填充块不满足输入分组长度要求，按照一定规则进行填充。该该散散列列函函数数重重复复使使用用一一个个压压缩缩函函数数f。压压缩缩函函数数f有有两两个个输输入入，一一个个是是前前一一阶阶段段的的n为为输输入入，另另外外一一

15、个个源源于于消消息息的的b位位分分组组，并并产产生生一一个个n位位的的输输出出，算算法法开开始始时时需需要要一一个个初初始始变变量量IV，最最终终的的输输出出值值通通过过一一个个输输出出变变换换函函数数g得得到到消消息息散散列列值值，通通常常bn,故故称称f为为压缩函数压缩函数，如下图所示：，如下图所示：压缩函数基本结构压缩函数基本结构122024/3/192024/3/19122024/3/172024/3/1712122024/3/192024/3/19122024/3/172024/3/17126.2.2 6.2.2 散列算法的分类及发展现状散列算法的分类及发展现状 最常用的散列函数主要

16、可分为如下几类：最常用的散列函数主要可分为如下几类：（1）MessageDigest（MD）系列系列 MD系列是由国际著名密码学家图灵奖获得者兼公钥加密算法RSA的创始人Rivest设计，包包包包括括括括MD2MD2（19891989年年年年针针针针对对对对8 8位位位位计计计计算算算算机机机机上上上上实实实实现现现现），MD4MD4（19901990年年年年针针针针对对对对3232位位位位计计计计算算算算机机机机上实现）和上实现）和上实现）和上实现）和MD5MD5（19911991年提出的，是对年提出的，是对年提出的，是对年提出的，是对MD4MD4的改进版，包括其散列值为的改进版，包括其散列

17、值为的改进版，包括其散列值为的改进版，包括其散列值为128128位）位）位）位）。（2）SHA（SecurityHashAlgorithm）系列系列 由由美美国国专专门门制制定定密密码码算算法法的的标标准准机机构构NIST和和NSA（National Security Agency，国国家家安安全全局局），在在1993年年，在在MD5基基础础上上首首先先提提出出SHA-0，美美国国国国家家安安全全局局（NSA）在在这个算法发布之后就将其撤回这个算法发布之后就将其撤回。1995年年SHA-1被被提提出出(即即美美国国的的FIPS PUB 180-1标标准准)，消消息息散散列列为为160 bits

18、。现现今今SHA-1应应用用到到DSA数数字字签签名名的的标标准准。在在2003年年，相相继继对对SHA系系列列算算法法进进行行扩扩展展，提提出出SHA-256、SHA-384、SHA-512(即即美美国国的的FIPS PUB 180-2标标准准)，并并于于2004年年加加入入了了额额外外的的变变种：种：SHA-224，统称为，统称为SHA-2。132024/3/192024/3/19132024/3/172024/3/1713132024/3/192024/3/19132024/3/172024/3/17132007年，年，NIST发起了发起了SHA-3竞赛以征集新的竞赛以征集新的Hash算

19、法算法。最终最终经过三轮的评选，经过三轮的评选，2012年年10月月2号，号，Keccak作为竞赛的胜利者，作为竞赛的胜利者，SHA-3标准标准被发布被发布(即美国的即美国的FIPS PUB 202），），提出了提出了4个个Hash算法算法SHA3-224,SHA3-256,SHA3-384,and SHA3-512，可完全替换，可完全替换SHA-2。（3）其它散列算法其它散列算法 HAVAL可以用来实现可变是那列的输出，RIPEMD-128、RIPEMD-160是是欧欧洲洲MD5和和MD4算算法法的的研研究究者者提提出出的的替替代代算算法法，Tiger算算法法主主要要是是设设计计思思想想是是

20、在在64位位和和32位计算机上能够很好的使用位计算机上能够很好的使用Hash算法。算法。142024/3/192024/3/19142024/3/172024/3/1714 目前在信息安全领域，最常用的散列函数有两大系列：MessageDigest（MD）系列和SHA（Security Hash Algorithm）系列，而MD5、SHA-1是当前国际通行的两大散列函数。MD5曾经是最广泛的摘要算法，但自从在美国加州圣巴巴拉召开的国际密码学会议（Crypto2004）原山东大学的王小云教授做了破译MD5、HAVAL-128、MD4和RIPEMD算法的报告，囊括了对MD5、HAVAL-128、M

21、D4和RIPEMD四个著名HASH算法的破译结果。-发展现状发展现状152024/3/192024/3/19152024/3/172024/3/17152007年，年，MarcStevens，ArjenK.Lenstra和和BennedeWeger进一步指出通过伪造进一步指出通过伪造软件签名，可重复性攻击软件签名，可重复性攻击MD5算法；算法；2008年，荷兰埃因霍芬技术大学科学家成功把年，荷兰埃因霍芬技术大学科学家成功把2个可执行文件进行了个可执行文件进行了MD5碰撞，使得这两个运行结果不同的程序被计算出同一个碰撞，使得这两个运行结果不同的程序被计算出同一个MD5；同年同年12月一组科研人员

22、通过月一组科研人员通过MD5碰撞成功生成了伪造的碰撞成功生成了伪造的SSL证书，这使得在证书，这使得在https协议中服务器可以伪造一些根协议中服务器可以伪造一些根CA的签名，因此的签名，因此MD5散列算法已不安全，不再推散列算法已不安全，不再推荐使用。荐使用。但是目前仍然在很多场合还在使用但是目前仍然在很多场合还在使用MD5算法，如算法，如Linux操作系统中的用户口令的验操作系统中的用户口令的验证算法。证算法。162024/3/192024/3/19162024/3/172024/3/17162012年，Mark Stevens使用了大量的云服务器来对SHA-1的进行差分路径攻击，仅用25

23、8.5次就能形成一次攻击碰撞，并且估计，在261次的循环计算后，就可以形成完整的哈希碰撞密码库。由于近年来对哈希算法的分析与破解取得了突破性的进展，由于MD5和SHA-0成功的破解，以及对SHA-1和SHA-2理论上的攻击出现，使得现行的MD系列和SHA系列算法都不再满足安全需要。NIST希望选出一个与之前算法不同的，可替换的Hash算法，于是于是NIST于于2007年发起了年发起了SHA-3竞赛以征集新的摘要算法竞赛以征集新的摘要算法。172024/3/192024/3/19172024/3/172024/3/1717到2008年10月31日为止，NIST收到了64份来自世界各个密码组织或个

24、人提交的候选算法，并且有51个候选算法进入第一轮评估。2009年的第一轮筛选后14个进入第二轮的评选。2010年，Keccak成功通过第二轮筛选进入SHA-3的最后一轮，成为5个最终候选摘要算法之一。2012年10月2号，Keccak从5个进入第三轮的算法中被选为SHA-3竞赛的胜利者。SHA-3的评选并不意味着要取代SHA-2，因为对SHA-2的已证实的有效攻击还没有出现。2017.2，Google宣布攻破宣布攻破SHA-1。182024/3/192024/3/19182024/3/172024/3/1718182024/3/192024/3/19182024/3/172024/3/1718

25、2024/3/192024/3/1918186.3 6.3 Hash散列算法散列算法 几种重要的散列算法几种重要的散列算法几种重要的散列算法几种重要的散列算法-MD5-MD5算法算法算法算法192024/3/192024/3/19192024/3/172024/3/1719-SecureHashAlggorithm-SecureHashAlggorithm：SHA-1SHA-1算法算法算法算法202024/3/192024/3/19202024/3/172024/3/1720-RIPEMD-160-RIPEMD-160 RIPEMD（RACE Integrity Primitives Eval

26、uation Message Digest，RACE原始完整性校验消息摘要），是Hans Dobbertin等3人在md4,md5的基础上，于1996年提出来的。算法共有4个标准128、160、256和320，其对应输出长度分别为16字节、20字节、32字节和40字节。不过，让人难以致信的是RIPEMD的设计者们根本就没有真正设计256和320位这2种标准，他们只是在128位和160位的基础上，修改了初始参数和s-box来达到输出为256和320位的目的。所以，256位的强度和128相当，而320位的强度和160位相当。RIPEMD建立在md的基础之上，所以，其添加数据的方式和md5完全一样。

27、212024/3/192024/3/19212024/3/172024/3/1721比较：比较：比较：比较：222024/3/192024/3/19222024/3/172024/3/17222024/3/192024/3/1922226.3 6.3 Hash散列算法散列算法6.3.1 MD5散列算法(选讲选讲选讲选讲)MD5由RSA的创始人Rivest设计开发的，能接收任意长度的消息作为输入，能接收任意长度的消息作为输入，能接收任意长度的消息作为输入，能接收任意长度的消息作为输入，并生成其并生成其并生成其并生成其128128位散列值位散列值位散列值位散列值。MD5散列函数总共两组输入散列函数

28、总共两组输入：512 bits 明文分块和上一组128 bits的输出块(或 IV初始变量)。输入的输入的输入的输入的128128bitsbits分别存储在四个缓存分别存储在四个缓存分别存储在四个缓存分别存储在四个缓存：A,B,C,DA,B,C,D，每个分块总共四个步骤每个分块总共四个步骤每个分块总共四个步骤每个分块总共四个步骤，每每每每步骤计算步骤计算步骤计算步骤计算1616次，次，次，次，合计合计合计合计6464轮轮轮轮次次次次，算法中需要加入 sin(x)非线性函数参数值，MD5散列算法总体结构散列算法总体结构如下图所示。232024/3/192024/3/19232024/3/1720

29、24/3/17232024/3/192024/3/1923231.MD5散列算法的具体步骤散列算法的具体步骤 242024/3/192024/3/19242024/3/172024/3/17242024/3/192024/3/192424（1）第一步：填充消息）第一步：填充消息 填填充充之之后后消消息息的的长长度度（bit为为单单位位）模模512为为448。如如果果数数据据长长度度正正好好是是模模512为为448，增加，增加512比特填充位，也就是说填充的个数至少比特填充位，也就是说填充的个数至少1个个512比特位。比特位。填充方法：第一个填充方法：第一个bit为为1，其余全部为，其余全部为0

30、。补补零零的的个个数数d=(447|x|)mod512（|x|为为原原始始消消息息长长度度值值），原原始始消消息息填填充充之之后后消消息可表达为息可表达为X|1|0d (0d表示为表示为d个个0)。例例如如消消息息由由704位位二二进进制制组组成成，那那么么在在其其末末尾尾添添加加256位位（255=(447704)mod512，即即1个个“1”后后面面255个个“0”），消消息息扩扩展展到到960位位（960mod512=448）；再再例例如如消消息息由由448位位二二进进制制组组成成，那那么么末末尾尾添添加加512位位（511=(447448)mod512，即即1个个“1”后面后面511个

31、个“0”），消息扩展到），消息扩展到960位（位（950mod512=448）。）。252024/3/192024/3/19252024/3/172024/3/17252024/3/192024/3/192525（2）第二步：补足长度）第二步：补足长度 在在填填充充的的消消息息的的末末尾尾添添加加64位位的的块块，该该64位位是是原原始始消消息息长长度度（二二进进制制位位表表示示）。如如果果长长度度超超过过64bit所所能能表表示示的的数数据据长长度度的的范范围围，则则仅仅取取最最低低64位位，即即mod264，增增加加到前面填充的数据后面，使得最后的数据为到前面填充的数据后面，使得最后的数据

32、为512bit的整数倍。的整数倍。至至此此，已已经经得得到到一一个个512位位的的整整倍倍数数长长度度的的新新的的消消息息。可可以以表表示示为为L个个512位位的的数数据块：据块：P PL-1L-1。其长度为其长度为L 512bits。令令N=L 16，则长度为则长度为N个个32位的字。令位的字。令M0N-1表示以字为单位的消息表示。表示以字为单位的消息表示。例例如如若若原原始始消消息息长长度度为为704位位二二进进制制组组成成，则则长长度度704变变换换为为二二进进制制为为1011000000，则则需需要要在在左左边边补补54个个0，达达到到64位位，并并把把它它添添加加到到消消息息的的末末

33、尾尾，其其结结果果是是最最后后原原始始消消息息扩扩充充到到一一个个1024位位的的消消息息，可可以以看看出出MD5算算法法中中，无无论论原原始始消消息息多多长长，补补足足长长度度之后的消息扩展为至少之后的消息扩展为至少2个分组，即扩展后消息的二进制长度至少是个分组，即扩展后消息的二进制长度至少是512的的2倍。倍。262024/3/192024/3/19262024/3/172024/3/17262024/3/192024/3/192626（3）第三步：初始化变量）第三步：初始化变量 初始化初始化MD缓冲区。缓冲区。一个一个128位位MD缓冲区用以保存中间和最终缓冲区用以保存中间和最终Hash

34、函数的结果。函数的结果。它可以表示为它可以表示为4个个32位的寄存器位的寄存器(A,B,C,D)。寄存器初始化为以下的寄存器初始化为以下的16进制值：进制值：A=67452301；B=EFCDAB89；C=98BADCFE；D=10325476（4）第四步：数据处理）第四步：数据处理 处处理理每每个个消消息息块块（512位位=16个个32位位字字），可可分分为为16个个字字记记为为为为M0,M1,M15。在在MD5算算法法中中四四轮轮循循环环，每每一一轮轮访访问问的的数数据据的的次次序序有有所所变变动动。MD5每每轮轮访访问问消消息息处理块的次序如下所示：处理块的次序如下所示：1）第第一一轮轮

35、16回回合合Mk的的访访问问次次序序为为：M0为为初初始始值值，依依次次访访问问次次序序为为下下标标k等等于于加加1模模16的值：的值：M0,M1,M2,M3,M4,M5,M6,M7,M8,M9,M10,M11,M12,M13,M14,M15；272024/3/192024/3/19272024/3/172024/3/17272024/3/192024/3/1927272）第第二二轮轮16回回合合Mk的的访访问问次次序序为为：M1为为初初始始值值，依依次次访访问问次次序序为为下下标标k等等于加于加5模模16的值：的值：M1,M6,M11,M0,M5,M10,M15,M4,M9,M14,M3,M

36、8,M13,M2,M7,M12；3）第第三三轮轮16回回合合Mk的的访访问问次次序序为为：M5为为初初始始值值，依依次次访访问问次次序序为为下下标标k等等于加于加3模模16的值：的值：M5,M8,M11,M14,M1,M4,M7,M10,M13,M0,M3,M6,M9,M12,M15,M2；4）第四轮第四轮16回合回合Mk的访问次序为：的访问次序为：M0为初始值，依次访问次序为下标为初始值，依次访问次序为下标k等等于加于加7模模16的值：的值：M0,M7,M14,M5,M12,M3,M10,M1,M8,M15,M6,M13,M4,M11,M2,M9；282024/3/192024/3/1928

37、2024/3/172024/3/17282024/3/192024/3/192828每个每个512比特比特消息块和消息块和MD5初始变初始变量量IV作为初作为初始输入，进入始输入，进入四轮循环，其四轮循环，其逻辑如右图所逻辑如右图所示。示。292024/3/192024/3/19292024/3/172024/3/17292024/3/192024/3/192929 MD5单个512比特分组它包括4轮处理，4轮轮处处理理具具有有相相似似的的结结构构,但但每每次次使使用用不不同同的的基基本本逻逻辑辑函函数数，记为F,G,H,I。每每一一轮轮以以当当前前的的512位位数数据据块块(Pq)和和128

38、位位缓缓冲冲值值ABCD作为输入，作为输入，并修改缓冲值的内容。每每次次使使用用64元元素素表表T164中中的的其其中中之之一一。其中T表由sin 函数构造而成。T的第i个元素表示为Ti，其值等于 232abs(sin(i),其中i是弧度。由于abs(sin(i)是一个0到1之间的数，T的的每每一一个个元元素素是是一一个个可可以以表表示示成成32位位的的整整数数。T表提供了随机化的32比特模板，消除了在输入数据中的任何规律性的特征。计算计算计算计算t1t1：x=sin(1)=0.8414709848078965066525023216303y=232=4294967296z=x*y=232*s

39、in(1)=3614090360.2828283386251439079649int(z)=3614090360=oxD76AA478。根据上述计算方法根据上述计算方法根据上述计算方法根据上述计算方法T T数值中的数值中的数值中的数值中的MD5MD5常量值如下页表所示。常量值如下页表所示。常量值如下页表所示。常量值如下页表所示。302024/3/192024/3/19302024/3/172024/3/17302024/3/192024/3/193030T数值中的数值中的MD5常量值常量值（5）步骤）步骤5：输出结果：输出结果 所有L个512位数据块处理完毕后，最后的结果就是128位消息摘要。

40、312024/3/192024/3/19312024/3/172024/3/17312024/3/192024/3/1931312.2.MD5压缩函数压缩函数 压压压压缩缩缩缩函函函函数数数数是是是是MD5MD5算算算算法法法法的的的的核核核核心心心心,如右图所示，它它就就是是处处理理一一个个512位位分分组组的的四四次次循循环环中中每每一一循循环环的的逻逻辑辑结结构构。每一轮包含对缓冲区ABCD的16回合操作所组成的一个序列。322024/3/192024/3/19322024/3/172024/3/17322024/3/192024/3/193232 在上图中：A、B、C、D=缓冲区的四个

41、字，以一个给定的次序排列；g=基本逻辑函数F、G、H、I之一；s =对32位字循环左移s位；Mk=Mq16+k=在第q个512位数据块中的第k个32位字；Ti=表T中的第i个32位字；+=模 232的加。1）每个回合缓冲区）每个回合缓冲区A，B，C，D的计算为：的计算为：A=DB=B+(A+g(B,C,D)+Mk+Ti)s)C=BD=C2）每个回合的基本逻辑函数每个回合的基本逻辑函数g(b,c,d)如下定义：如下定义：F(B,C,D)=(B C)(B D)G(B,C,D)=(B D)(C D)H(B,C,D)=B C DI(B,C,D)=C(B D)332024/3/192024/3/1933

42、2024/3/172024/3/17332024/3/192024/3/1933333）在在MD5中字循环移中字循环移s位在轮与轮之间和回合与回合之间是变化的，每一回位在轮与轮之间和回合与回合之间是变化的，每一回合的每一轮的循环移位如下表所示。合的每一轮的循环移位如下表所示。MD5中位循环移位量中位循环移位量342024/3/192024/3/19342024/3/172024/3/1734342024/3/192024/3/19342024/3/172024/3/17342024/3/192024/3/193434MD5强度特性特性散列码散列码(128b)的每一个比特是输入的每一个比特的函数

43、的每一个比特是输入的每一个比特的函数找两个冲突报文的计算量得找两个冲突报文的计算量得264找个给定报文冲突的计算量得找个给定报文冲突的计算量得2128攻击进展攻击进展 在美国加州圣巴巴拉召开的国在美国加州圣巴巴拉召开的国际密密码学会学会议（Crypto2004Crypto2004）山山东大学的致公大学的致公党党党党员王小云教授做了破王小云教授做了破译MD5MD5、HAVAL-128HAVAL-128、MD4 MD4和和RIPEMDRIPEMD算法的算法的报告，告，报告由王告由王小云、小云、冯登国、来学嘉、于登国、来学嘉、于红波四人共同完成，囊括了波四人共同完成，囊括了对MD5MD5、HAVAL

44、-128HAVAL-128、MD4 MD4和和RIPEMDRIPEMD四个著名四个著名HASHHASH算法的破算法的破译结果。果。352024/3/192024/3/19352024/3/172024/3/1735352024/3/192024/3/19352024/3/172024/3/17352024/3/192024/3/193535世界震惊:王小云破解全球两大密码算法40刚出头的王小云刚出头的王小云(当时当时)，毕业于山东大学数学系，师从于著名数学家潘承洞、于秀，毕业于山东大学数学系，师从于著名数学家潘承洞、于秀源教授，是一位外表普通却充满自信的中国女性。源教授，是一位外表普通却充满自

45、信的中国女性。2004年年8月，在美国加州圣芭芭拉召开月，在美国加州圣芭芭拉召开的国际密码大会上，并没有被安排发言的王小云教授拿着自己的研究成果找到会议主席，的国际密码大会上，并没有被安排发言的王小云教授拿着自己的研究成果找到会议主席，要求进行大会发言。就这样，王小云在国际会议上首次宣布了她及她的研究小组近年来的要求进行大会发言。就这样，王小云在国际会议上首次宣布了她及她的研究小组近年来的研究成果研究成果对对MD5、HAVAL128、MD4和和RIPEMD等四个著名密码算法的破译结果。等四个著名密码算法的破译结果。报告结束后，所有与会专家对她们的突出工作报以长时间的掌声。报告结束后，所有与会专

46、家对她们的突出工作报以长时间的掌声。王小云的研究成果作为密码学领域的重大发现宣告了固若金汤的世界通行密码标准王小云的研究成果作为密码学领域的重大发现宣告了固若金汤的世界通行密码标准MD5大厦轰然倒塌，引发了密码学界的轩然大波。这次会议的总结报告这样写道：大厦轰然倒塌，引发了密码学界的轩然大波。这次会议的总结报告这样写道：“我们我们该怎么办？该怎么办？MD5被重创了，它即将从应用中淘汰。被重创了，它即将从应用中淘汰。SHA1仍然活着，但也见到了它的末仍然活着，但也见到了它的末日。现在就得开始更换日。现在就得开始更换SHA1了。了。”362024/3/192024/3/19362024/3/172

47、024/3/1736362024/3/192024/3/19362024/3/172024/3/17362024/3/192024/3/193636世界震惊:王小云破解全球两大密码算法 2005年2月7日，美国国家标准技术研究院发表申明，SHA1没有被攻破，并且没有足够的理由怀疑它会很快被攻破，开发人员在2010年前应该转向更为安全的SHA256和SHA512算法。而仅仅在一周之后，王小云就宣布了破译而仅仅在一周之后，王小云就宣布了破译SHA1的消息。因为的消息。因为SHA1在美国等国家有更加广泛的应用，密码被破的消息一出，在美国等国家有更加广泛的应用，密码被破的消息一出，在国际社会的反响可谓

48、石破天惊。在国际社会的反响可谓石破天惊。换句话说，王小云的研究成果表明了从理论上讲电子签名可以伪造，必须及时添加限制条件，或者重新选用更为安全的密码标准，以保证电子商务的安全。372024/3/192024/3/19372024/3/172024/3/1737372024/3/192024/3/19372024/3/172024/3/17372024/3/192024/3/193737世界震惊:王小云破解全球两大密码算法 MD5、SHA-1是当前国际通行的两大密码标准。据了解，MD5由国际著名密码学家图灵奖获得者兼公钥加密算法RSA的创始人Rivest设计，SHA1是由美国专门制定密码算法的标

49、准机构美国国家标准技术研究院（NIST）与美国国家安全局（NSA）设计。两大算法是目前国际电子签名及许多其它密码应用领域的关键技术，广泛应用于金融、证券等电子商务领域。其中，SHA1早在1994年便为美国政府采纳，目前是美国政府广泛应用的计算机密码系统。世界上由于没有两个完全相同的指纹，因此手印成为人们身份惟一和安全的标志。在网络安全协议中，使用Hash函数来处理电子签名，以便产生理论上独一无二的“指纹”，形成“数字手印”。按照理想安全要求，经过Hash函数产生的指纹，原始信息即使只改变一位，其产生的“指纹”也会截然不同。如果能找到如果能找到Hash函数的碰撞，就意味着两个不同函数的碰撞，就意味着两个不同的文件可以产生相同的的文件可以产生相同的“指纹指纹”，这样就可以伪造签名。，这样就可以伪造签名。