Основы построения хэш-функций
Общепринятым принципом построения хэш-функций является итеративная последовательная схема. По этой методики ядром алгоритма является преобразование k бит в n бит. Величина n - разрядность результата хэш-функции, а k - произвольное число, большее n. Базовое преобразование должно обладать всеми свойствами хэш-функции т.е. необратимостью и невозможностью инвариантного изменения входных данных.
Хэширование производится с помощью промежуточной вспомогательной переменной разрядностью в n бит. В качестве ее начального значения выбирается произвольное известное всем сторонам значение, например, 0.
Входные данные разбиваются на блоки по (k-n) бит. На каждой итерации хэширования со значением промежуточной величины, полученной на предыдущей итерации, объединяется очередная (k-n)-битная порция входных данных, и над получившимся k-битным блоком производится базовое преобразование. В результате весь входной текст оказывается "перемешанным" с начальным значением вспомогательной величины. Из-за характера преобразования базовую функцию часто называют сжимающей. Значение вспомогательной величины после финальной итерации поступает на выход хэш-функции (рис.2). Иногда над получившимся значением производят дополнительные преобразования. Но в том случае, если сжимающая функция спроектирована с достаточной степенью стойкости, эти преобразования излишни.
При проектировании хэш-функции по итеративной схеме возникают два взаимосвязанных вопроса: как поступать с данными, не кратными числу (k-n), и как добавлять в хэш-сумму длину документа, если это требуется. Есть два варианта решения этих вопросов. В первом варианте в начало документа перед хэшированием добавляется поле фиксированной длины (например, 32 бита), в котором в двоичном виде записывается исходная длина текста. Затем объединенный блок данных дополняется нулями до ближайшего кратного (k-n) бит размера. Во втором варианте документ дополняется справа одним битом "1", а затем до кратного (k-n) бит размера битами "0". В этом варианте необходимость в поле длины отпадает - никакие два разных документа после выравнивания по границе порций не станут одинаковыми.
Кроме более популярных однопроходных алгоритмов хэширования существуют и многопроходные алгоритмы. В этом случае входной блок данных на этапе расширения неоднократно повторяется, а уже затем дополняется до ближайшей границы порции.
Рисунок 2 Итерактивная хэш-функция
Однонаправленные хэш-функции на основе симметричных блочных алгоритмов
Однонаправленную хэш-функцию можно построить, используя симметричный блочный алгоритм. Наиболее очевидный подход состоит в том, чтобы шифровать сообщение М посредством блочного алгоритма в режиме СВС или СFВ с помощью фиксированного ключа и некоторого вектора инициализации IV. Последний блок шифртекста можно рассматривать в качестве хэш-значения сообщения М. При таком подходе не всегда возможно построить безопасную однонаправленную хэш-функцию, но всегда можно получить код аутентификации сообщения МАС (Message Authentication Code).
Более безопасный вариант хэш-функции можно получить, используя блок сообщения в качестве ключа, предыдущее хэш-значение - в качестве входа, а текущее хэш-значение - в качестве выхода. Реальные хэш-функции проектируются еще более сложными. Длина блока обычно определяется длиной ключа, а длина хэш-значения совпадает с длиной блока.
Поскольку большинство блочных алгоритмов являются 64-битовыми, некоторые схемы хэширования проектируют так, чтобы хэш-значение имело длину, равную двойной длине блока.
Если принять, что получаемая хэш-функция корректна, безопасность схемы хэширования базируется на безопасности лежащего в ее основе блочного алгоритма. Схема хэширования, у которой длина хэш-значения равна длине блока, показана на рис.3. Ее работа описывается выражениями:
Н0 = Iн,
Нi = ЕA(В) Å С,
где Å - сложение по модулю 2 (исключающее ИЛИ); Iн - некоторое случайное начальное значение; А, В, С могут принимать значения Мi, Нi-1, (Мi Å Нi-1) или быть константами.
Рисунок 3 Обобщенная схема формирования хэш-функции
Сообщение М разбивается на блоки Мi принятой длины, которые обрабатываются поочередно.
Три различные переменные А, В, С могут принимать одно из четырех возможных значений, поэтому в принципе можно получить 64 варианта общей схемы этого типа. Из них 52 варианта являются либо тривиально слабыми, либо небезопасными. Остальные 12 схем безопасного хэширования, у которых длина хэш-значения равна длине блока перечислены в табл.1.
Таблица 1
Номер схемы |
Функция хэширования |
1 |
Нi = ЕHi-1 ( Мi ) Å Мi |
2 |
Нi = ЕHi-1 ( Мi Å Нi-1 ) Å Мi Å Нi-1 |
3 |
Нi = EHi-1 ( Мi ) Å Мi Å Нi-1 |
4 |
Нi = ЕHi-1 ( Мi Å Нi-1 ) Å Мi |
5 |
Нi = ЕMi ( Нi-1 ) Å Нi-1 |
6 |
Нi = ЕMi ( Мi Å Нi-1 ) Å Мi Å Нi-1 |
7 |
Нi = ЕMi ( Нi-1 ) Å Мi Å Нi-1 |
8 |
Нi = EMi ( Мi Å Нi-1) Å Нi-1 |
9 |
Нi = ЕMi Å Hi-1 ( Мi ) Å Мi |
10 |
Нi = ЕMi Å Hi-1 ( Нi-1) Å Нi-1 |
11 |
Нi = ЕMi ÅHi-1 ( Mi ) Å Нi-1 |
12 |
Нi = ЕMi Å Hi-1 ( Нi-1 ) Å Мi |
Первые четыре схемы хэширования, являющиеся безопасными при всех атаках, приведены на рис.4.
Рисунок 4 Четыре схемы безопасного хэширования
Недостатком хэш-функций, спроектированных на основе блочных алгоритмов, является несколько заниженная скорость работы
Развитие современных средств безбумажного документооборота, средств электронных платежей немыслимо без развития средств доказательства подлинности и целостности документа. Таким средством является электронно-цифровая подпись (ЭЦП), которая сохранила основные свойства обычной подписи.
Существует несколько методов построения ЭЦП, а именно:
шифрование электронного документа (ЭД) на основе симметричных алгоритмов. Данная схема предусматривает наличие в системе третьего лица – арбитра, пользующегося доверием обеих сторон. Авторизацией документа в данной схеме является сам факт шифрования ЭД секретным ключом и передачи его арбитру.
Использование ассиметричных алгоритмов шифрования. Фактом подписания документа является шифрование его на секретном ключе отправителя.
Развитием предыдущей идеи стала наиболее распространенная схема ЭЦП – шифрование окончательного результата обработки ЭД хеш-функцией при помощи ассиметричного алгоритма.
Появление этих разновидностей обусловлено разнообразием задач, решаемых с помощью электронных технологий передачи и обработки электронных документов.
При генерации ЭЦП используются параметры трех групп:
общие параметры
секретный ключ
открытый ключ
Отечественным стандартом на процедуры выработки и проверки ЭЦП является ГОСТ Р 34.10-94.