第17讲 Hash 函数（课堂PPT）

第8章Hash函数,1,Hash函数定义,数据安全机密性完整性认证性密码技术主要保证数据的机密性Hash函数能保证数据的完整性和认证性,2,Hash函数定义,Hash函数常用来构造数据的短“指纹”：消息的发送者使用所有的消息产生一个附件也就是短“指纹”，并将该短“指纹”与消息一起传输给接收者。即使数据存储在不安全的地方，接收者重新计算数据的指纹，并验证指纹是否改变，就能够检测数据的完整性。这是因为一旦数据在中途被破坏，或改变，短指纹就不再正确。,3,Hash函数定义,Hash函数定义：Hash函数是一个将任意长度的消息（message）映射成固定长度消息的函数。Hash函数是一个函数，它以一个变长的报文作为输入，并产生一个定长的散列码，有时也称为报文摘要，作为函数的输出。Hash函数（hashfunction），或称为哈希函数、散列函数。对于任何消息x，将h(x)称为x的Hash值、散列值、消息摘要（messagedigest）。,4,Hash函数作用,Hash函数最主要的作用于是用于鉴别，鉴别在网络安全中起到举足轻重的地位。鉴别的目的有以下两个：第一，验证信息的发送者是真正的，而不是冒充的，同时发信息者也不能抵赖，此为信源识别；第二，验证信息完整性，在传递或存储过程中未被篡改，重放或延迟等。,5,8.1Hash函数的性质,Hash函数的碰撞（collision）设x、x是两个不同的消息，如果h(x)=h(x)则称x和x是Hash函数h的一个（对）碰撞.,6,8.1Hash函数的性质,Hash函数的分类单向Hash函数（oneway）给定一个Hash值y，如果寻找一个消息x，使得y=h(x)是计算上不可行的，则称h是单向Hash函数.弱抗碰撞Hash函数（weaklycollisionfree）任给一个消息x，如果寻找另一个不同的消息x，使得h(x)=h(x)是计算上不可行的，则称h是弱抗碰撞Hash函数.强抗碰撞Hash函数（stronglycollisionfree）如果寻找两个不同的消息x和x，使得h(x)=h(x)是计算上不可行的，则称h是强抗碰撞Hash函数.,7,8.1Hash函数的性质,hash函数在现代密码学中起着重要的作用，主要用于对数据完整性和消息认证压缩性：任意长度的数据，算出的摘要长度都固定。容易计算：从原数据容易算出摘要。抗修改性：对原数据进行任何改动，哪怕只修改1个字节，所得到的摘要都有很大区别。弱抗碰撞：已知原数据和其摘要，想找到一个具有相同摘要的数据（即伪造数据），在计算上是困难的。强抗碰撞：想找到两个不同的数据，使它们具有相同的摘要，在计算上是困难的。,8,Hash函数的安全性,对Hash函数的攻击是指寻找一对碰撞消息的过程与传统密码体制的攻击方式相比，对散列函数的攻击方法主要有两种：穷举攻击：它可以用于任何类型的散列函数的攻击，最典型的方式就是所谓的“生日攻击”。采用生日攻击的攻击者将产生许多明文消息，然后计算这些明文消息的指纹（摘要），进行比较。利用散列函数的代数结构：攻击其函数的弱性质。通常的有中间相遇攻击、修正分组攻击和差分分析攻击等。,9,生日悖论（birthdayparadox）生日问题：假设每个人的生日是等概率的，每年有365天，在k个人中至少有两个人的生日相同的概率大于1/2，问k最小应是多少？k人生日都不同的概率是：,10,有P(365,23)=0.5073。即在23个人中，至少有两个人生日相同的概率大于0.5，这个数字比人们直观猜测的结果小得多，因而称为生日悖论。,11,生日攻击法生日悖论原理可以用于构造对Hash函数的攻击设Hash函数值有n个比特，m是真消息，M是伪造的假消息，分别把消息m和M表示成r和R个变形的消息。消息与其变形消息具有不同的形式，但有相同的含义。将消息表示成变形消息的方法很多，例如增加空格、使用缩写、使用意义相同的单词、去掉不必要的单词等。,Hash函数的安全性,12,Hash函数的安全性,生日攻击法分别把消息m和M表示成r和R个变形的消息,13,生日攻击法计算真消息m的变形与假消息M的变形发生碰撞的概率由于n比特长的散列值共有2n个，所以对于给定m的变形mi和M的变形Mj，mi与Mj不碰撞的概率是1-1/2n。由于M共有R个变形，所以M的全部变形都不与mi碰撞的概率是：,Hash函数的安全性,14,因为消息m共有r个变形，因此m的变形与M的变形都不碰撞的概率是：,m的变形与M的变形发生碰撞的概率是：,15,生日攻击法,当r=R=2n/2时，P(n)=1e10.63。对于Hash值长度为64比特的Hash函数，生日攻击的时间复杂度约为232，所以是不安全的。,为了抵抗生日攻击，建议Hash值长度至少为128比特.,Hash函数的安全性,16,8.2基于分组密码的Hash函数,17,8.3hash函数MD4,MD4是麻省理工学院教授RonaldRivest于1990年设计的一种信息摘要算法。它是一种用来测试信息完整性的密码散列函数的实行。其摘要长度为128位。这个算法影响了后来的算法如MD5、SHA家族和RIPEMD等。MD5算法是1991年发布的一项数字签名加密算法，它当时解决了MD4算法的安全性缺陷，成为应用非常广泛的一种算法。,18,8.3hash函数MD4,MD4算法的输入可以是任意长度的消息x，对输入消息按512位的分组为单位进行处理，输出128位的散列值MD(x)。整个算法分为五个步骤。步骤1:增加填充位步骤2:附加消息长度值步骤3:初始化MD缓冲区步骤4:以512位的分组(16个字)为单位处理消息步骤5:输出,19,消息的预处理步骤：,设x是一个消息,用二进制表示。首先由x生成一个数组,是长度为32比特(bit)的(0,1)序列,M由x生成：,d=(447-|x|)mod512,令l为的二进制表示。l的长度为64比特(bit)。如果l的长度不足64比特(bit),则在l的左端添0补足,M=,这里|x|表示x的长度,|表示序列的联接,譬如x|y表示将序列y排在序列x的右端。,20,步骤1:增加填充位在消息x右边增加若干比特，使其长度与448模512同余。也就是说，填充后的消息长度比512的某个倍数少64位。即使消息本身已经满足上述长度要求，仍然需要进行填充。例如，若消息长为448，则仍需要填充512位使其长度为960位。填充位数在1到512之间。填充比特的第一位是1，其它均为0。,21,步骤2:附加消息长度值,用64位表示原始消息x的长度，并将其附加在步骤1所得结果之后。若填充前消息长度大于等于264，则使用其64位。填充方法是把64比特的长度分成两个32比特的字，低32比特字先填充，高32比特字后填充。,22,步骤1与步骤2一起称为消息的预处理经预处理后，原消息长度变为512的倍数设原消息x经预处理后变为消息Y=Y0Y1YN1，其中Yi（i=0,1,N1）是32比特在后面的步骤中，将对512比特的分组Yi进行处理,23,例8.1假设消息为:x=“abcde”=0110000101100010011000110110010001100101=(6162636465)16,|x|=40=(28)16.步骤1在x的右边填充1个“1”和407个“0”，将x变成448比特的x1:x1=x|1|0(407个)=x|800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000.=6162636465800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000.,24,例8.1假设消息为:x=“abcde”=0110000101100010011000110110010001100101=(6162636465)16,|x|=40=(28)16.经步骤2处理后的比特串为（16进制表示）：x2=x1|28(64位)=61626364658000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002800000000000000.,25,步骤3:初始化MD缓冲区MD4算法的中间结果和最终结果都保存在128位的缓冲区里，缓冲区用4个32位的寄存器表示。4个缓冲区记为A、B、C、D，其初始值为下列32位整数（16进制表示）：A=67452301,B=EFCDAB89,C=98BADCFE,D=10325476.上述初始值以小端格式存储(字的最低有效字节存储在低地址位置)为：字A=01234567,字B=89ABCDEF,字C=FEDCBA98,字D=76543210.,26,步骤4:以512位的分组(16个字)为单位处理消息MD4是迭代Hash函数,其压缩函数为:,步骤4是MD4算法的主循环，它以512比特作为分组，重复应用压缩函数HMD4，从消息Y的第一个分组Y0开始，依次对每16个分组Yi进行压缩，直至最后分组N/16-1，然后输出消息x的Hash值。可见，MD4的循环次数等于消息Y中512比特分组的数目L。,27,步骤5:输出依次对消息的L个512比特的分组进行处理，第L个分组处理后的输出值即是消息x的散列值MD(x)。,28,8.3Hash函数MD4,MD4算法如下,设A、B、C、D是四个32位的寄存器,其初值(用十六进制表示)分别为A=67452301、B=efcdab89、C=98badcfe、D=10325476:,对i=0至N/16-1执行第3步至第8步,对j=0至15执行Xj=M16i+j,将寄存器A、B、C、D中的值存储到另外四个寄存器AA、BB、CC、DD中,AA=A，BB=B，CC=C，DD=D,执行Round1,执行Round2,执行Round3,A=A+AA，B=B+BB，C=C+CC，D=D+DD,29,8.4安全Hash算法SHA,安全Hash算法SHA（securehashalgorithm）由美国标准与技术研究所（NIST）设计并于1993年作为联邦信息处理标准（FIPS180）发布修改版于1995年发布（FIPS1801），通常称之为SHA1。该标准称为安全Hash函数。RFC3174也给出了SHA1，它基本上是复制FIPS1801的内容，但增加了C代码实现。SHA1算法的输入是长度小于264的任意消息x，输出160位的散列值。,30,8.4安全Hash算法SHA,SHA1处理消息的过程与MD4类似，对输入消息按512位的分组为单位进行处理，整个算法分为五个步骤步骤1:增加填充位在消息右边增加若干比特，使其长度与448模512同余。即使消息本身已经满足上述长度要求，仍然需要进行填充。填充位数在1到512之间。填充比特的第一位是“1”，其它均为“0”。,31,8.4安全Hash算法SHA,步骤2:附加消息长度值用64位表示原始消息x的长度，并将其附加在步骤1所得结果之后。步骤1与步骤2一起称为消息的预处理经预处理后，原消息长度变为512的倍数。设原消息x经预处理后变为消息M=M0M1MN1，其中Mi（i=0,1,N1）是32比特。在后面的步骤中，将对512比特的分组进行处理。,32,8.4安全Hash算法SHA,步骤3:初始化缓冲区SHA1算法的中间结果和最终结果保存在160位的缓冲区里，缓冲区用5个32位的寄存器表示。5个缓冲区记为A、B、C、D、E，其初始值为下列32位整数（16进制表示）：A=67452301,B=EFCDAB89,C=98BADCFE,D=10325476,E=C3D2E1F0.其中，前4个初始值与MD5的初始值相同。SHA1以大端格式存储缓冲区的值，即字的最高有效字节存于低地址字节位置。因此，上述初始值存储为（十六进制）：字A=67452301,字B=EFCDAB89,字C=98BADCFE,字D=10325476,字E=C3D2E1F0.,33,8.4安全Hash算法SHA,步骤4:以512位的分组（16个字）为单位处理消息SHA1是迭代Hash函数，其压缩函数为：,步骤4是SHA1算法的主循环，它以512比特作为分组，重复应用压缩函数HSHA，从消息的第一个分组开始，依次对每个分组进行压缩，直至最后分组，然后输出消息x的Hash值。SHA1循环次数等于消息中512比特分组的数目L。,34,SHA1的压缩函数HSHA,由四轮处理组成加法是模232相加,35,SHA1的压缩函数HSHA,压缩函数HSHA的四轮处理过程的算法结构相同，每一轮要对缓冲区ABCDE进行20次迭代，每次迭代的运算形式为,TEMP=(A5)+ft(B,C,D)+E+Xk+KtE=DD=CC=B30B=AA=TEMP,36,SHA1的压缩函数HSHA,基本逻辑函数f每一轮使用一个基本逻辑函数f，每个基本逻辑函数的输入是三个32位的字，输出是一个32位的字，它执行位逻辑运算，即输出的第n位是其三个输入第n位的函数。,37,SHA1的压缩函数HSHA,字组Xtt（0t79）代表迭代步数，依次表示第一、二、三、四轮处理过程进行的迭代次序Xt(0t79)是32比特的字，它的前面16个字X0,X1,X15依次取自当前输入分组Mi，其余字为,加法常数表Kt,38,8.4安全Hash算法SHA,步骤5:输出第N/16个分组处理后的输出值即是消息x的散列值MD(x),39,8.4安全Hash算法SHA,SHA-1算法如下,设A、B、C、D、E是5个32位的寄存器,其初值(用十六进制表示)分别为A=67452301、B=efcdab89、C=98badcfe、D=10325476、E=c3d2e1f0,对i=0至N/16-1执行第3步至第10步,对j=0至15执行Xj=M16i+j,将寄存器A、B、C、D、E中的值存储到另外四个寄存器AA、BB、CC、DD中,AA=A，BB=B，CC=C，DD=D，EE=E,