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

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

ОГЛАВЛЕНИЕ

Следующая >>

- Ввиду существования алгоритма Полига-Хеллмана трудную
задачу о дискретном логарифмировании следует ставить в груп­
пах, чей порядок имеет большой простой делитель.
- Существование обш;их алгоритмов, таких, например, как шаги
младенца/шаги гиганта, свидетельствует о том, что для обес­
печения той же криптостойкости, как в 80-битовом блочном
шифре, нужно выбирать группы с простым делителем поряд­
ка группы, насчитываюш;им не менее 160 бит.
- Шаги младенца/шаги гиганта — общий алгоритм, чье время
работы ограничено сверху числом y/q^ где q — большой про­
стой делитель порядка группы Л, в которой ставится задача
дискретного логарифмирования. Однако этому методу необ­
ходимо 0{y/q) памяти.
9.6. Специальные методы для эллиптической кривой

- Существует несколько техник, идеи которых восходят к Дол­
лар ду, основывающихся на детерминированном случайном блуж­
дании по группе. Это общие методы, не требующие много ком­
пьютерной памяти, и решающие задачу дискретного логариф­
мирования за среднее время 0{y/q).
- Для конечных полей существует алгоритмы вычисления пока­
зателей за суб-экспоненциальное время. Это означает, что для
постановки трудноразрешимой задачи дискретного логариф­
мирования необходимо выбирать большие конечные поля ?pt с

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


Дополнительная литература
Написано множество хороших обзоров проблемы дискретных ло­
гарифмов. Я бы рекомендовал Мак-Карлея и Одлыжко. Однако эти
статьи лишь мимоходом касаются проблемы логарифмирования на
эллиптической кривой. Для пополнения своих знаний по последней
проблеме Вы можете консультироваться с книгой Коблица.
N. Koblitz, А. Menezes and S. Vanstone. The state of elliptic curve
cryptography. Designs Codes and Cryptography, 19, 173-193, 2000.
K. McCurley. The discrete logarithm problem. In Cryptology and Com­
putational Number Theory^ Proc. Symposia in Applied Maths, Volume
42, 1990.
A. Odlyzko. Discrete logarithms: The past and the future. Designs Codes
and Cryptography, 19, 129-145, 2000.

Контрольные вопросы
9.1.1. Какие выводы в отношении криптографии можно вывести из
алгоритма Полига-Хеллмана?

9.1.2. Как работает алгоритм шаги младенца/шаги гиганта?

9.1.3. Какие проблемы возникают при реализации метода шаги мла­
денца/шаги гиганта, и как они преодолеваются с помоп1;ью
р-метода Полларда?
Глава 9. Дискретные логарифмы

9.1.4. Какие уроки в отношении криптосистем можно извлечь из
существования /9-метода Полларда?

9.1.5. Какие выводы следуют из суп1;ествования алгоритмов вычи­
сления показателей в конечных полях с точки зрения крипто­
графии?

9.1.6. Обсудите утверждение о том, что эллиптические кривые пред­
лагают более высокую криптостойкость на один бит, нежели
конечные поля.

Лабораторные работы
9.2.1. Реализуйте р-метод Полларда и поэкспериментируйте с раз­
ными определениями детерминированных случайных блужда­
ний, которые встречались в тексте. Какой из них наиболее
эффективен? (Эффективность здесь означает более быстрое
в среднем решение задачи о дискретных логарифмах.)

9.2.2. Разработайте программу для параллельного метода Поллар­
да решения задачи дискретного логарифмирования в конеч­
ных полях. Насколько сложную задачу дискретного логариф­
мирования Вы сможете решить с помош;ью этой программы
в течение 24 часов?

Упражнения
9.3.1. В тексте главы были определены три случайных блуждания,
по одной на каждый из методов: р, Л и параллельный мето­
ды Полларда. Можно ли использовать эти псевдо-случайные
последовательности ^^ля разных алгоритмов? Какие преиму-
ш;ества (недостатки) возникают при использовании в указан­
ных методах случайных блужданий, разработанных для дру­
гих алгоритмов?

9.3.2. Используя лишь карманный калькулятор, найдите число х^
удовлетворяющее уравнению 3^ = 5 (modp), где р = 2 3 •
101 • 103 • 1072 + 1.
ГЛАВА IО
РАСПРЕДЕЛЕНИЕ
КЛЮЧЕЙ,
СХЕМЫ ПОДПИСЕЙ
И ХЭШ-ФУНКЦИИ

Ц е л и главы
• Ввести протокол распределения ключей Диффи-Хеллмана.
• Объяснить все необходимые А,ЛЯ цифровых подписей понятия.
• Рассказать о двух наиболее широко употребляемых алгорит­
мах подписей, а именно RSA и DSA,
• Ввести и объяснить все необходимое для криптографических
хэш-функций.
• Рассказать о некоторых других алгоритмах подписей и тех­
нике распределения ключей, обладаюп1;их интересными свой­
ствами.


10.1. Распределение ключей Диффи-Хеллмана
Напомним, что основное препятствие к быстрому шифрованию боль­
шого количества данных с использованием блочного или поточного
шифра, — это сложная проблема распределения ключей. Мы уже по­
знакомились с некоторыми методами ее решения: с помощью прото­
колов, базируюп];ихся на симметричном шифровании или с исполь­
зованием алгоритма с открытым ключом для генерирования и пе­
редачи сеансового ключа заинтересованным партнерам. Однако все
эти методы не лишены недостатков. Например, протоколы с сим­
метричным ключом слишком сложны для анализа и требуют по­
стоянно работаюп1;их долговременных ключей для обмена закрытой
информацией между пользователями и центром доверия.
Говорят, что криптосистема обладает прогрессивной секретно­
стью^ если компрометация долгосрочного секретного ключа в какой-
Глава 10. Распределение ключей, схемы подписей и хэш-функции


то момент времени не приводит к вскрытию тайны прошлой пере­
писки, осуш;ествлявшейся с использованием этого ключа. Распреде­
ление ключей посредством систем с открытым ключом не облада­
ет прогрессивной секретностью. Чтобы понять, почему это важно,
предположим, что Вы шифруете видеопередачу сеансовым ключом,
который был получен с помощью открытого ключа RSA адресата.
Допустим, что в не очень отдаленном будущем секретный ключ Ва­
шего адресата будет вскрыт. В этот момент будет дешифрована
и Ваша секретная видеопередача, если, конечно, атакующий озабо­
тился ее вовремя записать.
Кроме того, при передаче ключей подразумевается, что получа­
тель доверяет отправителю в его способности генерировать хоро­
ший сеансовый ключ. Иногда у получателя может возникнуть же­
лание внести свои собственные случайные изменения в сеансовый
ключ. Однако это можно сделать только если обе переписывающие­
ся стороны находятся на связи в один и тот же момент времени. Пе­
редавать же ключ, вообще говоря, удобнее, когда в сети находится
только посылающий информацию, например, с помощью электрон­
ной почты.
Проблема распределения ключей была решена в той же осново­
полагающей работе Диффи и Хеллмана, где разработана схема ши­
фрования с открытым ключом. Их протокол распределения ключей,
названный протоколом Диффи - Хеллмана обмена ключей, позволя­
ет двум сторонам достигнуть соглашения о секретном ключе по
открытому каналу связи без предварительной личной встречи. Его
стойкость основывается на трудноразрешимой проблеме дискрет­
ного логарифмирования в конечной абелевой группе А.
В своей работе авторы предлагали использовать группу А — Fp,
но на сегодняшний день многие эффективные версии этого прото­
кола берут за основу группу эллиптической кривой. Такие версии
обозначают аббревиатурой EC-DH^ возникшей от сокращений ан­
глийских терминов: Elliptic Curve и Diffie-Hellman. Основные со­
общения в протоколе Диффи-Хеллмана представлены следующей
диаграммой^:
Алиса Боб
а G^ G^
G^ G^ b

^Напомню, что строчными знаками обозначаются секретные элементы прото­
кола, а прописными — открытые. — Прим. перев.
10.1. Распределение ключей Диффи-Хеллмапа

Каждая из сторон обладает своим кратковременным секретным клю­
чом а и b соответственно, с помощью которых они могут догово­
риться об общем сеансовом ключе:
- Алиса может вычислить к = (G^)^, поскольку она знает а и
посланное Бобом сообщение G^,
- Боб тоже может определить к = (G^)^, поскольку ему известно
Ь, а G^ он узнает от Алисы.
Атакующая Ева может перехватить сообщения G^ и G^ и попы­
таться восстановить секретный ключ, равный к = G^^, что являет­
ся в точности задачей Диффи - Хеллмана, рассмотренной в главе 7.
Следовательно, криптостойкость этого протокола основывается не
на дискретном логарифмировании, а на сложности решения задачи
Диффи - Хеллмана. Напомним, что, возможно, задача Диффи-Хел­
лмана более легкая, чем дискретное логарифмирование, хотя в это
с трудом верится, когда речь идет о группах, традиционно исполь­
зуемых в реальных протоколах.
Обратите внимание на то, что протокол Диффи - Хеллмана мо­
жет нормально работать и в режиме онлайн (когда обе стороны
вносят свои поправки в вырабатываемый ключ), и в режиме оф­
флайн (когда один из партнеров использует долговременный ключ
вида G^ вместо кратковременного). Значит, с помощью протоко­
ла Диффи - Хеллмана можно как договариваться о ключах, так и
менять их.
Приведем простой пример. Заметим, что для практических це­
лей выбирают ?р с Р ^ 2^^^"^, но мы в качестве параметров возьмем
F = 2147483 659 и G - 2.
На диаграмме изображен возможный обмен сообщениями в прото­
коле Диффи - Хеллмана:
Алиса Боб
а = 12 345 Ь = 654 323
Л - G^ = 428 647 416 А = 428 647 416
В = 450 904 856 В = G^ = 450 904 856
Общий ключ вычисляется по формулам:
А^ = 428 647 416^^^ ^^^ (modP) = 1333 327162,
В"" = 450 904856^^^"^^ (modP) = 1333 327162.
Обратите внимание на то, что в протоколе передаются элементы
Глава 10. Распределение ключей, схемы подписей и хэш-функции

выбранной абелевой группы. Следовательно, при использовании Fp
затраты на передачи составят около 1024 бит в каждом направле­
нии, поскольку Р ^ 2^^^^. Однако если используется группа элли­
птической кривой E{?Q)^ МОЖНО брать Q « 2^^^ и снизить затраты
на передачу сообщений до 160 бит на сообщение. Кроме того, воз­
ведение в степень на эллиптической кривой осуществляется более
эффективно, чем в числовом поле.
Для «игрушечного» примера протокола EC-DH возьмем эллипти­
ческую кривую, задаваемую уравнением
Е: Y^ = X^ + X-3
над полем Figg. Пусть элемент G имеет координаты (1,76). Тогда
возможные сообщения протокола имеют вид:
Алиса Боб
а = 23 Ь = 86
А = [a]G = (2,150) А = (2,150)
В = (123,187) В = [b]G = (123,187).
Общим ключом служит Х-координата точки, вычисляемой следую­
щим образом:
[Ь]А = [86](2,150) = (156,75),
[а]В = [23](123,187) = (156,75).
Общий ключ здесь — 156. Кроме того, вместо полной точки кри­
вой можно передавать сжатую точку, что существенным образом
скажется на времени передачи.
Итак, задача распределения ключей кажется решенной. Однако
остается важная проблема: откуда Вы знаете с кем Вы договарива­
етесь о сеансовом ключе? У Алисы нет оснований ^\ля уверенности,
что она переписывается именно с Бобом. Это может привести к сле­
дующей атаке, которая условно называется «человек посередине»:
Алиса Ева Боб
а &"
G^ . т


п G"
G^ 6
10.2. Схемы цифровой подписи

При этом
- Алиса договаривается о ключе с Евой, думая, что переписыва­
ется с Бобом;
- Боб ведет переговоры о ключе с Евой, считая, что его корре­
спондент — Алиса;
- Ева может изучать сообщения, т.к. они проходят через нее
как через коммутатор. Поскольку она не вносит изменений в
открытый текст, ее действия не могут быть обнаружены.
Итак, можно сделать вывод о том, что самого по себе протокола
Диффи - Хеллмана не достаточно д^ля обеспечения секретности рас­
пределения ключей.


10.2. Схемы цифровой подписи
Одна из возможностей пресечь атаку на протокол Диффи - Хеллмана,
описанную в конце предыдущего параграфа, заключается в визи­
ровании сообщений. В этом случае обе стороны доподлинно знают,
с кем ведут обмен сообщениями. Подписи — важнейший момент в
криптографии с открытым ключом. Они были предложены Диффи
и Хеллманом все в той же статье 1976 года, но первая практиче­
ская разработка подписи принадлежит Ривесту, Шамиру и Адле-
ману. Движущая пружина подписей в криптографии с открытым
ключом изображена на следующей схеме:
СООБЩЕНИЕ + секретный ключ Алисы = ПОДПИСЬ,
СООБЩЕНИЕ + ПОДПИСЬ + ОТКРЫТЫЙ КЛЮЧ АЛИСЫ =

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

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

ОГЛАВЛЕНИЕ

Следующая >>