第17讲Hash函数.

第8章Hash函数Hash函数定义数据安全机密性完整性认证性密码技术主要保证数据的机密性Hash函数能保证数据的完整性和认证性Hash函数定义Hash函数常用来构造数据的短“指纹”：消息的发送者使用所有的消息产生一个附件也就是短“指纹”，并将该短“指纹”与消息一起传输给接收者。即使数据存储在不安全的地方，接收者重新计算数据的指纹，并验证指纹是否改变，就能够检测数据的完整性。这是因为一旦数据在中途被破坏，或改变，短指纹就不再正确。Hash函数定义Hash函数定义：Hash函数是一个将任意长度的消息（message）映射成固定长度消息的函数。Hash函数是一个函数，它以一个变长的报文作为输入，并产生一个定长的散列码，有时也称为报文摘要，作为函数的输出。Hash函数（hashfunction），或称为哈希函数、散列函数。对于任何消息x，将h(x)称为x的Hash值、散列值、消息摘要（messagedigest）。Hash函数作用Hash函数最主要的作用于是用于鉴别，鉴别在网络安全中起到举足轻重的地位。鉴别的目的有以下两个：第一，验证信息的发送者是真正的，而不是冒充的，同时发信息者也不能抵赖，此为信源识别；第二，验证信息完整性，在传递或存储过程中未被篡改，重放或延迟等。8.1Hash函数的性质Hash函数的碰撞（collision）设x、x’是两个不同的消息，如果h(x)=h(x’)则称x和x’是Hash函数h的一个（对）碰撞.8.1Hash函数的性质Hash函数的分类单向Hash函数（oneway）•给定一个Hash值y，如果寻找一个消息x，使得y=h(x)是计算上不可行的，则称h是单向Hash函数.弱抗碰撞Hash函数（weaklycollisionfree）•任给一个消息x，如果寻找另一个不同的消息x’，使得h(x)=h(x’)是计算上不可行的，则称h是弱抗碰撞Hash函数.强抗碰撞Hash函数（stronglycollisionfree）•如果寻找两个不同的消息x和x’，使得h(x)=h(x’)是计算上不可行的，则称h是强抗碰撞Hash函数.8.1Hash函数的性质hash函数在现代密码学中起着重要的作用，主要用于对数据完整性和消息认证压缩性：任意长度的数据，算出的摘要长度都固定。容易计算：从原数据容易算出摘要。抗修改性：对原数据进行任何改动，哪怕只修改1个字节，所得到的摘要都有很大区别。弱抗碰撞：已知原数据和其摘要，想找到一个具有相同摘要的数据（即伪造数据），在计算上是困难的。强抗碰撞：想找到两个不同的数据，使它们具有相同的摘要，在计算上是困难的。Hash函数的安全性对Hash函数的攻击是指寻找一对碰撞消息的过程与传统密码体制的攻击方式相比，对散列函数的攻击方法主要有两种：穷举攻击：它可以用于任何类型的散列函数的攻击，最典型的方式就是所谓的“生日攻击”。采用生日攻击的攻击者将产生许多明文消息，然后计算这些明文消息的指纹（摘要），进行比较。利用散列函数的代数结构：攻击其函数的弱性质。通常的有中间相遇攻击、修正分组攻击和差分分析攻击等。生日悖论（birthdayparadox）生日问题：假设每个人的生日是等概率的，每年有365天，在k个人中至少有两个人的生日相同的概率大于1/2，问k最小应是多少？k人生日都不同的概率是：.36511...3652136511k有P(365,23)=0.5073。即在23个人中，至少有两个人生日相同的概率大于0.5，这个数字比人们直观猜测的结果小得多，因而称为生日悖论。.36511...36521365111),365(kkP2k人生日相同的概率为：人中至少有生日攻击法生日悖论原理可以用于构造对Hash函数的攻击设Hash函数值有n个比特，m是真消息，M是伪造的假消息，分别把消息m和M表示成r和R个变形的消息。消息与其变形消息具有不同的形式，但有相同的含义。将消息表示成变形消息的方法很多，例如增加空格、使用缩写、使用意义相同的单词、去掉不必要的单词等。Hash函数的安全性Hash函数的安全性生日攻击法分别把消息m和M表示成r和R个变形的消息生日攻击法计算真消息m的变形与假消息M的变形发生碰撞的概率由于n比特长的散列值共有2n个，所以对于给定m的变形mi和M的变形Mj，mi与Mj不碰撞的概率是1-1/2n。由于M共有R个变形，所以M的全部变形都不与mi碰撞的概率是：11/2.RnHash函数的安全性因为消息m共有r个变形，因此m的变形与M的变形都不碰撞的概率是：.2/1rRn1m的变形与M的变形发生碰撞的概率是：.12111)(2nrRrRnenP生日攻击法当r=R=2n/2时，P(n)=1e10.63。对于Hash值长度为64比特的Hash函数，生日攻击的时间复杂度约为232，所以是不安全的。为了抵抗生日攻击，建议Hash值长度至少为128比特.Hash函数的安全性8.2基于分组密码的Hash函数基于分组密码的CBC工作模式的Hash函数H首先选取一个初始向量令然后计算基于分组密码的CFB工作模式的Hash函数H令然后计算首先选取一个初始向量8.3hash函数MD4MD4是麻省理工学院教授RonaldRivest于1990年设计的一种信息摘要算法。它是一种用来测试信息完整性的密码散列函数的实行。其摘要长度为128位。这个算法影响了后来的算法如MD5、SHA家族和RIPEMD等。MD5算法是1991年发布的一项数字签名加密算法，它当时解决了MD4算法的安全性缺陷，成为应用非常广泛的一种算法。8.3hash函数MD4MD4算法的输入可以是任意长度的消息x，对输入消息按512位的分组为单位进行处理，输出128位的散列值MD(x)。整个算法分为五个步骤。步骤1:增加填充位步骤2:附加消息长度值步骤3:初始化MD缓冲区步骤4:以512位的分组(16个字)为单位处理消息步骤5:输出消息的预处理步骤：设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的右端。步骤1:增加填充位在消息x右边增加若干比特，使其长度与448模512同余。也就是说，填充后的消息长度比512的某个倍数少64位。即使消息本身已经满足上述长度要求，仍然需要进行填充。例如，若消息长为448，则仍需要填充512位使其长度为960位。填充位数在1到512之间。填充比特的第一位是1，其它均为0。步骤2:附加消息长度值用64位表示原始消息x的长度，并将其附加在步骤1所得结果之后。若填充前消息长度大于等于264，则使用其64位。填充方法是把64比特的长度分成两个32比特的字，低32比特字先填充，高32比特字后填充。步骤1与步骤2一起称为消息的预处理经预处理后，原消息长度变为512的倍数设原消息x经预处理后变为消息Y=Y0Y1…YN1，其中Yi（i=0,1,…,N1）是32比特在后面的步骤中，将对512比特的分组Yi进行处理例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.例8.1假设消息为:x=“abcde”=0110000101100010011000110110010001100101=(6162636465)16,|x|=40=(28)16.•经步骤2处理后的比特串为（16进制表示）：x2=x1||28(64位)=61626364658000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002800000000000000.步骤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.步骤4:以512位的分组(16个字)为单位处理消息MD4是迭代Hash函数,其压缩函数为:步骤4是MD4算法的主循环，它以512比特作为分组，重复应用压缩函数HMD4，从消息Y的第一个分组Y0开始，依次对每16个分组Yi进行压缩，直至最后分组N/16-1，然后输出消息x的Hash值。可见，MD4的循环次数等于消息Y中512比特分组的数目L。.}1,0{}1,0{:1285121284MDH步骤5:输出依次对消息的L个512比特的分组进行处理，第L个分组处理后的输出值即是消息x的散列值MD(x)。8.3Hash函数MD4MD4算法如下①设A、B、C、D是四个32位的寄存器,其初值(用十六进制表示)分别为A=67452301、B=efcdab89、C=98badcfe、D=10325476:②对i=0至N/16-1执行第3步至第8步③对j=0至15执行X[j]=M[16i+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点此查看Round1点此查看Round2点此查看Round38.4安全Hash算法SHA安全Hash算法SHA（securehashalgorithm）由美国标准与技术研究所（NIST）设计并于1993年作为联邦信息处理标准（FIPS180）发布修改版于1995年发布（FIPS1801），通常称之为SHA1。该标准称为安全Hash函数。RFC3174也给出了SHA1，它基本上是复制FIPS1801的内容，但增加了C代码实现。SHA1算法的输入是长度小于264的任意消息x，输出160位的散列值。8.4安全Hash算法SHASHA1处理消息的过程与MD4类似，对输入消息按512位的分组为单位进行处理，整个算法分为五个步骤步骤1:增加填充位在消息右边增加若干比特，使其长度与448模512同余。即使消息本身已经满足上述长度要求，仍然需要进行填充。填充位数在1到512之间。填充比特的第一位是“1”，其它均为“0”。8.4安全Hash算法SHA步骤2:附加消息长度值用64位表示原始消息x的长度，并将其附加在步骤1所得结果之后。步骤1与步骤2一起称为消息的预处理经预处理后，原消息长度变为512的倍数。设原消息x经预处理后变为消息