现代密码学-第6章课件

第六章第六章 消息认证和杂凑算法消息认证和杂凑算法Message Authentication and Hash Algorithms2024/7/71消息认证和杂凑算法n消息认证用于抗击主动攻击消息认证用于抗击主动攻击n验证接收消息的真实性和完整性验证接收消息的真实性和完整性n真实性真实性n的确是由所声称的实体发过来的的确是由所声称的实体发过来的n完整性完整性n未被篡改、插入和删除未被篡改、插入和删除n验证消息的验证消息的顺序性顺序性和和时间性时间性（未重排、重放和延迟）（未重排、重放和延迟）2024/7/726.1消息认证码(MAC)Message Authenticaion Code2024/7/736.1.1消息认证码的定义和使用方式消息认证码的定义和使用方式n消息认证码消息认证码:指指消息被一密钥控制的公开函数作用后产消息被一密钥控制的公开函数作用后产生的、用于认证符的、固定长度的数值，也称为密码生的、用于认证符的、固定长度的数值，也称为密码校验和。校验和。n通信双方共享密钥通信双方共享密钥K KM|CKMCK(M)CK比较比较消息认证消息认证1.接收方相信接收方相信发送方发来发送方发来的消息未受的消息未受篡改。篡改。2.接收方相信接收方相信发送方不是发送方不是冒充的冒充的2024/7/74消息认证码的定义和使用方式n认证性和保密性认证性和保密性-对明文认证对明文认证M|CK1CMCK(M)K1比较比较EK2DK22024/7/75消息认证码的定义和使用方式n认证性和保密性认证性和保密性-对密文认证对密文认证M|CK1CK1比较比较EK2DK2M2024/7/76产生MAC函数应满足的要求n产生产生MACMAC的函数一般为多到的函数一般为多到1 1映射。映射。nbitnbit长的长的MACMAC共有共有2 2n n个可能的取值，可能的消息数远大于个可能的取值，可能的消息数远大于2 2n n。n密钥长度为密钥长度为kbitkbit，可能的密钥数为，可能的密钥数为2 2k k。n敌手可获得明文和敌手可获得明文和MAC,MAC,敌手可穷举攻击密钥。如果敌手可穷举攻击密钥。如果kn,kn,(2(2k-nk-n个个)可产生相同的可产生相同的MAC,MAC,敌手无法确定，还需要在这敌手无法确定，还需要在这2 2k-nk-n个密钥中继续试验。个密钥中继续试验。n对消息认证码的穷举攻击代价大于攻击加密算法。对消息认证码的穷举攻击代价大于攻击加密算法。n敌手有可能不直接攻击密钥，而伪造能够通过检验的敌手有可能不直接攻击密钥，而伪造能够通过检验的MACMAC和和M M。2024/7/77产生MAC函数应满足的要求n假定敌手知道函数假定敌手知道函数C C，不知道，不知道K Kn如果敌手得到如果敌手得到M M和和C CK K(M)(M)，则构造一满足，则构造一满足C CK K(M)=C(M)=CK K(M)(M)的新消息在计算上不可行的新消息在计算上不可行nC CK K(M)(M)在以下意义下是均匀分布的：随机在以下意义下是均匀分布的：随机选两个选两个M,M,PrCM,M,PrCK K(M)=C(M)=CK K(M)=2(M)=2-n-nn若若MM是是M M的某个变换，的某个变换，PrCPrCK K(M)=C(M)=CK K(M)=2(M)=2-n-n2024/7/786.1.3 数据认证算法数据认证算法n基于基于CBC模式的模式的DES算法，初始向量取为零。算法，初始向量取为零。D1DES加密O1K第1次D2DES加密O2K第2次+D2DES加密ONK第N次+ON-12024/7/796.2 杂凑函数Hash Functions2024/7/710杂凑函数的定义n杂凑函数杂凑函数H H是一个公开函数，将任意长的是一个公开函数，将任意长的消息映射为较短的、固定长度的一个值消息映射为较短的、固定长度的一个值H(M)H(M)nH(M)H(M)称为杂凑值、消息摘要，是消息中称为杂凑值、消息摘要，是消息中所有所有bitbit的函数，提供了错误检测的能力的函数，提供了错误检测的能力2024/7/711杂凑函数的使用方式（1 1）消息与杂凑码链接以后用单钥加密，密钥）消息与杂凑码链接以后用单钥加密，密钥为为A,BA,B共享，保证消息来自共享，保证消息来自A A并且不被篡改并且不被篡改M|HHMH(M)比较EKDK2024/7/712杂凑函数的使用方式（2）单钥加密函数仅对）单钥加密函数仅对hash值加密值加密2024/7/713杂凑函数的使用方式（3）使用发送方秘密钥加密杂凑值）使用发送方秘密钥加密杂凑值2024/7/714杂凑函数的使用方式（4）用发送方秘密钥加密）用发送方秘密钥加密hash，再用单，再用单钥加密整个数据钥加密整个数据2024/7/715杂凑函数的使用方式（5）通信双方共享一个秘密值）通信双方共享一个秘密值SH2024/7/716杂凑函数的使用方式n在上一方式基础上加上加密在上一方式基础上加上加密H2024/7/717杂凑函数应满足的条件n函数的输入可以是任意长函数的输入可以是任意长n函数的输出是固定长函数的输出是固定长n已知已知x,x,求求H(x)H(x)较为容易较为容易n已知已知h h，求，求H(x)H(x)h h的在计算上不可行，即单向的在计算上不可行，即单向杂凑函数，如果满足这一性质，称为弱单向杂杂凑函数，如果满足这一性质，称为弱单向杂凑函数凑函数n找出任意两个不同的找出任意两个不同的x,yx,y，是，是H(x)=H(y)H(x)=H(y)在计算在计算上不可行，满足这一性质，称为强单向杂凑函上不可行，满足这一性质，称为强单向杂凑函数数2024/7/718生日攻击n（第（第I I类生日攻击）类生日攻击）H H有有n n个输出，个输出，H(x)H(x)是一个是一个特定的输出，如果对特定的输出，如果对H H随机取随机取k k个输入，至少有个输入，至少有一个一个y y使使H(y)=H(x)H(y)=H(x)的概率为的概率为0.50.5时，时，k k有多大？有多大？H(y)=H(x)H(y)=H(x)的概率为的概率为1/n1/n，不等的概率，不等的概率为为1-1/n.1-1/n.取取k k个值都不等的为个值都不等的为1-1/n1-1/nk k.至少有至少有一个等的概率为一个等的概率为1 1 1-1/n1-1/nk k，近似等于，近似等于k/nk/n。所以概率为所以概率为0.50.5，k k为为n/2n/2。2024/7/719生日悖论n在一个会场参加会议的人中，问使参会人员中至少有在一个会场参加会议的人中，问使参会人员中至少有两个同日生的概率超过两个同日生的概率超过0.50.5的参会人数仅为的参会人数仅为2323人。人。t t个人都不同时生日概率为个人都不同时生日概率为 ，因此，至少有两人于同日生的概率为，因此，至少有两人于同日生的概率为 解之，当解之，当t t 2323时，时，p p0.50.5。对于。对于n n比特杂凑值的比特杂凑值的生日攻击，由上式可计算出，当进行生日攻击，由上式可计算出，当进行2 2n/2n/2次的选择明次的选择明文攻击下成功的概率将超过文攻击下成功的概率将超过0.630.63。2024/7/720迭代型杂凑函数的一般结构fffY0Y1YL-1bbbnnnnnIV=CV0CV1CVL-1CVL明文明文M被分为被分为L个分组个分组Y0,Y1,YL-1b:明文分组长度明文分组长度n:输出输出hash长度长度CV：各级输出，最后：各级输出，最后一个输出值是一个输出值是hash值值无碰撞压缩函无碰撞压缩函数数f是设计的是设计的关键关键2024/7/721 MD4MD4是是MD5MD5杂凑算法的前身，由杂凑算法的前身，由Ron RivestRon Rivest于于19901990年年1010月作为月作为RFCRFC提出，提出，19921992年年4 4月公布的月公布的MD4MD4的的改进（改进（RFC 1320RFC 1320，13211321）称为称为MD5MD5。6.3.1 6.3.1 算法描述算法描述MD5MD5算法采用图算法采用图6.46.4描述的迭代型杂凑函数的一般结描述的迭代型杂凑函数的一般结构，算法的框图如图构，算法的框图如图6.56.5所示。算法的输入为任意所示。算法的输入为任意长的消息（图中为长的消息（图中为K K比特），分为比特），分为512512比特长的分组，比特长的分组，输出为输出为128128比特的消息摘要。比特的消息摘要。6.3 MD5杂凑算法2024/7/722图图6.5 MD5的算法框图的算法框图2024/7/723处理过程有以下几步：处理过程有以下几步：对消息填充对消息填充，使得其比特长在模对消息填充对消息填充，使得其比特长在模512下为下为448，即填充后消息的长度为，即填充后消息的长度为512的某一倍数的某一倍数减减64，留出的，留出的64比特备第比特备第2步使用。步骤步使用。步骤是必需是必需的，即使消息长度已满足要求，仍需填充。例如，的，即使消息长度已满足要求，仍需填充。例如，消息长为消息长为448比特，则需填充比特，则需填充512比特，使其长度比特，使其长度变为变为960，因此填充的比特数大于等于，因此填充的比特数大于等于1而小于等而小于等于于512。填充方式是固定的，即第填充方式是固定的，即第1位为位为1，其后各位皆为，其后各位皆为0。2024/7/724 附加消息的长度用步骤附加消息的长度用步骤留出的留出的64比特以比特以little-endian方式来表示消息被填充前的长度。如果消息长度大于方式来表示消息被填充前的长度。如果消息长度大于264，则以则以264为模数取模。为模数取模。Little-endian方式是指按数据的最低有效字节（方式是指按数据的最低有效字节（byte）（或最低有效位）优先的顺序存储数据，即将最低有效字或最低有效位）优先的顺序存储数据，即将最低有效字节（或最低有效位）存于低地址字节（或位）。相反的存节（或最低有效位）存于低地址字节（或位）。相反的存储方式称为储方式称为big-endian方式。前两步执行完后，消息的长方式。前两步执行完后，消息的长度为度为512的倍数（设为的倍数（设为L倍），则可将消息表示为分组长为倍），则可将消息表示为分组长为512的一系列分组的一系列分组Y0，Y1，YL-1，而每一分组又可表示而每一分组又可表示为为16个个32比特长的字，这样消息中的总字数为比特长的字，这样消息中的总字数为N=L16，因此消息又可按字表示为因此消息又可按字表示为M0,N-1。2024/7/725 对对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的输的输出即为产生的消息摘要。出即为产生的消息摘要。2024/7/726图图6.6 MD5的分组处理框图的分组处理框图2024/7/727nHMD5的的4轮处理的逻辑函数不同，分别表示为轮处理的逻辑函数不同，分别表示为F、G、H、I。n每轮的输入为当前处理的消息分组每轮的输入为当前处理的消息分组Yq和缓冲区的和缓冲区的当前值当前值A、B、C、D，输出仍放在缓冲区中以产生输出仍放在缓冲区中以产生新的新的A、B、C、D。n每轮处理过程还需加上常数表每轮处理过程还需加上常数表T中四分之一个元中四分之一个元素，分别为素，分别为T116,T1732,T3348,T4964。n第第4轮的输出再与第轮的输出再与第1轮的输入轮的输入CVq相加，相加时相加，相加时将将CVq看作看作4个个32比特的字，每个字与第比特的字，每个字与第4轮输出轮输出的对应的字按模的对应的字按模232相加，相加的结果即为压缩函相加，相加的结果即为压缩函数数HMD5的输出。（见的输出。（见175页表页表6.1）2024/7/728步骤步骤到步骤到步骤的处理过程可总结如下：的处理过程可总结如下：CV0=IV;CVq+1=CVq+RFIYq,RFHYq,RFGYq,RFFYq,CVqMD=CVL其中其中IV是步骤是步骤所取的缓冲区所取的缓冲区ABCD的初值，的初值，Yq是消息的第是消息的第q个个512比特长的分组，比特长的分组，L是消息经过步骤是消息经过步骤和步骤和步骤处理后的处理后的分组数，分组数，CVq为处理消息的第为处理消息的第q个分组时输入的链接变量（即个分组时输入的链接变量（即前一个压缩函数的输出），前一个压缩函数的输出），RFx为使用基本逻辑函数为使用基本逻辑函数x的轮函的轮函数，数，+为对应字的模为对应字的模232加法，加法，MD为最终的杂凑值。为最终的杂凑值。2024/7/729压缩函数压缩函数HMD5中有中有4轮处理过程，每轮又对缓冲区轮处理过程，每轮又对缓冲区ABCD进行进行16步迭代运算，每一步的运算形式为（见图步迭代运算，每一步的运算形式为（见图6.7）ab+CLSs(a+g(b,c,d)+Xk+TI)其中其中a、b、c、d为缓冲区的为缓冲区的4个字，运算完成后再右循环个字，运算完成后再右循环一个字，即得这一步迭代的输出。一个字，即得这一步迭代的输出。g是基本逻辑函数是基本逻辑函数F、G、H、I之一。之一。CLSs是左循环移是左循环移s位，位，s的取值由表的取值由表6.2给出。给出。（见（见176页表页表6.2）6.3.2 MD5的压缩函数的压缩函数2024/7/730图图6.7 压缩函数中的一步迭代示意图压缩函数中的一步迭代示意图2024/7/731Ti为表为表T中的第中的第i个字，个字，+为模为模232加法。加法。Xk=Mq16+k，即消息第即消息第q个分组中的第个分组中的第k个个字（字（k=1,16）。）。4轮处理过程中，每轮以不同轮处理过程中，每轮以不同的次序使用的次序使用16个字，其中在第个字，其中在第1轮以字的初始次序轮以字的初始次序使用。第使用。第2轮到第轮到第4轮分别对字的次序轮分别对字的次序i做置换后得做置换后得到一个新次序，然后以新次序使用到一个新次序，然后以新次序使用16个字。个字。3个置个置换分别为换分别为2(i)=(1+5i)mod 163(i)=(5+3i)mod 164(i)=7i mod 162024/7/7326.3.3 MD5的安全性目前对目前对MD5的攻击已取得以下结果：的攻击已取得以下结果：对单轮对单轮MD5使用差分密码分析，可在合理的时间内使用差分密码分析，可在合理的时间内找出具有相同杂凑值的两个消息。但这种攻击还未能找出具有相同杂凑值的两个消息。但这种攻击还未能成功地推广到成功地推广到4轮轮MD5。可找出一个消息分组和两个相关的链接变量（即缓可找出一个消息分组和两个相关的链接变量（即缓冲区变量冲区变量ABCD），），使得算法产生出相同的输出。目使得算法产生出相同的输出。目前这种攻击还未能成功地推广到整个算法。前这种攻击还未能成功地推广到整个算法。对单个对单个512比特长的消息分组已成功地找出了碰撞，比特长的消息分组已成功地找出了碰撞，即可找出另一个消息分组，使得算法对两个消息分组即可找出另一个消息分组，使得算法对两个消息分组的的128比特长的输出相同。目前这种攻击还未成功推比特长的输出相同。目前这种攻击还未成功推广到在有初值广到在有初值IV时对整个消息运行该算法。时对整个消息运行该算法。2024/7/7336.4 安全杂凑算法安全杂凑算法6.4.1安全杂凑算法安全杂凑算法(secure hash algorithm,SHA)描述描述算法的输入为小于算法的输入为小于264比特长的任意消息，分为比特长的任意消息，分为512比特长比特长的分组，输出为的分组，输出为160比特长的消息摘要。算法的框图与图比特长的消息摘要。算法的框图与图6.5一样，但杂凑值的长度和链接变量的长度为一样，但杂凑值的长度和链接变量的长度为160比特。比特。2024/7/734 对消息填充与对消息填充与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步迭代组成。步迭代组成。算法的处理过程有以下几步：算法的处理过程有以下几步：2024/7/735图图6.8 SHA的分组处理框图的分组处理框图2024/7/736第第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为最终的摘要值。为最终的摘要值。2024/7/737如上所述，如上所述，SHA的压缩函数由的压缩函数由4轮处理过程组成，每轮处理轮处理过程组成，每轮处理过程又由对缓冲区过程又由对缓冲区ABCDE的的20步迭代运算组成，每一步迭步迭代运算组成，每一步迭代运算的形式为（见图代运算的形式为（见图6.9）其中其中A，B，C，D，E为缓冲区的为缓冲区的5个字，个字，t是迭代的步数是迭代的步数（0t79），），ft(B,C,D)是第是第t步迭代使用的基本逻辑函数，步迭代使用的基本逻辑函数，CLSs为左循环移为左循环移s位，位，Wt是由当前是由当前512比特长的分组导出比特长的分组导出的一个的一个32比特长的字（导出方式见下面），比特长的字（导出方式见下面），Kt是加法常量，是加法常量，+是模是模232加法。加法。6.4.2 SHA的压缩函数2024/7/738图6.9 SHA的压缩函数中一步迭代示意图2024/7/739下面说明如何由当前的输入分组（下面说明如何由当前的输入分组（512比特长）导出比特长）导出Wt（32比特长）。前比特长）。前16个值（即个值（即W0,W1,W15）直接取为直接取为输入分组的输入分组的16个相应的字，其余值（即个相应的字，其余值（即W16,W17,W79）取为取为见图见图6.10。与。与MD5比较，比较，MD5直接用一个消息分组的直接用一个消息分组的16个字作为每步迭代的输入，而个字作为每步迭代的输入，而SHA则将输入分组的则将输入分组的16个字个字扩展成扩展成80个字以供压缩函数使用，从而使得寻找具有相同个字以供压缩函数使用，从而使得寻找具有相同压缩值的不同的消息分组更为困难。压缩值的不同的消息分组更为困难。2024/7/740图图6.10 SHA分组处理所需的分组处理所需的80个字的产生过程个字的产生过程2024/7/7416.4.3 SHA6.4.3 SHA与与MD5MD5的比较的比较n抗穷搜索攻击的强度抗穷搜索攻击的强度n抗击密码分析攻击的强度抗击密码分析攻击的强度n速度速度n简介与紧致性简介与紧致性n数据的存储方式数据的存储方式2024/7/7426.5 HMAC 研究构造研究构造MACMAC的兴趣已转移到基于密码杂的兴趣已转移到基于密码杂凑函数的构造方法，这是因为：凑函数的构造方法，这是因为：n 密码杂凑函数密码杂凑函数(如如MD5MD5、SHA)SHA)的软件实现快于的软件实现快于分组密码分组密码(如如DES)DES)的软件实现；的软件实现；n 密码杂凑函数的库代码来源广泛；密码杂凑函数的库代码来源广泛；n 密码杂凑函数没有出口限制，而分组密码即密码杂凑函数没有出口限制，而分组密码即使用于使用于MACMAC也有出口限制。也有出口限制。2024/7/7436.5.1 HMAC的设计目标nHashHash函数不使用密钥，不能直接用于函数不使用密钥，不能直接用于MACMACnHMACHMAC要求要求n可不经修改使用现有可不经修改使用现有hashhash函数函数n其中镶嵌的其中镶嵌的hashhash函数可易于替换为更快和更安全的函数可易于替换为更快和更安全的hashhash函数函数n保持镶嵌的保持镶嵌的hashhash函数的最初性能，不因适用于函数的最初性能，不因适用于HAMCHAMC而使其性能降低而使其性能降低n以简单方式使用和处理密钥以简单方式使用和处理密钥n在对镶嵌的在对镶嵌的hashhash函数合理假设的基础上，易于分析函数合理假设的基础上，易于分析HMACHMAC用于认证时的密码强度用于认证时的密码强度2024/7/7446.5.2 6.5.2 算法描述算法描述图图6.11 6.11 HMACHMAC的算法框图的算法框图Ipad:b/8个个Opad:b/8个个K+:左面经填充左面经填充0后的后的K.K的长度为的长度为b比特比特2024/7/745算法的输出可如下表示算法的输出可如下表示:2024/7/746算法的运行过程可描述如下：算法的运行过程可描述如下：K K的左边填充的左边填充0 0以产生一个以产生一个b b比特长的比特长的K+K+（例如例如K K的长的长为为160160比特，比特，b=512b=512，则需填充则需填充4444个零字节个零字节0 0 x00 x00）。）。K K+与与ipad ipad 逐比特异或以产生逐比特异或以产生b b比特的分组比特的分组SiSi。将将M M链接到链接到S Si i后。后。将将H H作用于步骤作用于步骤产生的数据流。产生的数据流。K K+与与opadopad逐比特异或逐比特异或,以产生以产生b b比特长的分组比特长的分组S S0 0。将步骤将步骤得到的杂凑值链接在得到的杂凑值链接在S S0 0后。后。将将H H作用于步骤作用于步骤产生的数据流并输出最终结果。产生的数据流并输出最终结果。2024/7/747图图6.12 6.12 HMACHMAC的有效实现的有效实现2024/7/748写在最后写在最后成功的基成功的基础在于好的学在于好的学习习惯The foundation of success lies in good habits49 结束语当你尽了自己的最大努力时，失败也是伟大的，所以不要放弃，坚持就是正确的。When You Do Your Best,Failure Is Great,So DonT Give Up,Stick To The End演讲人：XXXXXX 时 间：XX年XX月XX日