- •2. Функции хеширования
- •2.1. Ключевые функции хеширования
- •2.2. Бесключевые функции хеширования
- •3. Электронная цифровая подпись
- •3 А. Схемы эцп с использованием дискретных логарифмов в простом конечном поле
- •Некоторые стандарты цифровой подписи
- •3 А.1. Федеральный стандарт сша.
- •3 А.2. Стандарт России – гост р34.10-94.
- •Введение
- •1 Область применения
- •2 Нормативные ссылки
- •3 Определения и обозначения
- •3.1 Определения
- •3.2 Обозначения
- •4. Общие положения
- •5. Математические соглашения
- •5.1. Математические определения
- •5.2. Параметры цифровой подписи
- •5.3. Двоичные векторы
- •6. Основные процессы
- •6.1. Формирование цифровой подписи
- •6.2. Проверка цифровой подписи
- •Приложение а (справочное) Дополнительные термины в области эцп
- •Приложение б (справочное) Контрольный пример
- •7B956de33814e95b7fe64fed924594dceab
- •Приложение в (справочное) Библиография*1
- •4. Режимы использования блочных шрифтов
2.1. Ключевые функции хеширования
Ключевая хеш-функция может быть построена на основе алгоритма блочного шифрования. Пусть – функция зашифрования -битового блока под управлением секретного ключа . Тогда значение n-битовой свертки ) может быть определено как
Данный способ вычисления хеш-значения в российском стандарте криптографической защиты данных ГОСТ 28147-89 называется режимом выработки имитовставки.
Ключевая хеш-функция может быть построена также на основе бесключевой хеш-функции . Секретный ключ , дополненный некоторым способом до размера, кратного длине блока , вставляется в начало и конец сообщения . Значение определяется как
.
Заметим, что ключ k непосредственно не пересылается, а присоединяется к только на время вычисления значения .
Другой способ вычисления хеш-значения определяется как
где .
2.2. Бесключевые функции хеширования
Бесключевую хеш-функцию можно построить, используя симметричный блочный шифр. Пусть – функция зашифрования -битовых блоков под управлением -битового ключа , а – сообщение, представленное в виде последовательности -битовых блоков , ,……, . Схема вычисления n-битового хеш-значения имеет следующий вид (см. рис.2):
где , , могут принимать значения , , или быть константами. Существует комбинации для выбора переменных , , , но установлено, что только комбинаций, перечисленных в таблице 1, приводят к безопасным хеш-функциям. Первые четыре из этих схем иллюстрируются на рис.3.
Рис.2. Обобщенная схема хеш-функции на основе блочного шифра с размером хеш‑значения, равным размеру блока
Таблица 1. Параметры схем безопасного хеширования (к рис.2)
Номер схемы |
|
|
|
Номер схемы |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Mi |
|
|
|
|
|
|
|
|
|
Для противодействия атакам на хеш-функцию необходимо, чтобы длина вырабатываемого хеш‑значения составляла по меньшей мере 128 битов. Увеличить размер хеш‑значения можно, используя, например, следующий прием:
Вычисляется ‑битовое хеш‑значение ).
Значение приписывается в начало сообщения и вычисляется новое хеш‑значение ).
Этап 2 повторяется для конкатенации и т.д.
В результате получается последовательность ‑битовых хеш‑значений, конкатенация которых дает хеш‑значение длины . Формально данная схема определяется как:
.
Из ‑битового значения можно извлечь хеш-значение требуемой длины , отбрасывая, например, последние битов. Другие способы увеличения длины хеш‑значения (в раза) представлены на рис.4, 5 (опущено).
Рис.3. Четыре безопасные хеш‑функции с размером хеш‑значения,
равным размеру блока
-
Алгоритм SHA-1 (Secure Hast Algorith) стандарта США на хеш‑функцию SHS (Secure Hash Standard) вычисляет 160‑битовые хеш‑значения для любого сообщения, длина которого меньше 264 битов. Вычисленное хеш‑значение используется затем в алгоритме DSA (Digital Signature Algorith), стандарта DSS (Digital Signature Standard), вычисляющем цифровую подпись сообщения.
Оригинальное сообщение дополняется до длины, кратной . Способ дополнения такой же, как и в MD5: сначала добавляется битовая комбинация так, чтобы общая длина в битах была сравнима с по модулю (операция дополнения выполняется всегда, даже если сообщение уже имело требуемую длину); затем к сообщению добавляется ‑битовое представление длины исходного сообщения.
(Замечание. В отличие от MD5 и RIPEMD-160 в SHA-1 используется обратный порядок байтов (big endian): наиболее значимый байт идет первым, т.е. занимает младшую адресную позицию. Это относится как к ‑битовому представлению длины исходного сообщения, так и к ‑битовым числам.)
Дополненное сообщение разбивается на ‑битовые блоки ,…, . Каждый блок представляется в виде массива из шестнадцати ‑битовых подблоков: . Вычисляемое хеш‑значение представляется в виде массива из пяти ‑битовых подблоков: .
Псевдокод алгоритма SHA‑1 представлен в табл. 9 (см. рис. 9 и 10). В алгоритме используются вспомогательные переменные: – массив из пяти ‑битовых подблоков, – массив из ‑битовых подблоков. Основные операции над ‑битовыми подблоками те же, что и в алгоритме MD5. Функции с ‑битовыми аргументами и значениями и ‑битовые константы определяются как (опущено)
Рис. 9. Элементарная операция SHA-1
Таблица 9. Псевдокод SHA‑1
h:=($67452301,$efcdab89,$98badcfe,$10325476,$c3d2e1fo); for i:=1 to N do { a:= h; for j:=0 to 15 do wj:= Mij; for j:=16 to 79 do wj:=rol1(wj-3 Å wj-8 Å wj-14 Å wj-16); for j:=0 to 79 do { a4:=rol5(a0) + F(a1,a2,a3) + a4 + wj + Cj; (a0,a1,a2,a3,a4):= (a4,a0,rol30(a1),a2,a3)}; h:= (h0 + a0,h1 + a1,h2 + a2,h3 + a3,h4 + a4)}.
|
Рис.10. Функция сжатия в SHA‑1 (обработка одного 512‑битового блока)
ГОСТ
Хеш‑функция, определенная в стандарте ГОСТ Р34.11‑94, вычисляет 256‑битовое хеш‑значение сообщения произвольной длины. Данное хеш‑значение используется для формирования и проверки электронной цифровой подписи в стандарте ГОСТ Р.10‑94.
Исходное сообщение разбивается на ‑битовые блоки . Если последний блок не является полным, то он дополняется (слева) нулями до требуемого размера. В вычислении хеш‑значения используются два дополнительных ‑битовых блока: , в котором записывается длина исходного сообщения (до дополнения), и , в котором формируется контрольная сумма.
Хеш‑значение вычисляется по схеме (см.рис.11а):
h:= h0; Z:= 0;
for i:= 1 to N do {h:= f(Mi,h); Z:= (Z+Mi) mod 2256};
h:= f(L,h); h:= f(Z,h).
Здесь – ‑битовый стартовый вектор хеширования, на выбор которого в стандарте ограничений не накладывается.
Используемая при вычислении значения функция сжатия определяется следующим образом. Пусть
– ‑битовый блок, где – конкатенация экземпляров набора . В определении используется функции , и с -битовыми аргументами и значениями:
Функция с аргументом , где – ‑битовые блоки, задана как
Функция P с аргументом , где – байты, задана как
,
где , .
Функция T с аргументом , где – ‑битовые блоки, задана как
,
где v=w1Åw2Åw3Åw4Åw13Åw16.
Пусть обозначает функцию зашифрования 64‑битового блока под управлением ‑битового ключа согласно ГОСТ 28147‑89 (принципиально можно использовать любой другой алгоритм зашифрования с ‑битовым блоком и ‑битовым ключом). При таких обозначениях функция определяется как (см. рис. 11б):
f(m,h)º{
U:=m; V:=h; (X4,X3,X2,X1):= m;
K4:=P(U Å V);
U:= S(U); V:= S2(V); K3:= P(U Å V);
U:= S(U)Å c; V:= S2(V); K2:= P(U Å V);
U:= S(U); V:= S2(V); K1:= P(U Å V);
W:= (EK4(X4),EK3(X3),EK2(X2),EK1(X1));
f:= T61(h Å T(m Å T12(W)))}.
Здесь , .
(а)
(б)
Рис.11. Функция хеширования в ГОСТ Р34.11-94:
(а) общая схема; (б) функция сжатия