【教学课件】第十一讲认证、哈希算法.ppt
第十一讲 认证、哈希算法上海交通大学计算机科学系1.Message Authentication消息认证包括:消息完整性 身份识别 不可否认性 2.消息认证码消息认证码(MAC)message authentication code(MAC)签名的电子等价形式 与消息同时发送 通过一些算法,依赖于消息及双方共享的秘密消息可以是不任意长MAC 可以是任意长,但常选固定长度这需要hash function“压缩”消息成固定长度3.消息认证过程消息认证过程 4.1利用对称密码进行认证利用对称密码进行认证利用对称密码加密的消息可以作为认证内容因为只有密钥的拥有者才可以生成(要求消息有一定的冗余度)但不能解决消息的不可否认性（无法证明谁生成的消息）4.2 报文鉴别码HH(M)HH5.Hashing Functions把任意长的消息“压缩”成固定长的消息的算法数字签名时，常被使用通常，HASH 函数是公开的 输出长度应足够大，防止生日攻击64-bits 认为太小通常 128-512bits6.Hash 函数设计原理函数设计原理H H能用于任何大小的数据分组能用于任何大小的数据分组;H H产生定长输出产生定长输出;对任意给定的对任意给定的x,H(x)x,H(x)要相对易于计算要相对易于计算,使得软硬件使得软硬件实现都实际可行实现都实际可行;对任意给定的码对任意给定的码h,h,寻求寻求x x使得使得H(x)=hH(x)=h在计算上是不在计算上是不可行的可行的(单向性单向性););任意给定分组任意给定分组x,x,寻求不等于寻求不等于x x的的y,y,使得使得H(y)=H(y)=H(x)H(x)在计算上不可行在计算上不可行(弱抗攻击性弱抗攻击性););寻求对任何的寻求对任何的(x,y)(x,y)对使得对使得H(x)=H(y)H(x)=H(y)在计算上不可在计算上不可行行(强抗攻击性强抗攻击性););7 Hash 函数设计原理函数设计原理生日攻击生日攻击(基于生日悖论基于生日悖论)在在k k个人中个人中,找一个与某人生日相同的人找一个与某人生日相同的人的的概率超过概率超过0.50.5时时,只需只需k183;k183;而在此人群中而在此人群中,至少有两个人生日相同的概率超过至少有两个人生日相同的概率超过0.5,0.5,只只需需k23.k23.bY0nfbY1nfbYL-1nCVL-1fCV1nnIV =初始值初始值CV=链接值链接值Yi =第第i 个输入数据块个输入数据块f =压缩算法压缩算法n =散列码的长度散列码的长度b =输入块的长度输入块的长度8 安全杂凑算法的一般结构安全杂凑算法的一般结构CVLCV0=IV=initial n-bit valueCVi=f(CVi-1,Yi-1)(1 i L)H(M)=CVL9 MD5 9 MD5 算法逻辑算法逻辑输入：任意长度的消息输入：任意长度的消息输出：输出：128位消息摘要位消息摘要处理：以处理：以512位输入数据块为单位位输入数据块为单位MD5(RFC 1321)developed by Ron Rivest at MIT in 90s.报文报文K bitsL 512 bits=N 32bits报文长度报文长度(K mod 264)1000Y0512 bitsY1512 bitsYq512 bitsYL-1512 bitsHMD5IV128HMD5CV1128HMD5CVq128HMD5CVL-1128512512512512128-bit 摘要摘要MD5产生报文摘要的过程产生报文摘要的过程填充填充(1 to 512 bits)11 MD5算法描述算法描述步骤步骤1 1：添加填充位添加填充位(一个一个1 1 和若干个和若干个0)0)。在消息的最。在消息的最后添加适当的填充位使得数据位的长度满足后添加适当的填充位使得数据位的长度满足length length 448 mod 512448 mod 512。步骤步骤2 2：添加长度。原始消息长度（二进制位的个数）添加长度。原始消息长度（二进制位的个数），用，用6464位表示。位表示。表示为表示为L L个个512512位的数据块：位的数据块：Y Y0 0,Y,Y1 1,Y,YL-1L-1。其长度为其长度为L L 512bits512bits。令。令N=N=L L 16,16,则长度则长度为为N N个个3232位的字。令位的字。令M0N-1M0N-1表示以字为单位的消息表表示以字为单位的消息表示。示。12 MD5算法描述算法描述(Cont.)步骤步骤3：初始化：初始化MD缓冲区。一个缓冲区。一个128位位MD缓冲缓冲区用以保存中间和最终散列函数的结果。它可区用以保存中间和最终散列函数的结果。它可以表示为以表示为4个个32位的寄存器位的寄存器(A,B,C,D)。寄存器初始化为以下的寄存器初始化为以下的16进制值。进制值。A=67452301B=EFCDAB89C=98BADCFED=1032547613Word A:01 23 45 67Word B:89 AB CD EFWord C:FE DC BA 98Word D:76 54 32 1014 MD5算法描述算法描述(Cont.)步骤步骤4：处理消息块（：处理消息块（512位位=16个个32位位字）。一个压缩函数是本算法的核心字）。一个压缩函数是本算法的核心(HMD5)。它包括。它包括4轮处理。四轮处理具有轮处理。四轮处理具有相似的结构相似的结构,但每次使用不同的基本逻辑但每次使用不同的基本逻辑函数，记为函数，记为F,G,H,I。每一轮以当前的。每一轮以当前的512位数据块位数据块(Yq)和和128位缓冲值位缓冲值ABCD作为作为输入，并修改缓冲值的内容。每次使用输入，并修改缓冲值的内容。每次使用64元素表元素表T164中的四分之一中的四分之一T表，由表，由sin 函数构造而成。函数构造而成。T的第的第i个元素表示个元素表示为为Ti，其值等于，其值等于 232 abs(sin(i),其中其中i是弧度。是弧度。由于由于abs(sin(i)是一个是一个0到到1之间的数，之间的数，T的每一的每一个元素是一个可以表示成个元素是一个可以表示成32位的整数。位的整数。T表提表提供了随机化的供了随机化的32位模板，消除了在输入数据中位模板，消除了在输入数据中的任何规律性的特征的任何规律性的特征15 T 表T49 =F4292244T50 =432AFF97T51 =AB9423A7T52 =FC93A039T64 =EB86D391T1 =D76AA478T2 =E8C7B756T3 =242070DBT4 =C1BDCEEET16 =49b4082116 MD5算法描述算法描述(Cont.)步骤步骤5：输出结果。所有：输出结果。所有L个个512位数据块处理完毕后，最后的结果位数据块处理完毕后，最后的结果就是就是128位消息摘要。位消息摘要。CV0=IV CVq+1=SUM32(CVq,RFIYq,RFHYq,RFGYq,RFFYq,CVq)MD=CVL 其中：其中：IV =ABCD的初始值（见步骤的初始值（见步骤3）Yq =消息的第消息的第q个个512位数据块位数据块 L =消息中数据块数；消息中数据块数；CVq =链接变量，用于第链接变量，用于第q个数据块的处理个数据块的处理 RFx =使用基本逻辑函数使用基本逻辑函数x的一轮功能函数。的一轮功能函数。MD =最终消息摘要结果最终消息摘要结果 SUM32=分别按分别按32位字计算的模位字计算的模232加法结果。加法结果。F,T116,Xi16 stepsG,T1732,X2i16 stepsH,T3348,X3i16 stepsI,T4964,X4i16 steps+ABCDABCDABCDABCDCVq12832Yq512CVq+1128+is mod 232单个单个 512-bit 分组的分组的MD5 处理过程处理过程17 MD5 压缩函数压缩函数每一轮包含对缓冲区每一轮包含对缓冲区ABCD的的16步操作所组成的一个序列。步操作所组成的一个序列。ab+(a+g(b,c,d)+Xk+Ti)s)其中，其中，a,b,c,d =缓冲区的四个字，以一个给定的次序排列缓冲区的四个字，以一个给定的次序排列;g =基本逻辑函数基本逻辑函数F,G,H,I之一；之一；s =对对32位字循环左移位字循环左移s位位Xk =Mq 16+k=在第在第q个个512位数据块中的第位数据块中的第k个个32位字位字Ti =表表T中的第中的第i个个32位字；位字；+=模模 232的加；的加；ABCDABCD+CLSs+gXkTi2i=(1+5i)mod 163i=(5+3i)mod 162i=7i mod 16基本基本MD5操作操作(单步单步)Function g g(b,c,d)1 F(b,c,d)(b c)(b d)2 G(b,c,d)(b d)(c d)3 H(b,c,d)b c d4 I(b,c,d)c(b d)19 MD4(1990年年10月作为月作为RFC1320发表发表)by Ron Rivest at MITMD4的设计目标的设计目标安全性：安全性：速度：速度：32位体系结构下计算速度快位体系结构下计算速度快.简明与紧凑：易于编程简明与紧凑：易于编程.有利的小数在前的结构有利的小数在前的结构(Intel 80 xxx,Pentium)MD4与与MD5的区别的区别MD4用用3轮轮,每轮每轮16 步步,MD5用用4轮轮,每轮每轮16步步.MD4中第一轮没有常量加；中第一轮没有常量加；MD5中中64步每一步用了步每一步用了一个不同的常量一个不同的常量 Ti；MD5用了四个基本逻辑函数，每轮一个；用了四个基本逻辑函数，每轮一个；MD4用了用了三个三个.MD5每轮加上前一步的结果；每轮加上前一步的结果；MD4没有没有.END
