Hash函数-MD5

Hash函数MD5算法Hash函数“Hash函数一词最初来源于计算机科学，表示可以将任意长度的字符串压缩成固定长度的字符串的函数，Hash函数的输出结果，称为Hash值，又称为消息摘要、指纹等。Hash函数设计原则Hash函数的算法是公开的，实际应用中，安全的Hash函数必须符合以下三个设计原则：抗碰撞性攻击抗第二原像攻击抗第一原像攻击由于Hash函数具有压缩的性质，所以必然存在多个消息串对应同一Hash值的可能，这就是所说的碰撞的出现对于任意一个消息串a，容易得到它的Hash值h(a)；但是从它的Hash值h(a)很难推出相应的消息串a，此时消息串a称之为h(a)的原像。对于某一给定的消息串a，很难找到另一不同的消息串b，使得h(a)=h(b)。抗第二原像攻击使得Hash函数可以应用于数字签名和身份认证领域。Hash函数类别Hash函数有上述三个安全特性，由于这些特性，Hash函数在公钥密码、数字签名、完整性检验、身份认证等领域中有着广泛的应用。MDx系列SHA系列MD4MD5NAVALRIPENDSHA-0SHA-1SHA-256SHA-384MD5算法Md5的全称是Message-DigestAlgorithm5（信息-摘要算法），在90年代初由MitLaboratoryForComputerScience和RsaDataSecurityInc的Ronaldl.rivest开发出来，经md2、md3和md4发展而来。它的作用是让大容量信息在用数字签名软件签署私人密钥前被“压缩”成一种保密的格式。MD5算法2004年8月17日的美国加州圣巴巴拉的国际密码学会议上，山东大学的王小云教授做了破译MD5、HAVAL-128、MD4和RIPEMD算法的报告，提出了一套新的针对MDx系列的Hash函数的分析技术，同时给出了得到满足差分路线的充分条件的方法，以及如何使用明文修改技术来提高碰撞攻击的成功概率。公布了MD系列算法的破解结果，标志着MD5加密算法不再是一种安全的加密算法。MD5算法2005年，王小云等应用此技术对MD5、SHA-0、SHA-1算法进行碰撞攻击，取得了很好的效果，在普通的个人电脑上就可以找到相关碰撞的实例。这一攻击技术对现有的Hash函数提出了严峻的挑战，促进了新的Hash算法的开发研究：美国NIST于2007年开始在全球征集新的Hash算法。截至2008年11月，一共提交了64个入选算法；2008年12月有51个算法被NIST接收作为第一轮的候选算法；2009年7月，NIST公布了进入第二轮的14个算法；2010年将公布进入最终一轮的5个算法；最终将于2012年选出获胜算法并命名为SHA-3。MD5算法虽然王小云教授公布了破解MD5算法的报告，宣告该算法不再安全，但是对于公司以及普通用户来说，从算法上来破解MD5非常困难，因此MD5仍然算是一种安全的算法。MD5是一个安全的散列算法，输入两个不同的明文不会得到相同的输出值，根据输出值，不能得到原始的明文，即其过程不可逆；所以要解密MD5没有现成的算法，只能用穷举法，把可能出现的明文，用MD5算法散列之后，把得到的散列值和原始的数据形成一个一对一的映射表，通过比在表中比破解密码的MD5算法散列值，通过匹配从映射表中找出破解密码所对应的原始明文。MD5算法描述MD5以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由四个32位分组组成，将这四个32位分组级联后将生成一个128位散列值。L×512bit＝N×32bit消息Kbit100…0填充位消息长度(Kmod264)Y0512bit512HMD5Y1512HMD5CV1128128IV512bit……YL－1512HMD5128位消息摘要128512bitCVL－1MD5算法描述步骤一：附加填充位对报文填充使报文的长度（比特数）与448模512同余。即填充比特使长度为512的整数倍减去64。MD5算法描述步骤二：附加长度值将用64比特表示的初始报文（填充前）的位长度附加在步骤一的结果后（低位字节优先）。如果初始长度大于2^64，仅使用该长度的低64比特。MD5算法描述步骤二：附加长度值经扩展的报文表示成512比特的分组序列列Y1、Y2、Y3……Y（n-1），因此扩展的报文长度等于L乘512比特。与之等价的是，该结果也等于字长为16比特或32比特的整数倍。MD5算法描述步骤三：初始化MD缓冲区使用一个128比特的缓存来存放该散列函数的中间值及最终结果。该缓存可表示为4个32比特的寄存器(ABCD)。A=0x67452301，B=0xEFCDAB89，C=0x98BADCFE，D=0x10325476，这些值以低位字节放在在前的格式存储：A=01234567，B=89ABCDEF，C=FEDCBA98，D=76543210MD5算法描述步骤四：处理512比特报文分组序列算法的核心是一个包含四个“循环”的压缩函数，右图为单个512比特分组MD5处理过程：MD5算法描述步骤五：输出所有L个512比特的分组处理完成后，第L阶段产生的输出便是128比特的报文摘要。说明：最后的输出是A，B，C和D的级联。最后得到的A，B，C，D就是输出结果，A是低位，D为高位，DCBA组成128位输出结果。MD5算法描述步骤四中，四个循环有相似的结构，但每次循环使用不同的原始逻辑函数，说明中表示为FGHI。每一循环都以当前的正在处理的512比特分组(Yq)和128比特的缓存值ABCD为输入，然后更新缓存的内容。每一循环使用一个64元素表T[0…64]的四分之一，该表通过正弦函数构建。T的第i个元素（表示为[Ti]）的值等于的整数部分，每个T的值均能用32比特表示。MD5算法描述每轮运算用到了4个基本逻辑函数：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))（&代表与，|代表或，~代表非，^代表异或）MD5算法描述MD5单步操作设Xi表示消息的第i个子分组(从0到15)；S表示循环左移S位，则四种操作为：FF(a,b,c,d,Mi,s,ti)表示a=b+((a+(F(b,c,d)+Mi+ti)s)GG(a,b,c,d,Mi,s,ti)表示a=b+((a+(G(b,c,d)+Mi+ti)s)HH(a,b,c,d,Mi,s,ti)表示a=b+((a+(H(b,c,d)+Mi+ti)s)II(a,b,c,d,Mi,s,ti)表示a=b+((a+(I(b,c,d)+Mi+ti)s)MD5算法描述这四轮中的第1步进行不同处理，其他步骤是相同的。---每一轮有16个输入子块X[0]，X[1]，…，X[15]，或表示为X[i]，其中i为1～15。每个子块为32位。---T是个常量数组，包含64个元素，每个元素为32位。我们把数组t的元素表示为T[1]，T[2]，…，T[64]，或T[i]，其中i为1～64。由于有四轮，因此每一轮用64个T值中的16个。MD5算法描述在MD5算法中，明文字的顺序表（X[i]）有如下定义：即每次所取的X[i]顺序如下：MD5算法描述其中移位S的定义如下：MD5算法描述第一次循环：FF(a,b,c,d,M0,7,0xd76aa478)FF(d,a,b,c,M1,12,0xe8c7b756)FF(c,d,a,b,M2,17,0x242070db)FF(b,c,d,a,M3,22,0xc1bdceee)FF(a,b,c,d,M4,7,0xf57c0faf)FF(d,a,b,c,M5,12,0x4787c62a)FF(c,d,a,b,M6,17,0xa8304613)FF(b,c,d,a,M7,22,0xfd469501)FF(a,b,c,d,M8,7,0x698098d8)FF(d,a,b,c,M9,12,0x8b44f7af)FF(c,d,a,b,M10,17,0xffff5bb1)FF(b,c,d,a,M11,22,0x895cd7be)FF(a,b,c,d,M12,7,0x6b901122)FF(d,a,b,c,M13,12,0xfd987193)FF(c,d,a,b,M14,17,0xa679438e)FF(b,c,d,a,M15,22,0x49b40821)第二次循环：GG(a,b,c,d,M1,5,0xf61e2562)GG(d,a,b,c,M6,9,0xc040b340)GG(c,d,a,b,M11,14,0x265e5a51)GG(b,c,d,a,M0,20,0xe9b6c7aa)GG(a,b,c,d,M5,5,0xd62f105d)GG(d,a,b,c,M10,9,0x02441453)GG(c,d,a,b,M15,14,0xd8a1e681)GG(b,c,d,a,M4,20,0xe7d3fbc8)GG(a,b,c,d,M9,5,0x21e1cde6)GG(d,a,b,c,M14,9,0xc33707d6)GG(c,d,a,b,M3,14,0xf4d50d87)GG(b,c,d,a,M8,20,0x455a14ed)GG(a,b,c,d,M13,5,0xa9e3e905)GG(d,a,b,c,M2,9,0xfcefa3f8)GG(c,d,a,b,M7,14,0x676f02d9)GG(b,c,d,a,M12,20,0x8d2a4c8a)MD5算法描述第三次循环：HH(a,b,c,d,M5,4,0xfffa3942)HH(d,a,b,c,M8,11,0x8771f681)HH(c,d,a,b,M11,16,0x6d9d6122)HH(b,c,d,a,M14,23,0xfde5380c)HH(a,b,c,d,M1,4,0xa4beea44)HH(d,a,b,c,M4,11,0x4bdecfa9)HH(c,d,a,b,M7,16,0xf6bb4b60)HH(b,c,d,a,M10,23,0xbebfbc70)HH(a,b,c,d,M13,4,0x289b7ec6)HH(d,a,b,c,M0,11,0xeaa127fa)HH(c,d,a,b,M3,16,0xd4ef3085)HH(b,c,d,a,M6,23,0x04881d05)HH(a,b,c,d,M9,4,0xd9d4d039)HH(d,a,b,c,M12,11,0xe6db99e5)HH(c,d,a,b,M15,16,0x1fa27cf8)HH(b,c,d,a,M2,23,0xc4ac5665)第四次循环：II(a,b,c,d,M0,6,0xf4292244)II(d,a,b,c,M7,10,0x432aff97)II(c,d,a,b,M14,15,0xab9423a7)II(b,c,d,a,M5,21,0xfc93a039)II(a,b,c,d,M12,6,0x655b59c3)II(d,a,b,c,M3,10,0x8f0ccc92)II(c,d,a,b,M10,15,0xffeff47d)II(b,c,d,a,M1,21,0x85845dd1)II(a,b,c,d,M8,6,0x6fa87e4f)II(d,a,b,c,M15,10,0xfe2ce6e0)II(c,d,a,b,M6,15,0xa3014314)II(b,c,d,a,M13,21,0x4e0811a1)II(a,b,c,d,M4,6,0xf7537e82)II(d,a,b,c,M11,10,0xbd3af235)II(c,d,a,b,M2,15,0x2ad7d2bb)II(b,c,d,a,M9,21,0xeb86d391)MD5算法描述总结MD5的操作如下：其中：IV=缓存ABCD的初值，在步骤三定义Yq=第q个长度为512比特的报文分组L=报文（包括填充字段和长度字段）的分组数CVq=处理第q个报文分组时的连接变量RFx=使用原始逻辑函数x