杨波 《现代密码学(第2版)》06-2.ppt

第6章 消息认证和杂凑算法,消息认证码 杂凑函数 MD5杂凑算法 安全杂凑算法 HMAC算法,6.3 MD5杂凑算法,MD4由Ron Rivest于1990年10月作为RFC提出 1992年4月公布的MD4的改进（RFC 1320，1321）称为MD56.3.1 算法描述,MD5算法采用图6.4描述的迭代型杂凑函数的一般结构，算法的输入为任意长的消息（K比特），分为512比特长的分组，输出为128比特的消息摘要 MD5算法的框图如图6.5所示图6.5 MD5的算法框图,处理过程步骤： 对消息填充，使得其比特长在模512下为448，即填充后消息的长度为512的某一倍数减64，留出的64比特备第2步使用 步骤是必需的，即使消息长度已满足要求，仍需填充例如，消息长为448比特，则需填充512比特，使其长度变为960，因此填充的比特数大于等于1而小于等于512 填充方式是固定的，即第1位为1，其后各位皆为0 附加消息的长度用步骤留出的64比特以little-endian方式来表示消息被填充前的长度如果消息长度大于264，则以264为模数取模 Little-endian方式是指按数据的最低有效字节（byte）（或最低有效位）优先的顺序存储数据，即将最低有效字节（或最低有效位）存于低地址字节（或位）。

相反的存储方式称为big-endian方式前两步执行完后，消息的长度为512的倍数（设为L倍），则可将消息表示为分组长为512的一系列分组Y0，Y1，，YL-1，而每一分组又可表示为16个32比特长的字，这样消息中的总字数为N=L16，因此消息又可按字表示为M0, , N-1 对MD缓冲区初始化：算法使用128比特长的缓冲区以存储中间结果和最终杂凑值，缓冲区可表示为4个32比特长的寄存器（A，B，C，D），每个寄存器都以little-endian方式存储数据，其初值取为（以存储方式）： A=01234567，B=89ABCDEF， C=FEDCBA98，D=76543210 实际上为67452301，EFCDAB89，98BADCFE，10325476 以分组为单位对消息进行处理每一分组Yq(q=0,,L-1)都经一压缩函数HMD5处理HMD5是算法的核心，其中又有4轮处理过程，如图6.6所示 输出消息的L个分组都被处理完后，最后一个HMD5的输出即为产生的消息摘要图6.6 MD5的压缩函数,HMD5的4轮处理过程结构一样，但所用的逻辑函数不同，分别表示为F、G、H、I每轮的输入为当前处理的消息分组Yq和缓冲区的当前值A、B、C、D，输出仍放在缓冲区中以产生新的A、B、C、D。

每轮处理过程还需加上常数表T中四分之一个元素，分别为T116, T1732, T3348, T4964表T有64个元素（表6.1），第i个元素Ti为232abs(sin(i))的整数部分，其中sin为正弦函数，i以弧度为单位由于abs(sin(i))大于0小于1，所以Ti可由32比特的字表示第4轮的输出再与第1轮的输入CVq相加，相加时将CVq看作4个32比特的字，每个字与第4轮输出的对应的字按模232相加，相加的结果即为压缩函数HMD5的输出步骤到步骤的处理过程可总结如下： CV0=IV; CVq+1=CVq+RFIYq,RFHYq,RFGYq,RFFYq,CVq MD=CVL 其中IV是步骤所取的缓冲区ABCD的初值，Yq是消息的第q个512比特长的分组，L是消息经过步骤和步骤处理后的分组数，CVq为处理消息的第q个分组时输入的链接变量（即前一个压缩函数的输出），RFx为使用基本逻辑函数x的轮函数，+为对应字的模232加法，MD为最终的杂凑值6.3.2 MD5的压缩函数,压缩函数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给出Ti为表T中的第i个字，+为模232加法Xk=Mq16+k，即消息第q个分组中的第k个字（k=1,,16）4轮处理过程中，每轮以不同的次序使用16个字，其中在第1轮以字的初始次序使用第2轮到第4轮分别对字的次序i做置换后得到一个新次序，然后以新次序使用16个字3个置换分别为 2(i)=(1+5i) mod 16 3(i)=(5+3i) mod 16 4(i)=7i mod 16,图6.7 压缩函数中的一步迭代示意图,4轮处理过程分别使用不同的基本逻辑函数F、G、H、I，每个逻辑函数的输入为3个32比特的字，输出是一个32比特的字，其中的运算为逐比特的逻辑运算，即输出的第n个比特是3个输入的第n个比特的函数，函数的定义由表6.3给出，其中，，-，分别是逻辑与、逻辑或、逻辑非和异或运算，表6.4是四个函数的真值表6.3.3 MD5的安全性,6.4 安全杂凑算法,安全杂凑算法SHA(Secure Hash Algorithm)由美国NIST设计，于1993年作为联邦信息处理标准（FIPS PUB 180）公布SHA-0是SHA的早期版本，SHA-0被公布后，NIST很快就发现了它的缺陷，修改后的版本称为SHA-1，简称为SHA。

SHA是基于MD4算法，其结构与MD4非常类似6.4.1 算法描述,算法的输入为小于264比特长的任意消息，分为512比特长的分组，输出为160比特长的消息摘要算法的框图与图6.5一样，但杂凑值的长度和链接变量的长度为160比特算法的处理过程有以下几步： 对消息填充：与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步迭代组成4轮处理过程结构一样，但所用的基本逻辑函数不同，分别表示为f1, f2, f3, f4每轮的输入为当前处理的消息分组Yq和缓冲区的当前值A, B, C, D, E，输出仍放在缓冲区以替代A, B, C, D, E的旧值，每轮处理过程还需加上一个加法常量Kt，其中0t79表示迭代的步数。

80个常量中实际上只有4个不同取值，如表6.5所示，其中 为x的整数部分图6.8 SHA的分组处理框图,第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为最终的摘要值6.4.2 SHA的压缩函数,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.9 SHA的压缩函数中一步迭代,基本逻辑函数的输入为3个32比特的字，输出是一个32比特的字，其中的运算为逐比特逻辑运算，即输出的第n个比特是3个输入的相应比特的函数函数的定义如表6.6表中,, ,分别是与、或、非、异或4个逻辑运算函数的真值表如表6.7所示输入分组（512比特长）导出Wt（32比特长）：如图6.10，前16个值（W0,W1,,W15）直接取为输入分组的16个相应的字，其余值（即W16,W17,,W79）取为 与MD5比较，MD5直接用一个消息分组的16个字作为每步迭代的输入，而SHA则将输入分组的16个字扩展成80个字以供压缩函数使用，从而使得寻找具有相同压缩值的不同的消息分组更为困难图6.10 SHA分组处理所需的80个字的产生过程,6.4.3 SHA与MD5的比较,由于SHA与MD5都是由MD4演化而来，所以两个算法极为相似 1. 抗穷搜索攻击的强度 由于SHA和MD5的消息摘要长度分别为160和128，所以用穷搜索攻击寻找具有给定消息摘要的消息分别需做O(2160)和O(2128)次运算，而用穷搜索攻击找出具有相同消息摘要的两个不同消息分别需做O(280)和O(264)次运算。

因此SHA抗击穷搜索攻击的强度高于MD5抗击穷搜索攻击的强度2. 抗击密码分析攻击的强度 由于SHA的设计准则未被公开，所以它抗击密码分析攻击的强度较难判断，似乎高于MD5的强度 3. 速度 由于两个算法的主要运算都是模232加法，因此都易于在32位结构上实现但比较起来,SHA的迭代步数(80步)多于MD5的迭代步数（64步），所用的缓冲区（160比特）大于MD5使用的缓冲区（128比特），因此在相同硬件上实现时，SHA的速度要比MD5的速度慢4. 简洁与紧致性 两个算法描述起来都较为简单，实现起来也较为简单，都不需要大的程序和代换表 5. 数据的存储方式 MD5使用little-endian方式，SHA使用big-endian方式两种方式相比看不出哪个更具优势，之所以使用两种不同的存储方式是因为设计者最初实现各自的算法时，使用的机器的存储方式不同6.5 HMAC算法,近年来研究构造MAC的兴趣已转移到基于密码杂凑函数的构造方法，这是因为： 密码杂凑函数(如MD5、SHA)的软件实现快于分组密码(如DES)的软件实现； 密码杂凑函数的库代码来源广泛； 密码杂凑函数没有出口限制，而分组密码即使用于MAC也有出口限制。

杂凑函数并不是为用于MAC而设计的，由于杂凑函数不使用密钥，因此不能直接用于MAC目前已提出了很多将杂凑函数用于构造MAC的方法，其中HMAC就是其中之一，已作为RFC2104被公布，并在IPSec和其他网络协议(如SSL)中得以应用6.5.1 HMAC的设计目标,RFC2104列举了HMAC的以下设计目标： 可不经修改而使用现有的杂凑函数，特别是那些易于软件实现的、源代码可方便获取且免费使用的杂凑函数 其中镶嵌的杂凑函数可易于替换为更快或更安全的杂凑函数 保持镶嵌的杂凑函数的最初性能，不因用于HMAC而使其性能降低 以简单方式使用和处理密钥 在对镶嵌的杂凑函数合理假设的基础上，易于分析HMAC用于认证时的密码强度前两个目标是HMAC被公众普遍接受的主要原因，这两个目标是将杂凑函数当作一个黑盒使用，这种方式有两个优点: 第一，杂凑函数的实现可作为实现HMAC的一个模块，这样一来，HMAC代码中很大一块就可事先准备好，无需修改就可使用；第二，如果HMAC要求使用更快或更安全的杂凑函数，则只需用新模块代替旧模块，例如用实现SHA的模块代替MD5的模块 最后一条设计目标则是HMAC优于其他基于杂凑函数的MAC的一个主要方面，HMAC在其镶嵌的杂凑函数具有合理密码强度的假设下，可证明是安全的。