第03章_2单向散列函数

1、12第第5章章 Hash函数与数字签名函数与数字签名l 5.2 Hash5.2 Hash函数函数MD5MD5l 5.3 5.3 安全安全HashHash算法算法SHASHA 1 1 l 5.4 5.4 基于分组密码与离散对数的基于分组密码与离散对数的HashHash函数函数l 5.5 5.5 消息认证消息认证35.1 Hash函数概述函数概述45.1.1 Hash函数定义函数定义l 数据安全数据安全u机密性机密性u完整性完整性u认证性认证性l 密码技术主要保证数据的机密性密码技术主要保证数据的机密性l Hash函数能保证数据的完整性和认证性函数能保证数据的完整性和认证性55.1.1 Hash函

2、数定义函数定义l Hash函数定义：函数定义：Hash函数是一个将任意长度的消息函数是一个将任意长度的消息（message）映射成固定长度消息的函数。）映射成固定长度消息的函数。n*n*ii*nxhyx h nA AA AA AA AA AA AA AA A)(:0任任意意长长度度消消息息集集合合消消息息集集合合长长度度为为字字母母表表 将将h称为一个称为一个Hash函数（函数（hash function），或称为哈希函），或称为哈希函数、散列函数。对于任何消息数、散列函数。对于任何消息x ，将，将h(x)称为称为x的的Hash值、值、散列值、消息摘要（散列值、消息摘要（message dig

3、est）。）。65.1.1 Hash函数定义函数定义l Hash函数的碰撞（函数的碰撞（collision） 设x、x是两个不同的消息，如果 h(x)=h(x) 则称x和x是Hash函数h的一个（对）碰撞.75.1.1 Hash函数定义函数定义l Hash函数的分类函数的分类u单向单向Hash函数（函数（one way） 给定一个给定一个Hash值值y，如果寻找一个消息，如果寻找一个消息x，使得，使得y=h (x)是计算上不可行的，则称是计算上不可行的，则称h是单向是单向Hash函数函数. u弱抗碰撞弱抗碰撞Hash函数（函数（weakly collision free） 任给一个消息任给一个

4、消息x，如果寻找另一个不同的消息，如果寻找另一个不同的消息x，使，使得得h(x) =h(x)是计算上不可行的，则称是计算上不可行的，则称h是弱抗碰撞是弱抗碰撞Hash函数函数. u强抗碰撞强抗碰撞Hash函数函数 （strongly collision free） 如果寻找两个不同的消息如果寻找两个不同的消息x和和x，使得，使得h(x)=h(x)是计是计算上不可行的，则称算上不可行的，则称h是强抗碰撞是强抗碰撞Hash函数函数. 85.1.1 Hash函数定义函数定义l 安全安全Hash函数函数h应具有以下性质：应具有以下性质：u 对任意的消息对任意的消息x，计算，计算h(x)是容易的；是容易

5、的；u h是单向的；是单向的；u h是弱抗碰撞的，或是强抗碰撞的。是弱抗碰撞的，或是强抗碰撞的。95.1 Hash函数概述函数概述105.1.2 Hash函数的安全性l 对对Hash函数的攻击是指寻找一对碰撞消息的过程函数的攻击是指寻找一对碰撞消息的过程l 生日悖论（生日悖论（birthday paradox） 生日问题：假设每个人的生日是等概率的，每年有生日问题：假设每个人的生日是等概率的，每年有365天，天，在在k个人中至少有两个人的生日相同的概率大于个人中至少有两个人的生日相同的概率大于1/2，问，问k最小最小应是多少？应是多少？ k人生日都不同的概率是：人生日都不同的概率是： .365

6、11.3652136511k.36511.36521365111),365(kkP 2k人人生生日日相相同同的的概概率率为为：人人中中至至少少有有 有有P(365,23)=0.5073。即在。即在23个人中，至少有两个人生日相个人中，至少有两个人生日相同的概率大于同的概率大于0.5，这个数字比人们直观猜测的结果小得多，这个数字比人们直观猜测的结果小得多，因而称为生日悖论。因而称为生日悖论。11l 生日攻击法生日攻击法 生日悖论原理可以用于构造对生日悖论原理可以用于构造对Hash函数的攻击函数的攻击u设设Hash函数值有函数值有n个比特，个比特，m是真消息，是真消息，M是伪造的假是伪造的假消息，

7、分别把消息消息，分别把消息m和和M表示成表示成r和和R个个变形的消息变形的消息。消。消息与其变形消息具有不同的形式，但有相同的含义。息与其变形消息具有不同的形式，但有相同的含义。将消息表示成变形消息的方法很多，例如增加空格、将消息表示成变形消息的方法很多，例如增加空格、使用缩写、使用意义相同的单词、去掉不必要的单词使用缩写、使用意义相同的单词、去掉不必要的单词等。等。5.1.2 Hash函数的安全性函数的安全性125.1.2 Hash函数的安全性函数的安全性l 生日攻击法生日攻击法u分别把消息分别把消息m和和M表示成表示成r和和R个个变形的消息变形的消息13l 生日攻击法生日攻击法u计算真消息

8、计算真消息m的变形与假消息的变形与假消息M的变形发生碰撞的概率的变形发生碰撞的概率 由于由于n比特长的散列值共有比特长的散列值共有2n个，所以对于给定个，所以对于给定m的变形的变形mi和和M的变形的变形Mj，mi与与Mj不碰撞的概率是不碰撞的概率是1-1/2n。由于。由于M共有共有R个变形，所以个变形，所以M的全部变形都不与的全部变形都不与mi碰撞的概率是：碰撞的概率是： 1 1/2.Rn因为消息因为消息m共有共有r个变形，因此个变形，因此m的变形与的变形与M的变形都不碰撞的概的变形都不碰撞的概率是：率是：.2/1rRn1m的变形与的变形与M的变形发生碰撞的概率是：的变形发生碰撞的概率是：.1

9、2111)(2nrRrRnenP5.1.2 Hash函数的安全性函数的安全性14l 生日攻击法生日攻击法 当当r=R=2n/2时，时，P(n)=1 e 1 0.63。对于。对于Hash值长度为值长度为64比比特的特的Hash函数，生日攻击的时间复杂度约为函数，生日攻击的时间复杂度约为232，所以是，所以是不安全的。不安全的。为了抵抗生日攻击，建议为了抵抗生日攻击，建议Hash值长度至少为值长度至少为128 比特比特.5.1.2 Hash函数的安全性函数的安全性15l 中间相遇攻击（中间相遇攻击（in-the-middle attack）u用于攻击一类具有特殊结构的用于攻击一类具有特殊结构的Ha

10、sh函数函数u分析分析Hash函数运算的中间值相等的概率函数运算的中间值相等的概率u讨论一类利用加密变换构造的讨论一类利用加密变换构造的Hash函数函数 设加密体制为：设加密体制为： nKnE MMK KMMK K:, 对于消息对于消息m=(m1, m2)，其散列值的计算分以下两步：，其散列值的计算分以下两步： （1） h1= EK(m1, IV)； （2） d=h(m)=EK (m2, h1)， 其中其中IV是加密变换的初始值。是加密变换的初始值。 这类这类Hash函数将遭受中间相遇攻击。函数将遭受中间相遇攻击。5.1.2 Hash函数的安全性函数的安全性16l 中间相遇攻击（中间相遇攻击（

11、in-the-middle attack）u用于攻击一类具有特殊结构的用于攻击一类具有特殊结构的Hash函数函数u分析分析Hash函数运算的中间值相等的概率函数运算的中间值相等的概率u讨论一类利用加密变换构造的讨论一类利用加密变换构造的Hash函数函数 u攻击方式攻击方式: 假设攻击者要找出一个假消息假设攻击者要找出一个假消息M=(M1, M2)，使得使得M与与m是一个碰撞。设是一个碰撞。设m的散列值都为的散列值都为d。攻击者首。攻击者首先产生消息先产生消息M1的的r个变形，消息个变形，消息M2的的R个变形个变形.5.1.2 Hash函数的安全性函数的安全性17中间值集合假消息的第1部分 M1

12、变形M1,1 EKM1,2 EKM1,r EKIVM2,2 DKM2,R DK假消息的第2部分 M2M2,1 DKd目标摘要5.1.2 Hash函数的安全性函数的安全性h1= EK(m1, IV)d=h(m)=EK(m2, h1) 185.1.2 Hash函数的安全性函数的安全性.,.,2 , 1| ),(,.,2 , 1| ),(:.,.,2 , 1|,.,2 , 1|:, 2, 22, 1, 11, 2, 1RjdMDhH riIVMEhH RjM riM jKjiKiji计计算算令令 这里这里DK是解密变换。假设加密变换是解密变换。假设加密变换EK是随机的，那么是随机的，那么可以使用生日

13、攻击法来分析集合可以使用生日攻击法来分析集合H1和和H2中出现相同元中出现相同元素的概率。素的概率。 如果集合如果集合H1与与H2有相同元素，例如有相同元素，例如h1, i= h2, j=DK(M2, j, d)，则有则有d=EK (M2, j, h1,i )，即，即M与与m有相同的散列值有相同的散列值d。h1= EK(m1, IV)d=h(m)=EK(m2, h1) 195.1 Hash函数概述函数概述205.1.3 Hash5.1.3 Hash函数的迭代构造法函数的迭代构造法l 压缩函数（压缩函数（compression function）l 迭代技术迭代技术 设设x是一个长度为是一个长度

14、为L的比特串。重复应的比特串。重复应用压缩函数用压缩函数f，对消，对消息息x进行多次压缩，进行多次压缩，最后得到最后得到x的散列值的散列值) 1(1 , 01 , 0:tfmtm 215.1.3 Hash5.1.3 Hash函数的迭代构造法函数的迭代构造法 l 计算消息计算消息x的散列值的散列值h(x)的步骤的步骤u 预处理预处理: 用一个公开算法在消息用一个公开算法在消息x右方添加若干比特，右方添加若干比特，得到比特串得到比特串y，使得，使得y的长度为的长度为t的倍数。即有的倍数。即有 y= x | pad(x) = y1 | y 2 | | yr , 其中其中| yi|=t (i =1,

15、2, r)，pad(x)称为称为填充函数填充函数。典型的。典型的填充函数是先添加填充函数是先添加x长度长度| x|的值，再添加若干比特（例的值，再添加若干比特（例如如0）。）。 u迭代过程迭代过程: 设设H0=IV是一个长度为是一个长度为m的初始比特串，的初始比特串，重复使用压缩函数重复使用压缩函数f，依次计算，依次计算 Hi= f (Hi 1| yi) (i =1, 2, r).u输出变换输出变换: 设设g: 0,1m0,1t是一个公开函数，令是一个公开函数，令 h(x)=g(Hr). 225.1.3 Hash5.1.3 Hash函数的迭代构造法函数的迭代构造法 l 用上述方法构造的用上述方

16、法构造的Hash函数称为迭代函数称为迭代Hash函数。大多数函数。大多数实用实用Hash函数都是迭代函数都是迭代Hash函数函数l 在预处理阶段，必须保证变换在预处理阶段，必须保证变换xy是单射。因为如果预是单射。因为如果预处理变换处理变换xy不是单射，则存在不是单射，则存在x x使得使得y=y，从而，从而h(x)=h(x)，即能够找到，即能够找到h的碰撞。的碰撞。l 对于任意无碰撞的压缩函数，都可以使用迭代技术构造对于任意无碰撞的压缩函数，都可以使用迭代技术构造一个无碰撞的一个无碰撞的Hash函数。函数。 23第第5章章 Hash函数与数字签名函数与数字签名l 5.3 5.3 安全安全Has

17、hHash算法算法SHASHA 1 1 l 5.4 5.4 基于分组密码与离散对数的基于分组密码与离散对数的HashHash函数函数l 5.5 5.5 消息认证消息认证245.2 Hash5.2 Hash函数函数MD5MD5l MD5(MD:message digest,消息摘要消息摘要) 1990年年10月月, 著名密码学家著名密码学家R. L. Rivest在在MIT(Massachusetts Institute of Technology)提出了一种提出了一种Hash函数函数,作为作为RFC 1320 (RFC:互联网研究和开发机构互联网研究和开发机构工作记录工作记录)公开发表公开发表

18、,称为称为MD4. MD5是是MD4的改进版本的改进版本, 于于1992年年4月作为月作为RFC 1321公开发表公开发表.l MD5特性特性u直接构造法: 不依赖任何密码系统和假设条件 u算法简洁u计算速度快u特别适合32位计算机软件实现u倾向于使用低端结构.255.2.1 5.2.1 MD5算法算法 l MD5算法的输入可以是任意长度的消息算法的输入可以是任意长度的消息x，对输入消息，对输入消息按按512位的分组为单位进行处理，输出位的分组为单位进行处理，输出128位的散列值位的散列值MD(x)。整个算法分为五个步骤。整个算法分为五个步骤。 l 步骤步骤1: 增加填充位增加填充位u在消息x

19、右边增加若干比特，使其长度与448模512同余。也就是说，填充后的消息长度比512的某个倍数少64位。u即使消息本身已经满足上述长度要求，仍然需要进行填充。u例如，若消息长为448，则仍需要填充512位使其长度为960位。填充位数在1到512之间。填充比特的第一位是1，其它均为0。265.2.1 5.2.1 MD5算法算法 l 步骤步骤2: 附加消息长度值附加消息长度值 用64位表示原始消息x的长度，并将其附加在步骤1所得结果之。若填充前消息长度大于264，则只使用其低64位。填充方法是把64比特的长度分成两个32比特的字，低32比特字先填充，高32比特字后填充。l 步骤步骤1与步骤与步骤2一

20、起称为消息的预处理一起称为消息的预处理u 经预处理后，原消息长度变为512的倍数u设原消息x经预处理后变为消息 Y=Y0 Y1 YL1， 其中Yi（i =0,1,L1）是512比特u在后面的步骤中，将对512比特的分组Yi进行处理 275.2.1 5.2.1 MD5算法算法u例例5.1 假设消息为假设消息为: x=“abcde”=01100001 01100010 01100011 01100100 01100101=(61 62 63 64 65)16, |x|=40=(28)16.p步骤1在x的右边填充1个“1”和407个“0”，将x变成448比特的x1: x1= x | 1 | 0 (4

21、07个) = x | 800000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000. =61626364 65800000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000. 285.2.1 5.2.1 MD5算法算法u例例5.1 假设消息为假设消息为: x=“ab

22、cde”=01100001 01100010 01100011 01100100 01100101=(61 62 63 64 65)16, |x|=40=(28)16.p经步骤2处理后的比特串为（16进制表示）：x2=x1|28(64位) =61626364 65800000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 28000000 00000000. 295.2.1 5.2.1 MD5算法算法l 步骤步骤3: 初始化初

23、始化MD缓冲区缓冲区 uMD5算法的中间结果和最终结果都保存在128位的缓冲区里，缓冲区用4个32位的寄存器表示。u4个缓冲区记为A、B、C、D，其初始值为下列32位整数（16进制表示）： A=67 45 23 01, B=EF CD AB 89, C=98 BA DC FE, D=10 32 54 76.u上述初始值以小端格式存储(字的最低有效字节存储在低地址位置 )为： 字A=01 23 45 67, 字B=89 AB CD EF, 字C=FE DC BA 98, 字D=76 54 32 10.305.2.1 5.2.1 MD5算法算法l 步骤步骤4: 以以512位的分组位的分组(16个字

24、个字)为单位处理消息为单位处理消息 uMD5是迭代Hash函数, 其压缩函数为:. 1285121285MD1 , 01 , 0:Hu步骤4是MD5算法的主循环，它以512比特作为分组，重复应用压缩函数HMD5，从消息Y的第一个分组Y1开始，依次对每个分组Yi进行压缩，直至最后分组YL1，然后输出消息x的Hash值。可见，MD5的循环次数等于消息Y中512比特分组的数目L。31MD5压缩函数HMD5 uHMD5由四轮处理组成由四轮处理组成u加法是指缓冲区中的加法是指缓冲区中的4个字与个字与CVi中对应的中对应的4个字分别模个字分别模232相加相加 . 1285121285MD1 , 01 ,

25、0:H32MD5压缩函数压缩函数HMD5 uHMD5的四轮处理过程的算法结构相同，每一轮要对缓的四轮处理过程的算法结构相同，每一轮要对缓冲区冲区ABCD进行进行16次迭代，每次迭代的运算形式为次迭代，每次迭代的运算形式为:( , , ) )sabL ag b c dX kT i 其中其中a、b、c、d分别为缓冲分别为缓冲区区A、B、C、D中的字，运中的字，运算结束后再将（算结束后再将（a、b、c、d）循环右移一个字。循环右移一个字。 33MD5压缩函数压缩函数HMD5 uHMD5的基本逻辑函数的基本逻辑函数gp每一轮使用一个基本逻辑函数每一轮使用一个基本逻辑函数g，每个基本逻辑函数的，每个基本

26、逻辑函数的输入是三个输入是三个32位的字，输出是一个位的字，输出是一个32位的字，它执行位位的字，它执行位逻辑运算，即输出的第逻辑运算，即输出的第n位是其三个输入的第位是其三个输入的第n位的函数位的函数p基本逻辑函数基本逻辑函数g的定义的定义 符号符号 、 、 和和 分别表示逻辑操作分别表示逻辑操作AND、OR、NOT和和XOR 34MD5压缩函数压缩函数HMD5 uHMD5的基本逻辑函数的基本逻辑函数gp基本逻辑函数基本逻辑函数g的真值表的真值表 b c dF G H I0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 10 0 0 11 0 1 00 1 1 0

27、1 0 0 10 0 1 10 1 0 11 1 0 01 1 1 035MD5压缩函数压缩函数HMD5 u字组字组X 把当前处理的把当前处理的512比特的分组比特的分组Yi依次分成依次分成16个个32比特的字比特的字, 分别记为分别记为X0,1,15.u在每一轮的在每一轮的16步迭代中步迭代中, 每一步迭代使用一个字每一步迭代使用一个字,迭代步数不同使用的字也不相同迭代步数不同使用的字也不相同. 因此因此, 16步迭代步迭代恰好用完恰好用完16个字个字.36MD5压缩函数压缩函数HMD5 u对于不同轮处理过程对于不同轮处理过程, 使用使用16个字的顺序不一样个字的顺序不一样.p第一轮中，使用

28、顺序为X0,1,15。p第二轮中使用顺序由下列置换确定: 2(i)= (1+5i) mod 16p第三轮中使用顺序由下列置换确定: 3(i)= (5+3i) mod 16p第四轮中使用顺序由下列置换确定: 4(i)= 7i mod 16.u例如例如: 第三轮处理过程的第第三轮处理过程的第i步迭代使用字步迭代使用字 X 3(i)= X(5+3i) mod 16; 第第8步迭代使用字步迭代使用字 X 3(8)=X(5+3 8)=X29=X13. 37MD5压缩函数压缩函数HMD5 T1=D76AA478T2=E8C7B756T3=242070DBT4=C1BDCEEET5=F57C0FAFT6=4

29、787C62AT7=A8304613T8=FD469501T9=698098D8T10=8B44F7AFT11=FFFF5BB1T12=895CD7BET13=6B901122T14=FD987193T15=A679438ET16=49B40821T17=F61E2562T18=C040B340T19=265E5A51T20=E9B6C7AAT21=D62F105DT22=02441453T23=D8A1E681T24=E7D3FBC8T25=21E1CDE6T26=C33707D6T27=F4D50D87T28=455A14EDT29=A9E3E905T30=FCEFA3F8T31=676F

30、02D9T32=8D2A4C8AT33=FFFA3942T34=8771F681T35=699D6122T36=FDE5380CT37=A4BEEA44T38=4BDECFA9T39=F6BB4B60T40=BEBFBC70T41=289B7EC6T42=EAA127FAT43=D4EF3085T44=04881D05T45=D9D4D039T46=E6DB99E5T47=1FA27CF8T48=C4AC5665T49=F4292244T50=432AFF97T51=AB9423A7T52=FC93A039T53=655B59C3T54=8F0CCC92T55=FFEFF47DT56=8584

31、5DD1T57=6FA87E4FT58=FE2CE6E0T59=A3014314T60=4E0811A1T61=F7537E82T62=BD3AF235T63=2AD7D2BBT64=EB86D391u常数表常数表T：64个个32位常数位常数p Ti =232 abs(sin(i)的整数部分的整数部分(i=1,2,64).38MD5压缩函数压缩函数HMD5 u常数表常数表T：64个个32位常数位常数p Ti =232abs(sin(i)的整数部分(i=1,2,64).p常数表T的作用是“随机化”32位的输入数据，即消除输入数据的规律性。pHMD5的第k轮处理过程使用常数表T的元素 T16(k1

32、)+1, 16(k1)+2,16k (k=1,2,3,4)， 第k轮的第i次迭代使用元素 T16( k1)+ i(i=1,2,16).39MD5压缩函数HMD5 u循环左移位数循环左移位数s Ls(v)表示对表示对32位的变量位的变量v循环左移循环左移s位。位。s的值与轮的值与轮数和迭代步数有关。数和迭代步数有关。 步数轮数123456789101112 13 14 15 1612347546129111017141615222023217546129111017141615222023217546129111017141615222023217546129111017141615222023

33、21405.2.1 MD55.2.1 MD5算法算法 l 步骤步骤5: 输出输出 依次对消息的L个512比特的分组进行处理，第L个分组处理后的输出值即是消息x的散列值MD(x)。 可将MD5的处理过程归纳如下：uCV0=IVuCVi+1=SUM32CVi, RFI (Yi, RFH (Yi, RFG (Yi, RFF (Yi, CVi) ) (i=0,1, L1)uMD= CVL1.uIV =第三步定义的缓冲区ABCD的初值uL =消息经第一步和第二步处理后分组的个数uYi =消息的第i个512位分组uRFu =使用基本逻辑函数u的轮函数uSUM32=对输入字的模232相加uMD =散列值.4

34、15.2.2 MD55.2.2 MD5的安全性的安全性 l Rivest猜测，猜测，MD5可能是可能是128位位Hash函数中强度最大的。函数中强度最大的。l 目前，对MD5的攻击已取得以下结果：uT. Berson（1992）已经证明，对单轮的MD5算法，利用差分密码分析，可以在合理的时间内找出散列值相同的两条消息。这一结果对MD5四轮运算的每一轮都成立。但是，目前尚不能将这种攻击推广到具有四轮运算的MD5上.uB. Boer和A. Bosselaers（1993）说明了如何找到消息分组和MD5两个不同的初始值,使它们产生相同的输出. 也就是说, 对一个512位的分组, MD5压缩函数对缓冲

35、区ABCD的不同值产生相同的输出,这种情况称为伪碰撞（pseudo-collision）.目前尚不能用该方法成功攻击MD5算法.425.2.2 MD55.2.2 MD5的安全性的安全性 uH. Dobbertin（1996）找到了MD5无初始值的碰撞(pseudo-collision).给定一个512位的分组,可以找到另一个512位的分组,对于选择的初始值IV0,它们的MD5运算结果相同. 到目前为止, 尚不能用这种方法对使用MD5初始值IV的整个消息进行攻击. uR. L. Rivest曾猜想作为128比特长的Hash函数，MD5的强度达到了最大：要找出两个具有相同Hash值的消息需执行O(

36、264)次运算，而要找出具有给定Hash值的一个消息则要执行O(2128)次运算。43MD5算法的安全性算法的安全性u 我国山东大学王小云教授（我国山东大学王小云教授（2004）提出的攻击对）提出的攻击对MD5最具威胁。对于最具威胁。对于MD5的初始值的初始值IV，王小云找到了，王小云找到了许多许多512位的分组对，它们的位的分组对，它们的MD5值相同值相同. 王小云在美州密码年会（王小云在美州密码年会（Crypto2004）上做了攻击）上做了攻击MD5、HAVAL-128、MD4和和RIPEMD算法的报告，公算法的报告，公布了布了MD系列算法的破解结果。对于系列算法的破解结果。对于MD5的攻

37、击，报告的攻击，报告中给出了一个具体的碰撞例子。中给出了一个具体的碰撞例子。 44设m1表示消息（十六进制表示）：00000000 d1 31 dd 02 c5 e6 ee c4 69 3d 9a 06 98 af f9 5c00000010 2f ca b5 87 12 46 7e ab 40 04 58 3e b8 fb 7f 89 00000020 55 ad 34 06 09 f4 b3 02 83 e4 88 83 25 71 41 5a00000030 08 51 25 e8 f7 cd c9 9f d9 1d bd f2 80 37 3c 5b 00000040 96 0b 1d

38、 d1 dc 41 7b 9c e4 d8 97 f4 5a 65 55 d500000050 35 73 9a c7 f0 eb fd 0c 30 29 f1 66 d1 09 b1 8f 00000060 75 27 7f 79 30 d5 5c eb 22 e8 ad ba 79 cc 15 5c 00000070 ed 74 cb dd 5f c5 d3 6d b1 9b 0a d8 35 cc a7 e3. m2表示消息：00000000 d1 31 dd 02 c5 e6 ee c4 69 3d 9a 06 98 af f9 5c00000010 2f ca b5 07 12 46

39、 7e ab 40 04 58 3e b8 fb 7f 89 00000020 55 ad 34 06 09 f4 b3 02 83 e4 88 83 25 f1 41 5a 00000030 08 51 25 e8 f7 cd c9 9f d9 1d bd 72 80 37 3c 5b00000040 96 0b 1d d1 dc 41 7b 9c e4 d8 97 f4 5a 65 55 d500000050 35 73 9a 47 f0 eb fd 0c 30 29 f1 66 d1 09 b1 8f 00000060 75 27 7f 79 30 d5 5c eb 22 e8 ad b

40、a 79 4c 15 5c 00000070 ed 74 cb dd 5f c5 d3 6d b1 9b 0a 58 35 cc a7 e3. MD5算法的安全性算法的安全性45MD5算法的安全性算法的安全性l 则有 MD5(m1) = MD5(m2) a4c0d35c95a63a805915367dcfe6b751.l 消息m1与m2只有6个字节不同，即粗体字符部分。实际上，它们的Hamming距离也仅为6比特。这清楚地表明MD5不是强无碰撞的, 也否定了R. L. Rivest的猜想。 事实上, 利用数据链接的方法，可通过在消息m1与m2的后端链接相同的数据，得到无穷多个碰撞的例子。MD5

41、的安全性受到了严重的威胁。在安全强度要求较高的系统中，应避免MD5的使用。l 国际密码学家国际密码学家Lenstra利用王小云等提供的利用王小云等提供的MD5碰撞，伪造碰撞，伪造了符合了符合X.509标准的数字证书标准的数字证书. l MD5算法抗密码分析能力较弱算法抗密码分析能力较弱,对对MD5的生日攻击所需代价的生日攻击所需代价为为264数量级数量级. 所以所以, 必须设计新的必须设计新的Hash算法算法, 使其与使其与MD5相比相比具有更长的散列值和更高的安全性具有更长的散列值和更高的安全性.46第第5章章 Hash函数与数字签名函数与数字签名 l 5.4 5.4 基于分组密码与离散对数

42、的基于分组密码与离散对数的HashHash函数函数l 5.5 5.5 消息认证消息认证475.3 5.3 安全安全HashHash算法算法SHASHA 1 1l 安全安全Hash算法算法SHA（secure hash algorithm）由美国标）由美国标准与技术研究所（准与技术研究所（NIST）设计并于）设计并于1993年作为联邦信息年作为联邦信息处理标准（处理标准（FIPS 180）发布）发布l 修改版于修改版于1995年发布（年发布（FIPS 180 1），通常称之为），通常称之为SHA 1。该标准称为。该标准称为安全安全Hash函数函数。l RFC 3174也给出了也给出了SHA 1，

43、它基本上是复制，它基本上是复制FIPS 180 1的内容，但增加了的内容，但增加了C代码实现。代码实现。l SHA 1算法的输入是长度小于算法的输入是长度小于264的任意消息的任意消息x，输出，输出160位的散列值。位的散列值。485.3.1 SHA5.3.1 SHA 1 1算法步骤算法步骤l SHA 1处理消息的过程与处理消息的过程与MD5类似，对输入消息按类似，对输入消息按512位位的分组为单位进行处理，整个算法分为五个步骤的分组为单位进行处理，整个算法分为五个步骤l 步骤步骤1: 增加填充位增加填充位 在消息右边增加若干比特，使其长度与在消息右边增加若干比特，使其长度与448模模512同

44、余。即使消息本身同余。即使消息本身已经满足上述长度要求，仍然需要进行填充。填充位数在已经满足上述长度要求，仍然需要进行填充。填充位数在1到到512之之间。填充比特的第一位是间。填充比特的第一位是“1”，其它均为，其它均为“0”。l 步骤步骤2: 附加消息长度值附加消息长度值 用用64位表示原始消息位表示原始消息x的长度，并将其附加在步骤的长度，并将其附加在步骤1所得结果之后。所得结果之后。l 步骤步骤1与步骤与步骤2一起称为消息的预处理一起称为消息的预处理 经预处理后，原消息长度变为经预处理后，原消息长度变为512的倍数。设原消息的倍数。设原消息x经预处理后变经预处理后变为消息为消息Y=Y0

45、Y1 YL 1，其中，其中Yi（i =0,1,L 1）是）是512比特。在后面的比特。在后面的步骤中，将对步骤中，将对512比特的分组比特的分组Yi进行处理。进行处理。495.3.1 SHA5.3.1 SHA 1 1算法步骤算法步骤l 步骤步骤3: 初始化缓冲区初始化缓冲区 SHA 1算法的中间结果和最终结果保存在算法的中间结果和最终结果保存在160位的缓冲区里，缓冲区位的缓冲区里，缓冲区用用5个个32位的寄存器表示。位的寄存器表示。5个缓冲区记为个缓冲区记为A、B、C、D、E，其初始，其初始值为下列值为下列32位整数（位整数（16进制表示）：进制表示）： A=67 45 23 01, B=E

46、F CD AB 89, C=98 BA DC FE , D=10 32 54 76, E=C3 D2 E1 F0. 其中，前其中，前4个初始值与个初始值与MD5的初始值相同。的初始值相同。SHA 1以大端格式存储缓以大端格式存储缓冲区的值，即字的最高有效字节存于低地址字节位置。因此，上述冲区的值，即字的最高有效字节存于低地址字节位置。因此，上述初始值存储为（十六进制）：初始值存储为（十六进制）： 字字A=67 45 23 01, 字字B=EF CD AB 89, 字字C=98 BA DC FE, 字字D=10 32 54 76, 字字E=C3 D2 E1 F0.505.3.1 SHA5.3.1

47、 SHA 1 1算法步骤算法步骤l 步骤步骤4: 以以512位的分组（位的分组（16个字）为单位处理消息个字）为单位处理消息uSHA 1是迭代是迭代Hash函数，其压缩函数为：函数，其压缩函数为：. 160512160SHA1 , 01 , 0:Hu步骤步骤4是是SHA 1算法的主循环，它以算法的主循环，它以512比特作为分组，比特作为分组，重复应用压缩函数重复应用压缩函数HSHA，从消息，从消息Y的第一个分组的第一个分组Y1开开始，依次对每个分组始，依次对每个分组Yi进行压缩，直至最后分组进行压缩，直至最后分组YL 1，然后输出消息然后输出消息x的的Hash值。值。uSHA 1循环次数等于消

48、息循环次数等于消息Y中中512比特分组的数目比特分组的数目L。51SHASHA 1 1的的压缩函数压缩函数H HSHASHA u由四轮处理组成由四轮处理组成u加法是模加法是模232相加相加 CVi (160)Yi (512)BCDAEf4, K, W60,61,79, 20步BCDAEf2, K, W20,21,39, 20步BCDAEf3, K, W40,41,59, 20步BCDAEf1, K, W0,1,19, 20步 + + + + +CVi+1 (160)52SHASHA 1 1的压缩函数的压缩函数H HSHASHA u压缩函数压缩函数HSHA的四轮处理过程的算法结构相同，每一轮的四

49、轮处理过程的算法结构相同，每一轮要对缓冲区要对缓冲区ABCDE进行进行20次迭代，每次迭代的运算形次迭代，每次迭代的运算形式为式为DC,(B),A,),(A)D)C,(B,(EED,C,B,A,305LKWLftt A B C D E A B C D E + + f +Wt +KtL30L5 其中其中A、B、C、D、E分别为五个缓冲分别为五个缓冲区中的字，运算结区中的字，运算结束后再将（束后再将（A、B、C、D、E）循环右）循环右移一个字。移一个字。53DCBD)(CD)(BC)(BDCBD)B(C)(BSHASHA 1 1的压缩函数的压缩函数H HSHASHA u基本逻辑函数基本逻辑函数fp

50、每一轮使用一个基本逻辑函数每一轮使用一个基本逻辑函数f，每个基本逻辑函，每个基本逻辑函数的输入是三个数的输入是三个32位的字，输出是一个位的字，输出是一个32位的字，位的字，它执行位逻辑运算，即输出的第它执行位逻辑运算，即输出的第n位是其三个输入位是其三个输入第第n位的函数。位的函数。轮数基本逻辑函数ff(B, C, D)1234f1(B, C, D)f2(B, C, D)f3(B, C, D)f4(B, C, D)54SHASHA 1 1的压缩函数的压缩函数H HSHASHA u基本逻辑函数基本逻辑函数fp基本逻辑函数基本逻辑函数f的真值表的真值表B C Df1 f2 f3 f40 0 00

51、 0 10 1 00 1 11 0 01 0 11 1 01 1 10 0 0 01 1 0 10 1 0 11 0 1 00 1 0 10 0 1 01 0 1 01 1 1 155SHASHA 1 1的压缩函数的压缩函数H HSHASHA u字组字组Wtp t（0t79）代表迭代步数，依次表示第一、二、三、四轮处理过程进行的迭代次序pWt(0t79)是32比特的字，它的前面16个字W0,W1,W15依次取自当前输入分组Yi，其余字为).79,.,17,16()(3814161tWWWWLWttttt u加法常数表加法常数表Kt30303030222325210迭代步数迭代步数十六进制十六进

52、制十进制十进制0t1920t3940t5960t795A8279996ED9EBA18F1BBCDCCA62C1D6565.3.1 SHA5.3.1 SHA 1 1算法步骤算法步骤l 步骤步骤5: 输出输出u第L个分组处理后的输出值即是消息x的散列值MD(x)uSHA1的处理过程归纳如下：pCV0=IVp CVi+1=SUM32(CVi, ABCDEi ) (i=0,1, L1)pMD= CVL1u其中：pIV =第三步定义的缓冲区ABCDE的初值pABCDEi =处理第i个消息分组时最后一轮的输出pL =消息经第一步和第二步处理后分组的个数pSUM32=对输入字的模232相加pMD =散列值

53、.575.3.2 SHA5.3.2 SHA 1 1和和MD5MD5的比较的比较l SHA 1与与MD5的算法类似，所以它们的性质极为相似的算法类似，所以它们的性质极为相似l 抗穷举攻击的能力抗穷举攻击的能力uSHA1抗穷举攻击的能力比MD5强 u用穷举攻击方法产生具有给定散列值的消息pMD5需要的代价为2128数量级pSHA1需要的代价为2160数量级 u用穷举攻击方法产生两个具有相同散列值的消息 pMD5需要的代价为264数量级pSHA1需要的代价为280数量级 l 抗密码分析的能力抗密码分析的能力 uMD5算法抗密码分析的能力较弱算法抗密码分析的能力较弱uSHA 1算法抗密码分析的能力似乎

54、并不弱算法抗密码分析的能力似乎并不弱 585.3.2 SHA5.3.2 SHA 1 1和和MD5MD5的比较的比较l 速度速度 SHA 1执行的速度比执行的速度比MD5的速度慢得多的速度慢得多 l 简洁性简洁性 SHA 1和和MD5两种算法都易于描述和实现，不需要使用两种算法都易于描述和实现，不需要使用大的程序和置换表大的程序和置换表 l 数据的存储方式数据的存储方式 MD5使用使用little endian方式，方式，SHA 1使用使用big endian方式。方式。这两种方式没有本质的差异这两种方式没有本质的差异 59l MD5和和SHA-1其实都属于其实都属于MD4的改进版本，它们之间的

55、比的改进版本，它们之间的比较可简单地表示如下较可简单地表示如下(更好的雪崩是指将前一步的输出加到更好的雪崩是指将前一步的输出加到下一轮，以加速雪崩效应下一轮，以加速雪崩效应)， MD4、 MD5与与SHA-1比较如下比较如下表所示。表所示。60l 1、（、（1）利用）利用MD5算法对一个文件进行处理，计算它的算法对一个文件进行处理，计算它的Hash值，提交程序代码和运算结果。值，提交程序代码和运算结果。l （2）微软的系统软件都有）微软的系统软件都有MD5验证，尝试查找软件的验证，尝试查找软件的MD5值。同时，在值。同时，在Windows操作系统中，通过开始操作系统中，通过开始运运行行sigv

56、erif命令，利用数字签名查找非命令，利用数字签名查找非Windows的系统软的系统软件。件。练习题ex61第第5章章 Hash函数与数字签名函数与数字签名l 5.5 5.5 消息认证消息认证625.4 5.4 基于分组密码与离散对数的基于分组密码与离散对数的HashHash函数函数l Hash函数的间接构造法函数的间接构造法u利用已有的密码算法构造利用已有的密码算法构造Hash函数函数u如果密码算法是安全的，那么利用它所构造的如果密码算法是安全的，那么利用它所构造的Hash函数也是安全的函数也是安全的635.4.1 5.4.1 利用分组密码算法构造利用分组密码算法构造HashHash函数函数

57、l 已知条件已知条件 设设Ek是一个分组长度为是一个分组长度为n的分组密码的加密算法，的分组密码的加密算法，密钥为密钥为k，对于任意的消息，对于任意的消息x，首先对，首先对x进行分组，进行分组，每组的长度为每组的长度为n。设消息。设消息x为为: x=x1 x2xL, 其中其中xi GF(2)n（1 i L）.645.4.1 5.4.1 利用分组密码算法构造利用分组密码算法构造HashHash函数函数l 基于分组密码基于分组密码CBC(密文分组链接密文分组链接)工作模式构造工作模式构造Hash函数函数u首先选取一个初始值首先选取一个初始值: y0 =IV GF(2)n，u然后依次计算然后依次计算

58、: u最后定义最后定义Hash值为值为: hCBC(x)=yL. 1() (1),ikiiyExyiL IV=y0 x1 Ek y1 x2 Ek y2 xL EkyL=hCBC(x)65l 基于分组密码基于分组密码CFB(密文反馈密文反馈)工作模式构造工作模式构造Hash函数函数u首先选取一个初始值首先选取一个初始值: y0 =IV GF(2)n，u然后依次计算然后依次计算: u最后定义最后定义Hash值为值为: hCFB(x)=yL. 5.4.1 5.4.1 利用分组密码算法构造利用分组密码算法构造HashHash函数函数1() (1),iikiyxEyiL IV=y0 x1 y1 Ek x

59、2 y2 EkyL=hCFB(x) xL Ekl 在密钥公开的情况下，基于分组密码在密钥公开的情况下，基于分组密码CBC工作模工作模式和式和CFB工作模式构造的工作模式构造的Hash函数是不安全的，函数是不安全的，它们甚至不是弱无碰撞的它们甚至不是弱无碰撞的.66l 基于一些困难数学问题，诸如离散对数问题、因子分基于一些困难数学问题，诸如离散对数问题、因子分解问题、背包问题等可以构造出一些解问题、背包问题等可以构造出一些Hash函数，这些函数，这些Hash函数的安全性依赖于对应数学问题的困难性函数的安全性依赖于对应数学问题的困难性l Chaum、Heijst和和Pfitzmann（1992年）

60、提出的基于离年）提出的基于离散对数问题构造的散对数问题构造的Hash函数函数u运行速度不是很快运行速度不是很快u可以证明是安全的可以证明是安全的.l Chaum Heijst Pfitzmann Hash函数的构造函数的构造 设设p是一个大素数，是一个大素数，q=(p 1)/2是一个素数，是一个素数， 和和 是是Zp的两的两个本原元。假设离散对数个本原元。假设离散对数log 是计算上不可行的。定义是计算上不可行的。定义Hash函数函数h为：为：5.4.2 5.4.2 基于离散对数问题的基于离散对数问题的Hash函数函数 .mod),(,:2121*pxxhZZZhxxppp 67l Chaum