1、Chapter 11 密码学密码学Hash函数函数哈希函数（杂凑函数）（1） Hash编码；编码；（2） Hash函数；函数；（3）散列编码：）散列编码：（4）散列函数；）散列函数；（5）单向压缩函数。）单向压缩函数。哈希函数 在公钥密码的内容中，已经介绍了“单向函数”的概念。而哈希函数是一类特殊的单向函数。 设数据文件是任意长度的比特串x 。在密码应用中，希望有这样的函数 y=H(x)，满足： （1）将x压缩成为固定长度的比特串y。 （2）不同的x一定要生成不同的y。 （3）由y的值无法倒算x的值。哈希函数实际性质：哈希函数函数 y=H(x)满足（1）将任意长度的比特串x压缩成为固定长度的比
2、特串y。（2）已知x，计算y=H(x)很容易；已知y，找一个x满足y=H(x)却很困难。这一性质称为单向性。（3）找(x1，x2)，x1x2，H(x1)= H(x2)，很困难。这一性质称为无碰撞性。这样的函数称为哈希函数。2022-1-20华中农业大学信息学院5Hash函数函数n浓缩任意长的消息浓缩任意长的消息M到一个固定到一个固定长度的取值长度的取值 h = H(M) n通常假设通常假设hash函数是公开的且不函数是公开的且不使用密钥（使用密钥（MAC使用密钥）使用密钥）nHash函数用户检测对消息的改变函数用户检测对消息的改变n多种方式工作方式多种方式工作方式n常用于产生数字签名常用于产生
3、数字签名2022-1-20华中农业大学信息学院6Hash算法算法nHash函数和分组密码的发展变化具有相函数和分组密码的发展变化具有相似性似性q穷举攻击能力的增强穷举攻击能力的增强q算法的不断改进算法的不断改进q分组密码：从分组密码：从DES 到到 AES qHash算法算法: 从从MD4 、MD5 到到 SHA-1、RIPEMD-160、SHA-512、Whirlpool2022-1-20华中农业大学信息学院7哈希函数的应用哈希函数的应用n消息认证消息认证n 数字签名数字签名n 口令保护、文件完整性等口令保护、文件完整性等Hash函数用于消息认证2022-1-20华中农业大学信息学院8Has
4、h函数用于消息认证2022-1-20华中农业大学信息学院9Hash函数用于数字签名2022-1-20华中农业大学信息学院102022-1-20华中农业大学信息学院11n由由Ronald Rivest设计设计nMD2(1989), MD4(1990), MD5(1991) n产生产生128-bit的的hash值值n直到现在仍是被广泛使用的直到现在仍是被广泛使用的hash算法算法q最近已受到穷举攻击和密码分析攻击最近已受到穷举攻击和密码分析攻击n作为互联网的作为互联网的RFC1321标准标准2022-1-20华中农业大学信息学院12MD5 概览概览1.增加填充位。使得填充后的消息长度比增加填充位。
5、使得填充后的消息长度比512的某整数倍的某整数倍少少64位（即长度位（即长度 448 mod 512，64位用于存放消息的位用于存放消息的长度长度mod 264的结果）的结果）2.填充长度（填充前消息的长度为填充长度（填充前消息的长度为K位，将位，将mod264 的结的结果填充到第一步的最后，最低有效位在前。）果填充到第一步的最后，最低有效位在前。）3.初始化初始化MD缓冲区缓冲区(A, B, C, D) : 4个字共个字共128-bit，每字，每字32bit.A = 67452301 B = EFCDAB89C = 98BADCFE D = 103254764.以以16个字（个字（512bi
6、ts）为分组处理消息）为分组处理消息q用用4轮（轮（64次迭代）以次迭代）以16位操作对消息分组和缓冲区进行位操作对消息分组和缓冲区进行处理处理q把输出与缓冲输入相加作为新的缓冲值把输出与缓冲输入相加作为新的缓冲值 5.把最后的缓冲值作为把最后的缓冲值作为hash输出值（输出值（128比特）比特）2022-1-20华中农业大学信息学院13MD5 处理过程处理过程n CV0 = IVn CVq+1 = SUM32 CVq, RFI(Yq, RFH(Yq, RFG(Yq, RFF(Yq, CVq)n MD = CVL-1其中：其中：IV = 第三步定义的缓冲区第三步定义的缓冲区ABCD的初值的初值
7、Yq = 消息的第消息的第q个个512位分组位分组L = 消息分组的个数（包括填充位和长度域）消息分组的个数（包括填充位和长度域）CVq = 处理消息的第处理消息的第q个分组时所使用的链接变量个分组时所使用的链接变量RFx = 使用基本逻辑函数使用基本逻辑函数x的轮函数的轮函数MD = 消息摘要消息摘要SUM32 = 对输入字分别执行模对输入字分别执行模232加法加法2022-1-20华中农业大学信息学院14MD5 Overview2022-1-20华中农业大学信息学院152022-1-20华中农业大学信息学院16MD5 压缩函数压缩函数n每一轮都由每一轮都由16步迭代构成步迭代构成: a =
8、 b + ( ( a + g( b, c, d ) + X k + T i ) s ) na, b, c, d 表示缓冲区的表示缓冲区的4个个32位字位字,按照一定次序随迭代步骤而按照一定次序随迭代步骤而变化变化q每次迭代只更新缓冲区中的一个字每次迭代只更新缓冲区中的一个字aq16次迭代后，每个字被更新次迭代后，每个字被更新4次次n其中其中g ( b, c, d )表示每一轮的非线性函数，四轮依次为表示每一轮的非线性函数，四轮依次为( F, G, H, I )n s：32位的变量循环左移位的变量循环左移s位位nXk = Mq x 16 + k = 消息第消息第q个个512位分组的第位分组的第k
9、个个32位字位字nT i 是由是由 sin 导出的导出的 32 bit 的常量的常量n+ ：模：模232加法加法2022-1-20华中农业大学信息学院17MD5 压缩函数压缩函数2022-1-20华中农业大学信息学院182022-1-20华中农业大学信息学院192022-1-20华中农业大学信息学院202022-1-20华中农业大学信息学院212022-1-20华中农业大学信息学院222022-1-20华中农业大学信息学院232022-1-20华中农业大学信息学院24MD5的强度的强度nMD5的的hash值依赖于消息的所有比特位值依赖于消息的所有比特位nRivest声称它对于已知攻击安全性足够
10、好声称它对于已知攻击安全性足够好:qBerson 92 采用差分的方法对单轮的攻击采用差分的方法对单轮的攻击qBoer & Bosselaers 93 说明了如何找到碰撞说明了如何找到碰撞qDobbertin 96 提出的攻击对提出的攻击对MD5最具威胁，可使最具威胁，可使MD5压缩函数产生碰撞。压缩函数产生碰撞。n结论是结论是MD5似乎不久就会有风险似乎不久就会有风险2022-1-20华中农业大学信息学院252022-1-20华中农业大学信息学院2612.2 安全安全Hash算法算法(SHA-1)nSHA 由由NIST 和和NSA在在1993年提出年提出, 修订版于修订版于 1995年发布，
11、称作年发布，称作SHA-1n作为美国作为美国DSA数字签名方案的标准数字签名方案的标准qFIPS 180-1 1995, Internet RFC3174q注意：算法是注意：算法是SHA, 标准称为标准称为SHS n产生产生160-bit hash值值 n现在作为建议的现在作为建议的hash算法算法 n基于基于MD4的设计的设计2022-1-20华中农业大学信息学院27SHA 概览概览1.增加填充位增加填充位 2.填充长度填充长度3.初始化初始化5个字个字(160-bit) 缓冲区缓冲区(A, B, C, D, E) 为为 (67452301, efcdab89, 98badcfe, 1032
12、5476, c3d2e1f0) 4.以以16个字（个字（512-bit ）为分组处理消息）为分组处理消息:q将分组的将分组的16个字扩充为个字扩充为80个字用于压缩过程中个字用于压缩过程中q4轮，每轮轮，每轮20步迭代步迭代q把输出和输入相加以形成新的缓冲区取值把输出和输入相加以形成新的缓冲区取值5.将最后缓冲区的值作为将最后缓冲区的值作为hash值输出值输出2022-1-20华中农业大学信息学院282022-1-20华中农业大学信息学院29SHA-1 压缩函数压缩函数n每轮每轮20步迭代步迭代:(A, B, C, D, E) - (E + f(t, B ,C, D) + (A5)+Wt+Kt
13、), A, (B30), C, D)na, b, c, d, e指缓冲区的指缓冲区的5个字个字nt 是迭代步数，是迭代步数，0t79nf(t, B, C, D) 为第为第t步所用的非线性函数步所用的非线性函数nWt 从当前消息分组中导出的从当前消息分组中导出的32位的字位的字nKt 加法常量加法常量2022-1-20华中农业大学信息学院30SHA-1 压缩函数压缩函数2022-1-20华中农业大学信息学院312022-1-20华中农业大学信息学院322022-1-20华中农业大学信息学院33SHA-1 verses MD5n穷举攻击更加困难（穷举攻击更加困难（SHA-1:160, MD5:12
14、8） n对已知攻击不存在风险对已知攻击不存在风险 (与与 MD4/5相比相比)（SHA-1的设计原则尚未公开）的设计原则尚未公开） n速度比速度比MD5慢慢 (80 步，步，64 步步) n两者设计都很简单紧凑两者设计都很简单紧凑n低位结构和高位结构低位结构和高位结构qMD5:低位结构低位结构 SHA-1:高位结构高位结构2022-1-20华中农业大学信息学院34SHA的修改的修改nNIST1981年已经发布了年已经发布了FIPS 180-2n除除SHA-1外，新增加了外，新增加了3个个hash算法：算法： SHA-256, SHA-384, SHA-512，消息摘要的长度分别为：消息摘要的长度分别为：256，384，512n与与AES增强安全性相适应增强安全性相适应n结构和细节与结构和细节与SHA-1相似相似n与与SHA-1具有相同的抗密码分析攻击的能力具有相同的抗密码分析攻击的能力2022-1-20华中农业大学信息学院352022-1-20华中农业大学信息学院36推荐的推荐的SHA标准标准2022-1-20华中农业大学信息学院37小小 结结nHash函数函数qMD5qSHA-12022-1-20华中农业大学信息学院38第第12章作业章作业n思考题：思考题：12.4 或或 12.5
