现代密码学第5章Hash函数与消息认证1110

《现代密码学第5章Hash函数与消息认证1110》由会员分享，可在线阅读，更多相关《现代密码学第5章Hash函数与消息认证1110（83页珍藏版）》请在装配图网上搜索。

1、121世纪高等学校计算机规划教材Cryptography彭代渊彭代渊 信息科学与技术学院信息科学与技术学院 2009.9-2010.1作 者：何大可 彭代渊 唐小虎 何明星 梅其祥 出版社：人民邮电出版社2Cryptography彭代渊彭代渊 信息科学与技术学院信息科学与技术学院 2009年年11月月3第第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 消息认

2、证消息认证45.1 Hash函数概述函数概述55.1.1 Hash函数定义函数定义l 数据安全数据安全u机密性机密性u完整性完整性u认证性认证性l 密码技术主要保证数据的机密性密码技术主要保证数据的机密性l Hash函数能保证数据的完整性和认证性函数能保证数据的完整性和认证性65.1.1 Hash函数定义函数定义l Hash函数定义：函数定义：Hash函数是一个将任意长度的消息函数是一个将任意长度的消息（message）映射成固定长度消息的函数。）映射成固定长度消息的函数。n*n*ii*nxhyx h nA AA AA AA AA AA AA AA A)(:0任任意意长长度度消消息息集集合合消

3、消息息集集合合长长度度为为字字母母表表 将将h称为一个称为一个Hash函数（函数（hash function），或称为哈希函），或称为哈希函数、散列函数。对于任何消息数、散列函数。对于任何消息x ，将，将h(x)称为称为x的的Hash值、值、散列值、消息摘要（散列值、消息摘要（message digest）。）。75.1.1 Hash函数定义函数定义l Hash函数的碰撞（函数的碰撞（collision） 设x、x是两个不同的消息，如果 h(x)=h(x) 则称x和x是Hash函数h的一个（对）碰撞.85.1.1 Hash函数定义函数定义l Hash函数的分类函数的分类u单向单向Hash函数（

4、函数（one way） 给定一个给定一个Hash值值y，如果寻找一个消息，如果寻找一个消息x，使得，使得y=h (x)是计算上不可行的，则称是计算上不可行的，则称h是单向是单向Hash函数函数. u弱抗碰撞弱抗碰撞Hash函数（函数（weakly collision free） 任给一个消息任给一个消息x，如果寻找另一个不同的消息，如果寻找另一个不同的消息x，使，使得得h(x) =h(x)是计算上不可行的，则称是计算上不可行的，则称h是弱抗碰撞是弱抗碰撞Hash函数函数. u强抗碰撞强抗碰撞Hash函数函数 （strongly collision free） 如果寻找两个不同的消息如果寻找两个

5、不同的消息x和和x，使得，使得h(x)=h(x)是计是计算上不可行的，则称算上不可行的，则称h是强抗碰撞是强抗碰撞Hash函数函数. 95.1.1 Hash函数定义函数定义l 安全安全Hash函数函数h应具有以下性质：应具有以下性质：u 对任意的消息对任意的消息x，计算，计算h(x)是容易的；是容易的；u h是单向的；是单向的；u h是弱抗碰撞的，或是强抗碰撞的。是弱抗碰撞的，或是强抗碰撞的。105.1 Hash函数概述函数概述115.1.2 Hash函数的安全性l 对对Hash函数的攻击是指寻找一对碰撞消息的过程函数的攻击是指寻找一对碰撞消息的过程l 生日悖论（生日悖论（birthday p

6、aradox） 生日问题：假设每个人的生日是等概率的，每年有生日问题：假设每个人的生日是等概率的，每年有365天，天，在在k个人中至少有两个人的生日相同的概率大于个人中至少有两个人的生日相同的概率大于1/2，问，问k最小最小应是多少？应是多少？ k人生日都不同的概率是：人生日都不同的概率是： .36511.3652136511k.36511.36521365111),365(kkP 2k人人生生日日相相同同的的概概率率为为：人人中中至至少少有有 有有P(365,23)=0.5073。即在。即在23个人中，至少有两个人生日相个人中，至少有两个人生日相同的概率大于同的概率大于0.5，这个数字比人们

7、直观猜测的结果小得多，这个数字比人们直观猜测的结果小得多，因而称为生日悖论。因而称为生日悖论。12l 生日攻击法生日攻击法 生日悖论原理可以用于构造对生日悖论原理可以用于构造对Hash函数的攻击函数的攻击u设设Hash函数值有函数值有n个比特，个比特，m是真消息，是真消息，M是伪造的假消息，是伪造的假消息，分别把消息分别把消息m和和M表示成表示成r和和R个个变形的消息变形的消息。消息与其变形。消息与其变形消息具有不同的形式，但有相同的含义。将消息表示成变消息具有不同的形式，但有相同的含义。将消息表示成变形消息的方法很多，例如增加空格、使用缩写、使用意义形消息的方法很多，例如增加空格、使用缩写、

8、使用意义相同的单词、去掉不必要的单词等。相同的单词、去掉不必要的单词等。5.1.2 Hash函数的安全性函数的安全性135.1.2 Hash函数的安全性函数的安全性l 生日攻击法生日攻击法u分别把消息分别把消息m和和M表示成表示成r和和R个个变形的消息变形的消息14l 生日攻击法生日攻击法u计算真消息计算真消息m的变形与假消息的变形与假消息M的变形发生碰撞的概率的变形发生碰撞的概率 由于由于n比特长的散列值共有比特长的散列值共有2n个，所以对于给定个，所以对于给定m的变形的变形mi和和M的变形的变形Mj，mi与与Mj不碰撞的概率是不碰撞的概率是1-1/2n。由于。由于M共有共有R个变形，所以个

9、变形，所以M的全部变形都不与的全部变形都不与mi碰撞的概率是：碰撞的概率是： 1 1/2.Rn因为消息因为消息m共有共有r个变形，因此个变形，因此m的变形与的变形与M的变形都不碰撞的概的变形都不碰撞的概率是：率是：.2/1rRn1m的变形与的变形与M的变形发生碰撞的概率是：的变形发生碰撞的概率是：.12111)(2nrRrRnenP5.1.2 Hash函数的安全性函数的安全性15l 生日攻击法生日攻击法 当当r=R=2n/2时，时，P(n)=1 e 1 0.63。对于。对于Hash值长度为值长度为64比比特的特的Hash函数，生日攻击的时间复杂度约为函数，生日攻击的时间复杂度约为232，所以是

10、，所以是不安全的。不安全的。为了抵抗生日攻击，建议为了抵抗生日攻击，建议Hash值长度至少为值长度至少为128 比特比特.5.1.2 Hash函数的安全性函数的安全性16l 中间相遇攻击（中间相遇攻击（in-the-middle attack）u用于攻击一类具有特殊结构的用于攻击一类具有特殊结构的Hash函数函数u分析分析Hash函数运算的中间值相等的概率函数运算的中间值相等的概率u讨论一类利用加密变换构造的讨论一类利用加密变换构造的Hash函数函数 设加密体制为：设加密体制为： nKnE MMK KMMK K:, 对于消息对于消息m=(m1, m2)，其散列值的计算分以下两步：，其散列值的计

11、算分以下两步： （1） h1= EK(m1, IV)； （2） d=h(m)=EK (m2, h1)， 其中其中IV是加密变换的初始值。是加密变换的初始值。 这类这类Hash函数将遭受中间相遇攻击。函数将遭受中间相遇攻击。5.1.2 Hash函数的安全性函数的安全性17l 中间相遇攻击（中间相遇攻击（in-the-middle attack）u用于攻击一类具有特殊结构的用于攻击一类具有特殊结构的Hash函数函数u分析分析Hash函数运算的中间值相等的概率函数运算的中间值相等的概率u讨论一类利用加密变换构造的讨论一类利用加密变换构造的Hash函数函数 u攻击方式攻击方式: 假设攻击者要找出一个假

12、消息假设攻击者要找出一个假消息M=(M1, M2)，使得使得M与与m是一个碰撞。设是一个碰撞。设m的散列值都为的散列值都为d。攻击者首。攻击者首先产生消息先产生消息M1的的r个变形，消息个变形，消息M2的的R个变形个变形.5.1.2 Hash函数的安全性函数的安全性18中间值集合假消息的第1部分 M1变形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) 195.1.2 Hash函数的安全性函数的安全性.,.,2 , 1

13、| ),(,.,2 , 1| ),(:.,.,2 , 1|,.,2 , 1|:, 2, 22, 1, 11, 2, 1RjdMDhH riIVMEhH RjM riM jKjiKiji计计算算令令 这里这里DK是解密变换。假设加密变换是解密变换。假设加密变换EK是随机的，那么是随机的，那么可以使用生日攻击法来分析集合可以使用生日攻击法来分析集合H1和和H2中出现相同元中出现相同元素的概率。素的概率。 如果集合如果集合H1与与H2有相同元素，例如有相同元素，例如h1, i= h2, j=DK(M2, j, d)，则有则有d=EK (M2, j, h1,i )，即，即M与与m有相同的散列值有相同的

14、散列值d。h1= EK(m1, IV)d=h(m)=EK(m2, h1) 205.1 Hash函数概述函数概述215.1.3 Hash5.1.3 Hash函数的迭代构造法函数的迭代构造法l 压缩函数（压缩函数（compression function）l 迭代技术迭代技术 设设x是一个长度为是一个长度为L的比特串。重复应的比特串。重复应用压缩函数用压缩函数f，对消，对消息息x进行多次压缩，进行多次压缩，最后得到最后得到x的散列值的散列值) 1(1 , 01 , 0:tfmtm 225.1.3 Hash5.1.3 Hash函数的迭代构造法函数的迭代构造法 l 计算消息计算消息x的散列值的散列值h

15、(x)的步骤的步骤u 预处理预处理: 用一个公开算法在消息用一个公开算法在消息x右方添加若干比特，右方添加若干比特，得到比特串得到比特串y，使，使 得得y的长度为的长度为t的倍数。即有的倍数。即有 y= x | pad(x) = y1 | y 2 | | yr , 其中其中| yi|=t (i =1, 2, r)，pad(x)称为称为填充函数填充函数。典型的。典型的填充函数是先添加填充函数是先添加x长度长度| x|的值，再添加若干比特（例的值，再添加若干比特（例如如0）。）。 u迭代过程迭代过程: 设设H0=IV是一个长度为是一个长度为m的初始比特串，的初始比特串，重复使用压缩函数重复使用压缩

16、函数f，依次计算，依次计算 Hi= f (Hi 1| yi) (i =1, 2, r).u输出变换输出变换: 设设g: 0,1m0,1t是一个公开函数，令是一个公开函数，令 h(x)=g(Hr). 235.1.3 Hash5.1.3 Hash函数的迭代构造法函数的迭代构造法 l 用上述方法构造的用上述方法构造的Hash函数称为迭代函数称为迭代Hash函数。大多数函数。大多数实用实用Hash函数都是迭代函数都是迭代Hash函数函数l 在预处理阶段，必须保证变换在预处理阶段，必须保证变换xy是单射。因为如果预是单射。因为如果预处理变换处理变换xy不是单射，则存在不是单射，则存在x x使得使得y=y

17、，从而，从而h(x)=h(x)，即能够找到，即能够找到h的碰撞。的碰撞。l 对于任意无碰撞的压缩函数，都可以使用迭代技术构造对于任意无碰撞的压缩函数，都可以使用迭代技术构造一个无碰撞的一个无碰撞的Hash函数。函数。 24第第5章章 Hash函数与消息认证函数与消息认证l 5.3 5.3 安全安全HashHash算法算法SHASHA 1 1 l 5.4 5.4 基于分组密码与离散对数的基于分组密码与离散对数的HashHash函数函数l 5.5 5.5 消息认证消息认证255.2 Hash5.2 Hash函数函数MD5MD5l MD5(MD:message digest,消息摘要消息摘要) 19

18、90年年10月月, 著名密码学家著名密码学家R. L. Rivest在在MIT(Massachusetts Institute of Technology)提出了一种提出了一种Hash函数函数,作为作为RFC 1320 (RFC:互联网研究和开发机构互联网研究和开发机构工作记录工作记录)公开发表公开发表,称为称为MD4. MD5是是MD4的改进版本的改进版本, 于于1992年年4月作为月作为RFC 1321公开发表公开发表.l MD5特性特性u直接构造法: 不依赖任何密码系统和假设条件 u算法简洁u计算速度快u特别适合32位计算机软件实现u倾向于使用低端结构.265.2.1 5.2.1 MD5

19、算法算法 l MD5算法的输入可以是任意长度的消息算法的输入可以是任意长度的消息x，对输入消息，对输入消息按按512位的分组为单位进行处理，输出位的分组为单位进行处理，输出128位的散列值位的散列值MD(x)。整个算法分为五个步骤。整个算法分为五个步骤。 l 步骤步骤1: 增加填充位增加填充位u在消息x右边增加若干比特，使其长度与448模512同余。也就是说，填充后的消息长度比512的某个倍数少64位。u即使消息本身已经满足上述长度要求，仍然需要进行填充。u例如，若消息长为448，则仍需要填充512位使其长度为960位。填充位数在1到512之间。填充比特的第一位是1，其它均为0。275.2.1

20、 5.2.1 MD5算法算法 l 步骤步骤2: 附加消息长度值附加消息长度值 用64位表示原始消息x的长度，并将其附加在步骤1所得结果之。若填充前消息长度大于264，则只使用其低64位。填充方法是把64比特的长度分成两个32比特的字，低32比特字先填充，高32比特字后填充。l 步骤步骤1与步骤与步骤2一起称为消息的预处理一起称为消息的预处理u 经预处理后，原消息长度变为512的倍数u设原消息x经预处理后变为消息 Y=Y0 Y1 YL1， 其中Yi（i =0,1,L1）是512比特u在后面的步骤中，将对512比特的分组Yi进行处理 285.2.1 5.2.1 MD5算法算法u例例5.1 假设消息

21、为假设消息为: 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 (407个) = x | 800000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000. =61626364 65800000 00

22、000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000. 295.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经步骤2处理后的比特串为（16进制表示）：x2=x1|28(64位) =61626364 65800000 00000000

23、00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 28000000 00000000. 305.2.1 5.2.1 MD5算法算法l 步骤步骤3: 初始化初始化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

24、54 76.u上述初始值以小端格式存储(字的最低有效字节存储在低地址位置 )为： 字A=01 23 45 67, 字B=89 AB CD EF, 字C=FE DC BA 98, 字D=76 54 32 10.315.2.1 5.2.1 MD5算法算法l 步骤步骤4: 以以512位的分组位的分组(16个字个字)为单位处理消息为单位处理消息 uMD5是迭代Hash函数, 其压缩函数为:. 1285121285MD1 , 01 , 0:Hu步骤4是MD5算法的主循环，它以512比特作为分组，重复应用压缩函数HMD5，从消息Y的第一个分组Y1开始，依次对每个分组Yi进行压缩，直至最后分组YL1，然后输

25、出消息x的Hash值。可见，MD5的循环次数等于消息Y中512比特分组的数目L。32MD5压缩函数HMD5 uHMD5由四轮处理组成由四轮处理组成u加法是指缓冲区中的加法是指缓冲区中的4个字与个字与CVi中对应的中对应的4个字分别模个字分别模232相加相加 . 1285121285MD1 , 01 , 0:H33MD5压缩函数压缩函数HMD5 uHMD5的四轮处理过程的算法结构相同，每一轮要对缓的四轮处理过程的算法结构相同，每一轮要对缓冲区冲区ABCD进行进行16次迭代，每次迭代的运算形式为次迭代，每次迭代的运算形式为:( , , ) )sabL ag b c dX kT i 其中其中a、b、

26、c、d分别为缓冲分别为缓冲区区A、B、C、D中的字，运中的字，运算结束后再将（算结束后再将（a、b、c、d）循环右移一个字。循环右移一个字。 34MD5压缩函数压缩函数HMD5 uHMD5的基本逻辑函数的基本逻辑函数gp每一轮使用一个基本逻辑函数每一轮使用一个基本逻辑函数g，每个基本逻辑函数的，每个基本逻辑函数的输入是三个输入是三个32位的字，输出是一个位的字，输出是一个32位的字，它执行位位的字，它执行位逻辑运算，即输出的第逻辑运算，即输出的第n位是其三个输入的第位是其三个输入的第n位的函数位的函数p基本逻辑函数基本逻辑函数g的定义的定义 符号符号 、 、 和和 分别表示逻辑操作分别表示逻辑

27、操作AND、OR、NOT和和XOR 35MD5压缩函数压缩函数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 01 0 0 10 0 1 10 1 0 11 1 0 01 1 1 036MD5压缩函数压缩函数HMD5 u字组字组X 把当前处理的把当前处理的512比特的分组比特的分组Yi依次分成依次分成16个个32比特的字比特的字, 分别记为分别记为X0,1,15.u在每一轮的在每一轮的16步迭代中步迭代中

28、, 每一步迭代使用一个字每一步迭代使用一个字,迭代步数不同使用的字也不相同迭代步数不同使用的字也不相同. 因此因此, 16步迭代步迭代恰好用完恰好用完16个字个字.37MD5压缩函数压缩函数HMD5 u对于不同轮处理过程对于不同轮处理过程, 使用使用16个字的顺序不一样个字的顺序不一样.p第一轮中，使用顺序为X0,1,15。p第二轮中使用顺序由下列置换确定: 2(i)= (1+5i) mod 16p第三轮中使用顺序由下列置换确定: 3(i)= (5+3i) mod 16p第四轮中使用顺序由下列置换确定: 4(i)= 7i mod 16.u例如例如: 第三轮处理过程的第第三轮处理过程的第i步迭代

29、使用字步迭代使用字 X 3(i)= X(5+3i) mod 16; 第第8步迭代使用字步迭代使用字 X 3(8)=X(5+3 8)=X29=X23. 38MD5压缩函数压缩函数HMD5 T1=D76AA478T2=E8C7B756T3=242070DBT4=C1BDCEEET5=F57C0FAFT6=4787C62AT7=A8304613T8=FD469501T9=698098D8T10=8B44F7AFT11=FFFF5BB1T12=895CD7BET13=6B901122T14=FD987193T15=A679438ET16=49B40821T17=F61E2562T18=C040B340

30、T19=265E5A51T20=E9B6C7AAT21=D62F105DT22=02441453T23=D8A1E681T24=E7D3FBC8T25=21E1CDE6T26=C33707D6T27=F4D50D87T28=455A14EDT29=A9E3E905T30=FCEFA3F8T31=676F02D9T32=8D2A4C8AT33=FFFA3942T34=8771F681T35=699D6122T36=FDE5380CT37=A4BEEA44T38=4BDECFA9T39=F6BB4B60T40=BEBFBC70T41=289B7EC6T42=EAA127FAT43=D4EF3085

31、T44=04881D05T45=D9D4D039T46=E6DB99E5T47=1FA27CF8T48=C4AC5665T49=F4292244T50=432AFF97T51=AB9423A7T52=FC93A039T53=655B59C3T54=8F0CCC92T55=FFEFF47DT56=85845DD1T57=6FA87E4FT58=FE2CE6E0T59=A3014314T60=4E0811A1T61=F7537E82T62=BD3AF235T63=2AD7D2BBT64=EB86D391u常数表常数表T：64个个32位常数位常数p Ti =232 abs(sin(i)的整数部分的整

32、数部分(i=1,2,64).39MD5压缩函数压缩函数HMD5 u常数表常数表T：64个个32位常数位常数p Ti =232abs(sin(i)的整数部分(i=1,2,64).p常数表T的作用是“随机化”32位的输入数据，即消除输入数据的规律性。pHMD5的第k轮处理过程使用常数表T的元素 T16(k1)+1, 16(k1)+2,16k (k=1,2,3,4)， 第k轮的第i次迭代使用元素 T16( k1)+ i(i=1,2,16).40MD5压缩函数HMD5 u循环左移位数循环左移位数s Ls(v)表示对表示对32位的变量位的变量v循环左移循环左移s位。位。s的值与轮的值与轮数和迭代步数有关

33、。数和迭代步数有关。 步数轮数123456789101112 13 14 15 161234754612911101714161522202321754612911101714161522202321754612911101714161522202321754612911101714161522202321415.2.1 MD55.2.1 MD5算法算法 l 步骤步骤5: 输出输出 依次对消息的L个512比特的分组进行处理，第L个分组处理后的输出值即是消息x的散列值MD(x)。 可将MD5的处理过程归纳如下：uCV0=IVuCVi+1=SUM32CVi, RFI (Yi, RFH (Yi, R

34、FG (Yi, RFF (Yi, CVi) ) (i=0,1, L1)uMD= CVL1.uIV =第三步定义的缓冲区ABCD的初值uL =消息经第一步和第二步处理后分组的个数uYi =消息的第i个512位分组uRFu =使用基本逻辑函数u的轮函数uSUM32=对输入字的模232相加uMD =散列值.425.2.2 MD55.2.2 MD5的安全性的安全性 l Rivest猜测，猜测，MD5可能是可能是128位位Hash函数中强度最大的。函数中强度最大的。l 目前，对MD5的攻击已取得以下结果：uT. Berson（1992）已经证明，对单轮的MD5算法，利用差分密码分析，可以在合理的时间内找

35、出散列值相同的两条消息。这一结果对MD5四轮运算的每一轮都成立。但是，目前尚不能将这种攻击推广到具有四轮运算的MD5上.uB. Boer和A. Bosselaers（1993）说明了如何找到消息分组和MD5两个不同的初始值,使它们产生相同的输出. 也就是说, 对一个512位的分组, MD5压缩函数对缓冲区ABCD的不同值产生相同的输出,这种情况称为伪碰撞（pseudo-collision）.目前尚不能用该方法成功攻击MD5算法.435.2.2 MD55.2.2 MD5的安全性的安全性 uH. Dobbertin（1996）找到了MD5无初始值的碰撞(pseudo-collision).给定一个

36、512位的分组,可以找到另一个512位的分组,对于选择的初始值IV0,它们的MD5运算结果相同. 到目前为止, 尚不能用这种方法对使用MD5初始值IV的整个消息进行攻击.u我国山东大学王小云教授（我国山东大学王小云教授（2004）提出的攻击对）提出的攻击对MD5最具威胁。对于最具威胁。对于MD5的初始值的初始值IV，王小云找到，王小云找到了许多了许多512位的分组对，它们的位的分组对，它们的MD5值相同值相同.u国际密码学家国际密码学家Lenstra利用王小云等提供的利用王小云等提供的MD5碰撞，碰撞，伪造了符合伪造了符合X.509标准的数字证书标准的数字证书. l MD5算法抗密码分析能力较

37、弱算法抗密码分析能力较弱,对对MD5的生日攻击所需的生日攻击所需代价为代价为264数量级数量级. 所以所以, 必须设计新的必须设计新的Hash算法算法, 使其与使其与MD5相比具有更长的散列值和更高的安全性相比具有更长的散列值和更高的安全性.44第第5章章 Hash函数与消息认证函数与消息认证 l 5.4 5.4 基于分组密码与离散对数的基于分组密码与离散对数的HashHash函数函数l 5.5 5.5 消息认证消息认证455.3 5.3 安全安全HashHash算法算法SHASHA 1 1l 安全安全Hash算法算法SHA（secure hash algorithm）由美国标）由美国标准与技

38、术研究所（准与技术研究所（NIST）设计并于）设计并于1993年作为联邦信息年作为联邦信息处理标准（处理标准（FIPS 180）发布）发布l 修改版于修改版于1995年发布（年发布（FIPS 180 1），通常称之为），通常称之为SHA 1。该标准称为。该标准称为安全安全Hash函数函数。l RFC 3174也给出了也给出了SHA 1，它基本上是复制，它基本上是复制FIPS 180 1的内容，但增加了的内容，但增加了C代码实现。代码实现。l SHA 1算法的输入是长度小于算法的输入是长度小于264的任意消息的任意消息x，输出，输出160位的散列值。位的散列值。465.3.1 SHA5.3.1

39、SHA 1 1算法步骤算法步骤l SHA 1处理消息的过程与处理消息的过程与MD5类似，对输入消息按类似，对输入消息按512位位的分组为单位进行处理，整个算法分为五个步骤的分组为单位进行处理，整个算法分为五个步骤l 步骤步骤1: 增加填充位增加填充位 在消息右边增加若干比特，使其长度与在消息右边增加若干比特，使其长度与448模模512同余。即使消息本身同余。即使消息本身已经满足上述长度要求，仍然需要进行填充。填充位数在已经满足上述长度要求，仍然需要进行填充。填充位数在1到到512之之间。填充比特的第一位是间。填充比特的第一位是“1”，其它均为，其它均为“0”。l 步骤步骤2: 附加消息长度值附

40、加消息长度值 用用64位表示原始消息位表示原始消息x的长度，并将其附加在步骤的长度，并将其附加在步骤1所得结果之后。所得结果之后。l 步骤步骤1与步骤与步骤2一起称为消息的预处理一起称为消息的预处理 经预处理后，原消息长度变为经预处理后，原消息长度变为512的倍数。设原消息的倍数。设原消息x经预处理后变经预处理后变为消息为消息Y=Y0 Y1 YL 1，其中，其中Yi（i =0,1,L 1）是）是512比特。在后面的比特。在后面的步骤中，将对步骤中，将对512比特的分组比特的分组Yi进行处理。进行处理。475.3.1 SHA5.3.1 SHA 1 1算法步骤算法步骤l 步骤步骤3: 初始化缓冲区

41、初始化缓冲区 SHA 1算法的中间结果和最终结果保存在算法的中间结果和最终结果保存在160位的缓冲区里，缓冲区位的缓冲区里，缓冲区用用5个个32位的寄存器表示。位的寄存器表示。5个缓冲区记为个缓冲区记为A、B、C、D、E，其初始，其初始值为下列值为下列32位整数（位整数（16进制表示）：进制表示）： 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. 其中，前其中，前4个初始值与个初始值与MD5的初始值相同。的初始值相同。SHA 1以大端格式存储缓以大端格式存储缓冲区的值，即字的最高有效字节存于

42、低地址字节位置。因此，上述冲区的值，即字的最高有效字节存于低地址字节位置。因此，上述初始值存储为（十六进制）：初始值存储为（十六进制）： 字字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.485.3.1 SHA5.3.1 SHA 1 1算法步骤算法步骤l 步骤步骤4: 以以512位的分组（位的分组（16个字）为单位处理消息个字）为单位处理消息uSHA 1是迭代是迭代Hash函数，其压缩函数为：函数，其压缩函数为：. 160512160SHA1 , 01 , 0:Hu步骤步骤4是

43、是SHA 1算法的主循环，它以算法的主循环，它以512比特作为分组，比特作为分组，重复应用压缩函数重复应用压缩函数HSHA，从消息，从消息Y的第一个分组的第一个分组Y1开开始，依次对每个分组始，依次对每个分组Yi进行压缩，直至最后分组进行压缩，直至最后分组YL 1，然后输出消息然后输出消息x的的Hash值。值。uSHA 1循环次数等于消息循环次数等于消息Y中中512比特分组的数目比特分组的数目L。49SHASHA 1 1的的压缩函数压缩函数H HSHASHA u由四轮处理组成由四轮处理组成u加法是模加法是模232相加相加 CVi (160)Yi (512)BCDAEf4, K, W60,61,

44、79, 20步BCDAEf2, K, W20,21,39, 20步BCDAEf3, K, W40,41,59, 20步BCDAEf1, K, W0,1,19, 20步 + + + + +CVi+1 (160)50SHASHA 1 1的压缩函数的压缩函数H HSHASHA u压缩函数压缩函数HSHA的四轮处理过程的算法结构相同，每一轮的四轮处理过程的算法结构相同，每一轮要对缓冲区要对缓冲区ABCDE进行进行20次迭代，每次迭代的运算形次迭代，每次迭代的运算形式为式为DC,(B),A,),(A)D)C,(B,(EED,C,B,A,305LKWLftt A B C D E A B C D E + +

45、 f +Wt +KtL30L5 其中其中A、B、C、D、E分别为五个缓冲分别为五个缓冲区中的字，运算结区中的字，运算结束后再将（束后再将（A、B、C、D、E）循环右）循环右移一个字。移一个字。51DCBD)(CD)(BC)(BDCBD)B(C)(BSHASHA 1 1的压缩函数的压缩函数H HSHASHA u基本逻辑函数基本逻辑函数fp每一轮使用一个基本逻辑函数每一轮使用一个基本逻辑函数f，每个基本逻辑函，每个基本逻辑函数的输入是三个数的输入是三个32位的字，输出是一个位的字，输出是一个32位的字，位的字，它执行位逻辑运算，即输出的第它执行位逻辑运算，即输出的第n位是其三个输入位是其三个输入第

46、第n位的函数。位的函数。轮数基本逻辑函数ff(B, C, D)1234f1(B, C, D)f2(B, C, D)f3(B, C, D)f4(B, C, D)52SHASHA 1 1的压缩函数的压缩函数H HSHASHA u基本逻辑函数基本逻辑函数fp基本逻辑函数基本逻辑函数f的真值表的真值表B C Df1 f2 f3 f40 0 00 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 153SHASHA 1 1的压缩函数的压缩函数H HSHASHA u字组字组Wtp

47、t（0t79）代表迭代步数，依次表示第一、二、三、四轮处理过程进行的迭代次序pWt(0t79)是32比特的字，它的前面16个字W0,W1,W15依次取自当前输入分组Yi，其余字为).79,.,17,16()(3814161tWWWWLWttttt u加法常数表加法常数表Kt30303030222325210迭代步数迭代步数十六进制十六进制十进制十进制0t1920t3940t5960t795A8279996ED9EBA18F1BBCDCCA62C1D6545.3.1 SHA5.3.1 SHA 1 1算法步骤算法步骤l 步骤步骤5: 输出输出u第L个分组处理后的输出值即是消息x的散列值MD(x)u

48、SHA1的处理过程归纳如下：pCV0=IVp CVi+1=SUM32(CVi, ABCDEi ) (i=0,1, L1)pMD= CVL1u其中：pIV =第三步定义的缓冲区ABCDE的初值pABCDEi =处理第i个消息分组时最后一轮的输出pL =消息经第一步和第二步处理后分组的个数pSUM32=对输入字的模232相加pMD =散列值.555.3.2 SHA5.3.2 SHA 1 1和和MD5MD5的比较的比较l SHA 1与与MD5的算法类似，所以它们的性质极为相似的算法类似，所以它们的性质极为相似l 抗穷举攻击的能力抗穷举攻击的能力uSHA1抗穷举攻击的能力比MD5强 u用穷举攻击方法产

49、生具有给定散列值的消息pMD5需要的代价为2128数量级pSHA1需要的代价为2160数量级 u用穷举攻击方法产生两个具有相同散列值的消息 pMD5需要的代价为264数量级pSHA1需要的代价为280数量级 l 抗密码分析的能力抗密码分析的能力 uMD5算法抗密码分析的能力较弱算法抗密码分析的能力较弱uSHA 1算法抗密码分析的能力似乎并不弱算法抗密码分析的能力似乎并不弱 565.3.2 SHA5.3.2 SHA 1 1和和MD5MD5的比较的比较l 速度速度 SHA 1执行的速度比执行的速度比MD5的速度慢得多的速度慢得多 l 简洁性简洁性 SHA 1和和MD5两种算法都易于描述和实现，不需

50、要使用两种算法都易于描述和实现，不需要使用大的程序和置换表大的程序和置换表 l 数据的存储方式数据的存储方式 MD5使用使用little endian方式，方式，SHA 1使用使用big endian方式。方式。这两种方式没有本质的差异这两种方式没有本质的差异 57第第5章章 Hash函数与消息认证函数与消息认证l 5.5 5.5 消息认证消息认证585.4 5.4 基于分组密码与离散对数的基于分组密码与离散对数的HashHash函数函数l Hash函数的间接构造法函数的间接构造法u利用已有的密码算法构造利用已有的密码算法构造Hash函数函数u如果密码算法是安全的，那么利用它所构造的如果密码算

51、法是安全的，那么利用它所构造的Hash函数也是安全的函数也是安全的595.4.1 5.4.1 利用分组密码算法构造利用分组密码算法构造HashHash函数函数l 已知条件已知条件 设设Ek是一个分组长度为是一个分组长度为n的分组密码的加密算法，的分组密码的加密算法，密钥为密钥为k，对于任意的消息，对于任意的消息x，首先对，首先对x进行分组，进行分组，每组的长度为每组的长度为n。设消息。设消息x为为: x=x1 x2xL, 其中其中xi GF(2)n（1 i L）.605.4.1 5.4.1 利用分组密码算法构造利用分组密码算法构造HashHash函数函数l 基于分组密码基于分组密码CBC工作模

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

53、分组密码算法构造HashHash函数函数1() (1),iikiyxEyiL IV=y0 x1 y1 Ek x2 y2 EkyL=hCFB(x) xL Ekl 在密钥公开的情况下，基于分组密码在密钥公开的情况下，基于分组密码CBC工作模工作模式和式和CFB工作模式构造的工作模式构造的Hash函数是不安全的，函数是不安全的，它们甚至不是弱无碰撞的它们甚至不是弱无碰撞的.62l 基于一些困难数学问题，诸如离散对数问题、因子分基于一些困难数学问题，诸如离散对数问题、因子分解问题、背包问题等可以构造出一些解问题、背包问题等可以构造出一些Hash函数，这些函数，这些Hash函数的安全性依赖于对应数学问题

54、的困难性函数的安全性依赖于对应数学问题的困难性l Chaum、Heijst和和Pfitzmann（1992年）提出的基于离年）提出的基于离散对数问题构造的散对数问题构造的Hash函数函数u运行速度不是很快运行速度不是很快u可以证明是安全的可以证明是安全的.l Chaum Heijst Pfitzmann Hash函数的构造函数的构造 设设p是一个大素数，是一个大素数，q=(p 1)/2是一个素数，是一个素数， 和和 是是Zp的两的两个本原元。假设离散对数个本原元。假设离散对数log 是计算上不可行的。定义是计算上不可行的。定义Hash函数函数h为：为：5.4.2 5.4.2 基于离散对数问题的

55、基于离散对数问题的Hash函数函数 .mod),(,:2121*pxxhZZZhxxppp 63l Chaum Heijst Pfitzmann Hash函数是强抗碰撞的函数是强抗碰撞的 用反证法，如果用反证法，如果Hash函数函数h有一对碰撞，那么可以有一对碰撞，那么可以证明离散对数证明离散对数log 能被有效计算能被有效计算. 设设(x1, x2)，(x3, x4)是是h的一对碰撞消息，即的一对碰撞消息，即(x1, x2) (x3, x4)，h(x1, x2)=h(x3, x4)，那么，那么 5.4.2 5.4.2 基于离散对数问题的基于离散对数问题的Hash函数函数 .modmod243

56、14321p p xxxxxxxx 记记d=gcd(x4 x2, p 1)。因为。因为p 1=2q，且，且q是一个素是一个素数，所以数，所以d 1,2, q, p 1。下面对。下面对d的四个取值分别的四个取值分别进行讨论。进行讨论。64l Chaum Heijst Pitzmann Hash函数是强抗碰撞的函数是强抗碰撞的 5.4.2 5.4.2 基于离散对数问题的基于离散对数问题的Hash函数函数 u情况情况1：d =1 此时此时x4 x2关于模关于模p 1有逆，设有逆，设y=(x4 x2) 1 mod (p 1)，则存在整数则存在整数k，使得，使得(x4 x2) y=1+ (p 1) k，

57、则有，则有.mod)()1()()1()(313124pyxxkpyxxkpyxx 因此，可计算离散对数因此，可计算离散对数).1(mod)()(log1243131pxxxxyxx 655.4.2 5.4.2 基于离散对数问题的基于离散对数问题的Hash函数函数 u情况情况2：d =2 因为因为p 1=2q,且且q是奇数是奇数,所以所以gcd(x4 x2, q)=1. 设设y=(x4 x2) 1 mod q，则存在整数，则存在整数k，使得，使得 (x4 x2) y=1+qk, 有有.mod,mod) 1(,mod1mod1)()(1)(21243124p p p p yxxyxxkqkyxx

58、qqp).1(mod) 1(log)(),1(mod)()(log124311243131p xxxxp xxxxyxx或或由于由于 q= 1 mod p，所以，所以).1(mod)(),1(mod)()(log124311243131p qxxxxp xxxxyxx或或容易检验二式中哪一个成立容易检验二式中哪一个成立. 即离散对数即离散对数log 能被有效能被有效计算计算.665.4.2 5.4.2 基于离散对数问题的基于离散对数问题的Hash函数函数 u情况情况3：d = q 因为因为 0 x2q 1, 0 x4q 1 (q 1)x4 x2q 1 gcd(x4 x2, q 1)= q不成立

59、不成立. 情况情况3不存在不存在.u情况情况4：d =p 1 这种情况只有在这种情况只有在x2=x4时才可能发生。这样就有时才可能发生。这样就有.mod31pxx 所以所以x1=x3，(x1, x2)= (x3, x4)，与已知矛盾，与已知矛盾! 即情况即情况4也不也不存在存在.67第第5章章 Hash函数与消息认证函数与消息认证685.5 5.5 消息认证消息认证l 认证（认证（authentication）是防止网络系统遭受主动攻击）是防止网络系统遭受主动攻击的重要技术的重要技术l 认证的主要目的有两个认证的主要目的有两个u第一，验证消息的发送者是真的，而不是冒充的，第一，验证消息的发送者

60、是真的，而不是冒充的，称为称为实体认证实体认证，包括信源、信宿等的认证和识别。，包括信源、信宿等的认证和识别。u第二，验证信息的完整性，即验证数据在传送或存第二，验证信息的完整性，即验证数据在传送或存储过程中未被篡改、重放或延迟，称为储过程中未被篡改、重放或延迟，称为消息认证消息认证。695.5.15.5.1 消息认证码消息认证码l 带密钥的带密钥的Hash函数称为函数称为消息认证码消息认证码(MAC：message authentication code).u消息认证码是实现消息认证的重要工具消息认证码是实现消息认证的重要工具.uMAC有两个不同的输入，一个是消息有两个不同的输入，一个是消息

61、x，另一个是密钥，另一个是密钥K .uMAC产生定长的输出产生定长的输出.u实例实例: 某一个大公司某一个大公司A想给它的客户发布一个新产品的广告想给它的客户发布一个新产品的广告,A希望不对广告内容加密希望不对广告内容加密,但又希望其它公司不能修改广告内容或但又希望其它公司不能修改广告内容或冒充公司冒充公司A发布同样的广告发布同样的广告,或者当广告内容被修改后能够发现或者当广告内容被修改后能够发现.如果使用不带密钥的如果使用不带密钥的Hash函数函数,由于其它公司可能在修改广告内由于其它公司可能在修改广告内容后产生新的散列值容后产生新的散列值,从而使从而使A无法确认原广告是否被修改无法确认原广

62、告是否被修改. l 设计设计MAC算法的要求算法的要求 在不知道密钥的情况下，难以找到两个不同的消息具有相在不知道密钥的情况下，难以找到两个不同的消息具有相同的输出。同的输出。705.5.15.5.1 消息认证码消息认证码l 基于分组密码基于分组密码CBC工作模式构造工作模式构造MACu基于分组密码基于分组密码CBC工作模式构造工作模式构造MAC算法已经成为算法已经成为ISO/IEC 9797 标准，它使用密文链接和双密钥三重标准，它使用密文链接和双密钥三重加密技术。加密技术。u设设EK表示以表示以K为密钥的加密算法，设为密钥的加密算法，设K是一个与是一个与K不不同的密钥，消息分组长度为同的密

63、钥，消息分组长度为n。u首先把消息首先把消息x分成分成L个个n位块位块 x=x1 x2xL，u计算：计算：uhK是一个是一个n位位MAC. 记为记为CBC-MAC.).()(),2()(),(1111,LKKKiiKiKHEExhLi xHEHxEH715.5.15.5.1 消息认证码消息认证码l 基于基于Hash函数构造函数构造MACu设设h是一个（不带密钥）是一个（不带密钥）Hash函数，函数，K是密钥，是密钥，x是是消息，则定义消息认证码消息，则定义消息认证码hK如下：如下：).|()(xKhxhKl 基于基于MD5算法直接构造消息认证码算法直接构造消息认证码MD5-MACuMD5-MA

64、C算法使用算法使用96字节的常数字节的常数).20(|3.c7bd75bdc27d29da94b87bc421b21d918,be3643a0aab5f5c7e728e962ce177b801134,c551b1e457cd43f290ac45ef972121210i TTTTTTUTTTiiiiiii 其中下标加法运算是模其中下标加法运算是模3相加相加. u如果密钥如果密钥K的长度小于的长度小于128位，则通过多次自行链接，最位，则通过多次自行链接，最后截取左边后截取左边128位作为以下算法中使用的密钥位作为以下算法中使用的密钥K。725.5.15.5.1 消息认证码消息认证码u将密钥将密钥

65、K扩展成扩展成3个个16字节的子密钥字节的子密钥K0，K1，K2，其中，其中 把把K0，K1分成分成4个个32位的子串位的子串Kji（j=0,1, i=0,1,2,3）.5MD).20()|(5MDMD5i KUKK ii表表示示不不进进行行填填充充的的其其中中u对对MD5进行修改：用进行修改：用K0代替代替MD5的的4个个32位寄存器位寄存器ABCD. 把把K1i与与MD5第第i +1遍中每个常数遍中每个常数232sin(j)进行模进行模232加法加法.u将将512位的分组位的分组 链接到消息链接到消息x右边，再按右边，再按MD5的要求进行填充的要求进行填充. 2212022|TKTKTKK

66、u将上一步的结果输入到修改后的将上一步的结果输入到修改后的MD5中，取其输出的前中，取其输出的前一半（一半（64位）作为消息位）作为消息x的消息认证码的消息认证码MD5-MAC (x).uMD5-MAC软件实现比较容易，其运算速度与软件实现比较容易，其运算速度与MD5大体相近大体相近 .735.5.25.5.2 HMAC HMAC算法算法 l 消息认证码消息认证码HMAC（keyed-hashing for message authentication code）是）是Bellare等人于等人于1996年提出，年提出，1997年作为年作为RFC 2104发表，成为事实上的发表，成为事实上的Internet标准，包括标准，包括IPSec协议在内的一些安全协议都使用协议在内的一些安全协议都使用了了HMAC算法。算法。l HMAC算法利用已有的算法利用已有的Hash函数，关键问题是如何函数，关键问题是如何使用密钥。使用不同的使用密钥。使用不同的Hash函数，就可以得到不同函数，就可以得到不同的的HMAC。选用。选用MD5时的时的HMAC记为记为HMAC-MD5，选用选用SHA-1时的时的HM