密码学（第十三讲）HASH函数张焕国武汉大学计算机学院目录密码学的基本概念1、密码学2、古典、古典密码3、数据加密标准（）DES）、数据加密标准（DES4、高级）AES）数据加密标准（AES高级数据加密标准（5、中国商用密码（）SMS4）、中国商用密码（SMS46、分组密码的应用技术7、序列密码8、习题课：复习对称密码、公开密钥密码（11）9、公开密钥密码（目录公开密钥密码（22）1010、11、数字签名（1）12、数字签名（2）13、、HASH函数131414、15、15PKI技术1616、、PKI17、习题课：复习公钥密码18、总复习一、HASH 函数函数的概念的概念1、Hash Hash的作用的作用•Hash Hash码也称报文摘要码也称报文摘要。

•它具有极强的错误检测能力错误检测能力。

•用Hash Hash码作码作MAC ，可用于认证认证。

•用Hash Hash码辅助码辅助数字签名数字签名。

•Hash Hash函数可用于函数可用于保密保密。

一、HASH 函数的概念2、Hash Hash函数的定义函数的定义①Hash Hash函数将任意长的数据函数将任意长的数据M 变换为定长的码h ，记为记为：：h=HASH(M)h=HASH(M)或或h=H(M)h=H(M)。

②实用性：对于给定的数据对于给定的数据M M ，计算，计算h=HASH(M)h=HASH(M)是是高效的。

③安全性安全性：：•单向性：对给定的对给定的Hash Hash值值h ，找到满足H(x)H(x)＝＝h 的x 在计算上是不可行的计算上是不可行的。

否则否则，，设传送数据为设传送数据为C=C=＜＜M ，H(M||K )＞,K 是密钥。

攻击者可以截获攻击者可以截获C,C,求出求出Hash 函数的逆函数的逆，，从而得出M||S ＝H -1(C)，然后从M 和M ||Ｋ即可即可得出得出Ｋ。

一、HASH 函数的概念2、Hash Hash函数的定义函数的定义③安全性安全性：：•抗弱碰撞性：对任何给定的对任何给定的x x ，找到满足找到满足y≠x y≠x且H(x)=H(y)H(x)=H(y)的的y 在计算上是不可行的在计算上是不可行的。

否则否则，，攻击者可以截获报文M 及其Hash 函数值H(M)，并找出另一报文M ′使得H(M ′)=H(M)。

这样攻击者可用M ′去冒充M ，而收方不能发现而收方不能发现。

•抗强碰撞性：找到任何满足H(x)=H(y)的偶对(x,y)在计算上是不可行的在计算上是不可行的。

一、HASH 函数的概念3、安全安全Hash Hash函数的一般结构函数的一般结构•Merkle Merkle提出了安全提出了安全Hash Hash函数主处理的一般结构函数主处理的一般结构•对数据压缩对数据压缩，，产生产生Hash Hash码码。

b 位分组位分组，，f 为压缩函数，L 轮链接迭代，n 位输出位输出。

f f f M 0M L -1M 1b 位b 位b 位n 位n 位n 位n 位IV=CV 0CV 1CV L -1HASH 值CV L一、HASH 函数的概念3、安全安全Hash Hash函数的一般结构函数的一般结构•分组：将输入分为L -1个大小为b 位的分组位的分组。

•填充：若第L -1个分组不足b 位，则将其填充为b 位。

•附加：再附加上一个表示输入的总长度分组。

•共L 个大小为b 位的分组位的分组。

•由于输入中包含长度由于输入中包含长度，，所以攻击者必须找出具有相同Hash 值且长度相等的两条报文值且长度相等的两条报文，，或者找出两条长度不等但加入报文长度后Hash 值相同的报文的报文，，从而增加了攻击的难度。

•目前大多数Hash 函数均采用这种结构。

二、SHA SHA--1 HASH 函数1、SHA 系列系列Hash Hash函数函数•SHA 系列系列Hash Hash函数函数是由美国标准与技术研究所(NIST)设计的设计的。

•1993年公布了SHA SHA--0(FIPS PUB 180180))，后来发现它不安全安全。

•1995年又公布了SHA SHA--1（FIPS PUB 180180--1）。

•2002年又公布了SHA SHA--2（FIPS PUB 180180--2）。

SHA SHA--2包括3个Hash Hash函数：函数：SHA SHA--256，SHA SHA--384，SHA SHA--512•2005年王小云给出一种攻击SHA SHA--1的方法的方法，，用269操作找到一个碰撞找到一个碰撞，，以前认为是280。

•NIST 打算2010年废弃SHA SHA--1。

二、SHA SHA--1 HASH 函数1、SHA 系列系列Hash Hash函数函数•SHA SHA--1是在MD MD55的基础上发展起来的的基础上发展起来的。

它采用Merkle Merkle提出了安全提出了安全Hash Hash结构结构。

已被美国政府和许多国际组织采纳作为标准。

•SHA SHA--1的输入为长度小于264位的报文，输出为160位的报文摘要，该算法对输入按512位进行分组位进行分组，，并以分组为单位进行处理处理。

2、SHA SHA--1的结构•采用采用Merkle Merkle提出了安全提出了安全Hash Hash结构结构输入填充初始化缓冲区主处理160位HASH 值二、SHA SHA--1 HASH 函数输出报文长度< 2643、运算算法⑴输入输入填充填充•目的是使填充后的报文长度满足目的是使填充后的报文长度满足：：长度=448mod 512。

①填充方法是在报文后附加一个一个11和若干个和若干个00。

②然后附上表示填充前报文长度的64位数据(最高有效位在前)。

•若报文本身已经满足上述长度要求若报文本身已经满足上述长度要求，，仍然需要进行填充（例如例如，，若报文长度为若报文长度为448448位位，则仍需要填充则仍需要填充512512位位使其长度为使其长度为960960位位），因此填充位数在因此填充位数在11到512512之间之间。

二、SHA SHA--1 HASH 函数3、运算算法⑵初始化缓冲区•缓冲区由5个32位的寄存器(A ，B ，C ，D ，E )组成组成，，用于保存160位的中间结果和最终结果位的中间结果和最终结果。

•将寄存器初始化为下列32位的整数：A ：67452301B ：EFCDAB EFCDAB8989C ：9898BADCFE BADCFE D ：10325476E ：C 3D 2E 1F 0注意：高有效位存于低地址注意：高有效位存于低地址。

二、SHA SHA--1 HASH 函数3、运算算法⑶主处理•主处理是SHA SHA--1HASH 函数的核心函数的核心。

•每次处理一个512位的分组，循环次数为填充后报文的分组数L 。

二、SHA SHA--1 HASH 函数3、运算算法⑶主处理•主处理的结构：f 为SHA SHA--1的压缩函数的压缩函数。

f ffBLK 0BLK L -1BLK 1512位512位512位160位160位160位160位IV=CV 0CV 1CV L -1HASH 值二、SHA SHA--1 HASH 函数CV L3、运算算法⑶主处理•压缩函数是主处理的核心压缩函数是主处理的核心。

•它由四层运算它由四层运算（（每层20步迭代步迭代））组成组成，，四层的运算结构相同构相同。

•每轮的输入是当前要处理的512位的分组BLK 和160位缓冲区ABCDE 的内容的内容，，每层都对ABCDE 的内容更新的内容更新，，而且每轮使用的逻辑函数不同而且每轮使用的逻辑函数不同，，分别为f 1,f 2,f 3和f 4。

•第四层的输出与第一层的输入相加得到压缩函数的输出。

二、SHA SHA--1 HASH 函数二、SHA SHA--1 HASH 函数第一轮使用函数f 1第二轮使用函数f 2第三轮使用函数f 3第四轮使用函数f 4A B CD E A B CD E A B CD E A B CD E ＋＋＋＋＋CV i 160位BLK i 160位512位Cv i+1Cv i20步迭代20步迭代20步迭代20步迭代3、运算算法⑷输出•所有的L 个512位的分组处理完后，第L 个分组的输出即是160位的报文摘要位的报文摘要。

二、SHA SHA--1 HASH 函数3、运算算法⑸归纳•CV 0＝IV （ABCDE 的初值的初值））•CV i+i+11＝CV i0≤i ≤L -1CV i+i+11(0)＝CV i (0)+A iCV i+i+11(1)＝CV i (1)+B iCV i+i+11(2)＝CV i (2)+C i CV i+i+11(3)＝CV i (3)+D i CV i+i+11(4)＝CV i (4)+E iz h ＝CV L二、SHA SHA--1 HASH 函数+ 为模232加法3、运算算法⑹压缩函数缺点：输出B=输入A输出D=输入C 输出E=输入DA 、C 、D 没有运算二、SHA SHA--1 HASH 函数ABC DE A B C D E＋＋＋＋f t <<5<<30W t K t3、运算算法⑹压缩函数•每步具有下述形式：A,B,C,D,E ←(E+f t (B,C,D)+(A<<(B,C,D)+(A<<55)+W t +K t ),A,(B<<),A,(B<<3030),C,D ),C,D •每轮对A,B,C,D,E 进行20次迭代次迭代，，四轮共80次迭代次迭代。

t 为迭代次数编号为迭代次数编号，，所以0≤t ≤79。

•其中其中，，f t (B,C,D)=第t 步使用的基本逻辑函数；<<s =32位的变量循环左移s 位W t =从当前分组BLK 导出的32位的字K t =加法常量加法常量，，共使用4个不同的加法常量个不同的加法常量。

+为模232加法二、SHA SHA--1 HASH 函数3、运算算法⑹压缩函数•逻辑函数f t每层使用一个逻辑函数每层使用一个逻辑函数，，其输入均为B,C,D(每个32位)，输出为一个32位的字位的字。

定义分别为：第一层0≤t ≤19f 1=f t (B,C,D)=(B ∧C)∨(¬B ∧D)第二层20≤t ≤39f 2=f t (B,C,D)=B ⊕C ⊕D第三层40≤t ≤59f 3=f t (B,C,D)=(B ∧C)∨(B ∧D) ∨(C ∧D)第三层60≤t ≤79f 4=f t (B,C,D)=B ⊕C ⊕D•缺点：f 2和f 4都是线性函数。

二、SHA SHA--1 HASH 函数3、运算算法⑹压缩函数•加法常量K t每层使用一个加法常量每层使用一个加法常量。