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

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

ОГЛАВЛЕНИЕ

Следующая >>

- Распределение секретных ключей — основная проблема, свя­
занная с симметричными шифрами.
- Для распределения ключей по нескольким каналам можно ис­
пользовать схему порогового разделения секрета.
Глава 6. Распределение симметричных ключей

Многие существующие протоколы распределения ключей при­
бегают к посредничеству третьего лица (центра доверия) и
симметричным алгоритмам шифрования. Эти протоколы тре­
буют предварительной договоренности о долговременных клю­
чах р^ля обмена информацией клиентов с центром доверия и,
иногда, синхронизации часов.
Для анализа протоколов разработаны всевозможные аппара­
ты. Наиболее важным из них считается BAN-лотжкь.. Она по­
могает вычленить четкие предположения и проблемы, связан­
ные с протоколом.


Дополнительная литература
Удачное введение в современные схемы разделения секрета мож­
но найти в одиннадцатой главе книги Стинсона. Статья Барроуза,
Абади и Нидхейма — легко читаемое введение в 5Л#-логику с при­
мерами анализа протоколов распределения ключей. Многое из рас­
сказанного в этой главе основывается на этой работе.
М. Burrows, М. Abadi and R. Needham. A Logic of Authentication.
Digital Equipment Corporation, SRC Research Report 39, 1990.
D. Stinson. Cryptography: Theory and Practice. CRC Press, 1995.

Контрольные вопросы
6.1.1. Что собой представляет проблема распределения ключей?

6.1.2. Что такое схема порогового разделения секрета с порогом tl

6.1.3. Как числовые вставки используются в протоколах этой гла­
вы? Какие стороны безопасности протоколов они обеспечи­
вают?

6.1.4. Объясните значения следующих символов 5ЛЛ^-логики:
Р\ =Х, Р<Х и Р| - X

6.1.5. Расскажите, почему перечисленные ниже правила вывода име­
ют силу постулатов.
Правило о значении сообщения:

А\ =АЛ^В,А<{Х}К
А\=В\ ^Х
6.3. Формальные методы проверки протоколов 181

Правило проверки уникальных числовых вставок:
А\ =#Х,А\ = В\ ^Х
А\ шВ\ =Х
Правило юрисдикции:
А\ =В\ ^Х,А\ =В\ =Х
А\ =Х

6.1.6. Почему в протоколе Нидхейма-Шредера мы не посьмаем в
качестве пятого сообщения сообщение вида:



Упражнения
6.2.1. Просмотрите еш;е раз наш анализ протокола широкоротой
лягушки и осознайте, какие постулаты 5ЛЛ^-логики исполь­
зовались на каждом из этапов анализа.

6.2.2. Докажите, что интерполяционный метод Лагранжа действи­
тельно раскрывает секретный ключ схемы Шамира разделе­
ния секрета.

6.2.3. Алиса и Боб знают об абсолютной стойкости одноразового
шифр-блокнота, но не хотят мучиться со всеми перепития­
ми процедуры распределения ключей. Поэтому они разраба­
тывают свой протокол, основанный на одноразовом шифр-
блокноте. При этом Алиса шифрует сообш;ение т и пересы­
лает его Бобу. Как Алиса, так и Боб вычисляют свой поток
ключей, т. е. Алиса знает только свой ключ а, а Боб — только
свой Ь, Обмен сообш;ениями происходит по схеме:
А —> В : Ai = т®а,
В — > А : Bi = Ai®b,
А —^ В : А2 = Bi®a.
Покажите, что после такого обмена информацией, Боб смо­
жет расшифровать сообш;ение т , вычислив
А2®Ь.
Докажите, также, что Ева, т. е. противник, тоже в состоянии
прочесть оригинальное сообщение т.
ЧАСТЬ III


КРИПТОСИСТЕМЫ
с ОТКРЫТЫМ ключом
и подписи


Техника шифрования с открытым ключом, разработанная А^ЛЯ ре­
шения проблемы распределения ключей и аутентификации, имеет
много преимуществ перед симметричным шифрованием. Главное из
них состоит в том, что стороны, даже не подозревавшие о суш;ество-
вании друг друга до первого письма, могут успешно обмениваться
информацией, зашифрованной с помош;ью криптосистемы с откры­
тым ключом. Кроме того, она дает возможность сторонам подпи­
сывать сообш;ения, такие как электронные заказы или финансовые
поручения. В результате шифрование данных с открытым ключом
обеспечивает суш;ествование технологий электронной торговли.
ГЛАВА 7
ОСНОВНЫЕ
АЛГОРИТМЫ
ШИФРОВАНИЯ
С ОТКРЫТЫМ
ключом
Ц е л и главы
• Узнать о шифровании с открытым ключом и трудных мате­
матических задачах, на которых оно основывается.
• Понять алгоритм RSA и условия его криптостойкости.
• Разобраться в криптосистеме Эль-Гамаль.
• Узнать о шифрующем алгоритме Рабина.


7.1. Криптография с открытым ключом
Напомним, что в симметричной криптографии каждая из перепи-
сываюш;ихся сторон должна иметь копию общего секретного ключа,
что создает сложнейшую проблему управления ключами. В крипто­
системах, о которых пойдет речь в этой главе, используются два
ключа: открытый и секретный.
Открытый ключ может быть опубликован в справочнике наря­
ду с именем пользователя. В результате любой желающий может
зашифровать с его помощью свое письмо и послать закрытую ин­
формацию владельцу соответствующего секретного ключа. Расши­
фровать посланное сообщение сможет только тот, у кого есть се­
кретный ключ. Более точно, имеют место преобразования:
сообщение -h ОТКРЫТЫЙ КЛЮЧ АЛИСЫ = ШИФРОТЕКСТ
ШИФРОТЕКСТ -h секретный ключ Алисы = сообщение.
Таким образом, каждый может послать Алисе секретную инфор­
мацию, воспользовавшись ее открытым ключом. Но только Алиса
Глава 7. Основные алгоритмы шифрования с открытым ключом

в состоянии расшифровать сообщение, поскольку лишь у нее есть
соответствующий секретный ключ.
Причина работоспособности таких криптосистем заключается в
односторонней математической связи, существующей между двумя
ключами, при которой информация об открытом ключе никак не
помогает восстановить секретный, но владение секретным ключом
обеспечивает возможность расшифровывать сообщения, зашифро­
ванные открытым. На первый взгляд такая связь кажется странной,
и р,ля ее понимания требуется определенное время и умственные уси­
лия. Идея криптографии с открытым ключом впервые появилась в
1976 г. в революционной работе Диффи и Хеллмана «Новые напра­
вления в криптографии». Но только год спустя была опубликована
первая (и наиболее успешная) криптосистема с открытым ключом,
а именно, RSA,
В предыдущем абзаце описана «официальная» история возникно­
вения криптографии с открытым ключом. Однако в конце 1990-ых
годов появилась неофициальная версия освещения событий. Оказа­
лось, что в 1969 году, более чем за пять лет до публикации основопо­
лагающей работы Диффи и Хеллмана, Джеймс Эллис, работающий
на центр связи Британского правительства (GCHQ), открыл кон­
цепцию криптографии с открытым ключом (или несекретное ши­
фрование, как он ее называл) как средство решения проблемы рас­
пределения ключей. Впрочем, Эллис, как и Диффи с Хеллманом, не
смог разработать в деталях соответствуюшую криптосистему.
Проблема создания работающего алгоритма шифрования с от­
крытым ключом была решена новым сотрудником GCHQ по имени
Клиффорд Кокс в 1973 году. В течение одного дня Кокс разработал
систему, которая по существу, является алгоритмом RSA^ за целых
четыре года до Ривеста, Шамира и Адлемана. В 1974 году другой
служащий GCHQ, Малькольм Уильямсон, изобрел концепцию алго­
ритма (обмена ключом) Диффи-Хеллмана, к которому мы обратим­
ся в главе 10. Таким образом, к 1974 году Британская служба безо­
пасности уже имела основную технику криптографии с открытым
ключом.
В основе алгоритма шифрования с открытым ключом лежит на
удивление мало идей. Этим и объясняется близость алгоритмов,
найденных как Эллисом, так и Диффи с Хеллманом, к алгоритму
RSA. Малое количество идей объясняется необходимостью найти
какое-нибудь легко осуществимое на стадии шифрования матема­
тическое преобразование, которое сложно было бы обратить (без
знания специальной секретной информации) для реализации вто-
1,2. Односторонние функции

рой стадии алгоритма, т. е. расшифрования. Преобразование, обла­
дающее указанным свойством, называется односторонней функцией
или функцией-ловушкой.^ поскольку в ее дверь войти легко (заши­
фровать данные), а вот выйти без ключа довольно проблематично.
Придумать такую функцию на пустом месте довольно непросто,
но, к счастью, есть некоторый набор широко известных и всесто­
ронне изученных односторонних функций. К ним относятся задача
разложения целых чисел на множители, проблема вычисления дис­
кретных логарифмов или вычисление квадратных корней по моду­
лю составного числа. В следующем параграфе, предваряя рассказ об
алгоритмах шифрования с открытым ключом, мы познакомимся с
примерами односторонних функций. Однако они являются односто­
ронними только в вычислительном отношении, т. е. имея достаточ­
но большие компьютерные мощности, их вполне можно обратить,
причем быстрее, чем найти секретный ключ в результате полного
перебора.


7.2. Односторонние функции
Наиболее важная односторонняя функция, используемая в крипто­
графии с открытым ключом, — это разлоэюение на мнооюители или
факторизация целых чисел. Под разложением на множители цело­
го числа понимают его представление в виде произведения простых
делителей, например,
10 = 2 • 5,
60 = 2^ • 3 • 5,
2^1^ - 1 = 3391 • 23 279 • 65 993 • 1868 569 • 1066 818 132 868 207.
Определение множителей является очень трудоемкой вычислитель­
ной операцией. Для оценки сложности алгоритма, раскладывающего
целое число N на простые множители, часто используют функцию
L ^ ( a , / 3 ) - e x p ( ( / 3 + o(l))(ln7V)^(lnln7V)^-^).

Обратите внимание на то, что если алгоритм, раскладывающий на
множители целое число, имеет сложность О(1/дг(0,/3)), то ему требу­
ется полиномиальное время на работу (напомним, что размер зада­
чи на входе — InN), Однако при сложности алгоритма 0(1/дг(1,^))
ему А^ля работы потребуется уже экспоненциальное время. Таким
образом, скорость роста функции Ьм{а^Р) при О < а < 1 лежит
между полиномиальной и экспоненциальной. Поэтому про алгоритм
Глава 7. Основные алгоритмы шифрования с открытым ключом

со сложностью 0{Ь^{а^/3)) при О < а < 1 говорят, что он требу­
ет суб-экспоненциального времени. Заметим, что умножение, т.е.
процесс обратный к разложению на множители, — очень простая
операция, требующая времени меньше, чем О(Хдг(0,2)).
Существует несколько методов факторизации числа N = р - q с
простыми р и q. Некоторые из них мы будем обсуждать в следующей
главе, а сейчас лишь назовем наиболее известные.
- Пробное деление. В этом алгоритме для всех простых чисел
р^ не превосходящих проверяется условие N/p G Z. Ясно,
что такой подход близок к полному перебору и имеет экспо­
ненциальную сложность LN{1^ 1).
- Метод эллиптической кривой хорошо работает, если один из
простых множителей р не превосходит 2^^. Его сложность оце­
нивается как Lp(l/2,c), т.е. она суб-экспоненциальна. Заме­
тим, что оценка выражена через неизвестный простой дели­
тель. Так что, если N — произведение двух сильно отличаю­
щихся друг от друга простых чисел, то метод эллиптической
кривой может оказаться весьма эффективным.
- Квадратичное решето^ вероятно, наиболее быстрый способ
разложения чисел, лежащих между 10^^ и 10^^^. Его сложность

- Квадратичное решето в числовом поле, В настоящее время
это наиболее успешный метод для чисел, насчитывающих 100 и
более десятичных знаков. С его помощью можно разлагать на
множители числа до 10^^^ ^ 2^^^, а его сложность оценивается
как Ьдг(1/2,1).
Существует ряд других сложных задач, связанных с фактори­
зацией, которые используются для разработки криптосистем с от­
крытым ключом. Предположим, дано число N = p-q^ но не известен
ни один из его простых делителей. Возникают четыре основных за­
дачи:
- Факторизация: найти делители р и q числа N = р - q.
- Задача RSA: даны числа С и ?", последнее из которых удовле­
творяет соотношению:
Я0Д{Е,{р-1){д-1)) = 1.
Требуется найти такое число ш, что
m ^ = C(modiV).
7.2, Односторонние функции

- Тест на квадратичный вычет,: определить, является ли дан­
ное число А полным квадратом по модулю N,
- Извлечение квадратных корней: дано такое число А, что
А^х'^ (modTV);
нужно вычислить X.
Другой важный класс задач связан с дискретным логарифмиро­
ванием. Пусть (G, •) — конечная абелева группа, например, муль­
типликативная группа конечного поля или эллиптическая кривая
над конечным полем. Проблема вычисления дискретных логарифмов
[ПДЛ) состоит в определении целого числа ж, которое при данных
А^ В ^ G удовлетворяет соотношению
А"" = В.

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

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

ОГЛАВЛЕНИЕ

Следующая >>