第5章-消息认证与杂凑算法

1、现代密码理论-UESTC第第5章章 消息认证和杂凑算法消息认证和杂凑算法5.1 消息认证码消息认证码5.2 杂凑函数杂凑函数5.3 MD5杂凑算法杂凑算法5.4 安全杂凑算法安全杂凑算法5.5 HMAC算法算法现代密码理论-UESTC抗击被动攻击抗击被动攻击：加密加密抗击主动攻击：抗击主动攻击：消息认证消息认证消息认证是一个过程，用以验证接收消息的消息认证是一个过程，用以验证接收消息的真实性真实性和完整性和完整性，同时还用于验证消息的，同时还用于验证消息的顺序性和时间性顺序性和时间性。现代密码理论-UESTC消息认证机制需要产生消息认证机制需要产生认证符认证符。认证符：认证符：用于认证消息的数

2、值。用于认证消息的数值。认证符的产生方法：认证符的产生方法：消息认证码消息认证码MAC（message authentication code）和和杂凑函数杂凑函数（hash function）两大类。两大类。现代密码理论-UESTC消息认证码消息认证码: 指消息被一密钥控制的公开函数作用指消息被一密钥控制的公开函数作用后产生的、用作认证符的、固定长度的数值后产生的、用作认证符的、固定长度的数值, 或称或称为密码校验和。为密码校验和。此时需要通信双方此时需要通信双方A和和B共享一密钥共享一密钥K。5.1 消息认证码消息认证码 5.1.1 消息认证码的定义及使用方式消息认证码的定义及使用方式)(

3、MCMK现代密码理论-UESTC 如果仅收发双方知道如果仅收发双方知道K，且且B计算得到的计算得到的MAC与与接收到的接收到的MAC一致，则这一就实现了以下功能：一致，则这一就实现了以下功能： 接收方相信发送方发来的消息未被篡改。接收方相信发送方发来的消息未被篡改。 接收方相信发送方不是冒充的。接收方相信发送方不是冒充的。现代密码理论-UESTCMAC函数与加密算法类似，不同之处为函数与加密算法类似，不同之处为MAC函数函数不必是可逆的不必是可逆的，因此与加密算法相比更不易被攻破。，因此与加密算法相比更不易被攻破。上述过程中，由于消息本身在发送过程中是明文形上述过程中，由于消息本身在发送过程中

4、是明文形式，所以这一过程只提供认证性而未提供保密性。式，所以这一过程只提供认证性而未提供保密性。图图5.1 MAC的基本使用方式的基本使用方式现代密码理论-UESTC现代密码理论-UESTC5.1.2 产生产生MAC的函数应满足的要求的函数应满足的要求(1) 消息认证码的穷搜索攻击的代价比使用相同长度密消息认证码的穷搜索攻击的代价比使用相同长度密钥的加密算法的穷搜索攻击还要大。钥的加密算法的穷搜索攻击还要大。攻击者可假冒发假消息攻击者可假冒发假消息 给接收方。给接收方。(2)有些攻击法却不需要寻找产生有些攻击法却不需要寻找产生MAC所使用的密钥。所使用的密钥。(),KM CMMACK已知找 。

5、先说明两点，然后给出先说明两点，然后给出MAC函数应满足的要求。函数应满足的要求。)(MCMK 现代密码理论-UESTC第第1轮轮 已知已知M1、MAC1，其中其中MAC1=CK(M1)。对所有对所有2k个个可能的密钥计算可能的密钥计算MACi=CKi(M1)，得得2k-n个可能的密钥。个可能的密钥。第第2轮轮 已知已知M2、MAC2，其中其中MAC2=CK(M2)。对上一轮得对上一轮得到的到的2k-n个可能的密钥计算个可能的密钥计算MACi=CKi(M2)，得得2k-2n个可能个可能的密钥。的密钥。如此下去，如果如此下去，如果k=n，则上述攻击方式平均则上述攻击方式平均需要需要轮轮。例如，。

6、例如，密钥长为密钥长为80比特，比特，MAC长为长为32比特，则第比特，则第1轮将产生大约轮将产生大约248个可能密钥，第个可能密钥，第2轮将产生轮将产生216个可能的密钥，第个可能的密钥，第3轮即可轮即可找出正确的密钥。找出正确的密钥。攻击攻击MAC(找找K):现代密码理论-UESTC例如例如: 设设M=(X1X2Xm)是由是由64比特长的分组比特长的分组Xi(i=1,m)链接链接得到的，其消息认证码由以下方式得到：得到的，其消息认证码由以下方式得到：其中其中 表示异或运算，加密算法是电码本模式的表示异或运算，加密算法是电码本模式的DES。因此，因此，密钥长为密钥长为56比特，比特，MAC长

7、为长为64比特，如果敌手得到比特，如果敌手得到MCK(M)，那么敌手使用穷搜索攻击寻找那么敌手使用穷搜索攻击寻找K将需做将需做256次加密。次加密。然而敌手还可用以下方式攻击系统：然而敌手还可用以下方式攻击系统：12()()()mKKMXXXCMEM1111121121,()mmmmmmmmXXYYYYYYMXYMY YYY 伪造一新消息：且且M的的MAC与原消息与原消息M的的MAC相同。相同。现代密码理论-UESTC考虑到考虑到MACMAC所存在的以上攻击类型，可知它应满足以下要求，所存在的以上攻击类型，可知它应满足以下要求，其中假定敌手知道函数其中假定敌手知道函数C C，但不知道密钥但不知

8、道密钥K K： 如果敌手得到如果敌手得到M和和CK(M)，则构造一满足则构造一满足CK(M)=CK(M)的新消息的新消息M在计算上是不可行的。在计算上是不可行的。 CK(M)在以下意义下是均匀分布的：在以下意义下是均匀分布的： 随机选取两个消息随机选取两个消息M、M，PrCK(M)=CK(M)=2-n，其中其中n为为MAC的长。的长。 若若M是是M的某个变换，即的某个变换，即M=f(M)，例如例如f为插入一个或为插入一个或多个比特，那么多个比特，那么PrCK(M)=CK(M)= 2-n。现代密码理论-UESTC数据认证算法：数据认证算法：最为广泛使用的最为广泛使用的消息认证码消息认证码中的一中

9、的一个个。算法基于算法基于CBC模式的模式的DES算法算法，其初始向量取为零，其初始向量取为零向量。需被认证的数据被分为向量。需被认证的数据被分为64比特长的分组比特长的分组D1，D2，DN，其中最后一个分组不够其中最后一个分组不够64比特的话，比特的话，可在其右边填充一些可在其右边填充一些0，然后按以下过程计算数据认，然后按以下过程计算数据认证码：证码：5.1.3 数据认证算法数据认证算法现代密码理论-UESTC图图5.2 数据认证算法数据认证算法112213321()()()()KKKNKNNOEDOEDOOEDOOEDO其中其中E为为DES加密算法，加密算法，K为密钥。为密钥。数据认证码

10、或者取为数据认证码或者取为ON或者取为或者取为ON的最左的最左M个比特，其中个比特，其中16M64。现代密码理论-UESTC杂凑函数杂凑函数H是一公开函数是一公开函数：用于将任意长的消息：用于将任意长的消息M映射为较映射为较短的、固定长度的一个值短的、固定长度的一个值H(M)。作为认证符。作为认证符。称函数值称函数值H(M)为杂凑值、杂凑码、消息摘要，为杂凑值、杂凑码、消息摘要，hash值、散值、散列值。列值。杂凑码是消息中所有比特的函数，因此提供了一种杂凑码是消息中所有比特的函数，因此提供了一种错误检错误检测能力测能力，即改变消息中任何一个比特或几个比特都会使杂，即改变消息中任何一个比特或几

11、个比特都会使杂凑码发生改变。凑码发生改变。5.2 杂凑函数杂凑函数 5.2.1 杂凑函数的定义及使用方式杂凑函数的定义及使用方式现代密码理论-UESTC认证函数：认证函数：Hash函数（续）函数（续）哈希函数的基本用法（a）M|H(M)HKHM比较比较EKMDMBobAlice提供认证提供认证提供保密提供保密EK(M|H(M)现代密码理论-UESTC认证函数：认证函数：Hash函数（续）函数（续）哈希函数的基本用法（b）M|KEK(H(M)HHM比较比较EDBobAlice提供认证提供认证K现代密码理论-UESTC认证函数：认证函数：Hash函数（续）函数（续）哈希函数的基本用法（c）M|Kb

12、DKb(H(M)HHM比较比较DEBobAlice提供提供认证认证Kb现代密码理论-UESTC认证函数：认证函数：Hash函数（续）函数（续）哈希函数的基本用法(d)M|KDKb(H(M)HHM比较比较EDBobAlice提供认证提供认证提供保密提供保密KMMDKbEKbEk(M|DKb(H(M)现代密码理论-UESTC认证函数：认证函数：Hash函数（续）函数（续）哈希函数的基本用法（e）M|H(M|S)|HM比较比较BobAlice提供认证提供认证SS|H现代密码理论-UESTC认证函数：认证函数：Hash函数（续）函数（续）哈希函数的基本用法（f）M|H(M|S)|KHM比较比较EKMD

13、MBobAlice提供认证提供认证提供保密提供保密EK(M|H(M|S)SS|H现代密码理论-UESTC杂凑函数的目的是为需认证的数据产生一个杂凑函数的目的是为需认证的数据产生一个“指纹指纹”。为了。为了能够实现对数据的认证，杂凑函数应满足以下条件：能够实现对数据的认证，杂凑函数应满足以下条件： 函数的输入可以是任意长。函数的输入可以是任意长。 函数的输出是固定长。函数的输出是固定长。 已知已知x，求求H(x)较为容易，可用硬件或软件实现。较为容易，可用硬件或软件实现。 已知已知h，求使得求使得H(x)=h的的x在计算上是不可行的，这一性质在计算上是不可行的，这一性质称为函数的单向性，称称为函

14、数的单向性，称H(x)为为单向杂凑函数单向杂凑函数。 已知已知x，找出找出y(yx)使得使得H(y)=H(x)在计算上是不可行的。在计算上是不可行的。如果单向杂凑函数满足这一性质，则称其为如果单向杂凑函数满足这一性质，则称其为弱单向杂凑函数弱单向杂凑函数。 找出任意两个不同的输入找出任意两个不同的输入x、y，使得使得H(y)=H(x)在计算上在计算上是不可行的。是不可行的。强单向杂凑函数强单向杂凑函数。5.2.2 杂凑函数应满足的条件杂凑函数应满足的条件现代密码理论-UESTC1. 相关问题相关问题已知一杂凑函数已知一杂凑函数H有有n个可能的输出，个可能的输出，H(x)是一个是一个特定的输出，

15、如果对特定的输出，如果对H随机取随机取k个输入，则至少有个输入，则至少有一个输入一个输入y使得使得H(y)=H(x)的概率为的概率为0.5时，时，k有多大？有多大？以后为叙述方便，称对杂凑函数以后为叙述方便，称对杂凑函数H寻找上述寻找上述y的攻的攻击为击为第第类生日攻击类生日攻击。5.2.3 生日攻击生日攻击现代密码理论-UESTC因为因为H有有n个可能的输出，所以输入个可能的输出，所以输入y产生的输出产生的输出H(y)等于特等于特定输出定输出H(x)的概率是的概率是1/n，反过来说反过来说H(y)H(x)的概率是的概率是1-1/n。y取取k个随机值而函数的个随机值而函数的k个输出中没有一个等

16、于个输出中没有一个等于H(x)，其概其概率等于每个输出都不等于率等于每个输出都不等于H(x)的概率之积，为的概率之积，为1-1/nk，所所以以y取取k个随机值得到函数的个随机值得到函数的k个输出中至少有一个等于个输出中至少有一个等于H(x)的概率为的概率为1-1-1/nk。由由(1+x)k1+kx，其中其中|x|365，则不可能使得任意两个数据都不相同，因此假则不可能使得任意两个数据都不相同，因此假定定k365。k个数据项中任意两个都不相同的所有取值方式个数据项中任意两个都不相同的所有取值方式数为数为365!365 364(3651)(365)!kk现代密码理论-UESTC如果去掉任意两个都不

17、相同这一限制条件，可得如果去掉任意两个都不相同这一限制条件，可得k个数据项个数据项中所有取值方式数为中所有取值方式数为365k。所以可得所以可得365!(365, )(365)! 365365!(365, )1(365, )1(365)! 365kkQkkPkQkk 365!365 364(3651)(365)!kk当当k=23时，时，P(365,23)=0.5073，即上述问题只需即上述问题只需23人，人数人，人数如此之少。若如此之少。若k取取100，则，则P(365,100)=0.9999997，即获得如即获得如此大的概率。之所以称这一问题是悖论是因为当人数此大的概率。之所以称这一问题是悖

18、论是因为当人数k给定给定时，得到的至少有两个人的生日相同的概率比想象的要大时，得到的至少有两个人的生日相同的概率比想象的要大得多。得多。现代密码理论-UESTC将生日悖论推广为下述问题：将生日悖论推广为下述问题：已知一个在已知一个在1到到n之间之间均匀分布的整数型随机变量，若该变量的均匀分布的整数型随机变量，若该变量的k个取值个取值中至少有两个取值相同的概率大于中至少有两个取值相同的概率大于0.5，则，则k至少多至少多大？大？与上类似，与上类似， ，令令P(n, k)0.5，可可得得 。若取若取n=365，则则 。!( , )1()!knP n knkn 1.18knn1.18 36522.5

19、4k 现代密码理论-UESTC3. 生日攻击生日攻击生日攻击基于结论：设杂凑函数生日攻击基于结论：设杂凑函数H有有2m个可能的输个可能的输出（即输出长出（即输出长m比特），如果比特），如果H的的k个随机输入中个随机输入中至少有两个产生相同输出的概率大于至少有两个产生相同输出的概率大于0.5，则则 。第第类生日攻击：类生日攻击：寻找函数寻找函数H的具有相同输出的两的具有相同输出的两个任意输入的攻击方式。个任意输入的攻击方式。222mmk AB)(MHEMAsk现代密码理论-UESTC)(MHEAsk敌手对敌手对M产生出产生出2m/2个变形消息个变形消息:敌手还准备一个假冒的消息敌手还准备一个假冒

20、的消息M，产生出产生出2m/2个变形的消息个变形的消息:MM)()(MHMH 将将 提交给提交给A请求签字请求签字MAB)(MHEMAskAB)(MHEMAsk第第类生日攻击方式：类生日攻击方式：现代密码理论-UESTC第第类生日攻击方式：类生日攻击方式： 设用户将用图设用户将用图 (c)所示的方式发送消息，即所示的方式发送消息，即A用自己的秘用自己的秘密钥对消息的杂凑值加密，加密结果作为对消息的签字，密钥对消息的杂凑值加密，加密结果作为对消息的签字，连同明文消息一起发往接收者。连同明文消息一起发往接收者。 敌手对敌手对A发送的消息发送的消息M产生出产生出2m/2个变形的消息个变形的消息，同时

21、，同时敌敌手还准备一个假冒的消息手还准备一个假冒的消息M，并对假冒的消息产生出并对假冒的消息产生出2m/2个个变形的消息。变形的消息。 敌手在产生的两个消息集合中，找出杂凑值相同的一对敌手在产生的两个消息集合中，找出杂凑值相同的一对消息消息, ，由上述讨论可知敌手成功的概率大于由上述讨论可知敌手成功的概率大于0.5。如。如果不成功，则重新产生一个假冒的消息，并产生果不成功，则重新产生一个假冒的消息，并产生2m/2个变形，个变形，直到找到杂凑值相同的一对消息为止。直到找到杂凑值相同的一对消息为止。 敌手将敌手将 提交给提交给A请求签字请求签字，由于，由于 与与 的杂凑值相的杂凑值相同，所以可将同

22、，所以可将A对对 的签字当作对的签字当作对 的签字，将此签字连的签字，将此签字连同同 一起发给意欲的接收者。一起发给意欲的接收者。,M MMMMMMM现代密码理论-UESTC将一个消息变形为具有相同含义的另一消息的方法将一个消息变形为具有相同含义的另一消息的方法有很多。有很多。例如：对文件，敌手可在文件的单词之间插入很多例如：对文件，敌手可在文件的单词之间插入很多“space-space-backspace”字符对，然后将其中的字符对，然后将其中的某些字符对替换为某些字符对替换为“space-backspace-space ”就得就得到一个变形的消息。到一个变形的消息。现代密码理论-UESTC

23、目前使用的大多数杂凑函数其结构都是迭代型的，目前使用的大多数杂凑函数其结构都是迭代型的，如下图所示。如下图所示。5.2.4 迭代型杂凑函数的一般结构迭代型杂凑函数的一般结构现代密码理论-UESTC图图5.4 迭代型杂凑函数的一般结构迭代型杂凑函数的一般结构CV0=IV=n比特长的初值；比特长的初值；CVi=f(CVi-1,Yi-1)1iL；H(M)=CVLCVi-1，称为称为链接变量链接变量通常通常bn，称函数称函数f为压缩函数为压缩函数分析时需要先分析时需要先找出找出f 的碰撞的碰撞现代密码理论-UESTCMD4是是MD5杂凑算法的前身，由杂凑算法的前身，由Ron Rivest于于1990年

24、年10月作为月作为RFC提出，提出，1992年年4月公布的月公布的MD4的改的改进（进（RFC 1320，1321）称为称为MD5。5.3 MD5杂凑算法杂凑算法现代密码理论-UESTCMD5算法采用图算法采用图5.4描述的描述的迭代型杂凑函数迭代型杂凑函数的一般的一般结构，算法的框图如图结构，算法的框图如图5.5所示。所示。输入：输入：任意长任意长的消息的消息（图中为（图中为K比特）比特）分组：分组：512比特比特输出：输出：128比特的消息摘要。比特的消息摘要。5.3.1 算法描述算法描述现代密码理论-UESTC图图5.5 MD5的算法框图的算法框图现代密码理论-UESTC 对消息填充：对

25、消息填充：对消息填充，使得其比特长在模对消息填充，使得其比特长在模512下为下为448，即填充后消息的长度为，即填充后消息的长度为512的某一倍的某一倍数减数减64，留出的，留出的64比特备第比特备第2步使用。步使用。步骤是必需的，即使消息长度已满足要求，仍需步骤是必需的，即使消息长度已满足要求，仍需填充。例如，消息长为填充。例如，消息长为448比特，则需填充比特，则需填充512比特，比特，使其长度变为使其长度变为960，因此，因此填充的比特数大于等于填充的比特数大于等于1而而小于等于小于等于512。填充方式是填充方式是: 第第1位为位为1，其后各位皆为，其后各位皆为0。处理过程有以下几步：处

26、理过程有以下几步：现代密码理论-UESTC 附加消息的长度：用留出的附加消息的长度：用留出的64比特以比特以little-endian方式来表示消息被填充前的长度方式来表示消息被填充前的长度。如果消息。如果消息长度大于长度大于264，则以，则以264为模数取模。为模数取模。消息的长度为消息的长度为512的倍数的倍数（设为（设为L倍）倍）消息分消息分Y0，Y1，YL-1每一分组为每一分组为16个个32比特长的字比特长的字消息中的消息中的总字数为总字数为N=L16消息消息按按字字表示表示为为M0,N-1。Little-endian将将最低有效字节最低有效字节存于存于低地址字节低地址字节。相反的存储

27、方式称为相反的存储方式称为big-endian方式。方式。现代密码理论-UESTC 对对MD缓冲区初始化：缓冲区初始化：算法使用算法使用128比特长的缓比特长的缓冲区存储中间结果和最终杂凑值。冲区存储中间结果和最终杂凑值。缓冲区表示为缓冲区表示为4个个32比特长的寄存器比特长的寄存器(A，B，C，D)，每个寄存器都以每个寄存器都以little endian方式存储数据。方式存储数据。其初值取为（以存储方式）其初值取为（以存储方式）A=01234567，B=89ABCDEF， C=FEDCBA98，D=76543210实际上为实际上为67452301，EFCDAB89，98BADCFE，1032

28、5476。现代密码理论-UESTC 以分组为单位对消息进行处理：以分组为单位对消息进行处理：每一分组每一分组Yq(q=0,L-1)都经一压缩函数都经一压缩函数HMD5处理。处理。HMD5是算是算法的核心，其中又有法的核心，其中又有4轮处理过程，如图所示。轮处理过程，如图所示。 输出：输出：消息的消息的L个分组都被处理完后，最后一个个分组都被处理完后，最后一个HMD5的输出即为产生的消息摘要。的输出即为产生的消息摘要。现代密码理论-UESTCMD5的的分组处分组处理框图理框图CV0=IV;CVq+1=CVq+RFIYq,RFHYq,RFGYq,RFFYq,CVqMD=CVL现代密码理论-UEST

29、C处理过程总结如下：处理过程总结如下：CV0=IV;CVq+1=CVq+RFIYq,RFHYq,RFGYq,RFFYq,CVqMD=CVLIV: 缓冲区缓冲区ABCD的初值的初值Yq: 消息的第消息的第q个个512比特长的分组比特长的分组L: 消息经过处理后的分组数消息经过处理后的分组数CVq: 消息的第消息的第q个分组时输入的链接变量个分组时输入的链接变量RFx: 使用基本逻辑函数使用基本逻辑函数x的轮函数的轮函数+: 对应字的模对应字的模232加法加法MD: 最终的杂凑值。最终的杂凑值。现代密码理论-UESTC5.3.2 MD5的压缩函数的压缩函数 压缩函数压缩函数HMD5中有中有4轮处理

30、过程，每轮又对缓冲轮处理过程，每轮又对缓冲区区ABCD进行进行16步迭代运算，每一步的运算形式步迭代运算，每一步的运算形式:现代密码理论-UESTC压缩函数中的一步迭代示意图压缩函数中的一步迭代示意图ab+CLSs(a+g(b,c,d)+Xk+Ti)a、b、c、d: 缓冲区的缓冲区的4个字，运算后再个字，运算后再右循环一个字，即得这一右循环一个字，即得这一步迭代的输出步迭代的输出g: 基本逻辑函数基本逻辑函数F、G 、H、I之一之一CLSs: 左循环移左循环移s位，位，s的的取值由表取值由表5.2给出给出。Ti: 表表T中的第中的第i个字，个字，+为模为模232加法。加法。Xk=Mq16+k:

31、 消息第消息第q个分组中的第个分组中的第k个字个字（k=1,16）。）。现代密码理论-UESTC4轮处理过程中，每轮以不同的次序使用轮处理过程中，每轮以不同的次序使用16个字个字第第1轮轮以字的初始次序使用。以字的初始次序使用。第第2轮到第轮到第4轮轮分别对字的次序分别对字的次序i做置换后得到一个做置换后得到一个新次序，然后以新次序使用新次序，然后以新次序使用16个字。个字。3个置换分别为个置换分别为:2(i)=(1+5i) mod 163(i)=(5+3i) mod 164(i)=7i mod 16现代密码理论-UESTC4轮处理过程分别使用轮处理过程分别使用不同的基本逻辑函数不同的基本逻辑

32、函数F、G、H、I，输入输入为为3个个32比特的字比特的字输出输出是一个是一个32比特的字比特的字运算运算为逐比特的逻辑运算，分别是逻辑与、逻辑或、逻辑为逐比特的逻辑运算，分别是逻辑与、逻辑或、逻辑非和异或运算。非和异或运算。轮数轮数基本逻辑函数基本逻辑函数g(b, c, d)1234F(b, c, d)G(b, c, d)H(b, c, d)I(b, c, d)()(dbcb )()(dcdb )(dcb )(dbc 现代密码理论-UESTC现代密码理论-UESTC现代密码理论-UESTCMD5的安全性的安全性现代密码理论-UESTC 安全杂凑算法安全杂凑算法(Secure Hash Alg

33、orithm, SHA)由美由美国国NIST设计，于设计，于1993年作为联邦信息处理标准公年作为联邦信息处理标准公布。布。SHA是基于是基于MD4的算法，其结构与的算法，其结构与MD4非常非常类似。类似。5.4 安全杂凑算法安全杂凑算法现代密码理论-UESTC算法的输入：算法的输入：小于小于264比特长的任意消息，分为比特长的任意消息，分为512比特长的分组。比特长的分组。算法的输出：算法的输出：160比特长的消息摘要。比特长的消息摘要。算法的框图与算法的框图与MD5一样，但杂凑值的长度和链接一样，但杂凑值的长度和链接变量的长度为变量的长度为160比特。比特。5.4.1 算法描述算法描述现代

34、密码理论-UESTC160bit摘要KK264bit160SHASHASHASHA160160160现代密码理论-UESTC算法的处理过程有以下几步：算法的处理过程有以下几步： 对消息填充对消息填充: 与与MD5的步骤完全相同。的步骤完全相同。 附加消息的长度附加消息的长度: 与与MD5的步骤类似，不同以的步骤类似，不同以big-endian方式表示填充前消息的长度。方式表示填充前消息的长度。 对对MD缓冲区初始化缓冲区初始化: 使用使用160比特长的缓冲区存比特长的缓冲区存储中间结果和最终杂凑值。储中间结果和最终杂凑值。 缓冲区可表示为缓冲区可表示为5个个32比特长比特长的寄存器的寄存器(A

35、, B, C, D, E)，每个寄存器都以每个寄存器都以big-endian方式存储数据。方式存储数据。初始值分别为初始值分别为A=67452301，B=EFCDAB89，C=98BADCFB，D=10325476，E=C3D2E1F0。现代密码理论-UESTC 以分组为单位对消息进行处理：以分组为单位对消息进行处理：每一分组每一分组Yq都都经一压缩函数处理，压缩函数由经一压缩函数处理，压缩函数由4轮处理过程（如轮处理过程（如图图5.8所示）构成，每一轮又由所示）构成，每一轮又由20步迭代组成。步迭代组成。现代密码理论-UESTC5.8 SHA的分组处理框图的分组处理框图现代密码理论-UEST

36、C第第4轮的输出（即第轮的输出（即第80步迭代的输出）再与第步迭代的输出）再与第1轮的轮的输入输入CVq相加，以产生相加，以产生CVq+1，其中加法是缓冲区其中加法是缓冲区5个字中的每一个字与个字中的每一个字与CVq中相应的字模中相应的字模232相加。相加。 输出消息的输出消息的L个分组都被处理完后，最后一个分个分组都被处理完后，最后一个分组的输出即为组的输出即为160比特的消息摘要。比特的消息摘要。现代密码理论-UESTC步骤到步骤的处理过程可总结如下：步骤到步骤的处理过程可总结如下：CV0=IV;CVq+1=SUM32(CVq, ABCDEq);MD=CVL IV： 缓冲区缓冲区ABCDE

37、的初值。的初值。ABCDEq：第第q个消息分组经最后一轮处理过程处个消息分组经最后一轮处理过程处 理后的输出理后的输出 L： 是消息是消息(包括填充位和长度字段包括填充位和长度字段)的分组数的分组数 SUM32：是对应字的模是对应字的模232加法加法 MD： 最终的摘要值。最终的摘要值。现代密码理论-UESTCSHA的压缩函数由的压缩函数由4轮处理过程组成，每轮处理过程轮处理过程组成，每轮处理过程20步迭步迭代运算组成，每一步迭代运算的形式为代运算组成，每一步迭代运算的形式为A，B，C，D，E：缓冲区的缓冲区的5个字个字 t： 迭代的步数（迭代的步数（0t79）ft(B,C,D)：第第t t步

38、迭代使用的基本逻辑函数步迭代使用的基本逻辑函数CLSs： 左循环移左循环移s位位 Wt： 由当前由当前512比特长的分组导出的一个比特长的分组导出的一个32比特长的字比特长的字 Kt： 加法常量加法常量 +： 模模232加法。加法。5.4.2 SHA的压缩函数的压缩函数530, ,( ,)( ),( ),tttA B C D EEf B C DCLSAWKA CLSBC D现代密码理论-UESTC一步迭代一步迭代示意图示意图530, ,( ,)( ),( ),tttA B C D EEf B C DCLSAWKA CLSBC D现代密码理论-UESTC基本逻辑函数基本逻辑函数的输入为的输入为3

39、个个32比特的字，输出是一比特的字，输出是一个个32比特的字。表中比特的字。表中, ,分别是与、或、非、分别是与、或、非、异或异或4个逻辑运算。个逻辑运算。定义定义函数名函数名迭代的步数迭代的步数190 t3920 t5940 t7960 t),(1DCBfft ),(2DCBfft ),(3DCBfft ),(4DCBfft )()(DBCB DCB )()()(DCDBCB DCB )()(dbcb )()(dcdb )(dcb )(dbc 现代密码理论-UESTC下面说明如何由当前的输入分组（下面说明如何由当前的输入分组（512比特长）导比特长）导出出W0,W1,W15，W16,W17,

40、W79）现代密码理论-UESTC图图5.10 SHA分组处理所需的分组处理所需的80个字的产生过程个字的产生过程1161483()tttttWCLS WWWW现代密码理论-UESTC由于由于SHA与与MD5都是由都是由MD4演化而来，所以两个演化而来，所以两个算法极为相似。算法极为相似。1. 抗穷搜索攻击的强度抗穷搜索攻击的强度 由于由于SHA和和MD5的消息摘要长度分别为的消息摘要长度分别为160和和128，SHA抗击穷搜索攻击的强度高于抗击穷搜索攻击的强度高于MD5抗击穷搜索抗击穷搜索攻击的强度。攻击的强度。5.4.3 SHA与与MD5的比较的比较现代密码理论-UESTC2. 抗击密码分析攻击的强度抗击密码分析攻击的强度由于由于SHA的设计准则未被公开，所以它抗击密码分的设计准则未被公开，所以它抗击密码分析攻击的强度较难判断，似乎高于析攻击的强度较难判断，似乎高于MD5的强度。的强度。3. 速度速度由于两个算法的主要运算都是模由于两个算法的主要运算都是模232加