Python 中的 MD5 实现

Question

我正在关注 Wikipedia 上关于 MD5 实施的页面。伪代码直接嵌入在link.

然而，当我将伪代码翻译成 python 时，它给出了一个非常奇怪的输出，与演示中显示的完全不同。

md5.py

import math


def leftrotate(x, c):
    return (x << c) or (x >> (32 - c))


# All variables are unsigned 32 bit and wrap modulo 2^32 when calculating
s = [None] * 64
K = [None] * 64

# s specifies the per-round shift amounts
s[0:16] = [7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22]
s[16:32] = [5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20]
s[32:48] = [4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23]
s[48:64] = [6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21]

# Use binary integer part of the sines of integers (Radians) as constants:
K = [math.floor(math.pow(2, 32) * math.fabs(math.sin(i + 1))) for i in range(64)]

# Initialize variables
a0 = 0x67452301
b0 = 0xefcdab89
c0 = 0x98badcfe
d0 = 0x10325476

msg0 = "The quick brown fox jumps over the lazy dog"
# Converting String to binary
msg = ''.join(format(ord(i), 'b') for i in msg0)

# Pre-processing: adding a single bit
#   The input bytes are considered as bits strings,
#   where the first bit is the most significant bit of the byte
message = list(msg)
message.append("1")

# Pre-processing: padding with zeros
for i in range(447 - len(msg)):
    message.append("0")
for i in range(64):
    message.append("64")

msg = "".join(message)

M = []
for i in range(0, 512, 32):
    M.append("".join(message[i:i + 32]))
# Initialize hash value for this chunk
A = a0
B = b0
C = c0
D = d0

for i in range(64):
    F = 0
    g = 0
    if 0 <= i <= 15:
        F = D ^ (B and (C ^ D))
        g = i
    elif 16 <= i <= 31:
        F = C ^ (D and (B ^ C))
        g = (5 * i + 1) % 16
    elif 32 <= i <= 47:
        F = B ^ C ^ D
        g = (3 * i + 5) % 16
    elif 48 <= i <= 63:
        F = C ^ (B or (not D))
        g = (7 * i) % 16
    # Be wary of the below definitions of a, b, c, d
    F = F + A + K[i] + int(M[g])
    A = D
    D = C
    C = B
    B = B + leftrotate(F, s[i])

a0 += A
b0 += B
c0 += C
d0 += D

print(a0 + b0 + c0 + d0)

输出

(input = msg0 = "The quick brown fox jumps over the lazy dog")
64753135551430969455044517516606091785810184138594829859667366632969211689605539951611300227364936455768076694404884226395355419
03996976374438250472707827439981815374596773986313857734975864212023704601385676211761628136173288119161166663698645808505752643
4

详细一点，有人可以给我解释一下这一行：

break chunk into sixteen 32-bit words M[j], 0 ≤ j ≤ 15

此时我很困惑，认为 message 应该作为字符串输入，但将其转换为二进制不起作用。我认为，在页面上，短语 bit 表示 binary 还是我错了？

感谢任何帮助。

Answer 1

第一个明显错误：

K = [math.floor(math.pow(2, 32) * math.fabs(math.sin(i + 1))) for i in range(63)]

伪代码使用了包含边界符号； range 在上限上是独占的，所以你刚刚创建了一个 63 个元素长的 K，而它应该是 64 个元素长。

你的最后一个循环有同样的问题：

for i in range(63):

可能应该检查你的其他边界以确保你没有在其他地方犯过类似的错误。

这也是大错特错：

msg = ''.join(format(ord(i), 'b') for i in msg0)

因为它没有按照应有的方式填充输入字节，所以你的位都是一团糟。有很多方法可以做到这一点（假设所有字符的序数值都低于 256，你可以使用 '08b' 的格式字符串，尽管这是一个相当低效的解决方案）。

也错了：

for i in range(64):
    message.append("64")

你应该附加原始长度 mod 2**64，而不是 number 64 重复 64 次（我不知道在哪里你想到的）。

最后一个问题，解释一下"break chunk into sixteen 32-bit words M[j], 0 ≤ j ≤ 15"，“32位字”是指"integers comprised of 32 binary bits"。举一个简单的例子，将 0b100100001111 分成三个四位字会产生 0b1001, 0b0000, 0b1111.

不幸的是，在 Python 中，int 是无限精度；当计算产生超过 32 位的结果时，它们不会丢弃溢出的位，而 MD5 计算假设它们会这样做。因此，您将需要通过 & 0xffffffff.

按位和运算来使用大量掩码来模拟它

简而言之，从伪代码 Python 中简单地实现 MD5 是一件非常痛苦的事情，因为伪代码 依赖于 像 C 这样的低级语言。而且你显然没有足够小心地实现即使是自然转换为 Python.

的位

Python 中的 MD5 实现

Implementation of MD5 in Python

python

md5

bit

python-3.x