密码学与信息安全 第12章 散列算法和MAC算法

,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,第,12,章 散列算法和,MAC,算法,第,12,章 散列算法和,MAC,算法,消息认证是用来验证消息完整性的一种机制或服务。,产生消息认证符的函数分为如下三类：,消息加密：,整个消息的密文作为认证符。,消息认证码（,MAC,）,:,它是消息和密钥的函数，它产生定长的值，以该值作为认证符。目前有两种,MAC,：,HMAC,和,CMAC,散列函数：,它是将任意长的消息映射为定长的散列值的函数，以该散列值作为认证符。目前主要有：,MD5,，,SHA-1,，,SHA256,，,SHA-384,，,SHA-512,，,Whirlpool,等。,在数字签名方案中也要用到散列函数。对需要签名的消息用一个函数，产生一个固定长度的消息摘要（,Message Digest,），最后对消息摘要进行签名，得到确定长度的签名消息。,典型的安全散列函数的总体结构,典型的安全散列函数的总体结构,散列函数将输入消息分为,L,个固定长度的分组，每一分组长为,b,位，最后一个分组不足,b,位时需要将其填充为,b,位，最后一个分组还需要一些空间保存输入的总长度。,散列函数中重复使用了压缩函数,f,，它的输入是前一步中得出的,n,位结果（称为链接变量）和一个,b,位分组，输出为一个,n,位分组。链接变量的初值由算法在开始时指定，其终值即为散列值，通常,bn,，因此称其为压缩函数。散列函数可归纳如下：,CV,0,=IV=,初始,n,位值,CV,i,=f(CV,i-1,Y,i-1,) 1iL,H(M)=CV,L,安全散列算法,安全散列算法（,SHA,）是由美国标准与技术协会（,NIST,）设计，并于,1993,年作为联邦信息处理标准（,FIPS 180,）发布，修订版于,1995,年发布（,FIPS 180-1,），通常称之为,SHA-1.,SHA-1,产生,160,比特的散列值。,2002,年，,NIST,发布了修订版,2,，,FIPS180-2,，其中给出了三种新的,SHA,版本，散列值长度依次为,256,，,384,和,512,比特。分别称为,SHA-256,，,SHA-384,，,SHA-512,。这些新的版本和,SHA-1,具有相同的基础结构，使用了相同的模算术和二元逻辑运算。,2005,年，,NIST,宣布了逐步废除,SHA-1,的意图，到,2010,年，逐步转而依赖,SHA,的其他版本。,安全散列算法,.,所有的长度以比特为单位,.,安全性是指对输出长度为,n,比特散列函数的生日攻击产生碰撞的工作量大约为,2,n/2,SHA-1,SHA-256,SHA-384,SHA-512,消息摘要长度,160,256,384,512,消息长度,2,64,2,64,2,128,2,128,分组长度,512,512,1024,1024,字长度,32,32,64,64,步骤数,80,64,80,80,安全性,80,128,192,256,SHA-512,逻辑原理,+,为模,2,64,的逐字加,SHA-512,逻辑原理,这个过程包含下列步骤：,步骤,1,：,附加填充位。填充消息使其长度模,1024,与,896,同余,即长度,896 (mod 1024),，即使消息已经满足上述长度要求，仍然需要进行填充，因此填充位数在,1,到,1024,之间。填充由一个,1,和后续的,0,组成。,步骤,2,：,附加长度。在消息后附加一个,128,比特的块，将其看做是,128,比特的无符号整数，它包含填充前消息的长度。,SHA-512,逻辑原理,步骤,3,：,初始化散列缓冲区。散列函数的中间结果和最终结果保存于,512,比特的缓冲区中，缓冲区用,8,个,64,比特的寄存器（,a,b,c,d,e,f,g,h,）表示，并将这些寄存器初始化为下列,64,比特的整数：,a=6A09E667F3BCC908,e=510E527FADE682D1,b=BB67AE8584CAA73B,f=9B05688C2B3E6C1F,c=3C6EF372FE94F82B,g=1F83D9ABFB41BD6B,d=A54FF53A5F1D36F1,h=5BE0CD19137E2179,SHA-512,逻辑原理,步骤,4,：,以,1024,比特的分组（,16,个字）为单位处理消息。算法的核心是具有,80,轮运算的模块。每一轮，如,t,，使用一个,64,比特的值,W,t,，该值由当前被处理的,1024,比特消息分组,M,i,导出。每一轮还使用附加的常数,K,t,，其中,0t79,，用来表示轮数。这些常数如下获得：前,80,个素数取三次根，取小数部分的前,64,比特。第,80,轮的输出和第一轮的输入,H,i-1,进行模,2,64,相加产生,H,i,步骤,5,：,输出。所有的,N,个,1024,比特分组都处理完以后，从第,N,阶段输出的是,512,比特的消息摘要。,H,o,=IV,H,i,=SUM,64,(H,i-1,abcdefgh,i,),MD=H,N,SHA-512,轮函数,SHA-512,轮函数,T,1,=h+Ch(e,f,g)+( )+W,t,+K,t,T,2,=( )+Maj(a,b,c),a= T,1,+T,2,b=a,c=b,d=c,e=d+ T,1,f=e,g=f,h=g,SHA-512,轮函数,其中：,t :,步骤数，,0t79,Ch(e,f,g)= (e AND f),(NOT e AND g),Maj(a,b,c)= (a AND b),(a AND c),(b AND c),=ROTR,28,(a),ROTR,34,(a),ROTR,39,(a),= ROTR,14,(e),ROTR,18,(e),ROTR,41,(e),ROTR,n,(x):,对,64,比特的变量,x,循环右移,n,比特,W,t,: 64,比特字，从当前的,1024,比特输入分组导出,K,t,: 64,比特附加常数,+,： 模,2,64,加,SHA-512,轮函数,前,16,个,W,t,直接取自当前分组的,16,个字。余下的值按如下方式导出：,W,t,=,1,512,(W,t-2,),W,t-7,0,512,(W,t-15,),W,t-16,其中：,0,512,(x) = ROTR,1,(x),ROTR,8,(x),SHR,7,(x),1,512,(x)= ROTR,19,(x),ROTR,61,(x),SHR,6,(x),SHR,n,(x):,对,64,比特变量,x,向左移动,n,位，右边填充,0,HMAC,对于,MAC,，一种策略是利用,hash,函数来设计，因为：,1,、一般像,md5,、,sha-1,这样的散列函数，其软件执行速度比诸如,des,这样的对称分组密码钥要快。,2,、可以利用密码散列函数代码库。,由于散列函数不是专为,MAC,设计的，其不依赖于秘密钥，所以不能直接用于,MAC,，目前提出了许多方案，其中,HMAC,是最受支持的一种方案。它是,IP,安全里必须实现的,MAC,方案，并且在其他,Internet,协议中也使用了,HMAC,HMAC,设计目标,不必修改而直接使用现有的,hash,函数。特别地，很容易免费得到软件上执行速度较快的散列函数及其代码。,如果找到或者需要更快或更安全的,hash,函数，应能很容易地替代原来嵌入的,hash,函数。,应保持,hash,函数的原有性能。,对密钥的使用和处理应较简单。,如果已知嵌入的,hash,函数的强度，则完全可以知道认证机制抗密码分析的强度。,HMAC,算法,H,：嵌入的,hash,函数,IV,：作为散列函数的输入值,M,：,HMAC,的消息输入,Y,i,：,M,的第,i,个分组,L,：,M,中的分组数,b,：每一分组所含的位数,n,：嵌入的散列函数所产生散列码长,K,：密钥，若,k,长度大于,b,，则将密钥作为散列函数的输入产生一个,n,位的新密钥来使用,K+,： 为使,K,为,b,位长而在,K,左边填充,0,后所得的结果。,ipad: 00110110(,十六进制数,36),重复,b/8,次的结果。,opad: 01011100(,十六进制数,5C),重复,b/8,次的结果。,密钥可以进行预处理,