欢迎访问 生活随笔！
TAG聚合

生活随笔

当前位置： 首页 > 编程资源 > 编程问答 >内容正文

编程问答

MD5算法实现原理

发布时间：2025/6/17 编程问答 35 豆豆
生活随笔 收集整理的这篇文章主要介绍了 MD5算法实现原理 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

目录

  • 1 MD5 简介
  • 2 MD5 实现步骤
    • 2.1 将明文变为 ASCII 码
    • 2.2 填充和附加
    • 2.3 分组
    • 2.4 预处理
    • 2.5 循环加工
  • 3 blueimp-md5 源码
  • 4 遗留的问题
    • 4.1 四个非线性函数是如何设计的
    • 4.2 循环左移偏移量是如何设计的
    • 4.3 正弦补充值是如何设计的
  • 5 总结

1 MD5 简介

信息摘要算法 MD5 (Message Digest 5)，数字 5 代表这是第五代算法，之前还有 MD1、MD2、MD3 和 MD4。MD5 是一种被广泛使用的密码散列函数，可以产生出一个 128128128 位（161616 字节）的散列值（hash value），用于确保信息传输完整一致。

MD5 算法的特征是不可逆性，并且在计算的时候所有的数据都参与了运算，其中任何一个数据变化了都会导致计算出来的 Hash 值完全不同，所以通常用来校验数据是否正确或用作身份验证。

2 MD5 实现步骤

2.1 将明文变为 ASCII 码

要加密的明文：China,my great country。
ASCII码：43 68 69 6E 61 2C 6D 79 20 67 72 65 61 74 20 63 6F 75 6E 74 72 79

2.2 填充和附加

对数据进行填充的目的是使任意长度的数据能够被 512512512 整除，填充的首位是 111，其余位全部为 000，填充后数据变成 (N∗512−64)(N*512-64)(N∗512−64) 位（下图中假设 N = 1，则填充后要达到 448448448 位）。

减去 646464 是因为要在数据末尾附加长度项，如果数据的长度大于 646464 位，则只取低 646464 位。通过填充和附加后，整个数据变为 512512512 的整数倍。

下面对数据进行填充和附加操作，数据为4368696E612C6D7920677265617420636F756E747279，这段数据长度为 176176176 位（注意上述数据是用 161616 进制表示的），由于 176<448176 < 448176<448，所以需要进行填充，共需填充 448−176=272448-176=272448−176=272 位，用 161616 进制表示为 80000....0000（272272272位），再加上数据长度项 176176176 的 161616 进制为 00B0，但是要凑成 646464 位，所以最后附加 B000000000000000。

填充和附加后的数据为：4368696E612C6D7920677265617420636F756E747279 80000....0000（272272272位）B000000000000000。总长度刚好为 512512512 位。

2.3 分组

将数据按每组 512512512 位进行分组，每组内再分成 161616 组，每组 323232 位。

上述数据按要求分组后如下表，并把每组数据保存在数组 x 中，表中的 # 代表在数组中的下标：

#数据
06E696843
1796D2C61
265726720
363207461
4746E756F
……
1100000000
1200000000
1300000000
14000000B0
1500000000

2.4 预处理

首先要确定 444 个链接变量 A、B、C、D，每个变量 323232 位。

链接变量存储形式值
A0x67452301
B0xEFCDAB89
C0x98BADCFE
D0x10325476

这四个变量看似毫无章法，其实是有规律的，由于 Windows 是基于 Little Endian 的，即低位字节排放在内存的低地址端，高位字节排放在内存的高地址端，所以我们在定义这四个变量的值的时候要按它们在内存中的存储形式进行定义，实际上这四个变量的逻辑形式是：

链接变量逻辑形式值
A0x01234567
B0x89ABCDEF
C0xFEDCBA98
D0x76543210

仔细观察后，规律就很明显了。

2.5 循环加工

当第一轮的第一步开始处理时，将这 444 个变量先分别赋值到另外 444 个变量 oldA、oldB、oldC、oldD 中，以第一轮第一步为例，对应第一轮第一步的操作函数为 md5ff(a, b, c, d, x[0], 7, 0xD76AA478)（7 用于循环左移，0xD76AA478 为正弦补充值），首先将 b、c、d 经过非线性函数 (b&c) | (not(b)&d) 计算得到98BADCFE后，再将这个值加上 A、x[0] 和 0xD76AA478，即 67452301 + 98BADCFE + 6E696843 + D76AA478 = 45D40CBA。

再将相加结果 45D40CBA 循环左移七位得 EA065D22，再加上链接变量 B 的值，即 EA065D22 + EFCDAB89 = D9D408AB，最后把这个值赋值给链接变量 A。

依次类推，经过 444 轮操作，共 646464 个步骤后， 444 个链接变量变为：

链接变量存储形式值
A0xD32A3F0D
B0x0E63C780
C0x469E5215
D0x65C53CCA

接下来要将原 A、B、C、D 的值和上表中处理后的A、B、C、D 值相加求和，将和分别赋值给A、B、C、D，这个时候就用到了之前的 oldA、oldB、oldC、oldD ，具体操作以 A 为例，将 A 与 oldA 相加，即 D32A3F0D + 67452301 = 3A6F620E，再将和赋值给 A。全部求和后结果如下表：

链接变量存储形式值
A0x3A6F620E
B0xFE317309
C0xDF592F13
D0x75F79140

最后算得的散列值为：0E626F3A097331FE132F59DF4091F775。

3 blueimp-md5 源码

blueimp-md5 是由 blueimp 实现的 JavaScript MD5 算法。阅读源码后发现他们用了很多位运算来实现整个过程，有的地方生涩难懂。源码中一共提供了 444 种 API：

  • 给定一个字符串，计算得出它的 MD5 哈希值，如：var hash = md5('value')；
  • 给定一个字符串，计算得出它的 HMAC-MD5 哈希值，如：var hash = md5("value", "key")；
  • 给定一个字符串，计算其原始 MD5 哈希值，如：var hash = md5('value', null, true)；
  • 给定一个字符串和一个键值，计算其原始 HMAC-MD5 哈希值，如：var hash = md5("value", "key", true)

    • 最常用的还是第一个，下面列出 blueimp-md5 源码实现过程，只截取了关键部分。

    将字符串编码为 UTF-8。

    /** Encode a string as utf-8*/function str2rstrUTF8 (input) {return unescape(encodeURIComponent(input))}

    将原始字符串转换为 161616 进制。

    /** Convert a raw string to a hex string*/function rstr2hex (input) {var hexTab = '0123456789abcdef'var output = ''var xvar ifor (i = 0; i < input.length; i += 1) {x = input.charCodeAt(i)output += hexTab.charAt((x >>> 4) & 0x0f) + hexTab.charAt(x & 0x0f)}return output}

    四个非线性函数。

    /** These functions implement the four basic operations the algorithm uses.*/function md5cmn (q, a, b, x, s, t) {return safeAdd(bitRotateLeft(safeAdd(safeAdd(a, q), safeAdd(x, t)), s), b)}function md5ff (a, b, c, d, x, s, t) {return md5cmn((b & c) | (~b & d), a, b, x, s, t)}function md5gg (a, b, c, d, x, s, t) {return md5cmn((b & d) | (c & ~d), a, b, x, s, t)}function md5hh (a, b, c, d, x, s, t) {return md5cmn(b ^ c ^ d, a, b, x, s, t)}function md5ii (a, b, c, d, x, s, t) {return md5cmn(c ^ (b | ~d), a, b, x, s, t)}

    循环左移。

    /** Bitwise rotate a 32-bit number to the left.*/function bitRotateLeft (num, cnt) {return (num << cnt) | (num >>> (32 - cnt))}

    求和，生成新的链接变量。

    /** Add integers, wrapping at 2^32. This uses 16-bit operations internally* to work around bugs in some JS interpreters.*/function safeAdd (x, y) {var lsw = (x & 0xffff) + (y & 0xffff)var msw = (x >> 16) + (y >> 16) + (lsw >> 16)return (msw << 16) | (lsw & 0xffff)}

    计算 MD5 哈希值，注意该函数中的 a、b、c、d 和 非线性函数中的数（正弦补充值）都是以十进制表示的。

    /** Calculate the MD5 of an array of little-endian words, and a bit length.*/function binlMD5 (x, len) {/* append padding */x[len >> 5] |= 0x80 << (len % 32)x[((len + 64) >>> 9 << 4) + 14] = lenvar ivar oldavar oldbvar oldcvar olddvar a = 1732584193var b = -271733879var c = -1732584194var d = 271733878for (i = 0; i < x.length; i += 16) {olda = aoldb = boldc = coldd = da = md5ff(a, b, c, d, x[i], 7, -680876936)d = md5ff(d, a, b, c, x[i + 1], 12, -389564586)c = md5ff(c, d, a, b, x[i + 2], 17, 606105819)b = md5ff(b, c, d, a, x[i + 3], 22, -1044525330)a = md5ff(a, b, c, d, x[i + 4], 7, -176418897)d = md5ff(d, a, b, c, x[i + 5], 12, 1200080426)c = md5ff(c, d, a, b, x[i + 6], 17, -1473231341)b = md5ff(b, c, d, a, x[i + 7], 22, -45705983)a = md5ff(a, b, c, d, x[i + 8], 7, 1770035416)d = md5ff(d, a, b, c, x[i + 9], 12, -1958414417)c = md5ff(c, d, a, b, x[i + 10], 17, -42063)b = md5ff(b, c, d, a, x[i + 11], 22, -1990404162)a = md5ff(a, b, c, d, x[i + 12], 7, 1804603682)d = md5ff(d, a, b, c, x[i + 13], 12, -40341101)c = md5ff(c, d, a, b, x[i + 14], 17, -1502002290)b = md5ff(b, c, d, a, x[i + 15], 22, 1236535329)a = md5gg(a, b, c, d, x[i + 1], 5, -165796510)d = md5gg(d, a, b, c, x[i + 6], 9, -1069501632)c = md5gg(c, d, a, b, x[i + 11], 14, 643717713)b = md5gg(b, c, d, a, x[i], 20, -373897302)a = md5gg(a, b, c, d, x[i + 5], 5, -701558691)d = md5gg(d, a, b, c, x[i + 10], 9, 38016083)c = md5gg(c, d, a, b, x[i + 15], 14, -660478335)b = md5gg(b, c, d, a, x[i + 4], 20, -405537848)a = md5gg(a, b, c, d, x[i + 9], 5, 568446438)d = md5gg(d, a, b, c, x[i + 14], 9, -1019803690)c = md5gg(c, d, a, b, x[i + 3], 14, -187363961)b = md5gg(b, c, d, a, x[i + 8], 20, 1163531501)a = md5gg(a, b, c, d, x[i + 13], 5, -1444681467)d = md5gg(d, a, b, c, x[i + 2], 9, -51403784)c = md5gg(c, d, a, b, x[i + 7], 14, 1735328473)b = md5gg(b, c, d, a, x[i + 12], 20, -1926607734)a = md5hh(a, b, c, d, x[i + 5], 4, -378558)d = md5hh(d, a, b, c, x[i + 8], 11, -2022574463)c = md5hh(c, d, a, b, x[i + 11], 16, 1839030562)b = md5hh(b, c, d, a, x[i + 14], 23, -35309556)a = md5hh(a, b, c, d, x[i + 1], 4, -1530992060)d = md5hh(d, a, b, c, x[i + 4], 11, 1272893353)c = md5hh(c, d, a, b, x[i + 7], 16, -155497632)b = md5hh(b, c, d, a, x[i + 10], 23, -1094730640)a = md5hh(a, b, c, d, x[i + 13], 4, 681279174)d = md5hh(d, a, b, c, x[i], 11, -358537222)c = md5hh(c, d, a, b, x[i + 3], 16, -722521979)b = md5hh(b, c, d, a, x[i + 6], 23, 76029189)a = md5hh(a, b, c, d, x[i + 9], 4, -640364487)d = md5hh(d, a, b, c, x[i + 12], 11, -421815835)c = md5hh(c, d, a, b, x[i + 15], 16, 530742520)b = md5hh(b, c, d, a, x[i + 2], 23, -995338651)a = md5ii(a, b, c, d, x[i], 6, -198630844)d = md5ii(d, a, b, c, x[i + 7], 10, 1126891415)c = md5ii(c, d, a, b, x[i + 14], 15, -1416354905)b = md5ii(b, c, d, a, x[i + 5], 21, -57434055)a = md5ii(a, b, c, d, x[i + 12], 6, 1700485571)d = md5ii(d, a, b, c, x[i + 3], 10, -1894986606)c = md5ii(c, d, a, b, x[i + 10], 15, -1051523)b = md5ii(b, c, d, a, x[i + 1], 21, -2054922799)a = md5ii(a, b, c, d, x[i + 8], 6, 1873313359)d = md5ii(d, a, b, c, x[i + 15], 10, -30611744)c = md5ii(c, d, a, b, x[i + 6], 15, -1560198380)b = md5ii(b, c, d, a, x[i + 13], 21, 1309151649)a = md5ii(a, b, c, d, x[i + 4], 6, -145523070)d = md5ii(d, a, b, c, x[i + 11], 10, -1120210379)c = md5ii(c, d, a, b, x[i + 2], 15, 718787259)b = md5ii(b, c, d, a, x[i + 9], 21, -343485551)a = safeAdd(a, olda)b = safeAdd(b, oldb)c = safeAdd(c, oldc)d = safeAdd(d, oldd)}return [a, b, c, d]}

    4 遗留的问题

    4.1 四个非线性函数是如何设计的

    在循环加工中，(b&c) | (not(b)&d) = 98BADCFE，即为一次非线性函数计算。

    #非线性函数
    1F(X,Y,Z) = (X & Y) | ((~X) & Z);
    2G(X,Y,Z) = (X & Z) | (Y & (~Z));
    3H(X,Y,Z) = X ^ Y ^ Z;
    4I(X,Y,Z) = Y ^ (X | (~Z));

    这四个非线性函数分别被封装到四个操作函数中，即循环加工中的 md5ff 函数就为操作函数之一，还有 md5gg、md5hh 和 md5ii。

    4.2 循环左移偏移量是如何设计的

    四个操作函数中，都附带了参数作为循环左移偏移量，阅读代码后，发现循环左移偏移量分为如下四组：

    #左循环偏移量
    17, 12, 17, 22
    25, 9, 14, 20
    34, 11, 16, 23
    46, 10, 15, 21

    4.3 正弦补充值是如何设计的

    四个操作函数中，最后一个参数为正弦补充值，下面是十进制表示：

    a = md5ff(a, b, c, d, x[i], 7, -680876936)d = md5ff(d, a, b, c, x[i + 1], 12, -389564586)...

    转换为十六进制表示为：

    a = md5ff(a, b, c, d, x[i], 7, 0xD76AA478)d = md5ff(d, a, b, c, x[i + 1], 12, 0xE8C7B756)...

    5 总结

    目前只对 MD5 算法有个初步的了解，而上面遗留的问题正是 MD5 算法的核心实现部分，不禁让人感叹算法设计者的脑洞。

    从个人目前的认知来看，算法设计的数据和计算函数，目的只有一个，就是想方设法的打乱数据并直接让每一位都参与进来，这也就是为什么任何一位的变化，都会影响最后的哈希值，如明文：Hello syzdev的哈希值为：704558b48d6370fb71533d5ae50727b4，在改动其中一个字母后明文变为 Hallo syzdev ，其产生的哈希值为：2433084e178a2331d40c2ea16fd664fa，这两个哈希值看起来找不出有任何关联，即使两者的明文仅有一个字母差别。

    MD5 将整个数据拆分成多个组，再由每个组内分别计算累加，有些资料将分组过程分为 333 步，即先将整个数据按 512512512 位分块，再把每个 512512512 位分成 444 个 128128128 位数据块，最后将 444 个 128128128 位的数据块依次送到不同的散列函数进行 444 轮计算。每一轮又都按 323232 位的小数据块进行复杂的运算，一直到最后计算出 MD5 报文摘要代码，这也就是为什么 MD5 能把不定长的数据最后都变成 128128128 位的哈希值。

    可以发现，MD5 的处理函数，包括非线性函数和操作函数都包含了多个参数，而且还是变动的参数，这也就保证了 MD5 是个不可逆的算法。举个简单的例子，如有函数 z=f(x)=5∗xz=f(x)=5*xz=f(x)=5∗x，此时知道 z=10z=10z=10，那么显然得到 x=2x=2x=2；如函数为 z=f(x,y)=x∗yz=f(x, y)=x*yz=f(x,y)=x∗y，此时知道 z=10z=10z=10，这种情况下是无法推断出 xxx 和 yyy 的值的，这样也就保证了 MD5 算法具有不可逆性。

    正是因为 MD5 算法具有不可逆性，所以目前存在的破解算法都不是恢复明文，而是只要能找到能生成此摘要的其中一个原文即可，这种破解方法叫做“碰撞”。如 H(A)=MH(A) = MH(A)=M，H(B)=MH(B) = MH(B)=M，则称 BBB 为破解结果，此时 AAA 和 BBB 可能相等，也可能不等。

    总结

    以上是生活随笔为你收集整理的MD5算法实现原理的全部内容，希望文章能够帮你解决所遇到的问题。

    如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。