 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Вычисление
|
Читайте также: |
Введение.
MD5 — 128-битный алгоритм хеширования. Сначала сообщение делится на блоки по 512 бит (64 байта), затем от каждого блока вычисляется замысловатая, но простая в реализации функция и наконец все результаты функций собираются вместе в 128-битный хеш.
Разбиение на блоки.
Нужно сделать так, что сообщение состояло из нескольких 512-битных блоков. Это делают следующим образом:
1. N - размер сообщения в виде 64-битного целого числа
2. Дописывают единичный бит в конец сообщения (байт 0x80)
3. Затем необходимое число нулевых бит. Добавление производится всегда, даже если сообщение имеет нужную длину. Например, если длина сообщения 448 битов, оно дополняется 512 битами до 960 битов.
4. Затем дописывают 64-битный N. Число нулевых битов выбирают так, чтобы длина сообщения после дописывания N была кратна 512 битам. Сначала записывают младшие 4 байта. Если длина превосходит 264 − 1, то дописывают только младшие биты
Вычисление.
Используется 128-битный буфер для хранения промежуточных и окончательных результатов хэш-функции. Буфер может быть представлен как четыре 32-битных регистра (A, B, C, D). Эти регистры инициализируются следующими шестнадцатеричными числами:
А = 01234567
В = 89ABCDEF
C = FEDCBA98
D = 76543210
Четыре цикла имеют похожую структуру, но каждый цикл использует свою элементарную логическую функцию, обозначаемую fF, fG, fH и fI соответственно.
Каждый цикл принимает в качестве входа текущий 512-битный блок Yq, обрабатывающийся в данный момент, и 128-битное значение буфера ABCD, которое является промежуточным значением дайджеста, и изменяет содержимое этого буфера. Каждый цикл также использует четвертую часть 64-элементной таблицы T[1... 64], построенной на основе функции sin. i-ый элемент T, обозначаемый T[i], имеет значение, равное целой части от 232 * abs (sin (i)), i задано в радианах. Так как abs (sin (i)) является числом между 0 и 1, каждый элемент Т является целым, которое может быть представлено 32 битами. Таблица обеспечивает "случайный" набор 32-битных значений, которые должны ликвидировать любую регулярность во входных данных.
Для получения MDq+1 выход четырех циклов складывается по модулю 232 с MDq. Сложение выполняется независимо для каждого из четырех слов в буфере.
Рассмотрим более детально логику каждого из четырех циклов выполнения одного 512-битного блока. Каждый цикл состоит из 16 шагов, оперирующих с буфером ABCD. Каждый шаг можно представить в виде:
A = B + CLSs (A + f (B, C, D) + X [k] + T [i]), где
| A, B, C, D - четыре слова буфера; после выполнения каждого отдельного шага происходит циклический сдвиг влево на одно слово. |
| f - одна из элементарных функций fF, fG, fH, fI. |
| CLSs - циклический сдвиг влево на s битов 32-битного аргумента. |
| X [k] = M [q * 16 + k] - k-ое 32-битное слово в q-ом 512 блоке сообщения. |
| T [i] - i-ое 32-битное слово в матрице Т. |
| + - сложение по модулю 232. |
На каждом из четырех циклов алгоритма используется одна из четырех элементарных логических функций. Каждая элементарная функция получает три 32-битных слова на входе и на выходе создает одно 32-битное слово. Каждая функция является множеством побитовых логических операций, т.е. n-ый бит выхода является функцией от n-ого бита трех входов. Элементарные функции следующие:
Массив из 32-битных слов X [0..15] содержит значение текущего 512-битного входного блока, который обрабатывается в настоящий момент. Каждый цикл выполняется 16 раз, а так как каждый блок входного сообщения обрабатывается в четырех циклах, то каждый блок входного сообщения обрабатывается по схеме, показанной выше, 64 раза. Если представить входной 512-битный блок в виде шестнадцати 32-битных слов, то каждое входное 32-битное слово используется четыре раза, по одному разу в каждом цикле, и каждый элемент таблицы Т, состоящей из 64 32-битных слов, используется только один раз. После каждого шага цикла происходит циклический сдвиг влево четырех слов A, B, C и D. На каждом шаге изменяется только одно из четырех слов буфера ABCD. Следовательно, каждое слово буфера изменяется 16 раз, и затем 17-ый раз в конце для получения окончательного выхода данного блока.
Можно суммировать алгоритм MD5 следующим образом:
MD0 = IV
MDq+1 = MDq + fI[Yq, fH[Yq, fG[Yq, fF[Yq, MDq]]]]
MD = MDL-1, где
| IV - начальное значение буфера ABCD |
| Yq - q-ый 512-битный блок сообщения. |
| L - число блоков в сообщении (включая поля дополнения и длины). |
| MD - окончательное значение дайджеста сообщения. |
В конце цикла переменные вычисляются по такому принципу.
A = AA + A’B = BB + B’C = CC + C’D = DD + D’На примере первого шага:
AA, BB, CC, DD – текущие (начальные AA = A, BB = B, CC = C, DD = D)
A’, B’, C’, D’ – только что вычисленные
Затем AA = A’, BB = B’, CC = C’, DD = D’ и далее все повторяется.
Поиск по сайту: