《消息认证和杂凑算法幻灯片.ppt》由会员分享，可在线阅读，更多相关《消息认证和杂凑算法幻灯片.ppt（97页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、消息认证和杂凑算法消息认证和杂凑算法第1页，共97页，编辑于2022年，星期日第2页，共97页，编辑于2022年，星期日第第1章曾介绍过信息安全所面临的基本攻击类型，包章曾介绍过信息安全所面临的基本攻击类型，包括被动攻击（获取消息的内容、业务流分析）和主动括被动攻击（获取消息的内容、业务流分析）和主动攻击（假冒、重放、消息的篡改、业务拒绝）。抗击攻击（假冒、重放、消息的篡改、业务拒绝）。抗击被动攻击的方法是前面已介绍过的加密，本章介绍的被动攻击的方法是前面已介绍过的加密，本章介绍的消息认证则是用来抗击主动攻击的。消息认证是一个消息认证则是用来抗击主动攻击的。消息认证是一个过程，用以验证接收消息
2、的真实性（的确是由它所声过程，用以验证接收消息的真实性（的确是由它所声称的实体发来的）和完整性（未被篡改、插入、删除）称的实体发来的）和完整性（未被篡改、插入、删除），同时还用于验证消息的顺序性和时间性（未重排、，同时还用于验证消息的顺序性和时间性（未重排、重放、延迟）。除此之外，在考虑信息安全时还需考重放、延迟）。除此之外，在考虑信息安全时还需考虑业务的不可否认性，即防止通信双方中的某一方对虑业务的不可否认性，即防止通信双方中的某一方对所传输消息的否认。实现消息的不可否认性可通过数所传输消息的否认。实现消息的不可否认性可通过数字签字，数字签字也是一种认证技术，它也可用于抗字签字，数字签字也是
3、一种认证技术，它也可用于抗击主动攻击。击主动攻击。第3页，共97页，编辑于2022年，星期日消息认证机制和数字签字机制都需有产生认证符的基消息认证机制和数字签字机制都需有产生认证符的基本功能，这一基本功能又作为认证协议的一个组成部本功能，这一基本功能又作为认证协议的一个组成部分。认证符是用于认证消息的数值，它的产生方法又分。认证符是用于认证消息的数值，它的产生方法又分为消息认证码分为消息认证码MAC（message authentication code）和杂凑函数（）和杂凑函数（hash function）两大类，下面分）两大类，下面分别介绍。别介绍。第4页，共97页，编辑于2022年，星期
4、日消息认证码是指消息被一密钥控制的公开函数作用后消息认证码是指消息被一密钥控制的公开函数作用后产生的、用作认证符的、固定长度的数值，也称为密产生的、用作认证符的、固定长度的数值，也称为密码校验和。此时需要通信双方码校验和。此时需要通信双方A和和B共享一密钥共享一密钥K。设设A欲发送给欲发送给B的消息是的消息是M，A首先计算首先计算MAC=CK(M)，其中，其中CK()是密钥控制的公开函数，然后向是密钥控制的公开函数，然后向B发送发送MMAC，B收到后做与收到后做与A相同的计算，求得一新相同的计算，求得一新MAC，并与收到的，并与收到的MAC做比较，如图做比较，如图6.1(a)所示。所示。6.1
5、 消息认证码消息认证码 6.1.1 消息认证码的定义及使用方式消息认证码的定义及使用方式第5页，共97页，编辑于2022年，星期日如果仅收发双方知道如果仅收发双方知道K，且，且B计算得到的计算得到的MAC与接收与接收到的到的MAC一致，则这一系统就实现了以下功能：一致，则这一系统就实现了以下功能：接收方相信发送方发来的消息未被篡改，这是因接收方相信发送方发来的消息未被篡改，这是因为攻击者不知道密钥，所以不能够在篡改消息后相应为攻击者不知道密钥，所以不能够在篡改消息后相应地篡改地篡改MAC，而如果仅篡改消息，则接收方计算的，而如果仅篡改消息，则接收方计算的新新MAC将与收到的将与收到的MAC不同
6、。不同。接收方相信发送方不是冒充的，这是因为除收发接收方相信发送方不是冒充的，这是因为除收发双方外再无其他人知道密钥，因此其他人不可能对自双方外再无其他人知道密钥，因此其他人不可能对自己发送的消息计算出正确的己发送的消息计算出正确的MAC。第6页，共97页，编辑于2022年，星期日AC函数与加密算法类似，不同之处为函数与加密算法类似，不同之处为MAC函数不必函数不必是可逆的，因此与加密算法相比更不易被攻破。是可逆的，因此与加密算法相比更不易被攻破。上述过程中，由于消息本身在发送过程中是明文形式，上述过程中，由于消息本身在发送过程中是明文形式，所以这一过程只提供认证性而未提供保密性。为提供所以这
7、一过程只提供认证性而未提供保密性。为提供保密性可在保密性可在MAC函数以后函数以后(如图如图6.1(b)或以前或以前(如图如图6.1(c)进行一次加密，而且加密密钥也需被收发双方进行一次加密，而且加密密钥也需被收发双方共享。在图共享。在图6.1(b)中，中，M与与MAC链接后再被整体加密，链接后再被整体加密，在图在图6.1(c)中，中，M先被加密再与先被加密再与MAC链接后发送。通链接后发送。通常希望直接对明文进行认证，因此图常希望直接对明文进行认证，因此图6.1(b)所示的使所示的使用方式更为常用。用方式更为常用。第7页，共97页，编辑于2022年，星期日图图6.1 MAC的基本使用方式的基
8、本使用方式第8页，共97页，编辑于2022年，星期日使用加密算法（单钥算法或公钥算法）加密消息时，使用加密算法（单钥算法或公钥算法）加密消息时，其安全性一般取决于密钥的长度。如果加密算法没有其安全性一般取决于密钥的长度。如果加密算法没有弱点，则敌手只能使用穷搜索攻击以测试所有可能的弱点，则敌手只能使用穷搜索攻击以测试所有可能的密钥。如果密钥长为密钥。如果密钥长为k比特，则穷搜索攻击平均将进比特，则穷搜索攻击平均将进行行2k-1个测试。特别地，对惟密文攻击来说，敌手如个测试。特别地，对惟密文攻击来说，敌手如果知道密文果知道密文C，则将对所有可能的密钥值，则将对所有可能的密钥值Ki执行解密执行解密
9、运算运算Pi=DKi(C)，直到得到有意义的明文。，直到得到有意义的明文。6.1.2 产生产生MAC的函数应满足的要求的函数应满足的要求第9页，共97页，编辑于2022年，星期日对对MAC来说，由于产生来说，由于产生MAC的函数一般都为多到一的函数一般都为多到一映射，如果产生映射，如果产生n比特长的比特长的MAC，则函数的取值范围，则函数的取值范围即为即为2n个可能的个可能的MAC，函数输入的可能的消息个数，函数输入的可能的消息个数N2n，而且如果函数所用的密钥为，而且如果函数所用的密钥为k比特，则可能比特，则可能的密钥个数为的密钥个数为2k。如果系统不考虑保密性，即敌手能。如果系统不考虑保密
10、性，即敌手能获取明文消息和相应的获取明文消息和相应的MAC，那么在这种情况下要，那么在这种情况下要考虑敌手使用穷搜索攻击来获取产生考虑敌手使用穷搜索攻击来获取产生MAC的函数所的函数所使用的密钥。使用的密钥。第10页，共97页，编辑于2022年，星期日假定假定kn，且敌手已得到，且敌手已得到M1和和MAC1，其中，其中MAC1=CK1（M1），敌手对所有可能的密钥值），敌手对所有可能的密钥值Ki求求MACi=CKi(M1)，直到找到某个，直到找到某个Ki使得使得MACi=MAC1。由于不同的密钥个数为由于不同的密钥个数为2k，因此将产生，因此将产生2k个个MAC，但其中仅有但其中仅有2n个不同
11、，由于个不同，由于2k2n，所以有很多密钥，所以有很多密钥（平均有（平均有2k/2n=2k-n个）都可产生出正确的个）都可产生出正确的MAC1，而，而敌手无法知道进行通信的两个用户用的是哪一个密钥，敌手无法知道进行通信的两个用户用的是哪一个密钥，还必须按以下方式重复上述攻击：还必须按以下方式重复上述攻击：第11页，共97页，编辑于2022年，星期日第第1轮轮已知已知M1、MAC1，其中，其中MAC1=CK(M1)。对所有。对所有2k个可能的密钥计算个可能的密钥计算MACi=CKi(M1)，得，得2k-n个可能的个可能的密钥。密钥。第第2轮轮已知已知M2、MAC2，其中，其中MAC2=CK(M2
12、)。对上一。对上一轮得到的轮得到的2k-n个可能的密钥计算个可能的密钥计算MACi=CKi(M2)，得，得2k-2n个可能的密钥。个可能的密钥。如此下去，如果如此下去，如果k=n，则上述攻击方式平均需要，则上述攻击方式平均需要轮。轮。例如，密钥长为例如，密钥长为80比特，比特，MAC长为长为32比特，则第比特，则第1轮轮将产生大约将产生大约248个可能密钥，第个可能密钥，第2轮将产生轮将产生216个可能的个可能的密钥，第密钥，第3轮即可找出正确的密钥。轮即可找出正确的密钥。第12页，共97页，编辑于2022年，星期日如果密钥长度小于如果密钥长度小于MAC的长度，则第的长度，则第1轮就有可能找轮
13、就有可能找出正确的密钥，也有可能找出多个可能的密钥，如果出正确的密钥，也有可能找出多个可能的密钥，如果是后者，则仍需执行第是后者，则仍需执行第2轮搜索。轮搜索。所以对消息认证码的穷搜索攻击比对使用相同长度密所以对消息认证码的穷搜索攻击比对使用相同长度密钥的加密算法的穷搜索攻击的代价还要大。然而有些钥的加密算法的穷搜索攻击的代价还要大。然而有些攻击法却不需要寻找产生攻击法却不需要寻找产生MAC所使用的密钥。所使用的密钥。第13页，共97页，编辑于2022年，星期日例如，设例如，设M=(X1X2Xm)是由是由64比特长的分组比特长的分组Xi(i=1,m)链接得到的，其消息认证码由以下方式链接得到的
14、，其消息认证码由以下方式得到：得到：其中其中表示异或运算，加密算法是电码本模式的表示异或运算，加密算法是电码本模式的DES。因此，密钥长为因此，密钥长为56比特，比特，MAC长为长为64比特，如果敌比特，如果敌手得到手得到MCK(M)，那么敌手使用穷搜索攻击寻找，那么敌手使用穷搜索攻击寻找K将将需做需做256次加密。然而敌手还可用以下方式攻击系统：次加密。然而敌手还可用以下方式攻击系统：将将X1到到Xm-1分别用自己选取的分别用自己选取的Y1到到Ym-1替换，求出替换，求出Ym=Y1Y2Ym-1(M)，并用，并用Ym替换替换Xm。因。因此敌手可成功伪造一新消息此敌手可成功伪造一新消息M=Y1Y
15、m，且，且M的的MAC与原消息与原消息M的的MAC相同。相同。第14页，共97页，编辑于2022年，星期日考虑到考虑到MAC所存在的以上攻击类型，可知它应满足所存在的以上攻击类型，可知它应满足以下要求，其中假定敌手知道函数以下要求，其中假定敌手知道函数C，但不知道密钥，但不知道密钥K：如果敌手得到如果敌手得到M和和CK(M)，则构造一满足，则构造一满足CK(M)=CK(M)的新消息的新消息M在计算上是不可行的。在计算上是不可行的。CK(M)在以下意义下是均匀分布的：在以下意义下是均匀分布的：随机选取两随机选取两个消息个消息M、M，PrCK(M)=CK(M)=2-n，其中，其中n为为MAC的长。
16、的长。若若M是是M的某个变换，即的某个变换，即M=f(M)，例如，例如f为插入为插入一个或多个比特，那么一个或多个比特，那么PrCK(M)=CK(M)=2-n。第15页，共97页，编辑于2022年，星期日第第1个要求是针对上例中的攻击类型的，此要求是说个要求是针对上例中的攻击类型的，此要求是说敌手不需要找出密钥敌手不需要找出密钥K而伪造一个与截获的而伪造一个与截获的MAC相相匹配的新消息在计算上是不可行的。第匹配的新消息在计算上是不可行的。第2个要求是说个要求是说敌手如果截获一个敌手如果截获一个MAC，则伪造一个相匹配的消息，则伪造一个相匹配的消息的概率为最小。最后一个要求是说函数的概率为最小
17、。最后一个要求是说函数C不应在消息不应在消息的某个部分或某些比特弱于其他部分或其他比特，否的某个部分或某些比特弱于其他部分或其他比特，否则敌手获得则敌手获得M和和MAC后就有可能修改后就有可能修改M中弱的部分，中弱的部分，从而伪造出一个与原从而伪造出一个与原MAC相匹配的新消息。相匹配的新消息。第16页，共97页，编辑于2022年，星期日数据认证算法是最为广泛使用的消息认证码中的一个，数据认证算法是最为广泛使用的消息认证码中的一个，已作为已作为FIPS Publication（FIPS PUB 113）并被）并被ANSI作为作为X9.17标准。标准。算法基于算法基于CBC模式的模式的DES算法
18、，其初始向量取为零算法，其初始向量取为零向量。需被认证的数据（消息、记录、文件或程序）向量。需被认证的数据（消息、记录、文件或程序）被分为被分为64比特长的分组比特长的分组D1，D2，DN，其中最后，其中最后一个分组不够一个分组不够64比特的话，可在其右边填充一些比特的话，可在其右边填充一些0，然后按以下过程计算数据认证码（见图然后按以下过程计算数据认证码（见图6.2）：）：6.1.3 数据认证算法数据认证算法第17页，共97页，编辑于2022年，星期日图图6.2 数据认证算法数据认证算法第18页，共97页，编辑于2022年，星期日其中其中E为为DES加密算法，加密算法，K为密钥。为密钥。数据
19、认证码或者取为数据认证码或者取为ON或者取为或者取为ON的最左的最左M个比特，个比特，其中其中16M64。第19页，共97页，编辑于2022年，星期日杂凑函数杂凑函数H是一公开函数，用于将任意长的消息是一公开函数，用于将任意长的消息M映映射为较短的、固定长度的一个值射为较短的、固定长度的一个值H(M)，作为认证符，作为认证符，称函数值称函数值H(M)为杂凑值、杂凑码或消息摘要。杂凑为杂凑值、杂凑码或消息摘要。杂凑码是消息中所有比特的函数，因此提供了一种错误检码是消息中所有比特的函数，因此提供了一种错误检测能力，即改变消息中任何一个比特或几个比特都会测能力，即改变消息中任何一个比特或几个比特都会
20、使杂凑码发生改变。使杂凑码发生改变。6.2 杂凑函数杂凑函数 6.2.1 杂凑函数的定义及使用方式杂凑函数的定义及使用方式第20页，共97页，编辑于2022年，星期日图图6.3 表示杂凑函数用来提供消息认证的基本使用方表示杂凑函数用来提供消息认证的基本使用方式，共有以下式，共有以下6种种（见（见142页图页图6.3）：）：消息与杂凑码链接后用单钥加密算法加密。由于消息与杂凑码链接后用单钥加密算法加密。由于所用密钥仅为收发双方所用密钥仅为收发双方A、B共享，因此可保证消息共享，因此可保证消息的确来自的确来自A并且未被篡改。同时还由于消息和杂凑码并且未被篡改。同时还由于消息和杂凑码都被加密，这种方
21、式还提供了保密性，见图都被加密，这种方式还提供了保密性，见图6.3(a)。用单钥加密算法仅对杂凑码加密。这种方式用于用单钥加密算法仅对杂凑码加密。这种方式用于不要求保密性的情况下，可减少处理负担。注意这种不要求保密性的情况下，可减少处理负担。注意这种方式和图方式和图6.1(a)的的MAC结果完全一样，即将结果完全一样，即将EKH(M)看作一个函数，函数的输入为消息看作一个函数，函数的输入为消息M和密钥和密钥K，输出，输出为固定长度，见图为固定长度，见图6.3(b)。第21页，共97页，编辑于2022年，星期日 用公钥加密算法和发送方的秘密钥仅加密杂凑码。用公钥加密算法和发送方的秘密钥仅加密杂凑
22、码。和和一样，这种方式提供认证性，又由于只有发送方一样，这种方式提供认证性，又由于只有发送方能产生加密的杂凑码，因此这种方式还对发送方发送能产生加密的杂凑码，因此这种方式还对发送方发送的消息提供了数字签字，事实上这种方式就是数字签的消息提供了数字签字，事实上这种方式就是数字签字，见图字，见图6.3(c)。消息的杂凑值用公钥加密算法和发送方的秘密钥消息的杂凑值用公钥加密算法和发送方的秘密钥加密后与消息链接，再对链接后的结果用单钥加密算加密后与消息链接，再对链接后的结果用单钥加密算法加密，这种方式提供了保密性和数字签字，见图法加密，这种方式提供了保密性和数字签字，见图6.3(d)。第22页，共97
23、页，编辑于2022年，星期日 使用这种方式时要求通信双方共享一个秘密值使用这种方式时要求通信双方共享一个秘密值S，A计算消息计算消息M和秘密值和秘密值S链接在一起的杂凑值，并将链接在一起的杂凑值，并将此杂凑值附加到此杂凑值附加到M后发往后发往B。因。因B也有也有S，所以可重新，所以可重新计算杂凑值以对消息进行认证。由于秘密值计算杂凑值以对消息进行认证。由于秘密值S本身未本身未被发送，敌手无法对截获的消息加以篡改，也无法产被发送，敌手无法对截获的消息加以篡改，也无法产生假消息。这种方式仅提供认证，见图生假消息。这种方式仅提供认证，见图6.3(e)。这种方式是在这种方式是在中消息与杂凑值链接以后再
24、增加中消息与杂凑值链接以后再增加单钥加密运算，从而又可提供保密性，见图单钥加密运算，从而又可提供保密性，见图6.3(f)。第23页，共97页，编辑于2022年，星期日由于加密运算的速度较慢，代价较高，而且很多加密由于加密运算的速度较慢，代价较高，而且很多加密算法还受到专利保护，因此在不要求保密性的情况下，算法还受到专利保护，因此在不要求保密性的情况下，方式方式和和将比其他方式更具优势。将比其他方式更具优势。第24页，共97页，编辑于2022年，星期日杂凑函数的目的是为需认证的数据产生一个杂凑函数的目的是为需认证的数据产生一个“指纹指纹”。为了能够实现对数据的认证，杂凑函数应满足以下条为了能够实
25、现对数据的认证，杂凑函数应满足以下条件：件：函数的输入可以是任意长。函数的输入可以是任意长。函数的输出是固定长。函数的输出是固定长。已知已知x，求，求H(x)较为容易，可用硬件或软件实现。较为容易，可用硬件或软件实现。已知已知h，求使得，求使得H(x)=h的的x在计算上是不可行的，在计算上是不可行的，这一性质称为函数的单向性，称这一性质称为函数的单向性，称H(x)为单向杂凑函数。为单向杂凑函数。6.2.2 杂凑函数应满足的条件杂凑函数应满足的条件第25页，共97页，编辑于2022年，星期日 已知已知x，找出，找出y(yx)使得使得H(y)=H(x)在计算上是不可在计算上是不可行的。行的。如果单
26、向杂凑函数满足这一性质，则称其为弱单向杂如果单向杂凑函数满足这一性质，则称其为弱单向杂凑函数。凑函数。找出任意两个不同的输入找出任意两个不同的输入x、y，使得，使得H(y)=H(x)在在计算上是不可行的。计算上是不可行的。第26页，共97页，编辑于2022年，星期日如果单向杂凑函数满足这一性质，则称其为强单向杂如果单向杂凑函数满足这一性质，则称其为强单向杂凑函数。凑函数。第第和第和第个条件给出了杂凑函数无碰撞性的概念，个条件给出了杂凑函数无碰撞性的概念，如果杂凑函数对不同的输入可产生相同的输出，则称如果杂凑函数对不同的输入可产生相同的输出，则称该函数具有碰撞性。该函数具有碰撞性。第27页，共9
27、7页，编辑于2022年，星期日以上以上6个条件中，前个条件中，前3个是杂凑函数能用于消息认证的个是杂凑函数能用于消息认证的基本要求。第基本要求。第4个条件（即单向性）则对使用秘密值个条件（即单向性）则对使用秘密值的认证技术的认证技术(见图见图6.3(e)极为重要。假如杂凑函数不具极为重要。假如杂凑函数不具有单向性，则攻击者截获有单向性，则攻击者截获M和和C=H(SM)后，求后，求C的的逆逆SM，就可求出秘密值，就可求出秘密值S。第。第5个条件使得敌手无法个条件使得敌手无法在已知某个消息时，找到与该消息具有相同杂凑值的在已知某个消息时，找到与该消息具有相同杂凑值的另一消息。这一性质用于杂凑值被加
28、密情况时另一消息。这一性质用于杂凑值被加密情况时(见图见图6.3(b)和图和图6.3(c)防止敌手的伪造，由于在这种情况防止敌手的伪造，由于在这种情况下，敌手可读取传送的明文消息下，敌手可读取传送的明文消息M，因此能产生该消，因此能产生该消息的杂凑值息的杂凑值H(M)。第28页，共97页，编辑于2022年，星期日但由于敌手不知道用于加密杂凑值的密钥，他就不可但由于敌手不知道用于加密杂凑值的密钥，他就不可能既伪造一个消息能既伪造一个消息M，又伪造这个消息的杂凑值加密，又伪造这个消息的杂凑值加密后的密文后的密文EKH(M)。然而，如果第。然而，如果第5个条件不成立，个条件不成立，敌手在截获明文消息
29、及其加密的杂凑值后，就可按以敌手在截获明文消息及其加密的杂凑值后，就可按以下方式伪造消息：首先求出截获的消息的杂凑值，然下方式伪造消息：首先求出截获的消息的杂凑值，然后产生一个具有相同杂凑值的伪造消息，最后再将伪后产生一个具有相同杂凑值的伪造消息，最后再将伪造的消息和截获的加密的杂凑值发往通信的接收方。造的消息和截获的加密的杂凑值发往通信的接收方。第第6个条件用于抵抗生日攻击。个条件用于抵抗生日攻击。第29页，共97页，编辑于2022年，星期日1.相关问题相关问题已知一杂凑函数已知一杂凑函数H有有n个可能的输出，个可能的输出，H(x)是一个特是一个特定的输出，如果对定的输出，如果对H随机取随机
30、取k个输入，则至少有一个个输入，则至少有一个输入输入y使得使得H(y)=H(x)的概率为的概率为0.5时，时，k有多大？有多大？以后为叙述方便，称对杂凑函数以后为叙述方便，称对杂凑函数H寻找上述寻找上述y的攻击的攻击为第为第类生日攻击。类生日攻击。6.2.3 生日攻击生日攻击第30页，共97页，编辑于2022年，星期日因为因为H有有n个可能的输出，所以输入个可能的输出，所以输入y产生的输出产生的输出H(y)等于特定输出等于特定输出H(x)的概率是的概率是1/n，反过来说，反过来说H(y)H(x)的概率是的概率是1-1/n。y取取k个随机值而函数的个随机值而函数的k个输出中没个输出中没有一个等于
31、有一个等于H(x)，其概率等于每个输出都不等于，其概率等于每个输出都不等于H(x)的概率之积，为的概率之积，为1-1/nk，所以，所以y取取k个随机值得到函个随机值得到函数的数的k个输出中至少有一个等于个输出中至少有一个等于H(x)的概率为的概率为1-1-1/nk。由由(1+x)k1+kx，其中，其中|x|365，则不可能使得任意两个数据，则不可能使得任意两个数据都不相同，因此假定都不相同，因此假定k365。k个数据项中任意两个个数据项中任意两个都不相同的所有取值方式数为都不相同的所有取值方式数为第32页，共97页，编辑于2022年，星期日即第即第1个数据项可从个数据项可从365个中任取一个，
32、第个中任取一个，第2个数据项个数据项可在剩余的可在剩余的364个中任取一个，依次类推，最后一个个中任取一个，依次类推，最后一个数据项可从数据项可从365-k+1个值中任取一个。如果去掉任意个值中任取一个。如果去掉任意两个都不相同这一限制条件，可得两个都不相同这一限制条件，可得k个数据项中所有个数据项中所有取值方式数为取值方式数为365k。所以可得。所以可得第33页，共97页，编辑于2022年，星期日当当k=23时，时，P(365,23)=0.5073，即上述问题只需，即上述问题只需23人，人，人数如此之少。若人数如此之少。若k取取100，则，则P(365,100)=0.9999997，即获得如
33、此大的概率。之所以称这一问题是悖论是，即获得如此大的概率。之所以称这一问题是悖论是因为当人数因为当人数k给定时，得到的至少有两个人的生日相给定时，得到的至少有两个人的生日相同的概率比想象的要大得多。这是因为在同的概率比想象的要大得多。这是因为在k个人中考个人中考虑的是任意两个人的生日是否相同，在虑的是任意两个人的生日是否相同，在23个人中可能个人中可能的情况数为的情况数为C223=253。第34页，共97页，编辑于2022年，星期日将生日悖论推广为下述问题：已知一个在将生日悖论推广为下述问题：已知一个在1到到n之间之间均匀分布的整数型随机变量，若该变量的均匀分布的整数型随机变量，若该变量的k个
34、取值中个取值中至少有两个取值相同的概率大于至少有两个取值相同的概率大于0.5，则，则k至少多大？至少多大？与上类似，与上类似，令，令P(n,k)0.5，可得，可得 。若取若取n=365，则，则 。第35页，共97页，编辑于2022年，星期日3.生日攻击生日攻击生日攻击是基于下述结论：设杂凑函数生日攻击是基于下述结论：设杂凑函数H有有2m个可能个可能的输出（即输出长的输出（即输出长m比特），如果比特），如果H的的k个随机输入个随机输入中至少有两个产生相同输出的概率大于中至少有两个产生相同输出的概率大于0.5，则，则 。称寻找函数称寻找函数H的具有相同输出的两个任意输入的攻击的具有相同输出的两个任
35、意输入的攻击方式为第方式为第类生日攻击。类生日攻击。第36页，共97页，编辑于2022年，星期日第第类生日攻击可按以下方式进行：类生日攻击可按以下方式进行：设用户将用图设用户将用图6.3(c)所示的方式发送消息，即所示的方式发送消息，即A用用自己的秘密钥对消息的杂凑值加密，加密结果作为对自己的秘密钥对消息的杂凑值加密，加密结果作为对消息的签字，连同明文消息一起发往接收者。消息的签字，连同明文消息一起发往接收者。敌手对敌手对A发送的消息发送的消息M产生出产生出2m/2个变形的消息，个变形的消息，每个变形的消息本质上的含义与原消息相同，同时敌每个变形的消息本质上的含义与原消息相同，同时敌手还准备一
36、个假冒的消息手还准备一个假冒的消息M，并对假冒的消息产生，并对假冒的消息产生出出2m/2个变形的消息。个变形的消息。第37页，共97页，编辑于2022年，星期日 敌手在产生的两个消息集合中，找出杂凑值相同敌手在产生的两个消息集合中，找出杂凑值相同的一对消息的一对消息,，由上述讨论可知敌手成功的概，由上述讨论可知敌手成功的概率大于率大于0.5。如果不成功，则重新产生一个假冒的消。如果不成功，则重新产生一个假冒的消息，并产生息，并产生2m/2个变形，直到找到杂凑值相同的一对个变形，直到找到杂凑值相同的一对消息为止。消息为止。敌手将敌手将 提交给提交给A请求签字，由于请求签字，由于 与与 的杂的杂凑
37、值相同，所以可将凑值相同，所以可将A对对 的签字当作对的签字当作对 的签字，的签字，将此签字连同将此签字连同 一起发给意欲的接收者。一起发给意欲的接收者。第38页，共97页，编辑于2022年，星期日上述攻击中如果杂凑值的长为上述攻击中如果杂凑值的长为64比特，则敌手攻击成比特，则敌手攻击成功所需的时间复杂度为功所需的时间复杂度为O(232)。将一个消息变形为具有相同含义的另一消息的方法有将一个消息变形为具有相同含义的另一消息的方法有很多，例如对文件，敌手可在文件的单词之间插入很很多，例如对文件，敌手可在文件的单词之间插入很多多“space-space-backspace”字符对，然后将其中的字
38、符对，然后将其中的某些字符对替换为某些字符对替换为“space-backspace-space”就得到就得到一个变形的消息。一个变形的消息。第39页，共97页，编辑于2022年，星期日目前使用的大多数杂凑函数如目前使用的大多数杂凑函数如MD5、SHA，其结构，其结构都是迭代型的，如图都是迭代型的，如图6.4所示。其中函数的输入所示。其中函数的输入M被被分为分为L个分组个分组Y0,Y1,YL-1，每一个分组的长度为，每一个分组的长度为b比比特，最后一个分组的长度不够的话，需对其做填充。特，最后一个分组的长度不够的话，需对其做填充。最后一个分组中还包括整个函数输入的长度值，这样最后一个分组中还包括
39、整个函数输入的长度值，这样一来，将使得敌手的攻击更为困难，即敌手若想成功一来，将使得敌手的攻击更为困难，即敌手若想成功地产生假冒的消息，就必须保证假冒消息的杂凑值与地产生假冒的消息，就必须保证假冒消息的杂凑值与原消息的杂凑值相同，而且假冒消息的长度也要与原原消息的杂凑值相同，而且假冒消息的长度也要与原消息的长度相等。消息的长度相等。6.2.4 迭代型杂凑函数的一般结构迭代型杂凑函数的一般结构第40页，共97页，编辑于2022年，星期日图图6.4 迭代型杂凑函数的一般结构迭代型杂凑函数的一般结构第41页，共97页，编辑于2022年，星期日算法中重复使用一压缩函数算法中重复使用一压缩函数f（注意，
40、有些书将杂凑（注意，有些书将杂凑函数也称为压缩函数，在此用压缩函数表示杂凑函数函数也称为压缩函数，在此用压缩函数表示杂凑函数中的一个特定部分），中的一个特定部分），f 的输入有两项，一项是上一的输入有两项，一项是上一轮（第轮（第i-1轮）输出的轮）输出的n比特值比特值CVi-1，称为链接变量，称为链接变量，另一项是算法在本轮（第另一项是算法在本轮（第i轮）的轮）的b比特输入分组比特输入分组Yi。f 的输出为的输出为n比特值比特值CVi，CVi又作为下一轮的输入。又作为下一轮的输入。算法开始时还需对链接变量指定一个初值算法开始时还需对链接变量指定一个初值IV，最后，最后一轮输出的链接变量一轮输出
41、的链接变量CVL即为最终产生的杂凑值。即为最终产生的杂凑值。通常有通常有bn，因此称函数，因此称函数f为压缩函数。算法可表达如为压缩函数。算法可表达如下：下：CV0=IV=n比特长的初值；比特长的初值；CVi=f(CVi-1,Yi-1)；1iL；H(M)=CVL第42页，共97页，编辑于2022年，星期日算法的核心技术是设计无碰撞的压缩函数算法的核心技术是设计无碰撞的压缩函数f，而敌手，而敌手对算法的攻击重点是对算法的攻击重点是f 的内部结构，由于的内部结构，由于f 和分组密和分组密码一样是由若干轮处理过程组成，所以对码一样是由若干轮处理过程组成，所以对f 的攻击需的攻击需通过对各轮之间的位模
42、式的分析来进行，分析过程常通过对各轮之间的位模式的分析来进行，分析过程常常需要先找出常需要先找出f 的碰撞。由于的碰撞。由于f 是压缩函数，其碰撞是压缩函数，其碰撞是不可避免的，因此在设计是不可避免的，因此在设计f 时就应保证找出其碰撞时就应保证找出其碰撞在计算上是不可行的。在计算上是不可行的。下面介绍几个重要的迭代型杂凑函数。下面介绍几个重要的迭代型杂凑函数。第43页，共97页，编辑于2022年，星期日MD4是是MD5杂凑算法的前身，由杂凑算法的前身，由Ron Rivest于于1990年年10月作为月作为RFC提出，提出，1992年年4月公布的月公布的MD4的改进的改进（RFC 1320，1
43、321）称为）称为MD5。6.3 MD5杂凑算法杂凑算法第44页，共97页，编辑于2022年，星期日MD5算法采用图算法采用图6.4描述的迭代型杂凑函数的一般结描述的迭代型杂凑函数的一般结构，算法的框图如图构，算法的框图如图6.5所示。算法的输入为任意长所示。算法的输入为任意长的消息（图中为的消息（图中为K比特），分为比特），分为512比特长的分组，比特长的分组，输出为输出为128比特的消息摘要。比特的消息摘要。6.3.1 算法描述算法描述第45页，共97页，编辑于2022年，星期日图图6.5 MD5的算法框图的算法框图第46页，共97页，编辑于2022年，星期日处理过程有以下几步：处理过程有
44、以下几步：对消息填充对消息填充，使得其比特长在模对消息填充对消息填充，使得其比特长在模512下下为为448，即填充后消息的长度为，即填充后消息的长度为512的某一倍数减的某一倍数减64，留出的留出的64比特备第比特备第2步使用。步骤步使用。步骤是必需的，即使是必需的，即使消息长度已满足要求，仍需填充。例如，消息长为消息长度已满足要求，仍需填充。例如，消息长为448比特，则需填充比特，则需填充512比特，使其长度变为比特，使其长度变为960，因，因此填充的比特数大于等于此填充的比特数大于等于1而小于等于而小于等于512。填充方式是固定的，即第填充方式是固定的，即第1位为位为1，其后各位皆为，其后
45、各位皆为0。第47页，共97页，编辑于2022年，星期日 附加消息的长度用步骤附加消息的长度用步骤留出的留出的64比特以比特以little-endian方式来表示消息被填充前的长度。如果消息长方式来表示消息被填充前的长度。如果消息长度大于度大于264，则以，则以264为模数取模。为模数取模。Little-endian方式是指按数据的最低有效字节方式是指按数据的最低有效字节（byte）（或最低有效位）优先的顺序存储数据，即）（或最低有效位）优先的顺序存储数据，即将最低有效字节（或最低有效位）存于低地址字节将最低有效字节（或最低有效位）存于低地址字节（或位）。相反的存储方式称为（或位）。相反的存储
46、方式称为big-endian方式。方式。第48页，共97页，编辑于2022年，星期日前两步执行完后，消息的长度为前两步执行完后，消息的长度为512的倍数（设为的倍数（设为L倍），则可将消息表示为分组长为倍），则可将消息表示为分组长为512的一系列分组的一系列分组Y0，Y1，YL-1，而每一分组又可表示为，而每一分组又可表示为16个个32比比特长的字，这样消息中的总字数为特长的字，这样消息中的总字数为N=L16，因此消，因此消息又可按字表示为息又可按字表示为M0,N-1。第49页，共97页，编辑于2022年，星期日 对对MD缓冲区初始化算法使用缓冲区初始化算法使用128比特长的缓冲区比特长的缓冲
47、区以存储中间结果和最终杂凑值，缓冲区可表示为以存储中间结果和最终杂凑值，缓冲区可表示为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处理。处理。HMD
48、5是算是算法的核心，其中又有法的核心，其中又有4轮处理过程，如图轮处理过程，如图6.6所示。所示。输出消息的输出消息的L个分组都被处理完后，最后一个个分组都被处理完后，最后一个HMD5的输出即为产生的消息摘要。的输出即为产生的消息摘要。第50页，共97页，编辑于2022年，星期日图图6.6 MD5的分组处理框图的分组处理框图第51页，共97页，编辑于2022年，星期日HMD5的的4轮处理过程结构一样，但所用的逻辑函数不轮处理过程结构一样，但所用的逻辑函数不同，分别表示为同，分别表示为F、G、H、I。每轮的输入为当前处。每轮的输入为当前处理的消息分组理的消息分组Yq和缓冲区的当前值和缓冲区的当前
49、值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相
50、加，相加相加，相加时将时将CVq看作看作4个个32比特的字，每个字与第比特的字，每个字与第4轮输出的轮输出的对应的字按模对应的字按模232相加，相加的结果即为压缩函数相加，相加的结果即为压缩函数HMD5的输出。（见的输出。（见151页表页表6.1）第52页，共97页，编辑于2022年，星期日步骤步骤到步骤到步骤的处理过程可总结如下：的处理过程可总结如下：CV0=IV;CVq+1=CVq+RFIYq,RFHYq,RFGYq,RFFYq,CVqMD=CVL其中其中IV是步骤是步骤所取的缓冲区所取的缓冲区ABCD的初值，的初值，Yq是消是消息的第息的第q个个512比特长的分组，比特长的分组，L是消息