MD5算法笔记

MD5（Message-Digest Algorithm 5，消息摘要算法第五版），是广泛使用的哈希算法之一，主流编程语言普遍已有MD5的实现。第一次接触是在写项目的时候，直接用PHP中的现有函数来加密一些信息。Web安全选修课中的一个作业是要实现这个算法，这里记录一下学习的笔记。
MD5的输入是一条不定长度的信息，输出一条固定长度128位的信息，也即生成四个32位数据。基本方式为，求余、取余、调整长度、与链接变量进行循环运算。
例如英语中的经典句子“The quick brown fox jumps over the lazy dog”，经过加密后，
MD5("The quick brown fox jumps over the lazy dog") = 9e107d9d372bb6826bd81d3542a419d6

算法过程
预处理，假设我们要加密的信息长度为B 字节，即一共为b = 8B位。
根据MD5的填充原则，我们需要补上1个1和n个0，令总位数除512的时候余448。
可以推出，经过第一步填补后的位数仍为8的位数，因此补上一个1后必定至少补七个0，相当于补上0x80.
然后我们一直在后面补上0x00，直到总位数除512时余448。
之所以要让余数刚好为448，是因为我们需要在后面补上用64位表示的原信息长度，448+64 = 512，恰好能让信息位数为512的倍数。
原信息长度为8B bit，我们将8B这个数字用2进制64位表示出来，然后通过小段规则（低字节在前）补到信息的末尾。
这样一来，我们有了一组增补后长度为512N的信息。
增补后的信息可以分为N个512位（64字节）的块，可以分为16个4字节大小的组，每组32位。
我们定义4个幻数，0x67452301，0xefcdab89，0x98badcfe，0x10325476，分别为A，B，C，D
以及4个非线性位操作函数

对每一块进行操作，接下来的64次循环，每16次都会用到其中一个函数。
对于每一个64字节的块，我们都算出其非线性函数的值，然后与A，该轮对应分组，以及一个数组K的对应值相加，然后进行一定的逻辑循环移位。
K数组大小为64，产生过程K数组的过程是：遍历这个数组，求出当前下标的sin绝对值与2的32次幂的乘积，再取整。
每次循环后，我们将A，B，C，D的值循环交换，即A的值赋给D，B的值赋给A，如此循环左推。对于每个64字节块都进行一次这样的操作，完成后A，B，C，D的值即我们加密后的信息，注意的是我们需要小端格式的输出。

源代码
Github链接

算法应用
接触种子下载的用户会注意到，BT软件会通过计算MD5检验下载到的文件片段的完整性。MD5作为一个哈希算法不可能没有碰撞。2009年，谢涛和冯登国破解了MD5的碰撞抵抗，该攻击在普通计算机上运行只需要数秒钟。因为这一碰撞风险，用户的密码加密算法不应采取MD5。改进MD5的方式可以是，在加密前，字符串加上一组随机字符串，只有双方才掌握这一随机串，这种方法可以防止通过碰撞来获得加密的内容。网上我们能搜到的MD5解密算法，原理便是通过对大量已有的字符串进行加密获得加密后的串，当用户需要解密的时候，才在其中寻找其原串。