第18讲 消息认证和散列函数精选PPT.ppt

《第18讲 消息认证和散列函数精选PPT.ppt》由会员分享，可在线阅读，更多相关《第18讲 消息认证和散列函数精选PPT.ppt（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第18讲讲 消息认证和消息认证和散列函数散列函数第1页，此课件共44页哦2攻击的类型攻击的类型攻击攻击主动攻击主动攻击被动攻击被动攻击获取消息的内容获取消息的内容业务流分析业务流分析假冒假冒重放重放篡改篡改抗击抗击被动攻击被动攻击的方法是前面已介绍过的的方法是前面已介绍过的加密加密抗击抗击主动攻击主动攻击的方法是本章介绍的消息的方法是本章介绍的消息认证认证第2页，此课件共44页哦31 1用来验证消息的用来验证消息的真实性真实性的确是由它所声称的实体发来的的确是由它所声称的实体发来的2 2用来验证消息的用来验证消息的完整性完整性未被篡改、插入、删除未被篡改、插入、删除3 3 用来验证消息的用来

2、验证消息的顺序性和时间性顺序性和时间性未重排、未重排、重放重放、延迟、延迟4 4用来验证消息的用来验证消息的不可否认性不可否认性防止防止通信双方中的某一方对所传输消息的否认通信双方中的某一方对所传输消息的否认认证的功能认证的功能第3页，此课件共44页哦41.1.消息加密：消息加密：整个消息的密文作为认证符整个消息的密文作为认证符2.2.消息认证码（密码校验和）：消息认证码（密码校验和）：（MACMACMessage Authentication Code)Message Authentication Code)以以消息和密钥消息和密钥作为公开函数的输入，产生定长的输作为公开函数的输入，产生定长

3、的输 出，并以此输出值作为认证标识。出，并以此输出值作为认证标识。3.3.杂凑杂凑/散列函数散列函数(Hash(Hash function)function)：是一个是一个不需要密钥不需要密钥的公开函数，它将任意长度的输的公开函数，它将任意长度的输 入消息映射成一个固定长度的输出值，并以此值作入消息映射成一个固定长度的输出值，并以此值作 为认证标识。为认证标识。认证的实现：认证符认证的实现：认证符第4页，此课件共44页哦5消息加密消息加密对称加密能够提供认证？对称加密能够提供认证？由于密钥没有第三方知道，所以接收方应该可以确信消息由于密钥没有第三方知道，所以接收方应该可以确信消息的来源真实性。

4、的来源真实性。这并不绝对，因为存在一种可能性，是对密文的篡改。这并不绝对，因为存在一种可能性，是对密文的篡改。问题：对密文的篡改，能否一定被察觉？问题：对密文的篡改，能否一定被察觉？第5页，此课件共44页哦能够察觉的举例能够察觉的举例nCBC模式加密得到密文n某处被窜改，导致其后续部分解密失败#openssl enc-e-des-cbc-in 2.txt-out 2.out#openssl enc-d-des-cbc-in 2modi.out-out 2modi.txt第6页，此课件共44页哦不能够察觉的举例不能够察觉的举例nrc4加密中，对密文部分比特的窜改导致明文对应部分解密错误n另外，精

5、心伪造的密文可能恰好解密为有效的明文n结论：加密并不能完全抵抗篡改或假冒加密并不能完全抵抗篡改或假冒第7页，此课件共44页哦教训：对密文的保护教训：对密文的保护n在加密之前，给明文添加结构特征x|h(x)x|h(x)/h=crc,md5,sha1n加密E(x|h(x),k)=yE(x|h(x),k)=yn传输有可能出错或被窜改ny会变做yn解密n判断是否依旧符合 x|h(x)x|h(x)的结构特征第8页，此课件共44页哦公钥加密公钥加密nA A使用使用B B的公钥加密消息，能否提供认证？的公钥加密消息，能否提供认证？第9页，此课件共44页哦10nA A可以先使用自己的私钥加密消息（即签名），再

6、用可以先使用自己的私钥加密消息（即签名），再用B B的公钥加密，的公钥加密，这样可以提供认证。这样可以提供认证。n缺点：缺点：4 4次复杂的公钥运算次复杂的公钥运算第10页，此课件共44页哦11密钥密钥K是是A和和B的共享密钥的共享密钥发送方发送方：A首先计首先计MAC=CK(M)，其中，其中CK()是密钥控制的公开函数，是密钥控制的公开函数，然后向然后向B发送发送MMAC接收方接收方：B收到后做与收到后做与A相同的计算，求得一新相同的计算，求得一新MAC，并与收到的，并与收到的MAC做比较，如果与接收到的做比较，如果与接收到的MAC一致，则通过验证一致，则通过验证消息认证码：使用方式之一消息

7、认证码：使用方式之一第11页，此课件共44页哦12 接收方相信发送方发来的消息未被篡改接收方相信发送方发来的消息未被篡改这是因为攻击者不知道密钥，所以不能够在篡改消息后相应地这是因为攻击者不知道密钥，所以不能够在篡改消息后相应地篡改篡改MAC，而如果仅篡改消息，则接收方计算的新，而如果仅篡改消息，则接收方计算的新MAC将与收将与收到的到的MAC不同。不同。接收方相信发送方不是冒充的接收方相信发送方不是冒充的这是因为除收发双方外再无其他人知道密钥，因此其他人不可能对自这是因为除收发双方外再无其他人知道密钥，因此其他人不可能对自己发送的消息计算出正确的己发送的消息计算出正确的MAC。6.1消息认证

8、码：使用方式之一消息认证码：使用方式之一第12页，此课件共44页哦13消息认证码：使用方式之一消息认证码：使用方式之一n特点：特点：nMAC函数无需可逆函数无需可逆n收发双方使用相同的密钥收发双方使用相同的密钥n只提供消息认证，不能提供机密性只提供消息认证，不能提供机密性 第13页，此课件共44页哦14发送方和接收方发送方和接收方共享两对密钥共享两对密钥k1和和k2发送方发送方：在计算：在计算MAC后，对后，对MMAC进行整体加密再发送进行整体加密再发送接收方：接收方：解密后进行比较解密后进行比较提供保密性和认证性提供保密性和认证性消息认证码：使用方式之二消息认证码：使用方式之二第14页，此课

9、件共44页哦15发送方和接收方发送方和接收方共享两对密钥共享两对密钥k1k1和和k2k2发送方发送方：MM先被加密再与先被加密再与MACMAC链接后发送。链接后发送。接收方：接收方：解密后进行比较。解密后进行比较。消息认证码：使用方式三消息认证码：使用方式三第15页，此课件共44页哦避免使用加密方法产生避免使用加密方法产生MACMAC码码n生成生成MACMAC没有必要对整个报文加密没有必要对整个报文加密n速度、进出口障碍速度、进出口障碍n不需要能恢复原文不需要能恢复原文nMACMAC的计算过程只需体现明文的特征唯一的计算过程只需体现明文的特征唯一nKeyKey是必要的是必要的n从报文产生特征的

10、数学方法：从报文产生特征的数学方法：HASHHASH函数函数n先计算特征，再把特征加密的思想先计算特征，再把特征加密的思想n把散列函数和把散列函数和KeyKey结合得结合得MACMACHMAC=HashHMAC=HashKeyKey(Message)(Message)第16页，此课件共44页哦17消息认证码：消息认证码：FIPS PUB 113FIPS PUB 1131.1.算法基于算法基于CBCCBC模式的模式的DESDES算法算法，其初始向量取为零向量。，其初始向量取为零向量。需被认证的数据被分为需被认证的数据被分为6464比特长的分组比特长的分组D D1 1，D D2 2，D DN N，

11、最后一个分组不够最后一个分组不够6464比特的话，可在其右边填充一些比特的话，可在其右边填充一些0 02.2.数据认证码或者取为数据认证码或者取为O ON N或者取为或者取为O ON N的最左的最左M M个比特，其中个比特，其中16M6416M64。第17页，此课件共44页哦18（1）数字签名数字签名（2）身份认证身份认证 (3(3）消息完整性认证）消息完整性认证 在在密密码码学学和和数数据据安安全全技技术术中中，它它是是实实现现有有效效、安安全全可可靠靠数数字字签签字字和和认认证证的的重重要要工工具具，是是安安全认证协议中的重要模块。全认证协议中的重要模块。杂凑杂凑/散列函数散列函数散列函数

12、的应用背景散列函数的应用背景第18页，此课件共44页哦19别名：压缩压缩(Compression)函数、紧缩紧缩(Contraction)函数、数据认证码数据认证码(Data Authentication Code)、消息摘要消息摘要(Message Digest)、数字指纹数字指纹(Digital Finger Print)、数据完整性校验数据完整性校验(Data Integity Check)、密码检验和密码检验和(Cryptographic Check Sum)、窜改检测码窜改检测码MDC(Manipulation Detection Code)第19页，此课件共44页哦20散列函数散列

13、函数H是一公开函数，用于将任意长是一公开函数，用于将任意长的消息的消息M映射为较短的、固定长度的一个值映射为较短的、固定长度的一个值H(M)。它是消息中所有比特的函数，改变消息它是消息中所有比特的函数，改变消息中任何一个比特或几个比特都会使杂凑码发中任何一个比特或几个比特都会使杂凑码发生改变。生改变。散列函数的定义及使用方式散列函数的定义及使用方式第20页，此课件共44页哦21 A和和B共享密钥共享密钥K由于所用密钥仅为收发双方由于所用密钥仅为收发双方A、B共享，可保证消息的确来自共享，可保证消息的确来自A并且未被篡改。并且未被篡改。同时还由于消息和杂凑码都被加密，提供了保密性。同时还由于消息

14、和杂凑码都被加密，提供了保密性。散列函数的使用方式之一散列函数的使用方式之一第21页，此课件共44页哦22n 用单钥加密算法仅对杂凑码加密。用单钥加密算法仅对杂凑码加密。n这种方式用于不要求保密性的情况下，可减少处理负担。这种方式用于不要求保密性的情况下，可减少处理负担。散列函数的使用方式之二散列函数的使用方式之二第22页，此课件共44页哦23散列函数的使用方式之三散列函数的使用方式之三 用公钥加密算法和发送方的秘密钥仅加密杂凑码。用公钥加密算法和发送方的秘密钥仅加密杂凑码。功能：提供认证性和功能：提供认证性和数字签名，不提供保密性数字签名，不提供保密性由于只有发送方能产生加密的杂凑码，因此对

15、发送方发送的消由于只有发送方能产生加密的杂凑码，因此对发送方发送的消息提供了数字签字。息提供了数字签字。方式选择方式选择第23页，此课件共44页哦24 消息的杂凑值用公钥加密算法和发送方的秘密钥加密后与消息链消息的杂凑值用公钥加密算法和发送方的秘密钥加密后与消息链接，再对链接后的结果用单钥加密算法加密接，再对链接后的结果用单钥加密算法加密功能：提供了功能：提供了保密性和数字签字保密性和数字签字散列函数的使用方式之四散列函数的使用方式之四第24页，此课件共44页哦25 通信双方共享一个秘密值通信双方共享一个秘密值S S，A A计算消息计算消息MM和秘密值和秘密值S S链接在一起的杂凑值，链接在一

16、起的杂凑值，并将此杂凑值附加到并将此杂凑值附加到MM后发往后发往B B。接收方接收方B B可重新计算杂凑值以对消息进行认证。可重新计算杂凑值以对消息进行认证。由于敌手无法得到由于敌手无法得到S S，所以无法对截获的消息加以篡改，也无法产生假消息。，所以无法对截获的消息加以篡改，也无法产生假消息。功能：提供认证性功能：提供认证性.散列函数的使用方式之五散列函数的使用方式之五第25页，此课件共44页哦26 将消息与杂凑值链接以后再增加单钥加密运算将消息与杂凑值链接以后再增加单钥加密运算功能：提供认证性和功能：提供认证性和保密性保密性.散列函数的使用方式之六散列函数的使用方式之六第26页，此课件共4

17、4页哦27 由于加密运算的速度较慢，代价较高，由于加密运算的速度较慢，代价较高，而且很多加密算法还受到专利保护，在不要而且很多加密算法还受到专利保护，在不要求保密性的情况下，方式求保密性的情况下，方式和和将比其他方将比其他方式更具优势。式更具优势。散列函数的使用方式选择散列函数的使用方式选择2第27页，此课件共44页哦28散列函数应满足以下条件：散列函数应满足以下条件：函数的输入可以是任意长。函数的输入可以是任意长。函数的输出是固定长。函数的输出是固定长。已知已知x x，求，求H(x)H(x)较为容易，可用硬件或软件实现。较为容易，可用硬件或软件实现。这三个条件是散列函数能用于消息认证的基本要

18、求这三个条件是散列函数能用于消息认证的基本要求。散列函数应满足的条件散列函数应满足的条件 已知已知h h，求使得，求使得H(x)=hH(x)=h的的x x在计算上是不可行的在计算上是不可行的这一性质称为函数的单向性，称这一性质称为函数的单向性，称H(x)H(x)为为单向散列函数。单向散列函数。第28页，此课件共44页哦29散列函数应满足的条件散列函数应满足的条件n 找出任意两个不同的输入找出任意两个不同的输入x x、y y，使得，使得H(y)=H(x)H(y)=H(x)在计算上在计算上是不可行的。是不可行的。如果单向散列函数满足这一性质，则称其为如果单向散列函数满足这一性质，则称其为强强单向散

19、列函数。单向散列函数。n第第6 6个条件用于个条件用于抵抗生日攻击。抵抗生日攻击。n第第和第和第个条件给出了散列函数无碰撞性的概念个条件给出了散列函数无碰撞性的概念n如果散列函数对不同的输入可产生相同的输出，则称该函数具如果散列函数对不同的输入可产生相同的输出，则称该函数具有碰撞性。有碰撞性。已知已知x x，找出，找出y(yx)y(yx)使得使得H(y)=H(x)H(y)=H(x)在计算上是不可行的。在计算上是不可行的。如果单向散列函数满足这一性质，则称其为如果单向散列函数满足这一性质，则称其为弱单向散列函数。弱单向散列函数。这这使得敌手无法在已知某个消息时，找到与该消息具有相同使得敌手无法在

20、已知某个消息时，找到与该消息具有相同杂凑值的另一消息，防止敌手的伪造。杂凑值的另一消息，防止敌手的伪造。MD5第29页，此课件共44页哦30HashHash函数的两种穷举攻击生日问题函数的两种穷举攻击生日问题 附录中附录中 n第第类生日攻击类生日攻击n一是给定消息的一是给定消息的HashHash函数函数H H（x x），破译者逐个生成其他文件，破译者逐个生成其他文件y y，以使，以使H H（x x）=H=H（y y）n第第类生日攻击类生日攻击n二是攻击者寻找两个随机的消息：二是攻击者寻找两个随机的消息：x x，y y，并使并使H H（x x）=H=H（y y）n在一个教室中最少应有多少学生才使

21、得找一个学生与某人生日（该人也在在一个教室中最少应有多少学生才使得找一个学生与某人生日（该人也在教室）相同的概率不小于教室）相同的概率不小于1/21/2？n在一个教室中最少应有多少学生才使得至少有两个学生的生日在同一天的概率在一个教室中最少应有多少学生才使得至少有两个学生的生日在同一天的概率不小于不小于1/21/2？第30页，此课件共44页哦31在一个教室中最少应有多少学生才使得找一个学生与某学生生日（该学生也在教室）相同的概率不小于1/2？n教室中有教室中有k k人：人：n一同学（给定）生日为某天；一同学（给定）生日为某天；n其他某个同学不是和他同一天生的概率是其他某个同学不是和他同一天生的

22、概率是364/365364/365（1-1/3651-1/365）n随机取随机取k k个人与该同学都不同生日的概率是个人与该同学都不同生日的概率是(364/365)(364/365)k kn所以随机取所以随机取k k个人至少有一个人与该同学同生日的概率是个人至少有一个人与该同学同生日的概率是n1-(364/365)1-(364/365)k kn254254第31页，此课件共44页哦32在一个教室中最少应有多少学生才使得至少有两个学生的生日在一个教室中最少应有多少学生才使得至少有两个学生的生日在同一天的概率不小于在同一天的概率不小于1/21/2？（生日悖论）（生日悖论）n第一个人的生日第一个人的

23、生日为为一个特定生日一个特定生日n第二个人不在第二个人不在该该日出生的概率是日出生的概率是(1-1/365)(1-1/365)n第三个人与前两位不同生日的概率是第三个人与前两位不同生日的概率是(1-2/365)(1-2/365)n第第k k个人与前个人与前k-1k-1个人不同生日的概率是个人不同生日的概率是(1-(k-1)/365)(1-(k-1)/365)n所以所以k k个人都不同生日的概率是个人都不同生日的概率是n(1-1/365)(1-2/365)(1-(k-1)/365)=(1-1/365)(1-2/365)(1-(k-1)/365)=nk k个人至少有两个人生日相同的概率是个人至少有

24、两个人生日相同的概率是1-1-(1-1/365)(1-2/365)(1-(k-1)/365)=(1-1/365)(1-2/365)(1-(k-1)/365)=n利用利用1-x1-x e e-x-x(当当x x很小很小)，概率概率约为约为1-e1-e-k(k-1)/-k(k-1)/（2 2 365365）nk k 1.181.18 3653651/21/2 22.5422.54，n即随机即随机选择选择2323人，至少有人，至少有2 2人生日相同的概率至少人生日相同的概率至少为为1/21/2。第32页，此课件共44页哦33当当k=23k=23时，时，P(365,23)=0.5073P(365,23

25、)=0.5073，即上述问题只需即上述问题只需2323人，人数如此之少。人，人数如此之少。当当k=100k=100时，时，P(365,100)=0.9999997P(365,100)=0.9999997，即获得如此大的概率。即获得如此大的概率。“生日悖论生日悖论”是因为当人数是因为当人数k k给定时，得到的至少有两个人给定时，得到的至少有两个人的生日相同的概率比想象的要大得多。的生日相同的概率比想象的要大得多。生日悖论生日悖论第33页，此课件共44页哦34n寻找特定生日的一个人类似于第一种攻击；寻找特定生日的一个人类似于第一种攻击；n寻找两个随机的具有相同生日的两个人则是第二种攻击；寻找两个随

26、机的具有相同生日的两个人则是第二种攻击；n第二种方法通常被称为生日攻击第二种方法通常被称为生日攻击（Birthday AttackBirthday Attack）；）；n生生日日攻攻击击意意味味着着HASHHASH值值的的长长度度有有一一个个下下界界，128128位位的的消消息息摘摘要要，在在2 26464个个随随机机输输入入的的HASHHASH值中至少有一个碰撞。所以，通常建议用值中至少有一个碰撞。所以，通常建议用160160位或更长的消息摘要。位或更长的消息摘要。nK=2K=2m/2m/2m位的消息摘要位的消息摘要有效级仅为有效级仅为2m/2HashHash函数的两种穷举攻击生日问题函数的

27、两种穷举攻击生日问题第34页，此课件共44页哦35nK=2K=2m/2m/2m位的消息摘要位的消息摘要有效级仅为有效级仅为2m/2HashHash函数的两种穷举攻击生日问题函数的两种穷举攻击生日问题第35页，此课件共44页哦36n州立大学的计算机系有一个教员的位置和两个候选人州立大学的计算机系有一个教员的位置和两个候选人TOMTOM和和JACKJACK，TOMTOM比比JACKJACK早雇用两年，因此他优先被考察。如果他被通过了，早雇用两年，因此他优先被考察。如果他被通过了，JACKJACK就没有机会了。就没有机会了。TOMTOM知道系主任知道系主任MARILYNMARILYN对自己工作评价很

28、高，因对自己工作评价很高，因此他请求她给院长写封推荐信，院长将决定此他请求她给院长写封推荐信，院长将决定TOMTOM能否获得此职位。能否获得此职位。一旦发出，所有的信件都变成秘密的。一旦发出，所有的信件都变成秘密的。nMARILYNMARILYN让她的秘书让她的秘书ELLENELLEN给院长写封信，并简要地叙述了信的内给院长写封信，并简要地叙述了信的内容。当信完成后，容。当信完成后，MANRILYNMANRILYN检查一下，计算并签署检查一下，计算并签署6464比特比特的摘要，的摘要，然后把它发给院长。然后把它发给院长。ELLENELLEN随后用电子邮件把信发走。随后用电子邮件把信发走。第36

29、页，此课件共44页哦37ELLEN以具有以具有3232个括号选项的形式写这封信个括号选项的形式写这封信nThe letter|message is to give my honest|frank opinion of Prof.Tom Wilson,who is a candidate|up for tenure now|this year,I have known|worked with Tom for about|almost six years.He is outstanding|excellent researcher well known in his field|area.He i

30、s a highly|greatly respected|admired teacher.232变种变种第一封第一封第37页，此课件共44页哦38TOMTOM很不幸，很不幸，ELLENELLEN正迷恋着正迷恋着JACKJACK，所以想陷害所以想陷害TOMTOM。她以如下。她以如下的具有的具有3232个括号选项的形式写这封信：个括号选项的形式写这封信：nThe letter|message is to give my honest|frank opinion of Prof.Tom Wilson,who is a candidate|up for tenure now|this year,I h

31、ave known|worked with Tom for about|almost six years.He is poor|weak researcher well known in his field|area.He is not a respected|admired teacher232变种变种第二封第二封第38页，此课件共44页哦39n现在现在ELLENELLEN让她的计算机整夜地计算每封信的让她的计算机整夜地计算每封信的2 23232变种变种的的报文摘报文摘要要n n第一封信的某个变种的摘要第一封信的某个变种的摘要第一封信的某个变种的摘要第一封信的某个变种的摘要和和第二封信的某个

32、变种摘第二封信的某个变种摘第二封信的某个变种摘第二封信的某个变种摘一样一样n如果不一样，她可以增加一些选项，如果不一样，她可以增加一些选项，在周末再试一遍在周末再试一遍n假定她找到了一个匹配。我们把假定她找到了一个匹配。我们把“好好”的信叫做的信叫做A(A(有利于有利于tom)tom)，“坏坏”的信叫做的信叫做B B。nELLENELLEN现在把信现在把信A A给给MARILYNMARILYN以征询她的同意。以征询她的同意。MARILYNMARILYN当当然同意，计算自己的然同意，计算自己的6464比特报文摘要比特报文摘要，签署该摘要签署该摘要nELLENELLEN把该把该摘要摘要附加在附加在

33、信信B B寄给院长寄给院长n收到信和签名的报文摘要后，院长对收到信和签名的报文摘要后，院长对信信B B运行报文摘要算法，看见运行报文摘要算法，看见确实是确实是MAEILYNMAEILYN发送给自己的，就解雇了发送给自己的，就解雇了Tom Tom。第39页，此课件共44页哦11.6nWhatisthedifferencebetweenamessageauthenticationcodeandaone-wayhashfunction?n消息认证码和哈希函数的区别消息认证码和哈希函数的区别nAhashfunction,byitself,doesnotprovidemessageauthenticat

34、ion.Asecretkeymustbeusedinsomefashionwiththehashfunctiontoproduceauthentication.AMAC,bydefinition,usesasecretkeytocalculatedacodeusedforauthentication.n40第40页，此课件共44页哦11.6nItispossibletouseahashfunctiontoconstructablockcipherwithastructuresimilartoDES.nBecauseahashfunctionisonewayandablockciphermust

35、bereversible(todecrypt),howisitpossible?41第41页，此课件共44页哦nIfyouexaminethestructureofasingleroundofDES,youseethattheroundincludesaone-wayfunction,f,andanXOR:nForDES,thefunctionfisdepictedinFigure3.5.Itmapsa32-bitRanda48-bitKintoa32-bitoutput.Thatis,itmapsan80-bitinputintoa32-bitoutput.Thisisclearlyaone

36、-wayfunction.Anyhashfunctionthatproducesa32-bitoutputcouldbeusedforf.Thedemonstrationinthetextthatdecryptionworksisstillvalidforanyone-wayfunctionf.42第42页，此课件共44页哦11.7nThe opponent has the two-block message B1,B2 and its hash RSAH(B1,B2).The following attack will work.Choose an arbitrary C1 and choo

37、se C2 such that:nC2=RSA(C1)RSA(B1)B2nthennRSA(C1)C2=RSA(C1)RSA(C1)RSA(B1)B2n =RSA(B1)B2nsonRSAH(C1,C2)=RSARSA(C1)C2)n =RSARSA(B1)B2n =RSAH(B1,B2)43第43页，此课件共44页哦11.8nThestatementisfalse.Suchafunctioncannotbeone-to-onebecausethenumberofinputstothefunctionisofarbitrary,butthenumberofuniqueoutputsis2n.Thus,therearemultipleinputsthatmapintothesameoutput.44第44页，此课件共44页哦