Реализация MD5 в Python

Question

Я следил за страницей в Википедии о реализации MD5. Псевдокод напрямую встроен в ссылку.

Однако, когда я переводил псевдокод в 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

Подробно, может кто-нибудь, пожалуйста, объясните мне эту строку:

разбить кусок на шестнадцать 32-битных слов M[j], 0 ≤ j ≤ 15

Я был довольно смущен в этот момент, полагая, что message должно быть вводится как строка, но преобразование в двоичный файл не работает. Я думал, что на странице фраза бит означает двоичный файл или я ошибаюсь?

Любая помощь приветствуется.

Answer 1

Первая очевидная ошибка:

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

Псевдокод использует запись с включенными границами; range является эксклюзивным для верхней границы, поэтому вы только что сделали K длиной 63 элемента, когда длина должна составлять 64 элемента.

Та же проблема с вашим последним l oop:

for i in range(63):

Возможно, следует проверить другие границы, чтобы убедиться, что вы не допустили подобных ошибок в других местах.

Это также совершенно неверно:

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

, потому что это не дополняет входные байты так, как должно, поэтому все ваши биты беспорядочные. Есть много способов сделать это (вы, вероятно, могли бы заставить его работать со строкой формата '08b', предполагая, что все ваши символы имеют порядковые значения ниже 256, хотя это довольно неэффективное решение).

Также неправильно:

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

Вы должны добавить оригинальную длину в битах мод 2**64, а не число 64, повторенное 64 раза (я понятия не имею, откуда вы это взяли) .

Для вашего последнего вопроса, чтобы объяснить «разбить фрагмент на шестнадцать 32-битных слов M [j], 0 ≤ j ≤ 15», «32-битные слова» означает «целые числа, состоящие из 32 двоичных битов». Для простого примера разбиение 0b100100001111 на три четырехбитных слова привело бы к получению 0b1001, 0b0000, 0b1111.

К сожалению для вас, в Python, int s - бесконечная точность; они не сбрасывают переполненные биты, когда вычисления дают результат с более чем 32 битами, и вычисления MD5 предполагают, что они это делают. Таким образом, вам нужно будет смоделировать его с помощью большого количества маскировок, поразрядно и с помощью & 0xffffffff.

Короче говоря реализация MD5 на обычном Python из псевдокода является королевской боль в заднице, потому что псевдокод опирается на ограничения языка низкого уровня, такого как C. И вы явно недостаточно осторожны в реализации даже тех битов, которые естественным образом переводятся в Python.