现代密码学-第6章课件

第六章消息认证和杂凑算法MessageAuthenticationandHashAlgorithms2023/7/231消息认证和杂凑算法消息认证用于抗击主动攻击验证接收消息的真实性和完整性真实性的确是由所声称的实体发过来的完整性未被篡改、插入和删除验证消息的顺序性和时间性（未重排、重放和延迟）2023/7/2326.1消息认证码(MAC)MessageAuthenticaionCode2023/7/2336.1.1消息认证码的定义和使用方式消息认证码:指消息被一密钥控制的公开函数作用后产生的、用于认证符的、固定长度的数值，也称为密码校验和。通信双方共享密钥KM||CKMCK(M)CK比较消息认证接收方相信发送方发来的消息未受篡改。接收方相信发送方不是冒充的2023/7/234消息认证码的定义和使用方式认证性和保密性-对明文认证M||CK1CMCK(M)K1比较EK2DK22023/7/235消息认证码的定义和使用方式认证性和保密性-对密文认证M||CK1CK1比较EK2DK2M2023/7/236产生MAC函数应满足的要求产生MAC的函数一般为多到1映射。nbit长的MAC共有2n个可能的取值，可能的消息数远大于2n。密钥长度为kbit，可能的密钥数为2k。敌手可获得明文和MAC,敌手可穷举攻击密钥。如果k>n,(2k-n个)可产生相同的MAC,敌手无法确定，还需要在这2k-n个密钥中继续试验。对消息认证码的穷举攻击代价大于攻击加密算法。敌手有可能不直接攻击密钥，而伪造能够通过检验的MAC和M。2023/7/237产生MAC函数应满足的要求假定敌手知道函数C，不知道K如果敌手得到M和CK(M)，则构造一满足CK(M’)=CK(M)的新消息在计算上不可行CK(M)在以下意义下是均匀分布的：随机选两个M,M’,Pr[CK(M)=CK(M’)]=2-n若M’是M的某个变换，Pr[CK(M)=CK(M’)]=2-n2023/7/2386.1.3数据认证算法基于CBC模式的DES算法，初始向量取为零。D1DES加密O1K第1次D2DES加密O2K第2次+D2DES加密ONK第N次+ON-12023/7/2396.2杂凑函数HashFunctions2023/7/2310杂凑函数的定义杂凑函数H是一个公开函数，将任意长的消息映射为较短的、固定长度的一个值H(M)H(M)称为杂凑值、消息摘要，是消息中所有bit的函数，提供了错误检测的能力2023/7/2311杂凑函数的使用方式（1）消息与杂凑码链接以后用单钥加密，密钥为A,B共享，保证消息来自A并且不被篡改M||HHMH(M)比较EKDK2023/7/2312杂凑函数的使用方式（2）单钥加密函数仅对hash值加密2023/7/2313杂凑函数的使用方式（3）使用发送方秘密钥加密杂凑值2023/7/2314杂凑函数的使用方式（4）用发送方秘密钥加密hash，再用单钥加密整个数据2023/7/2315杂凑函数的使用方式（5）通信双方共享一个秘密值SH2023/7/2316杂凑函数的使用方式在上一方式基础上加上加密H2023/7/2317杂凑函数应满足的条件函数的输入可以是任意长函数的输出是固定长已知x,求H(x)较为容易已知h，求H(x)＝h的在计算上不可行，即单向杂凑函数，如果满足这一性质，称为弱单向杂凑函数找出任意两个不同的x,y，是H(x)=H(y)在计算上不可行，满足这一性质，称为强单向杂凑函数2023/7/2318生日攻击（第I类生日攻击）H有n个输出，H(x)是一个特定的输出，如果对H随机取k个输入，至少有一个y使H(y)=H(x)的概率为0.5时，k有多大？

H(y)=H(x)的概率为1/n，不等的概率为1-1/n.取k个值都不等的为[1-1/n]k.至少有一个等的概率为1－[1-1/n]k，近似等于k/n。所以概率为0.5，k为n/2。2023/7/2319生日悖论在一个会场参加会议的人中，问使参会人员中至少有两个同日生的概率超过0.5的参会人数仅为23人。

t个人都不同时生日概率为，因此，至少有两人于同日生的概率为

解之，当t23时，p>0.5。对于n比特杂凑值的生日攻击，由上式可计算出，当进行2n/2次的选择明文攻击下成功的概率将超过0.63。

2023/7/2320迭代型杂凑函数的一般结构fffY0Y1YL-1bbbnnnnnIV=CV0CV1CVL-1CVL明文M被分为L个分组Y0,Y1,…,YL-1b:明文分组长度n:输出hash长度CV：各级输出，最后一个输出值是hash值无碰撞压缩函数f是设计的关键2023/7/2321

MD4是MD5杂凑算法的前身，由RonRivest于1990年10月作为RFC提出，1992年4月公布的MD4的改进（RFC1320，1321）称为MD5。6.3.1算法描述MD5算法采用图6.4描述的迭代型杂凑函数的一般结构，算法的框图如图6.5所示。算法的输入为任意长的消息（图中为K比特），分为512比特长的分组，输出为128比特的消息摘要。6.3MD5杂凑算法2023/7/2322图6.5MD5的算法框图2023/7/2323处理过程有以下几步：①对消息填充对消息填充，使得其比特长在模512下为448，即填充后消息的长度为512的某一倍数减64，留出的64比特备第2步使用。步骤①是必需的，即使消息长度已满足要求，仍需填充。例如，消息长为448比特，则需填充512比特，使其长度变为960，因此填充的比特数大于等于1而小于等于512。填充方式是固定的，即第1位为1，其后各位皆为0。2023/7/2324②附加消息的长度用步骤①留出的64比特以little-endian方式来表示消息被填充前的长度。如果消息长度大于264，则以264为模数取模。Little-endian方式是指按数据的最低有效字节（byte）（或最低有效位）优先的顺序存储数据，即将最低有效字节（或最低有效位）存于低地址字节（或位）。相反的存储方式称为big-endian方式。前两步执行完后，消息的长度为512的倍数（设为L倍），则可将消息表示为分组长为512的一系列分组Y0，Y1，…，YL-1，而每一分组又可表示为16个32比特长的字，这样消息中的总字数为N=L×16，因此消息又可按字表示为M[0,…,N-1]。2023/7/2325③对MD缓冲区初始化算法使用128比特长的缓冲区以存储中间结果和最终杂凑值，缓冲区可表示为4个32比特长的寄存器（A，B，C，D），每个寄存器都以littleendian方式存储数据，其初值取为（以存储方式）A=01234567，B=89ABCDEF，C=FEDCBA98，D=76543210，实际上为67452301，EFCDAB89，98BADCFE，10325476。④以分组为单位对消息进行处理每一分组Yq(q=0,…,L-1)都经一压缩函数HMD5处理。HMD5是算法的核心，其中又有4轮处理过程，如图6.6所示。⑤输出消息的L个分组都被处理完后，最后一个HMD5的输出即为产生的消息摘要。2023/7/2326图6.6MD5的分组处理框图2023/7/2327HMD5的4轮处理的逻辑函数不同，分别表示为F、G、H、I。每轮的输入为当前处理的消息分组Yq和缓冲区的当前值A、B、C、D，输出仍放在缓冲区中以产生新的A、B、C、D。每轮处理过程还需加上常数表T中四分之一个元素，分别为T[1…16],T[17…32],T[33…48],T[49…64]。第4轮的输出再与第1轮的输入CVq相加，相加时将CVq看作4个32比特的字，每个字与第4轮输出的对应的字按模232相加，相加的结果即为压缩函数HMD5的输出。（见175页表6.1）2023/7/2328步骤③到步骤⑤的处理过程可总结如下：CV0=IV;CVq+1=CVq+RFI[Yq,RFH[Yq,RFG[Yq,RFF[Yq,CVq]]]]MD=CVL其中IV是步骤③所取的缓冲区ABCD的初值，Yq是消息的第q个512比特长的分组，L是消息经过步骤①和步骤②处理后的分组数，CVq为处理消息的第q个分组时输入的链接变量（即前一个压缩函数的输出），RFx为使用基本逻辑函数x的轮函数，+为对应字的模232加法，MD为最终的杂凑值。2023/7/2329压缩函数HMD5中有4轮处理过程，每轮又对缓冲区ABCD进行16步迭代运算，每一步的运算形式为（见图6.7）a←b+CLSs(a+g(b,c,d)+X[k]+T[I])其中a、b、c、d为缓冲区的4个字，运算完成后再右循环一个字，即得这一步迭代的输出。g是基本逻辑函数F、G、H、I之一。CLSs是左循环移s位，s的取值由表6.2给出。（见176页表6.2）6.3.2MD5的压缩函数2023/7/2330图6.7压缩函数中的一步迭代示意图2023/7/2331T[i]为表T中的第i个字，+为模232加法。X[k]=M[q×16+k]，即消息第q个分组中的第k个字（k=1,…,16）。4轮处理过程中，每轮以不同的次序使用16个字，其中在第1轮以字的初始次序使用。第2轮到第4轮分别对字的次序i做置换后得到一个新次序，然后以新次序使用16个字。3个置换分别为 ρ2(i)=(1+5i)mod16 ρ3(i)=(5+3i)mod16 ρ4(i)=7imod162023/7/23326.3.3MD5的安全性目前对MD5的攻击已取得以下结果：①对单轮MD5使用差分密码分析，可在合理的时间内找出具有相同杂凑值的两个消息。但这种攻击还未能成功地推广到4轮MD5。②可找出一个消息分组和两个相关的链接变量（即缓冲区变量ABCD），使得算法产生出相同的输出。目前这种攻击还未能成功地推广到整个算法。③对单个512比特长的消息分组已成功地找出了碰撞，即可找出另一个消息分组，使得算法对两个消息分组的128比特长的输出相同。目前这种攻击还未成功推广到在有初值IV时对整个消息运行该算法。2023/7/23336.4安全杂凑算法6.4.1安全杂凑算法(securehashalgorithm,SHA)描述

算法的输入为小于264比特长的任意消息，分为512比特长的分组，输出为160比特长的消息摘要。算法的框图与图6.5一样，但杂凑值的长度和链接变量的长度为160比特。2023/7/2334①对消息填充与MD5的步骤①完全相同。②附加消息的长度与MD5的步骤②类似，不同之处在于以big-endian方式表示填充前消息的长度。即步骤①留出的64比特当作64比特长的无符号整数。③对MD缓冲区初始化算法使用160比特长的缓冲区存储中间结果和最终杂凑值，缓冲区可表示为5个32比特长的寄存器(A,B,C,D,E)，每个寄存器都以big-endian方式存储数据，其初始值分别为A=67452301，B=EFCDAB89，C=98BADCFB，D=10325476，E=C3D2E1F0。④以分组为单位对消息进行处理每一分组Yq都经一压缩函数处理，压缩函数由4轮处理过程（如图6.8所示）构成，每一轮又由20步迭代组成。算法的处理过程有以下几步：2023/7/2335图6.8SHA的分组处理框图2023/7/2336第4轮的输出（即第80步迭代的输出）再与第1轮的输入CVq相加，以产生CVq+1，其中加法是缓冲区5个字中的每一个字与CVq中相应的字模232相加。⑤输出消息的L个分组都被处理完后，最后一个分组的输出即为160比特的消息摘要。步骤③到步骤⑤的处理过程可总结如下： CV0=IV; CVq+1=SUM32(CVq,ABCDEq); MD=CVL其中IV是步骤③定义的缓冲区ABCDE的初值，ABCDEq是第q个消息分组经最后一轮处理过程处理后的输出，L是消息（包括填充位和长度字段）的分组数，SUM32是对应字的模232加法，MD为最终的摘要值。2023/7/2337如上所述，SHA的压缩函数由4轮处理过程组成，每轮处理过程又由对缓冲区ABCDE的20步迭代运算组成，每一步迭代运算的形式为（见图6.9）其中A，B，C，D，E为缓冲区的5个字，t是迭代的步数（0≤t≤79），ft(B,C,D)是第t步迭代使用的基本逻辑函数，CLSs为左循环移s位，Wt是由当前512比特长的分组导出的一个32比特长的字（导出方式见下面），Kt是加法常量，+是模232加法。6.4.2SHA的压缩函数2023/7/2338图6.9SHA的压缩函数中一步迭代示意图2023/7/2339下面说明如何由当前的输入分组（512比特长）导出Wt（32比特长）。前16个值（即W0,W1,…,W15）直接取为输入分组的16个相应的字，其余值（即W16,W17,…,W79）取为见图6.10。与MD5比较，MD5直接用一个消息分组的16个字作为每步迭代的输入，而SHA则将输入分组的16个字扩展成80个字以供压缩函数使用，从而使得寻找具有相同压缩值的不同的消息分组更为困难。2023/7/2340图6.10SHA分组处理所需的80个字的产生过程2023/7/23416.4.3SHA与MD5的比较抗穷搜索攻击的强度抗击密码分析攻击的强度速度简介与紧致性数据的存储方式2023/7/23426.5HMAC研究构造MAC的兴趣已转移到基于密码杂凑函数的构造方法，这是因为：密码杂凑函数(如MD5、SHA)的软件实现快于分组密码(如DES)的软件实现；密码杂凑函数的库代码来源广泛；密码杂凑函数没有出口限制，而分组密码即使用于MAC也有出口限制。2023/7/23436.5.1HMAC的设计目标Hash函数不使用密钥，不能直接用于MACHMAC要求可不经修改使用现有hash函数其中镶嵌的hash函数可易于替换为更快和更安全的hash函数保持镶嵌的hash