第3章-单向散列函数详解

第3章单向散列函数1NetworkandInformationSecurity第3章单向散列函数3.1单向散列函数概述3.2MD5算法3.3SHA-1算法3.4消息认证码(MAC)3.5对单向散列函数的攻击第3章单向散列函数2NetworkandInformationSecurity•随着以Internet为基础的电子商务技术的迅猛发展,以公钥密码、数字签名等为代表的加密安全技术已成为研究的热点。•单向散列函数是数字签名中的一个关键环节,可以大大缩短签名时间并提高安全性,另外在消息完整性检测,内存的散布分配,软件系统中帐号口令的安全存储单向散列函数也有重要应用。第3章单向散列函数3NetworkandInformationSecurity3.1单向散列函数概述•所谓的单向散列函数(HashFunction，又称哈希函数、杂凑函数)，是将任意长度的消息M映射成一个固定长度散列值h(设长度为m)的函数H：•h=H(M)•散列函数要具有单向性，则必须满足如下特性：•●给定M，很容易计算h。•●给定h，根据H(M)=h反推M很难。•●给定M，要找到另一消息M'并满足H(M)=H(M')很难。•在某些应用中，单向散列函数还需要满足抗碰撞(Collision)的条件：要找到两个随机的消息M和M'，使H(M)=H(M')很难。第3章单向散列函数4NetworkandInformationSecurityHash函数的良好性质•（1）广泛的应用性•Hash函数能用于任何大小的消息。•（2）定长输出•将消息集合∑中的任意长度的消息Ｍ映射为长度为ｍ的消息摘要。•（3）实现性•对Hash函数的一个非常重要的要求是简单易实现性。•（4）单向性质•要求Hash函数是单向函数。给定h值，求信息M（是一对多的关系），只有通过枚举，在现有的计算环境下是不可行的。第3章单向散列函数5NetworkandInformationSecurity（5）抗弱对抗性确定与x有相同位数的y,使H(x)=H(y),在现有的计算环境下是不可行的。（6）抗强对抗性找到两个不同位数信息x,y,使H(x)=H(y)，在现有的计算环境下是不可行的。注：以上两种，哪一种更容易找？（7）独立性哈希函数值“不依赖输入信息”，从某种程度上说是由算法决定的。（8）抗近冲突Hash函数满足独立性，输入信息某一位的变化，应该引起平均一半的输出位的变化。（9）安全性在很广泛的条件下,Hash值Ｈ(Ｍ)的分布是均匀分布的.第3章单向散列函数6NetworkandInformationSecurity散列函数工作模式消息分组1消息分组2压缩函数压缩函数IV……消息分组n填充位压缩函数函数值图3-1单向散列函数工作模式第3章单向散列函数7NetworkandInformationSecurity3.2.1算法MD表示消息摘要(MessageDigest)。MD5是MD4的改进版，该算法对输入的任意长度消息产生128位散列值(或消息摘要)。MD5算法可用图3-2表示。3.2MD5算法第3章单向散列函数8NetworkandInformationSecurity图3-2MD5算法1)附加填充位2)附加长度643)初始化MD缓冲区5)输出4)按512位的分组处理输入消息100…0消息Kbit32bitN512bitL512bit…512512bit512bit512128512…128128IVCVL-1CV1128位消息摘要HMD5HMD5HMD5Y0Y1YL-1消息长度（Kmod264）填充位图3-2MD5算法第3章单向散列函数9NetworkandInformationSecurity由上图可知，MD5算法包括以下五个步骤。1)附加填充位首先填充消息，使其长度为一个比512的倍数小64位的数。填充方法：在消息后面填充一位1，然后填充所需数量的0。填充位的位数从1～512。填充消息长度=512-(k+64)mod5122)附加长度将原消息长度的64位表示附加在填充后的消息后面。当原消息长度大于264时，用消息长度mod264填充。这时，总长度恰好是512的整数倍。令M[01…N−1]为填充后消息的各个字(每字为32位)，N是16的倍数。第3章单向散列函数10NetworkandInformationSecurity3)初始化MD缓冲区初始化用于计算消息摘要的128位缓冲区。这个缓冲区由四个32位寄存器A、B、C、D表示。寄存器的初始化值为(按低位字节在前的顺序存放)：A:01234567B:89abcdefC:fedcba98D:765432104)按512位的分组处理输入消息这一步为MD5的主循环，包括四轮，如图3-3所示。每个循环都以当前的正在处理的512比特分组Yq和128比特缓冲值ABCD为输入，然后更新缓冲内容。第3章单向散列函数11NetworkandInformationSecurity＋＋＋＋第四轮第三轮第二轮第一轮ABCDCVqYqABCDCVq＋1图3-3单个512比特分组的MD5主循环处理第3章单向散列函数12NetworkandInformationSecurity图3-3中，四轮的操作类似，每一轮进行16次操作。各轮的操作过程如图3-4所示。图3-4MD5某一轮的1次执行过程c＋＋＋s＋非线性函数bdaMjT[i]cbdaj:0—15,i:1—64(共四轮，每一轮用的都不同)第3章单向散列函数13NetworkandInformationSecurity四轮操作的不同之处在于每轮使用的非线性函数不同，在第一轮操作之前，首先把A、B、C、D复制到另外的变量a、b、c、d中。这四个非线性函数分别为(其输入/输出均为32位字)：F(X,Y,Z)=(X٨Y)٧((～X)٨Z)G(X,Y,Z)=(X٨Z)٧(Y٨(～Z))H(X,Y,Z)=XYZI(X,Y,Z)=Y(X٧(～Z))其中，٨表示按位与；٧表示按位或；～表示按位反；表示按位异或。第3章单向散列函数14NetworkandInformationSecurity•此外，由图3-4可知，这一步中还用到了一个有64个元素的表T[1..64]，T[i]=232×abs(sin(i))，i的单位为弧度。•根据以上描述，将这一步骤的处理过程归纳如下：•fori=0toN/16−1do•/*每次循环处理16个字，即512字节的消息分组*/•/*把A存为AA，B存为BB，C存为CC，D存为DD*/•AA=A•BB=B•CC=C•DD=D第3章单向散列函数15NetworkandInformationSecurity/*第一轮*//*令[abcdksi]表示操作b=b+((a+F(b,c,d)+M[k]+T[i])s)其中，Ys表示Y循环左移s位*//*完成下列16个操作*/[ABCD071][DABC1122][CDAB2173][BCDA3224][ABCD475][DABC5126][CDAB6177][BCDA7228][ABCD879][DABC91210][CDAB101711][BCDA112212][ABCD12713][DABC131214][CDAB141715][BCDA152216]第3章单向散列函数16NetworkandInformationSecurity/*第二轮*//*令[abcdksi]表示操作b=b+((a+G(b,c,d)+M[k]+T[i])s)*//*完成下列16个操作*/[ABCD1517][DABC6918][CDAB111419][BCDA02020][ABCD5521][DABC10922][CDAB151423][BCDA42024][ABCD9525][DABC14926][CDAB31427][BCDA82028][ABCD13529][DABC2930][CDAB71431][BCDA122032]第3章单向散列函数17NetworkandInformationSecurity/*第三轮*//*令[abcdkst]表示操作b=b+((a+H(b,c,d)+M[k]+T[i])s)*//*完成以下16个操作*/[ABCD5433][DABC81134][CDAB111635][BCDA142336][ABCD1437][DABC41138][CDAB71639][BCDA102340][ABCD13441][DABC01142][CDAB31643][BCDA62344][ABCD9445][DABC121146][CDAB151647][BCDA22348]第3章单向散列函数18NetworkandInformationSecurity/*第四轮*//*令[abcdkst]表示操作b=b+((a+I(b,c,d)+M[k]+T[i])s)*//*完成以下16个操作*/[ABCD0649][DABC71050][CDAB141551][BCDA52152][ABCD12653][DABC31054][CDAB101555][BCDA12156][ABCD8657][DABC151058][CDAB61559][BCDA132160][ABCD4661][DABC111062][CDAB21563][BCDA92164]A=A+AAB=B+BBC=C+CCD=D+DDend/*i循环*/第3章单向散列函数19NetworkandInformationSecurity5)输出由A、B、C、D四个寄存器的输出按低位字节在前的顺序(即以A的低字节开始、D的高字节结束)得到128位的消息摘要。以上就是对MD5算法的描述。MD5算法的运算均为基本运算，比较容易实现且速度很快。第3章单向散列函数20NetworkandInformationSecurity3.2.2举例我们以求字符串“abc”的MD5散列值为例来说明上面描述的过程。“abc”的二进制表示为011000010110001001100011。1．填充消息消息长24，先填充1位1，然后填充423位0，再用消息长24，即0x0000000000000018填充，则：M[0]=61626380M[1]=00000000M[2]=00000000M[3]=00000000M[4]=00000000M[5]=00000000M[6]=00000000M[7]=00000000M[8]=00000000M[9]=00000000M[10]=00000000M[11]=00000000M[12]=00000000M[13]=00000000M[14]=00000000M[15]=000000182．初始化A:01234567B:89abcdefC:fedcba98D:765432103．主循环利用3.2.1节中描述的过程对字块1（本例只有一个字块）进行处理。变量a、b、c、d每一次计算后的中间值不再详细列出。4．输出消息摘要=900150983cd24fb0d6963f7d28e17f72第3章单向散列函数21NetworkandInformationSecurity3.3安全散列函数(SHA-1)3.3.1算法SHA是美国NIST和NSA共同设计的安全散列算法(SecureHashAlgorithm)，用于数字签名标准DSS(DigitalSignatureStandard)。SHA的修改版SHA–1于1995年作为美国联邦信息处理标准公告(FIPSPUB180–1)发布。SHA–1产生消息摘要的过程类似MD5，如图3-5所示。第3章单向散列函数22NetworkandInformationSecurity图3-5SHA–1算法消息100…0Kbit32bitN512bitL512bit…512512bit512bit512160512…160160IVCVL-1CV1160位消息摘要HSHAHSHAHSHAY0Y1YL-1消息长度（Kmod264）填充位图3-5SHA-1算法第3