<< Предыдущая

стр. 41
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

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

10.3.!• Семейство MD4
Несколько хэш-функций находят широкое применение. Все они по
своей природе итерационны. Назовем три из них: MD5^ RIPEMD-
160 и SHA-1, Алгоритм MD5 производит 128-битовые строки, в
то время как значения RIPEMD-160 и SHA-1 имеют длину в 160
битов. Недавно национальный институт стандартов и технологий
США предложил новые хэш-функции: SHA-256^ SHA-384 и SHA-
512^ значения которых — 256-, 384- и 512-битовые строки соответ­
ственно. Все они — обобщение более раннего и простого алгоритма,
который называется MD4' Семь основных алгоритмов семейства
MD4 представлены следующим списком:
- MD4^ состоящий из 3 раундов по 16 шагов в каждом со 128-
битовой выходной строкой.
- MD5^ насчитывающий 4 раунда по 16 шагов в каждом со 128-
битовой выходной строкой.
- SHA-1 включает в себя 4 раунда по 20 шагов в каждом. Длина
его выходных данных — 160 битов.
- RIPEMD-160 состоит из 5 раундов по 16 шагов в каждом и
имеет длину выходной строки в 160 битов.
- SHA-256 имеет 64 раунда по одному шагу, а длина его значе­
ния — 256 битов.
- SHA-512 состоит из 80 од пошаговых раундов и выдает строки
в 512 битов.
- SHA-384 практически идентичен SHA-512 за исключением то­
го, что его выход урезан до 384 битов.
10.3. Хэш-функции 269

Обсудим подробно MD4, поскольку остальные — более сложные
версии этого алгоритма. Оставим их изучение по доступной литера­
туре на усмотрение любознательного читателя. В MD4 участвуют
три поразрядные функции от трех 32-битовых переменных:
/(гл, г?, w) — {и Av) W {й Aw),
д{и, г;, w) = {и Av) V {и Aw) У {v А w).,
h{u.^v^w) = u®v ®w.
Ha протяжении всего алгоритма мы следим за текущим хэш-состо­
янием
(Я1,Я2,Яз,Я4)
32-битовых переменных, начальные значения которых равны
Hi = '67452301/i', Щ= '98BADCFEh',
Н2 = 'ЕРСВАВЪШ', Щ = '10325476/1'.
Существуют различные фиксированные константы (Vii Zi, Si), свои
для каждого раунда. Имеем

О, О ^ J ^ 15,
Vj = { '5Л827999/1', 16 ^ j < 31,
'QEDQEBAlh', 32 < j ^ 47.
Значения Zi и Sj приведены в следующих массивах:
zo...i5 = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15],
216...31 = [0,4,8,12,1,5,9,13,2,6,10,14,3,7, И , 15],
Z32..A7 = [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15],
S0...15 = [3,7,11,19,3,7,11,19,3,7,11,19,3,7,11,19],
S16...31 = [3,5,9,13,3,5,9,13,3,5,9,13,3,5,9,13],
S32...47 = [3,9,11,15,3,9,11,15,3,9,11,15,3,9, И , 15].
Поток данных состоит из 16 одновременно загружаемых слов в мас­
сив ХЦ] (о ^ J < 16). Затем мы выполняем следующие преобразо­
вания над каждым из 16 слов, внесенных в поток данных:

(А,В,CD) = (Н[1],Н[2,Н[3],Н[4]).
Выполнить первый раунд.
Выполнить второй раунд.
Выполнить третий раунд.
(Н[1],Н[2],Н[3],Н[4]) = (Н[1]+А, Н[2]+В, Н[3]+С, H[4]+D).
270 Глава 10. Распределение ключей, схемы подписей и хэш-функции

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


Подробности раундов приведены в следующем описании, где <^
обозначает побитывый циклический сдвиг влево:
- Раунд 1
For j = О to 15 do
l.t = A + f{B,C,D)+X[zj] + yj.
2. {A,B,C,D) = {D,t ^ Sj,B,C),
- Раунд 2
For j = 16 to 31 do
l,t = A-h g{B, C, D) + X[zj] + Vj.
2. (Л, Б , C, D) = {D,t<m: Sj, B, C),
- Раунд 3
For j = 32 to 47 do
l.t = A-\- h{B, C, D) + X[zj] + Vj,
2. (Л,Б,С,1)) = {D,t^Sj,B,C).

10.3.2. Хэ1п-функции и блочные ш и ф р ы
Хэш-функции можно строить с помощью п-битового блочного ши­
фра Ek- Есть несколько способов такого конструирования. Все они
используют постоянное открытое начальное значение IV. Некото­
рые схемы привлекают еще функцию ^, переводящую п-битовые
строки в ключи.
Сначала сообщение пополняется до нужной длины и разбивается
на группы жо, Ж1, . . . , xt^ длина которых совпадает с размером бло­
ков или длиной ключа используемого блочного шифра. Выбор раз­
мера групп зависит от точного определения хэш-функции, которую
мы собираемся строить. Значение конструируемой хэш-функции со­
впадает с окончательным значением Ht^ полученным итерацией сле­
дующего процесса:
Ho = IV, Hi = fixi,Hi^i).
Определение функции / , участвующей в итерациях, зависит от ис­
пользуемой схемы. Мы предложим Вашему вниманию три возмож­
ности, хотя есть и другие.
- Хэш-функция Матиаса-Мейера-Осиса
f{xi,Hi-i) = Eg(^Hi.i){xi) ® Xi.
10.4' Алгоритмы цифровой подписи 271

Хэш-функция Давиэса-Мейера
f{xi,Hi-i) = E^^{Hi.i) ® Щ^1,

Хэш-функция Миягучи-Пренила




10.4. Алгоритмы цифровой подписи
Мы уже рассказывали об одной из схем цифровой подписи, а именно
о схеме RSA. Можно спросить: зачем нужны еще какие-то схемы
подписей? Ответ разобьем на несколько утверждений:
- Что если кто-то вскроет алгоритм RSA или решит задачу раз­
ложения на множители?
- Алгоритм RSA неприменим в некоторых приложениях, посколь­
ку генерирование подписи с его помощью — слишком дорого­
стоящая операция.
- Сама /^б'Л-подпись очень велика, а в некоторых практических
приложениях требуется, чтобы подпись занимала мало места.
Один из алгоритмов, в котором учтены все эти возражения, на­
зывают алгоритмом цифровой подписи, или DSA (от английско­
го эквивалента: Digital Signature Algorithm). Иногда его именуют
стандартом цифровой подписи или DSS (Digital Signature Standard).
Оригинальная версия алгоритма использовала мультипликативную
группу Fp с большим простым числом Р , сейчас же повсеместно
пользуются группой эллиптической кривой. Такие методы обозна­
чают EC-DSA^ т.е. алгоритм цифровой подписи на эллиптических
кривых. Этот вариант DSA работает быстрее, и подпись, получен­
ная с его помощью, занимает места меньше, чем практически во
всех других алгоритмах подписи. Более того, и размер ключа в нем
сравнительно невелик.
Сначала мы опишем основной /^^Л-алгоритм, который работает
с конечными полями. Здесь криптостойкость зиждется на сложно­
сти дискретного логарифмирования в поле Fp.
DSA — алгоритм подписи с дополнением, в котором собствен­
но подпись состоит из двух 160-битовых целых чисел R и S. Число
R является функцией 160-разрядного случайного числа fc, которое
называют эфемерным ключом, изменяемым с каждым новым сооб­
щением. Число S — функция от сообщения, секретного ключа гг,
272 Глава 10. Распределение ключей, схемы подписей и хэш-функции

принадлежащего подписывающему сообщение лицу, числа R и эфе­
мерного ключа к.
Аналогично алгоритму Эль-Гамаль, здесь есть несколько пара­
метров домена, которые являются общими р,ля ряда пользователей.
Параметры домена в DSA открыты и очень похожи на параметры
домена в криптосистеме Эль-Гамаль. J\jiK их задания сначала фик­
сируется 160-битовое простое число Q, а затем выбирается такое
большое простое число F , лежащее между 2^^^ и 2^^^^, что Р — 1
делится на Q. Наконец, генерируется случайное число Н < Р и вы­
числяется
р-1


Если G = 1, то переходят к другому случайному Н до тех пор, пока
не получат G Ф 1, Этим обеспечивается выполнение следующего
условия: G — элемент группы Fp порядка Q, т. е.
С^ = 1 (modP).
После выбора параметров домена (Р, Q, G) каждый пользователь
генерирует свой собственный секретный подписывающий ключ ж,
удовлетворяющий неравенству Q < х < Q, Соответствующим от­
крытым ключом служит число У, вычисляемое по правилу
F = G^ (modP).
Обратите внимание на то, что процедура выбора пользовательской
ключевой пары существенно проще, чем в RSA^ поскольку она тре­
бует лишь одного возведения в степень в числовом поле.
Чтобы подписать сообщение М, пользователь осуществляет сле­
дующие шаги:
- вычисляет значение хэш-функции Н = h{M)^
- выбирает случайный эфемерный ключ О < А < Q,
:
- определяет
R={G^ (modP)) (modQ),

- находит


Подписью сообщения М служит пара (Л, 5), имеющая в общей слож­
ности 320 двоичных знаков.
]\ля проверки подписи (Р, S) на сообщении М делают так:
- вычисляют хэш-значение Н = h{M)^
- определяют А = H/S (modQ) и В = R/S (modQ),
10.4- Алгоритмы цифровой подписи

- находят
V = {G^Y^ (modP)) (modg),
где Y — открытый ключ автора сообщения.
- Подпись считается корректной тогда и только тогда, когда
V=Я
Приведем пример работы DSA^ выбрав малые параметры домена:
Q = 13, Р = 4Q + 1 - 53 и G = 16.
Предположим, что ключевая пара пользователя имеет вид я; = 3 и
Y = G^ (modP) = 15. Если мы хотим подписать сообщение с хэш-
значением iif = 5, то сначала нам нужно выбрать эфемерный ключ
к = 2 и найти
R = (G^ (modP)) (modQ) = 5,
S={H + xR)/k (mod Q) = 10.
Для проверки нашей подписи получатель определяет

А - I (modQ) = 7,
P - | ( m o d Q ) = 7,
V = {G^Y^ (modP)) (modQ) - 5.
Ввиду равенства V = R^ делаем вывод о корректности подписи.
Алгоритм DSA использует подгруппу в Fp порядка Q, поро­
жденную элементом G. Следовательно, задача дискретного лога­
рифмирования должна решаться в циклической группе (G) поряд­
ка Q. Для обеспечения криптостойкости нам необходимо потребо­
вать, чтобы
- Р > 2^^^, хотя, в целях предупреждения атаки, опирающие­
ся на решето в числовом поле, более благоразумно выбирать
Р > 21024.
- Q > 2^^^; это предотвратит атаки с использованием алгоритма
шаги младенца/шаги гиганта.
Следовательно, д^ля достижения грубого эквивалента стойкости 80-
битового алгоритма DES^ нам нужно оперировать с целыми числа­
ми, насчитывающими около 1024 двоичных знаков. В результате
DSA работает даже медленнее, чем RSA^ поскольку арифметиче­
ские операции в нем сложнее. Процедура проверки в RSA привлека­
ет лишь одно возведение в степень по модулю 1024-разрядного чи­
сла, а в алгоритме DSA процедура проверки предусматривает два
Глава 10. Распределение ключей, схемы подписей и хэш-функции

возведения в степень по модулю 1024-разрядного числа. Кроме то­
го, процедура подписания в DSA более сложная, поскольку при этом
нам нужно вычислять значение S.
Основная причина этих проблем кроется в том, что теоретиче­
ски DSA-2uiTOY>wTM должен работать в абелевых группах порядка
2^^^, но так как целые числа по модулю Р поддаются атакам с по­
мощью решета в числовом поле, на практике нам нужно работать с
группой элементов по 1024 знаков каждый, что очень сильно замед­
ляет работу.
К счастью, можно обобш;ить DSA на произвольную конечную
абелеву группу, в которой сложно решается задача о дискретном
логарифмировании. Мы можем использовать ту, где эта задача ре­
шается труднее всего, например, группу точек эллиптической кри­
вой над конечным полем.
Пусть А — циклическая группа, порожденная элементом G, Бу­
дем считать, что
- элемент G имеет простой порядок Q > 2^^^;
- дискретное логарифмирование по основанию G — труднораз­
решимая задача;
- суп];ествует открытая функция F : А —> Z/QZ.
Сведем различия в средах оперирования DSA и EC-DSA в табл. 10.1

Таблица 10.1.
Параметр DSA EC-DSA
А (G) с ?*р (Р) С Е{?р)
Ge?*p Р е Е(?р)
G
QX
Y [х]Р
F (modg) ж-координата Р по модулю Q


В обобщенной версии DSA каждый пользователь тоже генери­
рует секретный подписываюш;ий ключ к и вычисляет открытый по
формуле: Y = О^. Подпись получается в результате следуюш;его
процесса:
- Вычисляется хэш-значение Н = h{M).
- Выбирается эфемерный ключ О < к < Q.
- Определяется R = F{G^) ж S = {Н + xR)/k (modQ).
Подписью сообщения М служит пара (R^S),

<< Предыдущая

стр. 41
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>