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

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

ОГЛАВЛЕНИЕ

Следующая >>

Боб • Алиса: G^.
До некоторой степени это напоминает стандартный протокол Диф-
фи-Хеллмана без всяких подписей. Однако дело в том, что здесь
окончательный сеансовый ключ будет зависеть также от долговре­
менных ключей А и В.
Допустим, что Вы — Алиса. Тогда Вы знаете
А, J5, С, D.avL 7.
Пусть I обозначает половину битового размера порядка группы А,
например, если порядок группы Q ^ 2^^^, то Z = 160/2 = 80. Чтобы
определить сеансовый ключ, Алиса производит следующие операции:
1) преобразует С в целое число / ,
2) полагает SA — (i (mod 2^)) + 2\
3) преобразует D в целое число j ,
Глава 10, Распределение ключей, схемы подписей и хэш-функции

4) вычисляет ТА = {З (mod20) + 2^
5) находит НА = ^ -\- SA' ос^
6) определяет рл = (1)5^^)^^.
Боб делает то же, но со своей ключевой парой:
1) преобразует D в целое число / ,
2) полагает SB = (г (mod2^)) + 2^
3) преобразует С в целое число j ,
4) вычисляет Тв = {j (mod20) -h 2^
5) находит кв = S -{- SB • Р^
6) определяет рв = (СА^^)^^.
В результате, РА = Рв — общий секрет. Дабы убедиться, что ве­
личина/)д, найденная Алисой, совпадает с р ^ , вычисленной Бобом,
заметим, что SA = Тв vi^ SB = ТА- Поэтому


- ,5(7 + Зла) + /?Тл(7 + Зла) =
= <5(7 + Тва) + рЗвЬ + Тва) =
= 7(^ + Зв13) + аТв{6 + Звй =
= (7 + аТв)кв = logo ((СЛ^^)'*^) = logG(pB).

К р а т к о е содерж:ание главы

- Протокол Диффи - Хеллмана можно использовать для дости­
жения соглашения о сеансовом секретном ключе по открыто­
му каналу. Однако этот протокол восприимчив к атаке «че­
ловек посередине», поэтому нуждается в какой-нибудь форме
удостоверения подлинности переговаривающихся сторон.
- Цифровая подпись обеспечивает аутентификацию как для дол­
говременных, так и для краткосрочных целей. Ее применяют
в виде двух схем: либо подпись с приложением, либо подпись
с восстановлением сообщения.
- Используя алгоритм шифрования RSA в обратном направле­
нии, можно получить схему подписи с открытым ключом, но
необходимо комбинировать этот алгоритм с хэш-функциями,
чтобы добиться стойкости как для коротких, так и для длин­
ных сообщений.
- Для целей криптографии нужны односторонние, защищенные
от повторений хэш-функции. Такие функции препятствуют
10.7. Соглашение об аутентифицированпом ключе

атакам, направленным на фальсификацию цифровой подписи.
Благодаря парадоксу дней рождений, размер значений хэш-
функции должен по крайней мере вдвое превышать размер
первоначальной оценки вычислительных возможностей атаку-
юп1;его.
- DSA — алгоритм цифровой подписи, основанный на дискрет­
ных логарифмах. Он уменьшает размер подписи по сравнению
с RSA^ но работает медленнее. EC-DSA — вариант DSA., осно­
ванный на эллиптических кривых, являюш;ийся более эффек­
тивным, чем оригинал.
- Суш;ествуют и другие алгоритмы подписи с различными свой­
ствами, используюпще дискретное логарифмирование. Мы рас­
смотрели алгоритмы Шнорра и Нуберга-Руппеля.
- Другой путь распределения ключей, не требующий цифровой
подписи, состоит в применении системы MQV., которая предъ­
являет слабые требования к пропускной способности канала.
При этом происходит неявное удостоверение подлинности клю­
ча, о котором ведутся переговоры, с помош;ью комбинации
эфемерного ключа и долговременного ключа каждого из поль­
зователей.


Дополнительная литература
Информацию о более криптостойких схемах подписи, таких, как,
например, одноразовые подписи, подписи с завершением процесса
при ошибке, неоспоримые подписи, можно найти в книгах Стинсо-
на и Шнайера. В них также хорошо изложены хэш-функции и коды
аутентификации сообш;ений, хотя безусловно, самый лучший источ­
н и к — Я Л С.
В. Schneier. Applied Cryptography. Wiley, 1996.
D. Stinson. Cryptography: Theory and Practice. CRC Press, 1995.

Контрольные вопросы
10.1.1. Расскажите об атаке «человек посередине», направленной на
протокол Диффи - Хеллмана.

10.1.2. Почему алгоритмы цифровой подписи решают проблему, свя­
занную с атакой «человек посередине»?

10.1.3. Почему MAC не обеспечивает защиту от ренегатства?
284 Глава 10. Распределение ключей, схемы подписей и хэш-функции

10.1.4. Чем хэш-функции отличаются от блочных шифров?

10.1.5. Что означает каждое из следуюш;их свойств хэш-функций:
- зап];иш;енность от восстановления прообразов;
- заш;ищенность от повторений;
- заш;ип];енность от вторых прообразов ?

10.1.6. Опишите алгоритм подписи DSA и объясните, как в нем
обеспечивается стойкость.

10.1.7. В чем преимуп1;ества алгоритма Шнорра перед DSA1

10.1.8. Объясните различия и совпадения в протоколах Диффи-Хел-
лмана и MQV.

Лабораторные работы
10.2.1. Напишите программы, реализующие алгоритмы DSA., Шнор­
ра и Ниберга-Руппеля.

10.2.2. Реализуйте протокол MQV и сравните его со стандартной
реализацией схемы подписи Диффи - Хеллмана. С какой точ­
ки зрения протокол MQV более эффективен: пропускной спо­
собности или времени работы?

10.2.3. Разработайте на программном уровне основанные на элли­
птических кривых варианты алгоритмов DSA^ Шнорра, Ни­
берга-Руппеля, Диффи-Хеллмана и MQV. Что более эф­
фективно — Ваши варианты, или оригинальные, базируюш;и-
еся на проблеме дискретного логарифмирования в числовом
поле?

Упраж:нения
10.3.1. Обсудите утверждение: «криптография с открытым ключом
решает проблему распределения ключей с помош;ью аутенти-
фикационных методов и распределения открытых ключей.»

10.3.2. Покажите, что если пользователь применяет один и тот же
эфемерный ключ в алгоритме DSA J\JIA ПОДПИСИ двух разных
сообп];ений, то нападаюш;ий может раскрыть его долговре­
менный секретный ключ.

10.3.3. Предположим, что hi : {0,1}^^ • {0,1}'^ — хэш-функция,
заш;ищенная от повторений. Определим
10.7. Соглашение об аутентифицированном ключе 285


^^^ Г {о,1}4-—^{о,1Г,
\ xi\\x2^ hi{hi{xi)\\hi{x2)),
где Ж1, д:2 ^ {0,1}^^. Покажите, что /i2 тоже защищена от повторений.
10.3.4. Фиксируем открытый ключ (7V, Е) в алгоритме Д5Л и опре­
деляем хэш-функцию /г от сообщения М, состоящего из к
блоков: М = Mi...Mjt, сопоставляющую ему элемент Hk^
где Hi = Ml и
Щ= (Hf_i (modiV)) ©Mi, г = 2,...,А;.
Покажите, как найти повторяющиеся значения функции h.

10.3.5. Атака на функцию MAC, размер блоков и ключа в которой
равен п, в идеале требует 2^ операций. Рассмотрите следую­
щие хэш-функции, основанные на функциях MAC:
MAC = h{k\\M), MAC = h{M\\k).
Разработайте атаку, которая осуществляется менее чем за
2'^ операций.

10.3.6. Говорят, что схема распределения ключей обладает свойством
подтверждения, если каждая из сторон имеет гарантию, что
ее партнер пользуется тем же ключом, что и она. Продумай­
те, как придать это свойство протоколу MQV,
ГЛАВА 11
РЕАЛИЗАЦИЯ
ОПЕРАЦИЙ


Цели главы
• Показать, как работают алгоритмы возведения в степень.
• Объяснить, как эффективно реализовать арифметические опе­
рации в кольцах вычетов.
• Перечислить приемы, ускоряющие операции в алгоритмах RSA
HDSA.
• Объяснить, как эффективно реализовать конечные поля ха­
рактеристики 2.


11.1. Введение
в настоящей главе разбирается практическое воплощение крипто­
графических операций. Разговор будет идти, главным образом, об
операциях в криптосистемах с открытым ключом, поскольку на их
примере можно рассказать почти обо всех необходимых операциях.
Например, в RSA и DSA нам нужно возводить в степень по модулю
чисел, двузначное представление которых насчитывает более тыся­
чи знаков. Это означает, что нам нужно понять способы реализации
как арифметики остатков, так и алгоритмов возведения в степень.
Существует и другая причина фокусировки внимания на алго­
ритмах с открытым ключом: они работают существенно медленнее,
чем алгоритмы с симметричным ключом. Фактически эти алгорит­
мы могут выполняться настолько медленно, что их использование
может серьезно тормозить работу сети и серверов Интернета. Сле­
довательно, эффективная реализация операций весьма важна, если
заботиться об экономии средств.
Поскольку RSA наиболее доступна для понимания, мы сконцен­
трируемся именно на ней, хотя будем упоминать и о других схемах,
где работает специализированная техника вычислений. Будем гово­
рить в основном об алгоритмах, используемых в программном обес-
11.2. Алгоритмы возведения в степень

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


I 1.2. Алгоритмы возведения в степень
До сих пор в этой книге мы полагали, что вычисление а^ (mod с) —
простая операция. Она используется как в Д5Л, так и в систе­
мах, основанных на дискретном логарифмировании, таких как Эль-
Гамаль и DSA. В этом параграфе мы будем заниматься алгоритма­
ми возведения в степень, предполагая, что арифметические опера­
ции в кольце вычетов Z/iVZ реализуются достаточно эффективно.
В следующих разделах мы рассмотрим и эти операции.
Как уже отмечалось, основная операция в RSA и DSA — возве­
дение в степень по модулю целого числа, т. е.
М = С^ (modiV).
Прежде всего отметим, что не имеет смысла сначала находить Л = С^,
а потом определять его остаток от деления на N. Действительно,
поступая таким образом при вычислении
123^ (mod 511) = 28153 056 843 (mod 511) = 359,
мы получаем большой промежуточный результат — 28153 056 843.
В реальной ситуации, когда возводятся в степень числа с 1024 дво­
ичными знаками, промежуточный результат будет иметь 2^^^"^ • 1024
знаков. Только ц^ля записи таких чисел потребуется около
10301
ги­
габайт на винчестере.
Чтобы промежуточные результаты не были столь огромны, не­
обходимо вспомнить, что мы работаем по модулю N. Но даже при
этом стоит быть внимательным. Наивный подход к решению нашей
задачи привел бы к следуюш;им вычислениям:
X = 123,
х'^ = Х'Х (mod511) = 310,
х^ = Х'х'^ (mod511) =316,
х"^ = Х'Х^ (mod511) = 3 2 ,
х^ = Х'Х^ (mod511) =359.
На это уходит 4 умножения в кольце вычетов, что кажется прием­
лемым для нашего игрушечного примера. Но в обш;ем случае, при
Глава 11. Реализация операций

возведении в 1024-разрядную степень потребуется около 2^^^^^ таких
умножений. Если каждое произведение при этом осуществляется за
1 миллионную долю секунды, нам потребуется 10^^^ лет на осуще­
ствление операции расшифрования в алгоритме RSA.
Однако даже на нашем небольшом примерчике легко увидеть,
как можно было бы сократить количество умножений:
X = 123,
х^ = х-х (mod511) =310,
х^ ^х^ 'Х^ (mod 511) = 3 2 ,
х^ = Х'Х^ (mod511) = 359.
Здесь нам потребовалось только три произведения, а не 4, как рань­
ше. Обратите внимание на то, что двоичное представление числа 5
имеет вид: ^101Ь', т.е.
- это трехзначное число,
- его вес Хемминга^ равен h = 2.
Поэтому мы произвели 1 = /г — 1 умножение общего вида и 2 = < — 1
возведения в квадрат. Такой подсчет остается справедливым и в
общем случае: возведение в степень по модулю целого числа может
быть осуществлено с помощью
- h — 1 умножений и
- t — 1 возведения в квадрат,
где t — количество знаков в двоичном представлении показателя,
а /i — его вес Хемминга. Усредненный вес Хемминга целого числа
равен половине количества его двоичных знаков, т. е. t/2. Поэтому
среднее число умножений и возведений в квадрат при вычислении
экспоненты в кольце вычетов равно t + t/2 — 1. Это означает, что
при возведении в 1024-битовую степень потребуется не более 2048
умножений, а среднее число операций и того меньше — 1535.

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

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

ОГЛАВЛЕНИЕ

Следующая >>