Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Лекция 4.4 Однонаправленные хэш-функции






У однонаправленной хэш-функции может быть множество имен: функция сжатия, функция сокращения contraction function, краткое изложение, характерный признак, криптографическая контрольная сумма, код целостности сообщения. [2]

Хэш-функции, долгое время использующиеся в компьютерных науках, представляют собой функции, математические или иные, которые получают на вход строку переменной длины (называемую прообразом) и преобразуют ее в строку фиксированной, обычно меньшей, длины (называемую значением хэш — функции). В качестве простой хэш-функции можно рассматривать функцию, которая получает прообраз и возвращает байт, представляющий собой XOR всех входных байтов.

Однонаправленная хэш-функция - это хэш-функция, которая работает только в одном направлении: легко вычислить значение хэш-функции по прообразу, но трудно создать прообраз, значение хэш-функции которого равно заданной величине. Хорошей однонаправленной хэш-функцией является хэш-функция без столкновений — трудно создать два прообраза с одинаковым значением хэш-функции.

Хэш-функция является открытой, тайны ее расчета не существует. Безопасность однонаправленной хэш-функцией заключается именно в ее однонаправленности. У выхода нет видимой зависимости от входа. Изменение одного бита прообраза приводи к изменению, в среднем, половины битов значения хэш-функции. Вычислительно невозможно найти прообраз, соответствующий заданному значению хэш-функции.

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

Однонаправленная функция Н(М) применяется к сообщению произвольной длины М и возвращает значение фиксированной длины h.

h = Н(М), где h имеет длину т

Многие функции позволяют вычислять значение фиксированной длины по входным данным произвольной длины, но у однонаправленных хэш-функций есть дополнительные свойства, делающие их однонаправленными:

ü Зная М, легко вычислить h.

ü Зная Н, трудно определить М, для которого H(M)=h.

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

Должно быть трудно найти два случайных сообщения, М и М', для которых H(M)= H(М').

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

Это хэш-значение вместе со следующим блоком сообщения становится следующим входом функции сжатия. Хэш-значением всего сообщения является хэш-значение последнего блока (рисунок 15).

Рисунок 15 — Вычисление хэш - функции

MD4

MD4 - это однонаправленная хэш-функция, изобретенная Роном Ривестом. MD обозначает Message Digest (краткое изложение сообщения), алгоритм для входного сообщения выдает 128-битовое хэш-значение.

Ривест описал цели, преследуемые им при разработке алгоритма:

Безопасность. Вычислительно невозможно найти два сообщения с одинаковым хэш-значением. Вскрытие грубой силой является самым эффективным.

Скорость. MD4 подходит для высокоскоростных программных реализаций. Она основана на простом наборе битовых манипуляций с 32-битовыми операндами.

Простота и компактность. MD4 проста, насколько это возможна, и не содержит больших структур данных или сложных программных модулей.

Удачна архитектура. MD4 оптимизирована для микропроцессорной архитектуры (особенно для микропроцессоров Intel), для более крупных и быстрых компьютеров можно выполнить любые необходимые изменения.

MD5

MD5 - это улучшенная версия MD4. Хотя она сложнее MD4, их схемы похожи, и результатом MD5 также является 128-битовое хэш-значение.

Описание MD5

После некоторой первоначальной обработки MD5 обрабатывает входной текст 512-битовыми блоками, разбитыми на 16 32-битовых подблоков. Выходом алгоритма является набор из четырех 32-битовых блоков, которые объединяются в единое 128-битовое хэш-значение.

Во – первых, сообщение дополняется так, чтобы его длина была на 64 бита короче числа, кратного 512. Этим дополнением является 1, за которой вплоть до конца сообщения следует столько нулей, сколько нужно. Затем, к результату добавляется 64-битовое представление длины сообщения (истинной, до дополнения). Эти два дейст­вия служат для того, чтобы длина сообщения была кратна 512 битам (что требуется для оставшейся части алго­ритма), и чтобы гарантировать, что разные сообщения не будут выглядеть одинаково после дополнения. Инициализируются четыре переменных:

А = 0× 01234567

В = 0 × 89abcdef

С = 0 × fedcba98

D = 0× 76543210

Они называются переменными сцепления.

Теперь перейдем к основному циклу алгоритма. Этот цикл продолжается, пока не исчерпаются 512-битовые блоки сообщения.

Четыре переменных копируются в другие переменные: А в а, В в b, С в с и D в d.

Главный цикл состоит из четырех очень похожих этапов (у MD4 было только три этапа). На каждом этапе 16 раз используются различные операции. Каждая операция представляет собой нелинейную функцию над тремя из а, b, с и d. Затем она добавляет этот результат к четвертой переменной, подблоку текста и константе. Далее результат циклически сдвигается влево на переменное число битов и добавляет результат к одной из переменных а, b, с и d. Наконец результат заменяет одну из переменных а, b, с и d. Существуют четыре нелинейных функции, используемые по одной в каждой операции (для каждого этапа - другая функция).

Рисунок 19 — Главный цикл MD5.

Рисунок 20 — Одна операция MD5

F(X, Y, Z) = (Х Ù Y) Ú ((Ø X) Ù Z)

G(X, Y, Z) = (X Ù Z) Ú (Y Ù (Ø Z))

H (X, Y, Z) = X Å Y Å Z

I (X, Y, Z) = Y Å (X Ú (Ø Z))

(Å - это XOR, Ù - AND, Ú - OR, Ø NOT.)

Эти функции спроектированы так, чтобы, если соответствующие биты X, Y и Z независимы и несмещены, каждый бит результата также был бы независимым и несмещенным.

Если Mj обозначает j-ый подблок сообщения (от 0 до 15), a < < < s обозначает циклический сдвиг влево на s битов, то используются следующие четыре операции:

FF(a, b, c, d, Mj, s, ti) означает а = b + ((а + F(b, c, d) + Мj + ti) < < < s)

GG(a, b, c, d, Mj, s, ti) означает а = b + ((а + G(b, c, d) + Мj + ti) < < < s)

HH(a, b, c, d, Mj, s, tt) означает а = b + ((a + H(b, c, d) + Мj + ti) < < < s)

II(a, b, c, d, Mj, s, ti) означает a = b + ((a +I(b, c, d) + Мj + ti) < < < s)

Четыре этапа (64 действия выглядят следующим образом):

Этап 1: FF(a, b, с, d, M0, 7, 0× d76aa478) FF(d, a, b, с, M1 12, 0× e8c7b756) FF(c, d, a, b, M2, 17, 0× 242070db) FF(b, c, d, a, M3, 22, 0× c1bdceee) FF(a, b, c, d, M4, 7, 0× f57cOfaf) FF(d, a, b, c, M5, 12, 0× 4787c62a) FF(c, d, a, b, M6, 17, 0× a8304613) FF(b, c, d, a, M7, 22, 0× fd469501) FF(a, b, c, d, M8, 7, 0× 698098d8) FF(d, a, b, c, M9, 12, 0× 8b44f7af) FF(c, d, a, b, M10, 17, 0× ffff5bb1) FF(b, c, d, а, М11, 22, 0× 895cd7be) FF(a, b, c, d, M12, 7, 0× 6b901122) FF(d, a, b, c, M13, 12, 0× fd987193) FF(c, d, a, b, M14, 17, 0× a679438e) FF(b, c, d, a, M15, 22, 0× 49b40821) Этап 2: GG(a, b, c, d, M1 5, 0× f61e2562) GG(d, a, b, c, M6, 9, 0× c040b340) GG(c, d, a, b, М11, 14, 0× 265e5a51) GG(b, c, d, a, M0, 20, 0× e9b6c7aa) GG(a, b, c, d, M5, 5, 0× d62f105d) GG(d, a, b, c, M10, 9, 0× 02441453) GG(c, d, a, b, M15, 14, 0× d8a1e681) GG(b, c, d, a, M4, 20, 0× e7d3fbc8) GG(a, b, c, d, M9, 5, 0× 21e1cde6) GG(d, a, b, c, M14, 9, 0× c33707d6) GG(c, d, a, b, M3, 14, 0× f4d50d87) GG(b, c, d, a, M8, 20, 0× 455a14ed) GG(a, b, c, d, M13, 5, 0× a9e3e905) GG(d, a, b, c, M2, 9, 0× fcefa3f8) GG(c, d, a, b, M7, 14, 0× 676fD2d9) GG(b, c, d, a, M12, 20, 0× 8d2a4c8a)
ЭтапЗ: HH(a, b, с, d, M5, 4, 0× fffa3942) HH(d, a, b, c, M8, 11, 0× 8771f681) HH(c, d, a, b, M11, 16, 0× 6d9d6122) HH(b, c, d, a, M14, 23, 0× fde5380c) HH(a, b, c, d, M1, 4, 0× a4beea44) HH(d, a, b, c, M4, 11, 0× 4bdecfa9) HH(c, d, a, b, M7, 16, 0× f6bb4b60) HH(b, c, d, a, M10, 23, 0× bebfbcTO) HH(a, b, c, d, M13, 4, 0× 289b7ec6) HH(d, a, b, c, M0, 11, 0× eaal27fa) HH(c, d, a, b, M3, 16, 0× d4ef3085) HH(b, c, d, a, M6, 23, 0× 04881d05) HH(a, b, c, d, M9, 4, 0× d9d4d039) HH(d, a, b, c, M12, 11, 0× e6db99e5) HH(c, d, a, b, М15, 16, 0× lfa27cf8) HH(6, c, d, a, M2, 23, 0× c4ac5665) Этап 4: II(a, b, с, d, M0, 6, 0× f4292244) II(d, a, b, c, M7, 10, 0× 432aff97) II(c, d, a, b, M14, 15, 0× ab9423a7) II(b, c, d, a, M5, 21, 0× fc93a039) II(a, b, c, d, M12, 6, 0× 655b59c3) II(d, a, b, c, M3, 10, 0× 8fflccc92) II(c, d, a, b, M10, 15, 0× ffeff47d) II(b, c, d, a, M1, 21, 0× 85845ddl) II(a, b, c, d, M8, 6, 0× 6fa87e4f) II(d, a, b, c, M15, 10, 0× fe2ce6eO) II(c, d, a, b, M6, 15, 0× a3014314) II(b, c, d, a, M13, 21, 0× 4e0811al) II(a, b, c, d, M4, 6, 0× f7537e82) II(d, a, b, c, M11, 10, 0× bd3af235) II(c, d, a, b, M2, 15, 0× 2ad7d2bb) II(b, c, d, a, M9, 21, 0× eb86d391)

Константы, ti, выбирались следующим образом:

На i-ом этапе ti является целой частью 232*abs(sin(i)), где i измеряется в радианах.

После всего этого а, b, с и d добавляются к А, В, С и D, соответственно, и алгоритм продолжается для следующего блока данных. Окончательным результатом служит объединение А, В, С и D.

MD2

MD2 - это другая 128-битовая однонаправленная хэш-функция, разработанная Роном Ривестом. Безопасность MD2 опирается на случайную перестановку байтов. Эта перестановка фиксирована и зависит от разрядов p. S0, S1, S2, …, S255 и являются перестановкой. Чтобы выполнить хэширование сообщения М:

(1) Дополните сообщение i байтами, значение i должно быть таким, чтобы длина полученного сообщения была кратна 16 байтам.

(2) Добавьте к сообщению 16 байтов контрольной суммы.

(3) Проинициализируйте 48-байтовый блок: X 0, X1 , X2, …, X47. Заполните первые 16 байтов X нулями, во вторые 16 байтов X скопируйте первые 16 байтов сообщения, а третьи 16 байтов X должны быть равны XOR первых и вторых 16 байтов X.

(4) Вот как выглядит функция сжатия:

t=0

For j = 0 to 17

For k = 0 to 47

t=Xt XOR St

Xk=t

t = (t +j) mod 256

(5) Скопируйте во вторые 16 байтов Х вторые 16 байтов сообщения, а третьи 16 байтов X должны быть равны XOR первых и вторых 16 байтов X. Выполните этап (4). Повторяйте этапы (5) и (4) по очереди для каждых 16 байтов сообщения.

(6) Выходом являются первые 16 байтов X.

Хотя в MD2 пока не было найдено слабых мест, она работает медленнее большинства других предлагаемых хэш-функций.






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.