共计 5989 个字符，预计需要花费 15 分钟才能阅读完成。
前言
最近在看一些 NPM 库的时候总是看到各种哈希签名算法，之前工作中也有用到过签名算法，但并没有深入理解过其中的原理，于是找了点资料稍微了解了一下，总结了这篇文章。
哈希摘要算法
哈希函数（也称散列函数），是一种根据任意长度数据计算出固定签名长度的算法，比如 MD5，SHA 系列。
哈希签名摘要算法特点
不是加密算法，而是一种摘要算法
不可逆，“单向”函数
签名长度固定
存在 2 的 N 次方种结果，N 表示签名长度
以 MD5 为例
MD5 是由美国密码学家罗纳德·李维斯特（Ronald Linn Rivest）设计一种加密算法。
128 个 bits 长度，也就是 16 个字节
输出结果由为“0-F”字符组成，不区分大小写
存在 2 的 128 次方种输出结果
MD5 算法
一、源数据处理
计算原文长度 (bits) 对 512 求余的结果，需要填充原文使得原文对 512 求余的结果等于 448, 填充的方法是第一位填充 1，其余位填充 0。填充完后，信息的长度为 512 * N + 448。
剩余 64bits 存储空间用来填充源信息长度，填充在 448byte 数据之后。
最终经过处理后的数据长度为 512 * N。
动手画了一张简单的图来说明：
二、处理数据
1、数据进行处理前，会定义 4 个常量，作为初始值这 4 个常量分别是
var a = 0x67452301;
var b = 0xEFCDAB89;
var c = 0x98BADCFE;
var d = 0x10325476;
翻译成二进制就是
var a = 1732584193;
var b = -271733879;
var c = -1732584194;
var d = 271733878;
2、将处理后的数据，外循环处理 N 次，N 为第一步中 512 的整数倍。每次外循环处理的会产生新的“a、b、c、d”值，每次新产生的“a、b、c、d”值会再一次提供给下一次外循环使用
3、在每个外循环中又进行内循环处理 64 次，在这 64 次数据处理中会不停的将 512 bytes 数据中的 16 个小单元不停的通过 4 个函数进行交叉处理，共计进行 64 轮计算。
4、最终生成新的“a、b、c、d”，新的“a、b、c、d”分别是占用 32bytes 的数据
5、最终生成的“a、b、c、d”转换为对应的 ascll 占用的字节，32 bytes * 4 = 128 bytes，一个字节占用 8 个 bytes，也就是 16 个字节,16 个字节转换为 ASCII 码，再将 ASCII 码转换为 16 进制数据，即可得到一个 32 个字节长度的 hash 值。
内外循环代码
function binl_md5(x, len) {
/* append padding */
x[len >> 5] = x[len >> 5] | 0x80 << (len % 32);
x[(((len + 64) >>> 9) << 4) + 14] = len;
var i, olda, oldb, oldc, oldd,
a = 1732584193,
b = -271733879,
c = -1732584194,
d = 271733878;
// 每次计算位移值，可以理解为是常量
var ffShift = [7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22];
var ggShift = [5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20];
var hhShift = [4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23];
var iiShift = [6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21];
// Todo: 四个字节一组，每个组别之间不停的交叉计算，不停的根据已计算出来的值多次计算赋值
// x[i]装的是 4 个字节的数据
// x.length 为 512 * N / 32
// i += 16 每 512bits 长度的数据分为了 16 组，而每次循环的计算单位是以 512 为一个单元的，所以每次都是 +16
for (i = 0; i < x.length; i += 16) {
olda = a;
oldb = b;
oldc = c;
oldd = d;
// 64 轮计算中包含原始“a、b、c、d”值。
// 以及位移值，以及一个计算常量，这两个是 MD5 规范中所定义的常量
a = md5_ff(a, b, c, d, x[i], ffShift[0], -680876936);
d = md5_ff(d, a, b, c, x[i + 1], ffShift[1], -389564586);
c = md5_ff(c, d, a, b, x[i + 2], ffShift[2], 606105819);
b = md5_ff(b, c, d, a, x[i + 3], ffShift[3], -1044525330);
a = md5_ff(a, b, c, d, x[i + 4], ffShift[4], -176418897);
d = md5_ff(d, a, b, c, x[i + 5], ffShift[5], 1200080426);
c = md5_ff(c, d, a, b, x[i + 6], ffShift[6], -1473231341);
b = md5_ff(b, c, d, a, x[i + 7], ffShift[7], -45705983);
a = md5_ff(a, b, c, d, x[i + 8], ffShift[8], 1770035416);
d = md5_ff(d, a, b, c, x[i + 9], ffShift[9], -1958414417);
c = md5_ff(c, d, a, b, x[i + 10], ffShift[10], -42063);
b = md5_ff(b, c, d, a, x[i + 11], ffShift[11], -1990404162);
a = md5_ff(a, b, c, d, x[i + 12], ffShift[12], 1804603682);
d = md5_ff(d, a, b, c, x[i + 13], ffShift[13], -40341101);
c = md5_ff(c, d, a, b, x[i + 14], ffShift[14], -1502002290);
b = md5_ff(b, c, d, a, x[i + 15], ffShift[15], 1236535329);
a = md5_gg(a, b, c, d, x[i + 1], ggShift[0], -165796510);
d = md5_gg(d, a, b, c, x[i + 6], ggShift[1], -1069501632);
c = md5_gg(c, d, a, b, x[i + 11], ggShift[2], 643717713);
b = md5_gg(b, c, d, a, x[i], ggShift[3], -373897302);
a = md5_gg(a, b, c, d, x[i + 5], ggShift[4], -701558691);
d = md5_gg(d, a, b, c, x[i + 10], ggShift[5], 38016083);
c = md5_gg(c, d, a, b, x[i + 15], ggShift[6], -660478335);
b = md5_gg(b, c, d, a, x[i + 4], ggShift[7], -405537848);
a = md5_gg(a, b, c, d, x[i + 9], ggShift[8], 568446438);
d = md5_gg(d, a, b, c, x[i + 14], ggShift[9], -1019803690);
c = md5_gg(c, d, a, b, x[i + 3], ggShift[10], -187363961);
b = md5_gg(b, c, d, a, x[i + 8], ggShift[11], 1163531501);
a = md5_gg(a, b, c, d, x[i + 13], ggShift[12], -1444681467);
d = md5_gg(d, a, b, c, x[i + 2], ggShift[13], -51403784);
c = md5_gg(c, d, a, b, x[i + 7], ggShift[14], 1735328473);
b = md5_gg(b, c, d, a, x[i + 12], ggShift[15], -1926607734);
a = md5_hh(a, b, c, d, x[i + 5], hhShift[0], -378558);
d = md5_hh(d, a, b, c, x[i + 8], hhShift[1], -2022574463);
c = md5_hh(c, d, a, b, x[i + 11], hhShift[2], 1839030562);
b = md5_hh(b, c, d, a, x[i + 14], hhShift[3], -35309556);
a = md5_hh(a, b, c, d, x[i + 1], hhShift[4], -1530992060);
d = md5_hh(d, a, b, c, x[i + 4], hhShift[5], 1272893353);
c = md5_hh(c, d, a, b, x[i + 7], hhShift[6], -155497632);
b = md5_hh(b, c, d, a, x[i + 10], hhShift[7], -1094730640);
a = md5_hh(a, b, c, d, x[i + 13], hhShift[8], 681279174);
d = md5_hh(d, a, b, c, x[i], hhShift[9], -358537222);
c = md5_hh(c, d, a, b, x[i + 3], hhShift[10], -722521979);
b = md5_hh(b, c, d, a, x[i + 6], hhShift[11], 76029189);
a = md5_hh(a, b, c, d, x[i + 9], hhShift[12], -640364487);
d = md5_hh(d, a, b, c, x[i + 12], hhShift[13], -421815835);
c = md5_hh(c, d, a, b, x[i + 15], hhShift[14], 530742520);
b = md5_hh(b, c, d, a, x[i + 2], hhShift[15], -995338651);
a = md5_ii(a, b, c, d, x[i], iiShift[0], -198630844);
d = md5_ii(d, a, b, c, x[i + 7], iiShift[1], 1126891415);
c = md5_ii(c, d, a, b, x[i + 14], iiShift[2], -1416354905);
b = md5_ii(b, c, d, a, x[i + 5], iiShift[3], -57434055);
a = md5_ii(a, b, c, d, x[i + 12], iiShift[4], 1700485571);
d = md5_ii(d, a, b, c, x[i + 3], iiShift[5], -1894986606);
c = md5_ii(c, d, a, b, x[i + 10], iiShift[6], -1051523);
b = md5_ii(b, c, d, a, x[i + 1], iiShift[7], -2054922799);
a = md5_ii(a, b, c, d, x[i + 8], iiShift[8], 1873313359);
d = md5_ii(d, a, b, c, x[i + 15], iiShift[9], -30611744);
c = md5_ii(c, d, a, b, x[i + 6], iiShift[10], -1560198380);
b = md5_ii(b, c, d, a, x[i + 13], iiShift[11], 1309151649);
a = md5_ii(a, b, c, d, x[i + 4], iiShift[12], -145523070);
d = md5_ii(d, a, b, c, x[i + 11], iiShift[13], -1120210379);
c = md5_ii(c, d, a, b, x[i + 2], iiShift[14], 718787259);
b = md5_ii(b, c, d, a, x[i + 9], iiShift[15], -343485551);
a = safe_add(a, olda);
b = safe_add(b, oldb);
c = safe_add(c, oldc);
d = safe_add(d, oldd);
}
// 最终生成 4 个占用 32 bytes 控制的值
return [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))
6、第五点可以解释为什么生成的 hash 值中只会包含“0-F”，且不区分大小写的原因，长度为 16。
function rstr2hex(input) {
var hex_tab = ‘0123456789abcdef’,
output = ”,
x,
i;
for (i = 0; i < input.length; i += 1) {
x = input.charCodeAt(i);
output += hex_tab.charAt((x >>> 4) & 0x0F) +
hex_tab.charAt(x & 0x0F); x:${input.charCodeAt(i)}, output: ${output}`);
}
return output;
}
以上代码来自 https://github.com/blueimp/JavaScript-MD5，稍有改动。
适用场景：
私密数据加密，比如用户密码一般都不会明文存储，而是通过加密后存入数据库
赌场开盘前将开票结果公布，开盘后通过签名对比校验是否存在作弊行为
检测文件是否下载完成，比如迅雷下载
…
如何破解
MD5 中，虽然由源文可以推导出签名，反过来，并不能由签名推导出源文。但 MD5 并不是坚不可摧，目前有两种破解方式
碰撞法，虽然 MD5 签名存在 2 的 128 次方种输出结果，但每个签名对应的原文并不是唯一的，只要计算机性能够强大，给予充足的时间，总能找到能输出相同签名的数据源。
映射法，把常规字符串对应的签名存储，比如常用的“123456”，“abcdefg”等。当得到 MD5 签名时，就可以映射出源数据。
如何防范：
使用安全性更高的 SHA256，并不是说 SHA256 不能被破解，只是相对于 MD5 来说算法步骤更多，也更复杂，破解难度更大。
源数据 + KEY，比如“123456”加上 KEY 就变成了“123456@#DFF23DS”, 其中“@#DFF23DS”就是服务端存储的 KEY。“源数据 + KEY”=> 签名。
源数据 + KEY + 动态数据，KEY 有可能会被猜到，如果再加上动态数据的话，破解难度会进一步提升，比如用户名、动态密码。“源数据 + KEY + 动态密码”=> 签名。
多次 MD5，MD5(“123456”)很容易被猜到，MD5(MD5(“123456”)), 将 MD5 后的签名再进行一次 MD5 呢，如果进行三次，十次，是不是破解的难度会更大，当然这么做会增加计算时间，需要权衡。
其他：
中文编码需要转码，否则前端与后端编码后的值可能不一致。
除了 MD5 算法，还存在很多其他形式的哈希函数算法，比如 SHA 系列，他们的设计思路大体相同。
参考资料
阮一峰讲解操作符按位移动操作符各种进制在线转换维基百科 MD5 维基百科 SHA2NPM MD5
