*** 05/05/21 доступна новая статья: алгоритм Python с алгоритмом MD4, шаг за шагом, хорошая основа для понимания современных методов хеширования MD5, SHA,…: https://nickthecrypt.medium.com/cryptography-hash- метод-md4-дайджест-сообщения-4-объяснение-с-python-f201b74f51d ***
MD2 - это базовая хеш-функция и хорошее введение в то, что сейчас ежедневно используется для криптографических транзакций, хранения паролей,… Увлекательная функция, полная поэзии.
вступление
Я добровольно пропущу обширное введение о том, что такое хэш-методы, историю создания алгоритмов дайджеста сообщений и почему мы не находим следов MD1 (чего, кстати, я не знаю - источники говорят: он не был опубликован и это достаточно веская причина).
Меня всегда очаровывали хэш-функции, идея инкапсуляции бесконечной вселенной в фиксированное ограниченное количество байтов мне нравится (несмотря на то, что это математически невозможно - для бесконечной части вселенной).
Следовательно, эта случайно выбранная подпись MD2 c8c3cbb4b530034bac23565fa973f94f может быть подписью текста, описывающего решение, чтобы покончить с бедностью человечества, или хешем очаровательной фотографии котенка ... или и тем, и другим (согласно моему предыдущему абзацу, столкновения неизбежны и, как было доказано, происходят на MD2) .
В этой статье я хочу вульгаризировать алгоритм MD2 и предложить пошаговую реализацию Python для этого.
Я надеюсь, вам понравится это читать.
Первоначальный стандарт M2: RFC 1319
Я буду использовать исходный документ RFC в качестве стандартного источника, он доступен здесь https://tools.ietf.org/html/rfc1319. Здесь я снова не буду объяснять в этой статье историю этого алгоритма и почему его больше не следует реализовывать.
Приведенная ниже реализация будет немасштабируемой по назначению, чтобы понять, как работает этот алгоритм.
RFC описывает 4 шага для получения хэш-подписи (я лично не уверен в том, что третий шаг - «настоящий» шаг):
- шаг 1: заполнение сообщения
- шаг 2: добавить контрольную сумму
- шаг 3: инициализировать дайджест
- Шаг 4: обработайте сообщение блоками по 16 байтов
- шаг 5: вывод
Чтобы понять каждый шаг, мы вместе обработаем сообщение без вычислений / a.k.a. вручную.
Посланием будет красивое стихотворение Масаока Сики о хайку:
После убийства
паука, как я одиноко чувствую себя
среди ночи!
Мы рассмотрим это сообщение с его специальными символами, то есть это будет следующая строка:
msg = “After killing\r\na spider, how lonely I feel\r\nin the cold of night!”
Это сообщение размером 65 байтов, если мы разделим его на блоки по 16 байтов, это будет преобразовано в приведенную ниже таблицу.
Как вы знаете, символы представляют собой коды ascii, а операции со строкой / символами выполняются на этом уровне «кода». Что мы можем легко получить, переведя строку char в массив кодов ascii.
msg = [ord(c) for c in msg]
Это можно перевести в следующую таблицу:
Теперь мы можем перейти к различным этапам хеширования.
Шаг 1: заполнение сообщения, чтобы оно соответствовало длине 16 байтов
Как указано в RFC, при заполнении сообщение достигает длины 16 байт. Это означает, что заполнитель контактной площадки будет иметь длину 16 минус длина сообщения% 16. Значением байтов будет длина контактной площадки.
В нашем примере нам не хватает 15 байтов для достижения полного последнего блока. Следовательно, нам нужно добавить 15 байтов значения 15.
BLOCK_SIZE = 16 padding_pat = BLOCK_SIZE - (len(msg) % BLOCK_SIZE) padding = padding_pat * [padding_pat] msg = msg + padding
Как и следовало ожидать, таблица выглядит следующим образом:
Шаг 2: вычислить и добавить контрольную сумму
*** важное примечание: спасибо Кевину Найту, который справедливо упомянул, что основная версия RFC 1319 показывает ошибку в своем псевдокоде при вычислении контрольной суммы, исправленная в опечатке EID 555: https: // www.rfc-editor.org/rfc/inline-errata/rfc1319.html - действительно, контрольная сумма последовательно пересчитывается в предыдущее положение и не удаляется при каждой итерации, еще раз спасибо, Кевин ***
Расчет контрольной суммы требует, чтобы мы встретились с таблицей подстановки алгоритма MD2. Он состоит из таблицы из 256 элементов, выбранных в качестве десятичных знаков числа PI.
Вот наш друг:
S = [
41, 46, 67, 201, 162, 216, 124, 1, 61, 54, 84, 161, 236, 240, 6, 19,
98, 167, 5, 243, 192, 199, 115, 140, 152, 147, 43, 217, 188, 76, 130, 202,
30, 155, 87, 60, 253, 212, 224, 22, 103, 66, 111, 24, 138, 23, 229, 18,
190, 78, 196, 214, 218, 158, 222, 73, 160, 251, 245, 142, 187, 47, 238, 122,
169, 104, 121, 145, 21, 178, 7, 63, 148, 194, 16, 137, 11, 34, 95, 33,
128, 127, 93, 154, 90, 144, 50, 39, 53, 62, 204, 231, 191, 247, 151, 3,
255, 25, 48, 179, 72, 165, 181, 209, 215, 94, 146, 42, 172, 86, 170, 198,
79, 184, 56, 210, 150, 164, 125, 182, 118, 252, 107, 226, 156, 116, 4, 241,
69, 157, 112, 89, 100, 113, 135, 32, 134, 91, 207, 101, 230, 45, 168, 2,
27, 96, 37, 173, 174, 176, 185, 246, 28, 70, 97, 105, 52, 64, 126, 15,
85, 71, 163, 35, 221, 81, 175, 58, 195, 92, 249, 206, 186, 197, 234, 38,
44, 83, 13, 110, 133, 40, 132, 9, 211, 223, 205, 244, 65, 129, 77, 82,
106, 220, 55, 200, 108, 193, 171, 250, 36, 225, 123, 8, 12, 189, 177, 74,
120, 136, 149, 139, 227, 99, 232, 109, 233, 203, 213, 254, 59, 0, 29, 57,
242, 239, 183, 14, 102, 88, 208, 228, 166, 119, 114, 248, 235, 117, 75, 10,
49, 68, 80, 180, 143, 237, 31, 26, 219, 153, 141, 51, 159, 17, 131, 20]
Для каждого блока из 16 байтов мы продолжим «пропускать» контрольную сумму и сделаем следующее:
checksum = 16 * [0]
l = 0
blocks = math.ceil(N / BLOCK_SIZE)
for i in range(blocks):
for j in range(BLOCK_SIZE):
l = PI_SUBST[(msg[i*BLOCK_SIZE+j] ^ l)] ^ checksum[j]
checksum[j] = l
Как видите, для каждого байта в сообщении:
- мы находим суррогат в таблице S по индексу: значение ascii в текущей позиции сообщения XOR последняя вычисленная позиция контрольной суммы (начальное состояние: 0)
- Новая позиция контрольной суммы - это суррогатная позиция xor текущей контрольной суммы (начальное состояние: 0)
Вернемся к нашему сообщению и обработаем первые буквы «вручную». Если операция XOR подходит для обработки с помощью предпочтительного калькулятора, получение суррогата из таблицы S может быть немного сложной задачей. Вы можете создать небольшой сценарий, который поможет вам. i - текущая позиция сообщения, l - позиция предыдущей вычисленной контрольной суммы.
Приведенная выше таблица призвана успокоить вас при расчетах (чтобы вы могли почувствовать, что идете правильным путем). Если взять пример расчета 8-й позиции контрольной суммы, то во время второго прохода (или второго блока сообщения - красной ячейки) мы имеем следующее:
xor (181, 44) = 153
S [153] = 70
xor (70, 92) = 26
Вы можете поменять местами операнды XOR, поскольку XOR является коммутативным.
Для нашего Haiku вы должны получить следующую контрольную сумму:
[167, 222, 15, 251, 92, 111, 246, 45, 79, 203, 11, 129, 245, 139, 5, 178]
Следуя алгоритму, нам нужно добавить эту контрольную сумму как новый блок нашего сообщения, что на этом этапе приведет к следующему:
Не забудьте обновить свой код:
msg = msg + checksum blocks += 1
Шаг 3: инициализировать дайджест
Я большой поклонник этого «такого полезного» шага:
md_digest = 48 * [0]
Шаг 4: обработайте сообщение блоками по 16 байтов
Я хотел бы сказать, что сейчас мы переходим к интересной части, но шаг 2 также был очень интересным.
В любом случае, продолжим это сказочное путешествие.
Для этого вам нужно изобразить буфер md_digest как сегментированный на 3 блока по 16 байт каждый, каждый из которых будет иметь определенную задачу. Мы назовем их md_digest_0 / md_digest_1 / md_digest_2.
Следуя алгоритму, вот что будет добавлено для каждого блока:
- md_digest_1 = текущий блок
- md_digest_2 = xor (md_digest_1, md_digest_0)
- 18 передает md_digest операции xor и подстановки через S-таблицу.
В коде:
for i in range(blocks):
for j in range(BLOCK_SIZE):
md_digest[BLOCK_SIZE+j] = msg[i*BLOCK_SIZE+j]
md_digest[2*BLOCK_SIZE+j] = (md_digest[BLOCK_SIZE+j] ^ md_digest[j])
checktmp = 0
for j in range(18):
for k in range(48):
checktmp = md_digest[k] ^ PI_SUBST[checktmp]
md_digest[k] = checktmp
checktmp = (checktmp+j) % 256
Если первая часть проста, вторая часть - уловка. Почему 18 пасов? Я не могу ответить на этот вопрос. Если у кого-то из вас есть ответ, я буду счастлив узнать.
Теперь давайте помнить, что в большинстве случаев хеш-функции создаются эмпирическим путем. Это означает, что все операции могут не иметь обоснованной наукой причины быть / и быть таким образом.
В конце этого шага мы получаем следующее хеш-значение:
[16, 159, 142, 226, 78, 105, 28, 163, 49, 47, 33, 55, 4, 159, 19, 161, 211, 177, 59, 143, 64, 79, 220, 140, 190, 113, 197, 12, 244, 192, 47, 104, 174, 252, 102, 71, 161, 224, 170, 184, 56, 203, 66, 160, 241, 185, 197, 114]
Это подводит нас к этапу завершения.
Шаг 5: вывод
Как вы знаете, 16 первых байтов переменной md_digest будут представлять наш хеш. Но очевидно, что это далеко от того, что вы уже видели как хеш-представление текстов.
Следовательно, нам нужно преобразовать каждое значение в шестнадцатеричное значение.
print("".join(map(lambda x: hex(x).lstrip("0x"), md_digest[0:16])))
У вас получится такая красивая подпись:
109f8ee24e691ca3312f213749f13a1
Для нашего, прекрасного, Haiku.
Выводы
Как уже было сказано, моя реализация предназначена не для масштабируемости или красоты, а для того, чтобы помочь понять алгоритм. И потенциально, когда мы рассмотрим более сложные алгоритмы, мы сможем обнаружить различия и сходства.
Помните, что этот алгоритм оказался небезопасным, не используйте его в критических приложениях.
Если у вас есть второй, подумайте о поэзии хеш-функций :-)
Рад обратиться для дальнейшего обсуждения, если у вас есть предложения, обратная связь [email protected]
полный код доступен здесь https://github.com/NickRHR/hashfunctions/blob/f12fde7ed92e2ad3f5973b30985dc5ec597afd95/MD2/MD2_nfc.py
