Содержание

Меню


MD5

Оглавление

Описание
Алгоритм
Пример

MD5 (англ. Message Digest 5) — 128-битный алгоритм хеширования, разработанный профессором Рональдом Л. Ривестом из Массачусетского Технологического Института (MIT, Massachusetts Institute of Technlogy) в 1991 году.
Предназначендля создания «отпечатков» или «дайджестов» сообщений произвольной длины.
Пришёл на смену MD4, который был несовершенен. Работает на 32-битных машинах.
Зная MD5, невозможно восстановить входное сообщение, так как одному MD5 могут соответствовать разные сообщения.
Используется для проверки подлинности опубликованных сообщений путем сравнения дайджеста сообщения с опубликованным. Эту операцию называют «проверка хеша» (hashcheck). Описан в RFC 1321.

Алгоритм MD5

На вход алгоритма поступает входной поток данных, хеш которого необходимо найти. Длина сообщения может быть любой (в том числе нулевой). Запишем длину сообщения в L. Это число целое и не отрицательное. Кратность каким-либо числам не обязательна. После поступления даных идет процесс подготовки потока к вычислениям.
  • Ниже приведены 5 шагов алгоритма:
    Шаг 1. Выравнивание потока
    Входные данные выравниваются так, чтобы их размер был сравним с 448 по модулю 512 (L’ = 512 ? N + 448). Сначала дописывают единичный бит в конец потока, затем необходимое число нулевых бит (выравнивание происходит, даже если длина уже конгруэнтна — сравнима с 448).
    Шаг 2. Добавление длины сообщения.
    В оставшиеся 64 бита дописывают 64-битное представление длины данных до выравнивания. Если длина превосходит 2 64 ? 1, то дописывают только младшие биты. После этого длина потока станет кратной степеням двойки — 16, 32. Вычисления будут основываться на представлении этого потока данных в виде массива слов по 512 бит.
    Шаг 3. Инициализация MD-буфера.
    Для вычислений инициализируются 4 переменных размером по 32 бита и задаются начальные значения шестнадцатеричными числами:
      
    А = 01 23 45 67;
    В = 89 AB CD EF;
    С = FE DC BA 98;
    D = 76 54 32 10.

    В этих переменных будут храниться результаты промежуточных вычислений. Начальное состояние ABCD называется инициализирующим вектором.
    Определим еще функции и константы, которые нам понадобятся для вычислений.
  • Потребуются 4 функции для четырех раундов. Введем функции от трех параметров — слов, результатом также будет слово.
  • Определим таблицу констант T[1..64] — 64-элементная таблица данных, построенная следующим образом: T[i] = int(4294967296 * | sin(i) | ) и s — циклический сдвиг влево на s бит полученого 32-битного аргумента.
    Выравненные данные разбиваются на блоки (слова) по 32 бита, и каждый блок проходит 4 раунда из 16 операторов. Все операторы однотипны и имеют вид: [abcd k s i], определяемый как a = b + ((a + Fun(b,c,d) + X[k] + T[i]) < < < s), где X — блок данных. X[k] = M [n * 16 + k], где k — номер 32-битного слова из n-го 512-битного блока сообщения.
    Шаг 4. Вычисление в цикле
    Заносим в блок данных элемент n из массива. Сохраняются значения A, B, C и D, оставшиеся после операций над предыдущими блоками (или их начальные значения, если блок первый).
    AA = A
    BB = B
    CC = C
    DD = D
    
    Раунд 1
    /*[abcd k s i] a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
    [ABCD  0 7  1][DABC  1 12  2][CDAB  2 17  3][BCDA  3 22  4]
    [ABCD  4 7  5][DABC  5 12  6][CDAB  6 17  7][BCDA  7 22  8]
    [ABCD  8 7  9][DABC  9 12 10][CDAB 10 17 11][BCDA 11 22 12]
    [ABCD 12 7 13][DABC 13 12 14][CDAB 14 17 15][BCDA 15 22 16]
    
    Раунд 2
    /*[abcd k s i] a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
    [ABCD  1 5 17][DABC  6 9 18][CDAB 11 14 19][BCDA  0 20 20]
    [ABCD  5 5 21][DABC 10 9 22][CDAB 15 14 23][BCDA  4 20 24]
    [ABCD  9 5 25][DABC 14 9 26][CDAB  3 14 27][BCDA  8 20 28]
    [ABCD 13 5 29][DABC  2 9 30][CDAB  7 14 31][BCDA 12 20 32]
    
    Раунд 3
    /*[abcd k s i] a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
    [ABCD  5 4 33][DABC  8 11 34][CDAB 11 16 35][BCDA 14 23 36]
    [ABCD  1 4 37][DABC  4 11 38][CDAB  7 16 39][BCDA 10 23 40]
    [ABCD 13 4 41][DABC  0 11 42][CDAB  3 16 43][BCDA  6 23 44]
    [ABCD  9 4 45][DABC 12 11 46][CDAB 15 16 47][BCDA  2 23 48]
    
    Раунд 4
    /*[abcd k s i] a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
    [ABCD  0 6 49][DABC  7 10 50][CDAB 14 15 51][BCDA  5 21 52]
    [ABCD 12 6 53][DABC  3 10 54][CDAB 10 15 55][BCDA  1 21 56]
    [ABCD  8 6 57][DABC 15 10 58][CDAB  6 15 59][BCDA 13 21 60]
    [ABCD  4 6 61][DABC 11 10 62][CDAB  2 15 63][BCDA  9 21 64]
    Суммируем с результатом предыдущего цикла:
    A = AA + A
    B = BB + B
    C = CC + C
    D = DD + D
    После окончания цикла необходимо проверить, есть ли еще блоки для вычислений. Если да, то изменяем номер элемента массива (n++) и переходим в начало цикла.
    Шаг 5. Результат вычислений
    Результат вычислений находится в буфере ABCD, это и есть хеш. Если вывести слова в обратном порядке DCBA, то мы получим наш MD5 хеш.

    Пример

     MD5("md5") = 1bc29b36f623ba82aaf6724fd3b16718
    Хеш содержит 128 бит (16 байт) и обычно представляется как последовательность из 32 шестнадцатеричных чисел.

    Виды
  • MD6
  • MD4
  • MD5
  • SECURE HASH ALGORITHM (SHA)
  • RIPE-MD
  • HAVAL
  • MDC

  • Основы криптографии
    Шифры
    Цифровые подписи
    Хеш-функции
    Криптоанализ
    Дополнительный материал
    MKZT© 2009 год
    Hosted by uCoz