Электронная цифровая подпись

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

Хэш-функция предназначена для сжатия подписываемого документа М до нескольких десятков или сотен бит. Хэш-функция h(•) принимает в качестве аргумента сообщение (документ) М произвольной длины и возвращает хэш-значение h(М)=Н фиксированной длины. Обычно хэшированная информация является сжатым двоичным представлением основного сообщения произвольной длины. Следует отметить, что значение хэш-функции h(М) сложным образом зависит от документа М и не позволяет восстановить сам документ М.

Хэш-функция должна удовлетворять целому ряду условий:

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

Большинство хэш-функций строится на основе однонаправленной функции f(•), которая образует выходное значение длиной n при задании двух входных значений длиной п. Этими входами являются блок исходного текста М, и хэш-значение Н_і-1 предыдущего блока текста (рис.1):

Н_і = f(М_i, Н_i-1).

Хэш-значение, вычисляемое при вводе последнего блока текста, становится хэш-значением всего сообщения М.

Рис.1. Построение однонаправленной хэш-функции

В результате однонаправленная хэш-функция всегда формирует выход фиксированной длины n (независимо от длины входного текста).

Алгоритм безопасного хэширования SНА

Алгоритм безопасного хэширования SНА (Secure Hash Algorithm) разработан НИСТ и АНБ США в рамках стандарта безопасного хэширования SHS (Secure Hash Standard) в 1992 г. Алгоритм хэширования SНА предназначен для использования совместно с алгоритмом цифровой подписи DSА.

При вводе сообщения М произвольной длины менее 2⁶⁴ бит алгоритм SНА вырабатывает 160-битовое выходное сообщение, называемое дайджестом сообщения МD (Message Digest). Затем этот дайджест сообщения используется в качестве входа алгоритма DSА, который вычисляет цифровую подпись сообщения М. Формирование цифровой подписи для дайджеста сообщения, а не для самого сообщения повышает эффективность процесса подписания, поскольку дайджест сообщения обычно намного короче самого сообщения.

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

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

Рассмотрим подробнее работу алгоритма хэширования SНА. Прежде всего исходное сообщение М дополняют так, чтобы оно стало кратным 512 битам. Дополнительная набивка сообщения выполняется следующим образом: сначала добавляется единица, затем следуют столько нулей, сколько необходимо для получения сообщения, которое на 64 бита короче, чем кратное 512, и наконец добавляют 64-битовое представление длины исходного сообщения.

Инициализируется пять 32-битовых переменных в виде:

А = 0 х 6 7 4 5 2 3 0 1

В = 0 х Е F С D А В 8 9

С = 0 х 9 8 В А D С F Е

D = 0 x 1 0 3 2 5 4 7 6

Е = 0 х С 3 D 2 Е 1 F 0

Затем начинается главный цикл алгоритма. В нем обрабатывается по 512 бит сообіцения поочередно для всех 512-битовых блоков, имеющихся в сообщении. Первые пять переменных А, В, С, D, Е копируются в другие переменные a, b, с, d, е:

а=А, b=В, с=С, d=D, е=Е.

Главный цикл содержит четыре цикла по 20 операций каждый. Каждая операция реализует нелинейную функцию от трех из пяти переменных а, b, с, d, е, а затем производит сдвиг и сложение.

Алгоритм SНА имеет следующий набор нелинейных функций:

f_t (Х, Y, Z) = (X ^Ù Y) Ú ((ØX) ^Ù Z) для t = 0...19,

f_t (Х, Y, Z) =Х Å Y Å Z для t =20...39,

f_t (Х, Y, Z) = (X ^Ù Y) Ú (X ^Ù Z) Ú (Y ^Ù Z) для t = 40...59,

f_t (Х, Y, Z) = Х Å Y Å Z для t = 60...79,

где t - номер операции.

В алгоритме используются также четыре константы:

К_t = 0х5А827999 для t = 0...19,

К_t = 0х6ЕD9ЕВА1 для t = 20...39,

К_t = 0х8F1ВВСDС для t = 40...59,

К_t = 0хСА62С1D6 для t = 60...79.

Блок сообщения преобразуется из шестнадцати 32-битовых слов (М₀...М₁₅) в восемьдесят 32-битовых слов (W₀...W₇₉) с помощью следующего алгоритма:

W_t = М_t для t = 0...15,

W_t = (W_t-3 Å W_t-8 Å W_t-14 Å W_t-16) <<< 1 для t = 16...79,

где t - номер операции (для t = 1...80),

W_t - t-й субблок расширенного сообщения,

<<< S - циклический сдвиг влево на S бит.

С учетом введенных обозначений главный цикл из восьмидесяти операций можно описать так:

FOR t = 0 до 79

ТЕМР = (а <<< 5) + f_t (b, c, d) + е + W_t + К_t

е = d

d = с

с = (b <<< 30)

b = а

а = ТЕМР

Схема выполнения одной операции показана на рис.2.

После окончания главного цикла значения а, b, с, d и е складываются с А, В, С, D и Е соответственно, и алгоритм приступает к обработке следующего 512-битового блока данных. Окончательный выход формируется в виде конкатенации значений А, В, С, D и Е.

Рис.2. Схема выполнения одной операции алгоритма SHA

Поскольку алгоритм SНА выдает 160-битовое хэш-значение, он более устойчив к атакам полного перебора и атакам "дня рождения", чем большинство других алгоритмов хэширования, формирующих 128-битовые хэш-значения.

Однонаправленные хэш-функции на основе симметричных блочных алгоритмов

Однонаправленную хэш-функцию можно построить, используя симметричный блочный алгоритм. Наиболее очевидный подход состоит в том, чтобы шифровать сообщение М посредством блочного алгоритма в режиме СВС или СFВ с помощью фиксированного ключа и некоторого вектора инициализации IV. Последний блок шифртекста можно рассматривать в качестве хэш-значения сообщения М. При таком подходе не всегда возможно построить безопасную однонаправленную хэш-функцию, но всегда можно получить код аутентификации сообoения МАС (Message Authentication Code).

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

Рис.3. Обобщённая схема формирования хэш-функции

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

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

Н₀ = І_н, Н_i = Е_A(В) Å С,

где І_н - некоторое случайное начальное значение; А, В и С могут принимать значения М_і, Н_і-1, (М_i Å Н_і-1) или быть константами.

Сообщение М разбивается на блоки М_i принятой длины, которые обрабатываются поочередно.

Три различные переменные А, В и С могут принимать одно из четырех возможных значений, поэтому в принципе можно получить 64 варианта общей схемы этого типа. Из них 52 варианта являются либо тривиально слабыми, либо небезопасными. Остальные 12 безопасных схем хэширования перечислены в табл.1.

Первые четыре схемы хэширования, являющиеся безопасными при всех атаках, приведены на рис.4.

Рис.4. Четыре схемы безопасного хэширования

Отечественный стандарт хэш-функции

Российский стандарт ГОСТ Р 34.11-94 определяет алгоритм и процедуру вычисления хэш-функции для любых последовательностей двоичных символов, применяемых в криптографических методах обработки и защиты информации. Этот стандарт базируется на блочном алгоритме шифрования ГОСТ 28147-89, хотя в принципе можно было бы использовать и другои блочный алгоритм шифрования с 64-битовым блоком и 256-битовым ключом.

Данная хэш-функция формирует 256-битовое хэш-значение.

Функция сжатия Н_і = f (М_i, Н_i-1) (оба операнда М_і и Н_і-1 являются 256-битовыми величинами) определяется следующим образом:

1. Генерируются 4 ключа шифрования К_j, j = 1...4, путем линейного смешивания М_і, Н_і-1 и некоторых констант С_j.

2. Каждый ключ К_j, используют для шифрования 64-битовых подслов h_і слова Н_i-1 в режиме простой замены: Si = E_Kj(h_j).

Результирующая последовательность S₄, S₃, S₂, S₁ длиной 256 бит запоминается во временной переменной S.

3. Значение Н_і является сложной, хотя и линейной функцией смешивания S, М_i, и Н_i-1.

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

Н_n - хэш-значение последнего блока сообщения;

Z - значение контрольной суммы, получаемой при сложении по модулю 2 всех блоков сообщения;

L - длина сообщения.

Эти три переменные и дополненный последний блок М' сообщения объединяются в окончательное хэш-значение следующим образом:

Н = f (Z Å М', f (L, f(М', Н_n))).

Данная хэш-функция определена стандартом ГОСТ Р 34.11-94 для использования совместно с российским стандартом электронной цифровой подписи.

[Предыдущий раздел][Содержание][Следующий раздел]