MD5（Message Digest Algorithm 5，消息摘要算法第五版）是计算机安全领域广泛使用的一种散列函数，经MD2、MD3和MD4发展而来，可以用于保护信息传输的完整一致性。本文将介绍MD5算法的原理及C++实现，并简单介绍其应用场景。
注意，虽然MD5算法是不可逆的，但是目前其已经被破解了，不再是认为安全的，因为通过多次尝试并进行对比，可能可以得到一个MD5刚好是给定MD5值的串，通过特殊的方法可以加速这种尝试，从而在较快的时间内对其进行破解。
介绍
MD5的作用是让大容量信息在用数字签名软件签署私人密钥前被"压缩"成一种保密的格式，可以把一个任意长度的字节串变换成一定长的十六进制数字串。其特点是输入任意长度的信息，经过处理，输出为128位的信息（数字指纹），不同的输入得到的不同的结果（唯一性），并且根据128位的输出结果不可能反推出输入的信息（不可逆）。除了MD5以外，其中比较有名的还有SHA-1、RIPEMD以及Haval等。
来自 RFC 1321 的解释 – MD5 报文摘要算法：MD5 报文摘要算法将任意长度的信息作为输入值，并将其换算成一个 128 位长度的"指纹信息"或"报文摘要"值来代表这个输入值，并以换算后的值作为结果。MD5 算法主要是为数字签名应用程序而设计的；在这个数字签名应用程序中，较大的文件将在加密（这里的加密过程是通过在一个密码系统下[如：RSA]的公开密钥下设置私有密钥而完成的）之前以一种安全的方式进行压缩。
MD5用途非常广泛，典型应用是对一段信息（Message）产生信息摘要（Message-Digest），以防止被篡改。比如，在Unix下有很多软件在下载的时候都有一个文件名相同，文件扩展名为.md5的文件，在这个文件中通常只有一行文本，保存该下载文件的数字签名。MD5将整个文件当作一个大文本信息，通过其不可逆的字符串变换算法，产生了这个唯一的MD5信息摘要。MD5可以为任何文件（不管其大小、格式、数量）产生一个同样独一无二的“数字指纹”，如果任何人对文件做了任何改动，其MD5值也就是对应的“数字指纹”都会发生变化。某些软件下载站点的某软件信息中看到其MD5值，它的作用就在于我们可以在下载该软件后，对下载回来的文件用专门的软件做一次MD5校验，以确保我们获得的文件与该站点提供的文件为同一文件。
原理
MD5算法可以简要的叙述为：MD5以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由四个32位分组组成，将这四个32位分组级联后将生成一个128位散列值。
在MD5算法中，首先需要对信息进行填充，使其位长对512求余的结果等于448。因此，信息的位长将被扩展至N*512+448，N为一个非负整数，N可以是零。填充的方法如下，在信息的后面填充一个1和无数个0，直到满足上面的条件时才停止用0对信息的填充。然后，在这个结果后面附加一个以64位二进制表示的填充前信息长度。经过这两步的处理，信息的位长=N*512+448+64=(N+1）*512，即长度恰好是512的整数倍。这样做的原因是为满足后面处理中对信息长度的要求。
MD5中的任意第i个分组，每次运算都由前一轮的128位结果值和第i块512bit值进行运算。初始的128位值为初试链接变量，这些参数用于第一轮的运算，以大端字节序来表示，他们分别为：A=0×01234567，B=0x89ABCDEF，C=0xFEDCBA98，D=0×76543210。
每一分组的算法流程如下：第一分组需要将上面四个链接变量复制到另外四个变量中：A到a，B到b，C到c，D到d。从第二分组开始的变量为上一分组的运算结果。
主循环有四轮（MD4只有三轮），每轮循环都很相似。第一轮进行16次操作。每次操作对a、b、c和d中的其中三个作一次非线性函数运算，然后将所得结果加上第四个变量，文本的一个子分组和一个常数。再将所得结果向左环移一个不定的数，并加上a、b、c或d中之一。最后用该结果取代a、b、c或d中之一。
以下是每次操作中用到的四个非线性函数（每轮一个）。
- F(X,Y,Z) =(X&Y)|((~X)&Z)
- G(X,Y,Z) =(X&Z)|(Y&(~Z))
- H(X,Y,Z) =X^Y^Z
- I(X,Y,Z)=Y^(X|(~Z))
这四个函数的说明：如果X、Y和Z的对应位是独立和均匀的，那么结果的每一位也应是独立和均匀的。F是一个逐位运算的函数。即，如果X，那么Y，否则Z。函数H是逐位奇偶操作符。
假设Mj表示消息的第j个子分组（从0到15），常数ti是4294967296*abs(sin(i)）的整数部分，i取值从1到64，单位是弧度。（4294967296等于2的32次方）
- FF(a,b,c,d,Mj,s,ti）表示 a = b + ((a + F(b,c,d) + Mj + ti) << s)
- GG(a,b,c,d,Mj,s,ti）表示 a = b + ((a + G(b,c,d) + Mj + ti) << s)
- HH(a,b,c,d,Mj,s,ti）表示 a = b + ((a + H(b,c,d) + Mj + ti) << s)
- Ⅱ（a,b,c,d,Mj,s,ti）表示 a = b + ((a + I(b,c,d) + Mj + ti) << s)
然后进行四轮（64步）的操作变换，分别是以上四个函数的调用，具体参考代码。
所有这些完成之后，将A、B、C、D分别加上a、b、c、d。然后用下一分组数据继续运行算法，最后的输出是A、B、C和D的级联。
Read full article from MD5算法原理及实现 » NoAlGo博客
No comments:
Post a Comment