应用密码学第10讲

12010-2011年度济南大学网络工程专业本科班课程应用密码学第十讲消息认证码与杂凑函数贾忠田济南大学信息科学与工程学院电子信箱：[e-mail]2回顾密钥分配方法单钥密码体制的分类双钥密码体制的分类密码体制的分类3本次课的内容：1、消息认证码2、杂凑函数4第一节消息认证码一、消息认证码的定义及使用方式1、消息认证码的定义消息认证码是指消息被一密钥控制的公开函数作用后产生的、用作认证符的、固定长度的数值，也称为密码校验和，简称MAC（messageauthenticationcode）。MAC=CK(M)其中：K是通信双方A和B共享的密钥，CK(·)是密钥控制的公开函数，M是A欲发送给B的消息。52、MAC的使用过程1)A首先计算MAC=CK(M)；2)A向B发送M‖MAC；3)B收到M‖MAC后做与A相同的计算MAC*=CK(M)，得到一新的MAC*；4)与收到的MAC做比较MACMAC*；?如果仅收发双方知道K，且B计算得到的MAC与接收到的MAC一致，则这一系统就实现了以下功能：①接收方相信发送方发来的消息未被篡改，这是因为攻击者不知道密钥，所以不能够在篡改消息后相应地篡改MAC，而如果仅篡改消息，则接收方计算的新MAC将与收到的MAC不同。6②接收方相信发送方不是冒充的，这是因为除收发双方外再无其他人知道密钥，因此其他人不可能对自己发送的消息计算出正确的MAC。上述过程中，由于消息本身在发送过程中是明文形式，所以这一过程只提供认证性而未提供保密性。为提供保密性可在MAC函数以后(如图6.1(b))或以前(如图6.1(c))进行一次加密，而且加密密钥也需被收发双方共享。3、MAC的基本使用方式7图6.1MAC的基本使用方式8二、产生MAC的函数应满足的要求①如果敌手得到M和CK(M)，则构造一满足CK(M′)=CK(M)的新消息M′在计算上是不可行的。-----给定M，找与其MAC相同的M′在计算上是不可行的。②CK(M)在以下意义下是均匀分布的：随机选取两个消息M、M′，Pr[CK(M)=CK(M′)]=2-n，其中n为MAC的长。-----随机选取两个消息M、M′，他们的MAC值相等是小概率事件。③若M′是M的某个变换，即M′=f(M)，例如f为插入一个或多个比特，那么Pr[CK(M)=CK(M′)]=2-n。-----函数C不应在消息的某个部分或某些比特弱于其他部分或其他比特，否则敌手获得M和MAC后就有可能修改M中弱的部分，从而伪造出一个与原MAC相匹配的新消息。9三、数据认证算法数据认证算法是最为广泛使用的消息认证码中的一个，已作为FIPSPublication（FIPSPUB113）并被ANSI作为X9.17标准。算法基于CBC模式的DES算法，其初始向量取为零向量。需被认证的数据（消息、记录、文件或程序）被分为64比特长的分组D1，D2，…，DN，其中最后一个分组不够64比特的话，可在其右边填充一些0，然后按以下过程计算数据认证码（见图6.2）：10图6.2数据认证算法11112213321()()()()KKKNKNNOEDOEDOOEDOOEDO其中E为DES加密算法，K为密钥。数据认证码或者取为ON或者取为ON的最左M个比特，其中16≤M≤64。12第二节杂凑函数一、杂凑函数的定义及使用方式杂凑函数H是一公开函数，用于将任意长的消息M映射为较短的、固定长度的一个值H(M)，作为认证符，称函数值H(M)为杂凑值、杂凑码或消息摘要。杂凑码是消息中所有比特的函数，因此提供了一种错误检测能力，即改变消息中任何一个比特或几个比特都会使杂凑码发生改变。1、杂凑函数的定义132、杂凑函数的使用方式基本使用方式，共有以下6种（图6.3）①消息与杂凑码链接后用单钥加密算法加密。由于所用密钥仅为收发双方A、B共享，因此可保证消息的确来自A并且未被篡改。同时还由于消息和杂凑码都被加密，这种方式还提供了保密性，见图6.3(a)。MH||EEK[M||H(M)]KDMH比较图6-3（a）杂凑函数使用方式之一K14②用单钥加密算法仅对杂凑码加密。这种方式用于不要求保密性的情况下，可减少处理负担。注意这种方式和图6.1(a)的MAC结果完全一样，即将EK[H(M)]看作一个函数，函数的输入为消息M和密钥K，输出为固定长度，见图6.3(b)。MHEEK[H(M)]KDM比较||KH图6-3（b）杂凑函数使用方式之二15MHEESKA[H(M)]SKADM比较||PKAH图6-3（c）杂凑函数使用方式之三③用公钥加密算法和发送方的秘密钥仅加密杂凑码。和②一样，这种方式提供认证性，又由于只有发送方能产生加密的杂凑码，因此这种方式还对发送方发送的消息提供了数字签字，事实上这种方式就是数字签字，见图6.3(c)。16④消息的杂凑值用公钥加密算法和发送方的秘密钥加密后与消息链接，再对链接后的结果用单钥加密算法加密，这种方式提供了保密性和数字签字，见图6.3(d)。MHEESKA[H(M)]SKADM比较||PKAH图6-3（d）杂凑函数使用方式之四EKDK17⑤使用这种方式时要求通信双方共享一个秘密值S，A计算消息M和秘密值S链接在一起的杂凑值，并将此杂凑值附加到M后发往B。因B也有S，所以可重新计算杂凑值以对消息进行认证。由于秘密值S本身未被发送，敌手无法对截获的消息加以篡改，也无法产生假消息。这种方式仅提供认证，见图6.3(e)。MHH(M||S)]M比较||H||S||S图6-3（e）杂凑函数使用方式之五18⑥这种方式是在⑤中消息与杂凑值链接以后再增加单钥加密运算，从而又可提供保密性，见图6.3(f)。MHH(M||S)]M比较||H||S||SEKDK图6-3（f）杂凑函数使用方式之六19二、杂凑函数应满足的条件杂凑函数的目的是为需认证的数据产生一个“指纹”。为了能够实现对数据的认证，杂凑函数应满足以下条件：①函数的输入可以是任意长。②函数的输出是固定长。③已知x，求H(x)较为容易，可用硬件或软件实现。④已知h，求使得H(x)=h的x在计算上是不可行的，这一性质称为函数的单向性，称H(x)为单向杂凑函数。⑤已知x，找出y(y≠x)使得H(y)=H(x)在计算上是不可行的。如果单向杂凑函数满足这一性质，则称其为弱单向杂凑函数。20⑥找出任意两个不同的输入x、y，使得H(y)=H(x)在计算上是不可行的。如果单向杂凑函数满足这一性质，则称其为强单向杂凑函数。第⑤和第⑥个条件给出了杂凑函数无碰撞性的概念，如果杂凑函数对不同的输入可产生相同的输出，则称该函数具有碰撞性。21三、迭代型杂凑函数的一般结构目前使用的大多数杂凑函数如MD5、SHA，其结构都是迭代型的，如图6.4所示。其中函数的输入M被分为L个分组Y0,Y1,…,YL-1，每一个分组的长度为b比特，最后一个分组的长度不够的话，需对其做填充。图6.4迭代型杂凑函数的一般结构22最后一个分组中还包括整个函数输入的长度值，这样一来，将使得敌手的攻击更为困难，即敌手若想成功地产生假冒的消息，就必须保证假冒消息的杂凑值与原消息的杂凑值相同，而且假冒消息的长度也要与原消息的长度相等。算法中重复使用一压缩函数f（注意，有些书将杂凑函数也称为压缩函数，在此用压缩函数表示杂凑函数中的一个特定部分），f的输入有两项，一项是上一轮（第i-1轮）输出的n比特值CVi-1，称为链接变量，另一项是算法在本轮（第i轮）的b比特输入分组Yi。f的输出为n比特值CVi，CVi又作为下一轮的输入。算法开始时还需对链接变量指定一个初值IV，23最后一轮输出的链接变量CVL即为最终产生的杂凑值。通常有bn，因此称函数f为压缩函数。算法可表达如下：CV0=IV=n比特长的初值；CVi=f(CVi-1,Yi-1)；1≤i≤L；H(M)=CVL24算法的核心技术是设计无碰撞的压缩函数f，而敌手对算法的攻击重点是f的内部结构，由于f和分组密码一样是由若干轮处理过程组成，所以对f的攻击需通过对各轮之间的位模式的分析来进行，分析过程常常需要先找出f的碰撞。由于f是压缩函数，其碰撞是不可避免的，因此在设计f时就应保证找出其碰撞在计算上是不可行的。25小结：一、消息认证码1、MAC的定义2、MAC的使用过程3、MAC的3种使用方式4、产生MAC的函数应该满足的要求5、了解数据认证算法二、杂凑函数1、杂凑函数定义2、杂凑函数的使用方式（重点掌握第四种）3、杂凑函数应该满足的条件4、杂凑函数的一般结构