- •1. Алгоритмы с открытым ключом
- •2.Алгоритмы на основе задачи об укладке ранца
- •3.Сверхвозрастающие ранцы
- •4.Ранцевый механизм. Создание открытого ключа по закрытому.
- •5. Открытое распределение ключей
- •6. Криптографическая система с открытым ключом
- •8. Схема Поллинга-Хеллмана
- •9. Схема Рабина
- •10.Схема Вильямса
- •11. Схема Эль-Гамаля
- •12. Шифрование Эль-Гамаля
- •13. Режим электронной подписи Эль-Гамаля
- •14. Эцп и проблемы аутентификации
- •15. Система формирования эцп (процедуры)
- •16. Однонаправленные хэш-функции
- •17. Основы построения хэш-функций
- •Однонаправленные хэш-функции на основе симметричных блочных алгоритмов
- •Алгоритм md-5
- •Алгоритм sha
- •Отличие md-5 от sha
- •Российский стандарт хэш-функций
- •26.Стандарт цифровой подписи гост р 34.10-94
- •27.Беспроводные сети. Способы зашифрования данных.
- •28.Протокол 802.1 X
- •Алгоритм цп на эллиптических кривых, формирование цп.
- •Алгоритм цп на эллиптических кривых, проверка цп.
- •Алгоритмы удвоения точки эллиптической кривой
- •43 Квантовая криптография
- •Простейший алгоритм генерации секретного ключа (bb84)
16. Однонаправленные хэш-функции
Хэш-функция предназначена для сжатия подписываемого документа до нескольких десятков или сотен бит. Хэш-функция h(·) принимает в качестве аргумента сообщение (документ) М произвольной длины и возвращает хэш-значение h(М)=Н фиксированной длины. Обычно хэшированная информация является сжатым двоичным представлением основного сообщения произвольной длины. Следует отметить, что значение хэш-функции h(М) сложным образом зависит от документа М и не позволяет восстановить сам документ М.
Хэш-функция должна удовлетворять целому ряду условий:
хэш-функция должна быть чувствительна к всевозможным изменениям в тексте М, таким как вставки, выбросы, перестановки и т.п.;
хэш-функция должна обладать свойством необратимости, то есть задача подбора документа М', который обладал бы требуемым значением хэш-функции, должна быть вычислительно неразрешима;
вероятность того, что значения хэш-функций двух различных документов (вне зависимости от их длин) совпадут, должна быть ничтожно мала.
Большинство хэш-функций строится на основе однонаправленной функции f(·), которая образует выходное значение длиной n при задании двух входных значений длиной n. Этими входами являются блок исходного текста М, и хэш-значение Нi-1 предыдущего блока текста (рис.1).
Рис.1. Построение однонаправленной хэш-функции
Нi = f(Мi, Нi-1) .
Хэш-значение, вычисляемое при вводе последнего блока текста, становится хэш-значением всего сообщения М.
В результате однонаправленная хэш-функция всегда формирует выход фиксированной длины n (независимо от длины входного текста).
17. Основы построения хэш-функций
Общепринятым принципом построения хэш-функций является итеративная последовательная схема. По этой методики ядром алгоритма является преобразование k бит вn бит. Величина n - разрядность результата хэш-функции, а k -произвольное число, большее n. Базовое преобразование должно обладать всеми свойствами хэш-функции т.е. необратимостью и невозможностью инвариантного изменения входных данных.
Хэширование производится с помощью промежуточной вспомогательной переменной разрядностью вn бит. В качестве ее начального значения выбирается произвольное известное всем сторонам значение, например, 0.
Входные данные разбиваются на блоки по (k-n) бит. На каждой итерации хэширования со значением промежуточной величины, полученной на предыдущей итерации, объединяется очередная (k-n)-битная порция входных данных, и над получившимся k-битным блоком производится базовое преобразование. В результате весь входной текст оказывается "перемешанным" с начальным значением вспомогательной величины. Из-за характера преобразования базовую функцию часто называют сжимающей. Значение вспомогательной величины после финальной итерации поступает на выход хэш-функции (рис.2). Иногда над получившимся значением производят дополнительные преобразования. Но в том случае, если сжимающая функция спроектирована с достаточной степенью стойкости, эти преобразования излишни.
При проектировании хэш-функции по итеративной схеме возникают два взаимосвязанных вопроса:как поступать с данными, не кратными числу (k-n), и как добавлять в хэш-сумму длину документа, если это требуется. Есть два варианта решения этих вопросов. В первом варианте в начало документа перед хэшированием добавляется поле фиксированной длины (например, 32 бита),в котором в двоичном виде записывается исходная длина текста. Затем объединенный блок данных дополняется нулями до ближайшего кратного (k-n) бит размера. Во втором варианте документ дополняется справа одним битом "1", а затем до кратного (k-n) бит размера битами "0". В этом варианте необходимость в поле длины отпадает - никакие два разных документа после выравнивания по границе порций не станут одинаковыми.
Кроме более популярных однопроходных алгоритмов хэширования существуют и многопроходные алгоритмы. В этом случае входной блок данных на этапе расширения неоднократно повторяется, а уже затем дополняется до ближайшей границы порции.
Рис.2. Итерактивная хэш-функция