hase函数.doc

Hash，一般翻译做“散列”，也有直接音译为"哈希"的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。
数学表述为：h = H(M) ，其中H( )--单向散列函数，M--任意长度明文，h--固定长度散列值。
在信息安全领域中应用的Hash算法，还需要满足其他关键特性：
第一当然是单向性(one-way)，从预映射，能够简单迅速的得到散列值，而在计算上不可能构造一个预映射，使其散列结果等于某个特定的散列值，即构造相应的M=H-1(h)不可行。这样，散列值就能在统计上唯一的表征输入值，因此，密码学上的 Hash 又被称为"消息摘要(message digest)"，就是要求能方便的将"消息"进行"摘要"，但在"摘要"中无法得到比"摘要"本身更多的关于"消息"的信息。
第二是抗冲突性(collision-resistant)，即在统计上无法产生2个散列值相同的预映射。给定M，计算上无法找到M'，满足H(M)=H(M') ，此谓弱抗冲突性；计算上也难以寻找一对任意的M和M'，使满足H(M)=H(M') ，此谓强抗冲突性。要求"强抗冲突性"主要是为了防范所谓"生日攻击(birthday attack)"，在一个10人的团体中，你能找到和你生日相同的人的概率是2.4%，而在同一团体中，有2人生日相同的概率是11.7%。类似的，当预映射的空间很大的情况下，算法必须有足够的强度来保证不能轻易找到"相同生日"的人。
第三是映射分布均匀性和差分分布均匀性，散列结果中，为 0 的 bit 和为 1 的 bit ，其总数应该大致相等；输入中一个 bit 的变化，散列结果中将有一半以上的 bit 改变，这又叫做"雪崩效应(avalanche effect)"；要实现使散列结果中出现 1bit 的变化，则输入中至少有一半以上的 bit 必须发生变化。其实质是必须使输入中每一个 bit 的信息，尽量均匀的反映到输出的每一个 bit 上去；输出中的每一个 bit，都是输入中尽可能多 bit 的信息一起作用的结果。
Damgard 和 Merkle 定义了所谓“压缩函数(compression function)”，就是将一个固定长度输入，变换成较短的固定长度的输出，这对密码学实践上 Hash 函数的设计产生了很大的影响。Hash函数就是被设计为基于通过特定压缩函数的不断重复“压缩”输入的分组和前一次压缩处理的结果的过程，直到整个消息都被压缩完毕，最后的输出作为整个消息的散列值。尽管还缺乏严格的证明，但绝大多数业界的研究者都同意，如果压缩函数是安全的，那么以上述形式散列任意长度的消息也将是安全的。这就是所谓 Damgard/Merkle 结构：
在下图中，任意长度的消息被分拆成符合压缩函数输入要求的分组，最后一个分组可能需要在末尾添上特定的填充字节，这些分组将被顺序处理，除了第一个消息分组将与散列初始化值一起作为压缩函数的输入外，当前分组将和前一个分组的压缩函数输出一起被作为这一次压缩的输入，而其输出又将被作为下一个分组压缩函数输入的一部分，直到最后一个压缩函数的输出，将被作为整个消息散列的结果。
MD5 和 SHA1 可以说是目前应用最广泛的Hash算法，而它们都是以 MD4 为基础设计的。
1) MD4
MD4(RFC 1320)是 MIT 的 Ronald L. Rivest 在 1990 年设计的，MD 是 Message Digest 的缩写。它适用在32位字长的处理器上用高速软件实现--它是基于 32 位操作数的位操作来实现的。它的安全性不像RSA那样基于数学假设，尽管 Den Boer、Bosselaers 和 Dobbertin 很快就用分析和差分成功的攻击了它3轮变换中的 2 轮，证明了它并不像期望的那样安全，但它的整个算法并没有真正被破解过，Rivest 也很快进行了改进。
下面是一些MD4散列结果的例子：
MD4 ("") = 31d6cfe0d16ae931b73c59d7e0c089c0
MD4 ("a") = bde52cb31de33e46245e05fbdbd6fb24
MD4 ("abc") = a448017aaf21d8525fc10ae87aa6729d
MD4 ("message digest") = d9130a8164549fe818874806e1c7014b
MD4 ("abcdefghijklmnopqrstuvwxyz") = d79e1c308aa5bbcdeea8ed63df412da9
MD4 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = 043f8582f241db351ce627e153e7f0e4
MD4 ("12345678901234567890123456789012345678901234567890123456789012345678901234567890") = e33b4ddc9c38f2199c3e7b164fcc0536

2) MD5
MD5(RFC 1321)是 Rivest 于1991年对MD4的改进版本。它对输入仍以512位分组，其输出是4个32位字的级联，与 MD4 相同。它较MD4所做的改进是：
1) 加入了第四轮
2) 每一步都有唯一的加法常数；
3) 第二轮中的G函数从((X ∧ Y) ∨ (X ∧ Z) ∨ (Y ∧ Z)) 变为 ((X ∧ Z) ∨ (Y ∧ ～Z))以减小其对称性；
4) 每一步都加入了前一步的结果，以加快"雪崩效应"；
5) 改变了第2轮和第3轮中访问输入子分组的顺序，减小了形式的相似程度；
6) 近似优化了每轮的循环左移位移量，以期加快"雪崩效应"，各轮的循环左移都不同。
尽管MD5比MD4来得复杂，并且速度较之要慢一点，但更安全，在抗分析和抗差分方面表现更好。
消息首先被拆成若干个512位的分组，其中最后512位一个分组是“消息尾+填充字节(100…0)+64 位消息长度”，以确保对于不同长度的消息，该分组不相同。64位消息长度的限制导致了MD5安全的输入长度必须小于264bit，因为大于64位的长度信息将被忽略。而4个32位寄存器字初始化为A=0x01234567，B=0x89abcdef，C=0xfedcba98，D=0x76543210，它们将始终参与运算并形成最终的散列结果。
接着各个512位消息分组以16个32位字的形式进入算法的主循环，512位消息分组的个数据决定了循环的次数。主循环有4轮，每轮分别用到了非线性函数
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) = X ⊕ (Y ∨ ～Z)
这4轮变换是对进入主循环的512位消息分组的16个32位字分别进行如下操作：将A、B、C、D的副本a、b、c、d中的3个经F、G、H、I运算后的结果与第4个相加，再加上32位字和一个32位字的加法常数，并将所得之值循环左移若干位，最后将所得结果加上a、b、c、d之一，并回送至ABCD，由此完成一次循环。
所用的加法常数由这样一张表T[i]来定义，其中i为1…64，T[i]是i的正弦绝对值之4294967296次方的整数部分，这样做是为了通过正弦函数和幂函数来进一步消除变换中的线性性。
当所有512位分组都运算完毕后，ABCD的级联将被输出为MD5散列的结果。下面是一些MD5散列结果的例子：
MD5 ("") = d41d8cd98f00b204e9800998ecf8427e
MD5 ("a") = 0cc175b9c0f1b6a831c399e269772661
MD5 ("abc") = 900150983cd24fb0d6963f7d28e17f72
MD5 ("message digest") = f96b697d7cb7938d525a2f31aaf161d0
MD5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b
MD5 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = d174ab98d277d9f5a5611c2c9f419d9f
MD5 ("12345678901234567890123456789012345678901234567890123456789012345678901234567890") = 57edf4a22be3c955ac49da2e2107b67a
参考相应RFC文档可以得到MD4、MD5算法的详细描述和算法的C源代码。
3) SHA1 及其他
SHA1是由NIST NSA设计为同DSA一起使用的，访问http://www.itl.nist.gov/fipspubs可以得到它的详细规范--[/url]"FIPS PUB 180-1 SECURE HASH STANDARD"。它对长度小于264的输入，产生长度为160bit的散列值，因此抗穷举(brute-force)性更好。SHA-1 设计时基于和MD4相同原理,并且模仿了该算法。因为它将产生160bit的散列值，因此它有5个参与运算的32位寄存器字，消息分组和填充方式与MD5相同，主循环也同样是4轮，但每轮进行20次操作，非线性运算、移位和加法运算也与MD5类似，但非线性函数、加法常数和循环左移操作的设计有一些区别，可以参考上面提到的规范来了解这些细节。下面是一些SHA1散列结果的例子：
SHA1 ("abc") = a9993e36 4706816a ba3e2571 7850c26c 9cd0d89d
SHA1 ("abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq") = 84983e44 1c3bd26e baae4aa1 f95129e5 e54670f1
其他一些知名的Hash算法还有MD2、N-Hash、RIPE-MD、HAVAL等等。上面提到的这些都属于"纯"Hash算法。还有另2类Hash算法，一类就是基于对称分组算法的单向散列算法，典型的例子是基于DES的所谓Davies-Meyer算法，另外还有经IDEA改进的Davies-Meyer算法，它们两者目前都被认为是安全的算法。另一类是基于模运算/离散对数的，也就是基于公开密钥算法的，但因为其运算开销太大，而缺乏很好的应用前景。
没有通过分析和差分攻击考验的算法，大多都已经夭折在实验室里了，因此，如果目前流行的Hash算法能完全符合密码学意义上的单向性和抗冲突性，就保证了只有穷举，才是破坏Hash运算安全特性的唯一方法。为了对抗弱抗冲突性，我们可能要穷举个数和散列值空间长度一样大的输入，即尝试2^128或2^160个不同的输入，目前一台高档个人电脑可能需要10^25年才能完成这一艰巨的工作，即使是最高端的并行系统，这也不是在几千年里的干得完的事。而因为"生日攻击"有效的降低了需要穷举的空间，将其降低为大约1.2*2^64或1.2*2^80，所以，强抗冲突性是决定Hash算法安全性的关键。
在NIST新的 Advanced Encryption Standard (AES)中，使用了长度为128、192、256bit 的密钥，因此相应的设计了 SHA256、SHA384、SHA512，它们将提供更好的安全性。
Hash算法在信息安全方面的应用主要体现在以下的3个方面：
1) 文件校验
我们比较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗数据篡改的能力，它们一定程度上能检测并纠正数据传输中的信道误码，但却不能防止对数据的恶意破坏。
MD5 Hash算法的"数字指纹"特性，使它成为目前应用最广泛的一种文件完整性校验和(Checksum)算法，不少Unix系统有提供计算md5 checksum的命令。它常被用在下面的2种情况下：
第一是文件传送后的校验，将得到的目标文件计算 md5 checksum，与源文件的md5 checksum 比对，由两者 md5 checksum 的一致性，可以从统计上保证2个文件的每一个码元也是完全相同的。这可以检验文件传输过程中是否出现错误，更重要的是可以保证文件在传输过程中未被恶意篡改。一个很典型的应用是ftp服务，用户可以用来保证多次断点续传，特别是从镜像站点下载的文件的正确性。
更出色的解决方法是所谓的代码签名，文件的提供者在提供文件的同时，提供对文件Hash值用自己的代码签名密钥进行数字签名的值，及自己的代码签名证书。文件的接受者不仅能验证文件的完整性，还可以依据自己对证书签发者和证书拥有者的信任程度，决定是否接受该文件。浏览器在下载运行插件和java小程序时，使用的就是这样的模式。
第二是用作保存二进制文件系统的数字指纹，以便检测文件系统是否未经允许的被修改。不少系统管理/系统安全软件都提供这一文件系统完整性评估的功能，在系统初始安装完毕后，建立对文件系统的基础校验和数据库，因为散列校验和的长度很小，它们可以方便的被存放在容量很小的存储介质上。此后，可以定期或根据需要，再次计算文件系统的校验和，一旦发现与原来保存的值有不匹配，说明该文件已经被非法修改，或者是被病毒感染，或者被木马程序替代。TripWire就提供了一个此类应用的典型例子。
更完美的方法是使用"MAC"。"MAC" 是一个与Hash密切相关的名词，即信息鉴权码(Message Authority Code)。它是与密钥相关的Hash值，必须拥有该密钥才能检验该Hash值。文件系统的数字指纹也许会被保存在不可信任的介质上，只对拥有该密钥者提供可鉴别性。并且在文件的数字指纹有可能需要被修改的情况下，只有密钥的拥有者可以计算出新的散列值，而企图破坏文件完整性者却不能得逞。
2) 数字签名
Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢，所以在数字签名协议中，单向散列函数扮演了一个重要的角色。
在这种签名协议中，双方必须事先协商好双方都支持的Hash函数和签名算法。
签名方先对该数据文件进行计算其散列值，然后再对很短的散列值结果--如Md5是16个字节，SHA1是20字节，用非对称算法进行数字签名操作。对方在验证签名时，也是先对该数据文件进行计算其散列值，然后再用非对称算法验证数字签名。
对 Hash 值，又称"数字摘要"进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点：
首先，数据文件本身可以同它的散列值分开保存，签名验证也可以脱离数据文件本身的存在而进行。
再者，有些情况下签名密钥可能与解密密钥是同一个，也就是说，如果对一个数据文件签名，与对其进行非对称的解密操作是相同的操作，这是相当危险的，恶意的破坏者可能将一个试图骗你将其解密的文件，充当一个要求你签名的文件发送给你。因此，在对任何数据文件进行数字签名时，只有对其Hash值进行签名才是安全的。
3) 鉴权协议
如下的鉴权协议又被称作"挑战--认证模式：在传输信道是可被侦听，但不可被篡改的情况下，这是一种简单而安全的方法。
需要鉴权的一方，向将被鉴权的一方发送随机串（“挑战”），被鉴权方将该随机串和自己的鉴权口令字一起进行 Hash 运算后，返还鉴权方，鉴权方将收到的Hash值与在己端用该随机串和对方的鉴权口令字进行 Hash 运算的结果相比较（“认证”），如相同，则可在统计上认为对方拥有该口令字，即通过鉴权。
第8章Hash函数
密码学上的Hash函数是一种将任意长度的消息(message)压缩为某一固定长度的消息摘要(message digest)的函数．
Hash函数可以用于数字签名．将Hash函数应用于数字签名有许多好处．
(1)可以提高签名的速度．当签名者想对一个消息优进行签名时，他可以首先利用Hash函数H，计算消息／'n的消息摘要。一日(m)，然后计算签名y-Sigt(z)．这里k是签名密钥，Sigt是签名函数．
(2)可以不泄露签名所对应的消息．对消息in的签名是y=Si9。(2)，其中名一H(研)，H是一个Hash函数．Y是签名应当公开，消息摘要2可以公开以便于验证签名，而消息m则可以保密．
(3)可以将对消息的签名变换与加密变换分开处理．
Hash函数除了可用于数字签名之外，还可以用于其他方面，譬如消息的完整性检测．为保证消息的完整性，及时发现消息是否被非法篡改，可以在消息传输之前先对消息做Hash变换，然后对消息进行传输，对于接收到的消息也做Hash变换，将传输前的消息的Hash变换值与接收到的消息的Hash变换值做比较，如果两者相同，则可以认为消息在传输过程中没有被篡改，否则消息一定被非法篡改了．
本章简单介绍Hash函数的基本性质和两个常见的Hash函数一一Hash函数MD4和安全Hash算法SHA．
8．1 Hash函数的性质
Hash函数的输入为任意长度的消息，而其输出为固定长度的消息．一个Hash函数是一个多对一的映射．
定义8．1设H是一个Hash函数，给定一个消息z，如果寻找另外一个与X不同的消息z'，使得H(z)一H(z')是计算上不可行的，则称H关于消息X是弱无碰撞的(weakly collision-free)．
在一个应用Hash函数的签名方案中，假设s是签名者对消息z的一个有效签名，S-Sigt(H(z))．对手可能会试图寻找另外一个与．27不同的消息x7，使得H(z)一H(z7)．如果对手找到了一个这样的z7，则对手就可以伪造对消息27的签名，这是因为S也是对消息z7的有效签名．如果应用于签名方案中的Hash函数H关于消息2是弱无碰撞的，则相应的签名方案就可以抵抗对手的上述伪造攻击．
对Hash函数的另外一种可能的攻击是对手可能会寻找两个不同的消息,27和z，使得H(z)一H(z 7)，然后对手说服签名者对消息z进行签名，得到S-Sigk(H(z))．由于s=Sim(日(z'))，所以对手得到了一个对消息z7的有效签名．对手的这种攻击方法导致我们定义强无碰撞的Hash函数．
定义8．2设H是一个Hash函数，如果寻找两个不同的消息2和z 7使得H(z)一H(z7)在计算上是不可行的，则称日是强无碰撞的(strongly collision-free)．
显然，一个Hash函数H是强无碰撞的当且仅当寻找一个消息32使得日关于z不是弱无碰撞的在计算上是不可行的，也就是说，一个Hash函数H是强无碰撞的当且仅当对任意消息37，H关于消息2是弱无碰撞的．
在一个应用Hash函数的签名方案中，假设对手得到了关于一个消息摘要z的有效签名s，s=Si9。(2)，则对手可能会试图寻找一个消息z，使得2一H(z)．如果对手找到了这样的消息z，则S就是消息2的有效签名．为抵抗对手的这种攻击，我们应该要求Hash函数是单向函数．
定义8．3设H是一个Hash函数，如果对于任意给定的2，寻找满足H(z)一2的消息z是计算上不可行的，则称H是单向的(one-way)．
可以证明，如果一个Hash函数H不是单向的，则H一定不是强无碰撞的，也就是说，如果一个Hash函数日是强无碰撞的，则H一定是单向的．
综上所述，一个密码学上安全的Hash函数日应具有以下性质：(1)对任意消息z，计算H(z)是容易的；
(2)寻找两个不同的消息z和z7使得H(z)一H(z 7)是难解的．
8．2基于分组密码的Hash函数
利用已有的分组密码来构造Hash函数是一种常见的比较简单的构造方法．在4．4节中我们提到，在分组密码的CBC工作模式和CFB工作模式中，一个明文块的改变，在加密时将会引起相应的密文块以及其后的所有密文块的改变．因此，我们自然会想到利用分组密码的CBC工作模式和CFB工作模式来构造Hash函数．
设&是一个分组长度为，z的分组密码的加密算法，密钥为k．对于任意消息z，首先对2进行分组，每组的长度为卵．如果z的长度不是咒的倍数，则在z的最后适当添加一些数据使得z的长度恰好是卵的倍数．在以下的讨论中，我们假设消息的长度都是以的倍数．
设z是任意一个消息，
基于分组密码的CBC工作模式的Hash函数H如图8．1所示，其构造过程可以形式化地描述为：首先选取一个初始向量IV∈GF(2)"，令Y。-----IV；然后计算
基于分组密码的CFB工作模式的Hash函数日如图8．2所示，其构造过程为：首先选取一个初始向量IV∈GF(2)"，令Y。----IV；然后计算
基二F分组密码的CBC工作模式和CFB工作模式的Hash函数中的密钥五可以公开也可以不公开．如果密钥k保密，则我们得到的是带密钥的Hash函数．如果密钥志公开，则我们得到的就是通常的不带密钥的Hash函数．
带密钥的Hash函数常用于产生消息认证码(message authentication code)．对于通信双方之间传输的任意消息z，用带密钥的Hash函数H对z做变换，结果H(z)作为消息2的认证码，附在消息z的后面．消息认证码用于保证通信双方之间传输的消息的完整性，使双方确信消息没有被第三方篡改或伪造．
不难看出，在密钥公开的情况下，基于分组密码的CBC工作模式和CFB工作模式的Hash函数是不安全的，它们甚至不是弱无碰撞的．
8．3 Hash函数MD4
Hash函数MD4是由R．L．Rivest于1990年提出的．MD4的设计没有基于任何假设和密码体制．Hash函数的这种直接构造方法受到了人们的广泛青睐．MD4的效率很高，非常实用．
下面我们来介绍Hash函数MD4．
设z是一个消息，用二进制表示．首先由37生成一个数组
(2)令z为Iz l mod 264的二进制表示．z的长度为64位．如果2的长度不足64位，则在z的左端添0补足．
(3)M=x ll l||04|11．
这里Izl表示37的长度，Il表示序列的连接，譬如z lI y表示将序列y排在序列z的右端．在M的构造中，首先在z的右端添加一个1，然后填充尽可能多的0使其长度恰好为512的倍数减去64，最后64位表示消息填充前长度的二进制表示．如果．27的长度Iz J不小于2"，则最后64位为Jz I rood 264的二进制表示．这样M的长度恰好为512的倍数．
MD4将从M开始产生一个l28位的消息摘要．算法如下：
(1)设A，B，c，D是四个32位的寄存器，其初值(用十六进制表示)Yt别为
A=67452301，B=efcdab89．C=98badcfe，D一10325476．(2)对i一0至N／16-1执行第(3)步至第(8)步．
(3)对J一0至15执行x[．『]=M[16i+力．
(4)将寄存器A，B，C，D中的值存储到另外四个寄存器AA，BB，CC，DD中．
AA=A，BB-B，CC=C，DD=D．
(5)执行Roundl．(6)执行Round2．(7)执行Round3．(8)A-A+AA，B-B+BB，C-C+cc，D-D+DD．
在上述算法中，每次循环处理16个字，循环的次数为N／16．最后一次循环结束时，将寄存器A，B，C，D中的值排列在一起即为MD4的输出．这就是消息z的一个l28位的消息摘要．
下面对MD4中的Roundl，Round2，Round3以及一些运算做进一步的描述．首先描述一些运算．设X和y为两个字．
(1)XAy表示x与y的按位逻辑"与(and)"运算．(2)XVY表示x与y的按位逻辑"或(or)"运算．(3)XoY表示x与y的按位逻辑"异或(xor)"运算．
(4)一X表示X的按位逻辑"补(complement)"运算．(5)X+y表示整数x与y的模232加法运算．
(6)X《s表示将X循环左移5个位置，0≤s≤31．
上述运算都是很快的．只有模232加法运算是算术运算．在计算机上实现MD4时，为了正确地完成加法运算，还必须考虑计算机的结构．
设alaza。a。表示一个字的4个字节，每个字节为8位．在一个具有bi9-endian结构的计算机中，这个字表示整数
MD4的设计是以little-endian结构为基础的．由于消息摘要应该独立于计算机的结构，所以如果要在一个具有bi9-endian结构的计算机上实现MD4，必须按下述方法来完成加法运算．
(1)交换21和z4，z2和z3，Yl和Y4，y2和Y3．(2)计算2-X+y mod 232．
(3)交换21和24，22和孙
这里2?，22，z3，zt分别是X的4个字节，Yl，Y2，Y3，Y。分别是y的4个字节，21，22，z。，2。分别是2的4个字节．
MD4中的Roundl，Round2，Round3分别使用了函数f，g，h．它们的定义如
下：
厂(X，Y，Z)一(X八y)V(X A Z)，
g(X，y，Z)一(X A y)V(X^Z)V(y A Z)，h(X，y，z)一X④Y o z．
Roundl如下：
A一(A+f(B，C，D)+X[o])《3，D_--(D+f(A，B，C)+X[1])《7，C一(C+f(D，A，B)+XEz])《11，B一(B+／'(C，D，A)+X[3])《19，
A一(A+f(B，C，D)+X[4])《3，D=(D+f(a，B，C)+xEs])《7，C一(C+厂(D，A，B)+xE6])《11，B一(B+f(C，D，A)+X[7])《19，A一(A+f(B，C，D)+X[8])《3，D一(D+f(A，B，C)+X[9])《7，c一(c+f(JD，A，B)+x[10])《11，B一(B+／'(C，D，A)+xEll])《19，A一(A+f(B，C，D)十xElz-1)《3，D一(D+f(A，B，C)+XCl3])《7，c一(c+／(D，A，B)+xEl43)《11，B一(B+f(c，D，A)+xEl5])《19．Round2如下：
A=(4+g(B，C，D)+XEo]+5a827999)《3，D一(D+g(A，B，C)+XE4]+5a827999)《5，c一(c+g(D，A，B)+X[8]+5a827999)《9，B一(B+g(C，D，A)+xFlz-1+5a827999)《13，A=(A+g(B，C，D)+X[1]+5a827999)《3，D一(D+g(A，B，c)+xE5]+5a827999)《5，C=(C+g(D，A，B)+XEg-1+5a827999)《9，B一(B+g(C，D，A)+xEl33+5a827999)《13，
A=(A+g(B，C，D)+X[2]+5a827999)《3，D=(D+g(A，B，c)+XE6]+5a827999)《5，C=(C+g(D，A，B)+XFlO]+5a827999)《9，B一(B+g(C，D，A)+X[14]+5a827999)《13，A一(A+g(B，C，D)+XE3]+5a827999)《3，
D=(D+g(A，B，C)+XET]+5a827999)《5，C=(C+g(D，A，B)+XEll]+5a827999)《9，B一(B+g(C，D，A)+XEl53+5a827999)《13．Round3如下：
A一(以+h(B，C，D)+X[o]+6edgebal)《3，D一(D+h(A，B，C)+X[8]+6ed9ebal)《9，C一(C+h(D，A，B)+XE4]+6ed9ebal)《11，B=(B+h(C，D，A)+X[12]+6edgebal)《15，A一(以+h(B，C，D)+XEz3+6edgebal)《3，
D一(D+h(A，B，C)+xFlo]+6ed9ebal)《9，
C一(C+h(D，A，B)+X[6]+6ed9ebal)《11，B一(B+h(C，D，A)+X[14]+6edgebal)《15，A一(A+h(B，C，D)+x[1]4-6edgebal)《3，
D一(D+h(A，B，C)+X[9]+6edgebal)《9，C一(C 4-h(D，A，B)+XE5]+6ed9ebal)《11，B一(B+h(C，D，A)+x[13]+6ed9ebal)《15，A一(A 4-h(B，C，D)4-X[3]+6ed9ebal)《3，
D一(D 4-h(A，B，C)+X[11]4-6ed9ebal)《9，C_--'(C+h(D，A，B)+X[7]+6edgebal)《11，B一(B 4-h(e，D，A)+X[15]+6ed9ebal)《15．MD4的执行速度很快，在Sun SPARCstation上软件实现的速度可达到1．4
兆字节／秒．关于MD4的安全性，目前还没有发现非常有效的攻击方法．但已经有人指出，如果删掉MD4中的Roundl或Round3，则MD4是不安全的．因此，为了克服MD4的缺陷并增强安全性，R．L．Rivest于1991年对MD4做了改进，改进后的Hash算法称为MD5．关于MD5，在此不再详述，有兴趣的读者可参阅相关的文献．
8．4安全Hash算法SHA
安全Hash算法SHA(Secure Hash Algorithm)是美国国家标准技术研究所(NIST)公布的安全Hash标准SHS(Secure Hash Standard)中的Hash算法．安全Hash标准SHS于1993年5月11日正式公布后，NIST又对其做了一点修改．1995年4月17日，NIST正式公布了修改后的SHS．在新的标准中，将修改后的SHA称为SHA一1．SHA的设计原则与MD4的设计原则极其相似，它是MD4的一种变型．
下面我们来介绍SHA一1．
设z为SHA一1的输入消息，用二进制表示．z的长度小于2"．SHA一1的输出
的长度为l60位，即5个字，每个字32位．给定消息2，首先由2产生一个数组M-M[0]M[-1]M[N一1]，
其中M[i]的长度为32位，0≤i≤Ⅳ一1，N=O(mod l6)．M[i]称为一个字，0≤i≤Ⅳ一l．M的产生方法与在MD4中的产生方法完全一样．在M的构造中，首先在37的后面添加一个1，然后填充尽可能多的0使其长度恰好为512的倍数减去64，最后64位是消息填充前的长度的二进制表示．
SHA一1将从M开始产生一个l60位的消息摘要．算法如下：
(])设A，B，c，D，E是五个32位的寄存器，其初始值(用十六进制表示)分别
为
A一67452301，B-efcdab89，C一98badcfe。D一10325476E-C3d2e1{0．(2)对i一0至N／16～1执行第(3)步至第(10)步．
(3)对歹=0至15执行X[J]=M[16i+j]．(4)对户l6至79执行
XEj]一(xEj一3]①xEy一8]④XEj一14]④XEj一16])《1．
(5)将寄存器A，B，C，D，E中的值分别存储到另外五个寄存器AA，BB，CC，
DD，EE中，
AA=A，BB=B，CC-C，DD-D，EE=E．
(6)执行Roundl．(7)执行Round2．(8)执行Round3．(9)执行Round4．(10)A-A+AA，B=B+BB，C=C+CC，D-D+DD，E-E+EE．
在上述算法中，每次循环处理16个字，循环的次数为N／16．最后一次循环结束时，将寄存器A，B，C，D，E中的值排列在一起即为SHA一1的输出．这就是消息z的长度为l60位的消息摘要．
SHA一1中涉及到的运算与MD4中的运算完全一样．与MD4不同的是SHA一1的设计是以bi9-endian结构为基础的．下面对SHA一1中的Roundl，Round2，Round3，Round4做进一步的描述．
Roundl．Round2，Round3，Round4中所使用的函数分别为
f。(X，Y，Z)一(X^y)V(X^Z)，f2(X，Y，z)一X o Y④Z，
f3(X，Y，Z)一(X^y)V(X八Z)V(y^Z)，f。(X，y，Z)一f2(X，Y，Z)
一X o Y④Z．
Roundl，Round2，Round3，Round4中所使用的常数(用十六进制表示)分别为
K1-5a827999，K2-6ed9ebal，K3-8flbbcdc，K4一ca62cld6．Roundl为
对k一0至19执行
TEMP一(A《51)+厂l(B，C，D)+E+XEk]+K，，E-D，D-C，C一(B《30)，B-A，A-TEMP．Round2为
对k一20至39执行
TEMP一(A《5)+fz(B，C，D)+E+X雎]+K2，E-D，D-C，C一(B《30)，B-A，A-TEMP．Round3为
对k一40至59执行
TEMP一(A《5)+f3(B，C，D)+E+x[五]+K。，E-D，D-C，C一(B《30)，B-A，A-TEMP．Round4为
对k一60至79执行
TEMP一(A《5)+f4(B，C，D)+E+X[志]+K。，E-D，D-C，C一(B《30)，B-A，A-TEMP．显然，SHA一1比MD4要复杂一点，其运行速度比MD4要慢．从已有的性能分
忻来看，SHA一1的安全性能比MD4要好．
习 题
3．1 为什么说在密钥公开的情况下，基于分组密码的CBC工作模式和CFB工作模式的Hash函数日是不安全的?对于任意给定的消息z，试寻找一个与z不同的消息z7，使得H(z')一H(z)．
3．2设&是一个分组长度为咒的分组密码的加密算法，密钥为k．假设密钥的长度也为咒．对于任意消息z，首先对2进行分组，每组的长度为；r／．如果2的长度不是n的倍数，则在z的最后适当添加一些数据使得z的长度恰好是y／的倍数．设
其中2，∈GF(2)"，l≤i≤z．选取IV∈GF(2)"作为初始向量，令Y。一IV．按下述四种不同的方式分别计算Y，，l≤i≤z．最后定义H(z)一M．试问按下述四种方式构造的Hash函数日都是安全的吗?
8．3 参照利用分组密码构造Hash函数的方法，试利用公钥密码体制RSA构造
一个Hash函数，并分析其安全性能．
8．4设H，是一个从(Z2)知到(Z2)"的Hash函数，即H?的输入为Zz上的长度为2咒的字符串，而输出为2。上的长度为竹的字符串，这里竹≥l，zz一{0，1)?对任意整数i≥2，J,l(z。)z'"到(z。)"的Hash函数H。按下述方式定义：
(1)对任意z∈(z：)孙i，设
Z 2 XlX2'
其中21，z2∈(z2)2'～"，XlX2表示22排在zl的后面；
(2)定义
日i(z)一Hl(Hl_1(z1)Hi一1(x2))，
其中HH(X1)Hl_1(z2)表示HH(z2)排在HH(x1)的后面．
假设H，是强无碰撞的．试证明对任意i≥2，H，也是强无碰撞的．