第11讲 认证、哈希算法

第十一讲认证、哈希算法•上海交通大学计算机科学系1.MessageAuthentication消息认证包括:•消息完整性•身份识别•不可否认性2.消息认证码(MAC)•messageauthenticationcode(MAC)•签名的电子等价形式•与消息同时发送•通过一些算法,依赖于消息及双方共享的秘密•消息可以是不任意长•MAC可以是任意长,但常选固定长度•这需要hashfunction•“压缩”消息成固定长度3.消息认证过程4.利用对称密码进行认证•利用对称密码加密的消息可以作为认证内容•因为只有密钥的拥有者才可以生成•(要求消息有一定的冗余度)•但不能解决消息的不可否认性•（无法证明谁生成的消息）5.HashingFunctions•把任意长的消息“压缩”成固定长的消息的算法•数字签名时，常被使用•通常，HASH函数是公开的•输出长度应足够大，防止生日攻击•64-bits认为太小•通常128-512bits6.Hash函数设计原理–H能用于任何大小的数据分组;–H产生定长输出;–对任意给定的x,H(x)要相对易于计算,使得软硬件实现都实际可行;–对任意给定的码h,寻求x使得H(x)=h在计算上是不可行的(单向性);–任意给定分组x,寻求不等于x的y,使得H(y)=H(x)在计算上不可行(弱抗攻击性);–寻求对任何的(x,y)对使得H(x)=H(y)在计算上不可行(强抗攻击性);7Hash函数设计原理•生日攻击(基于生日悖论)在k个人中,找一个与某人生日相同的人的概率超过0.5时,只需k183;而在此人群中,至少有两个人生日相同的概率超过0.5,只需k23.bY0nfbY1nfbYL-1nCVL-1fCV1nnIV=初始值CV=链接值Yi=第i个输入数据块f=压缩算法n=散列码的长度b=输入块的长度8安全杂凑算法的一般结构CVLCV0=IV=initialn-bitvalueCVi=f(CVi-1,Yi-1)(1iL)H(M)=CVL9MD5算法逻辑•输入：任意长度的消息•输出：128位消息摘要•处理：以512位输入数据块为单位MD5(RFC1321)developedbyRonRivestatMITin90’s.报文KbitsL512bits=N32bits报文长度(Kmod264)100…0Y0512bitsY1512bitsYq512bitsYL-1512bitsHMD5IV128HMD5CV1128HMD5CVq128HMD5CVL-1128512512512512128-bit摘要MD5产生报文摘要的过程填充(1to512bits)11MD5算法描述•步骤1：添加填充位(一个1和若干个0)。在消息的最后添加适当的填充位使得数据位的长度满足length448mod512。•步骤2：添加长度。原始消息长度（二进制位的个数），用64位表示。表示为L个512位的数据块：Y0,Y1,…,YL-1。其长度为L512bits。令N=L16,则长度为N个32位的字。令M[0…N-1]表示以字为单位的消息表示。12MD5算法描述(Cont.)•步骤3：初始化MD缓冲区。一个128位MD缓冲区用以保存中间和最终散列函数的结果。它可以表示为4个32位的寄存器(A,B,C,D)。寄存器初始化为以下的16进制值。A=67452301B=EFCDAB89C=98BADCFED=1032547613WordA:01234567WordB:89ABCDEFWordC:FEDCBA98WordD:7654321014MD5算法描述(Cont.)•步骤4：处理消息块（512位=16个32位字）。一个压缩函数是本算法的核心(HMD5)。它包括4轮处理。四轮处理具有相似的结构,但每次使用不同的基本逻辑函数，记为F,G,H,I。每一轮以当前的512位数据块(Yq)和128位缓冲值ABCD作为输入，并修改缓冲值的内容。每次使用64元素表T[1…64]中的四分之一•T表，由sin函数构造而成。T的第i个元素表示为T[i]，其值等于232abs(sin(i)),其中i是弧度。由于abs(sin(i))是一个0到1之间的数，T的每一个元素是一个可以表示成32位的整数。T表提供了随机化的32位模板，消除了在输入数据中的任何规律性的特征15T表T[49]=F4292244T[50]=432AFF97T[51]=AB9423A7T[52]=FC93A039．．．T[64]=EB86D391T[1]=D76AA478T[2]=E8C7B756T[3]=242070DBT[4]=C1BDCEEE．．．T[16]=49b4082116MD5算法描述(Cont.)•步骤5：输出结果。所有L个512位数据块处理完毕后，最后的结果就是128位消息摘要。CV0=IVCVq+1=SUM32(CVq,RFI[Yq,RFH[Yq,RFG[Yq,RFF[Yq,CVq]]]])MD=CVL其中：IV=ABCD的初始值（见步骤3）Yq=消息的第q个512位数据块L=消息中数据块数；CVq=链接变量，用于第q个数据块的处理RFx=使用基本逻辑函数x的一轮功能函数。MD=最终消息摘要结果SUM32=分别按32位字计算的模232加法结果。F,T[1…16],X[i]16stepsG,T[17…32],X[2i]16stepsH,T[33…48],X[3i]16stepsI,T[49…64],X[4i]16steps++++ABCDABCDABCDABCDCVq12832Yq512CVq+1128+ismod232单个512-bit分组的MD5处理过程17MD5压缩函数每一轮包含对缓冲区ABCD的16步操作所组成的一个序列。ab+((a+g(b,c,d)+X[k]+T[i])s)其中，a,b,c,d=缓冲区的四个字，以一个给定的次序排列;g=基本逻辑函数F,G,H,I之一；s=对32位字循环左移s位X[k]=M[q16+k]=在第q个512位数据块中的第k个32位字T[i]=表T中的第i个32位字；+=模232的加；ABCDABCD+++CLSs+gX[k]T[i]2i=(1+5i)mod163i=(5+3i)mod162i=7imod16基本MD5操作(单步)Functiongg(b,c,d)1F(b,c,d)(bc)(bd)2G(b,c,d)(bd)(cd)3H(b,c,d)bcd4I(b,c,d)c(bd)19MD4(1990年10月作为RFC1320发表)byRonRivestatMIT•MD4的设计目标•安全性：•速度：32位体系结构下计算速度快.•简明与紧凑：易于编程.•有利的小数在前的结构(Intel80xxx,Pentium)•MD4与MD5的区别•MD4用3轮,每轮16步,MD5用4轮,每轮16步.•MD4中第一轮没有常量加；MD5中64步每一步用了一个不同的常量T[i]；•MD5用了四个基本逻辑函数，每轮一个；MD4用了三个.•MD5每轮加上前一步的结果；MD4没有.•••END