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

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

ОГЛАВЛЕНИЕ

Следующая >>

Говоря нестрого, х = l o g ^ S , отсюда и название. Для некоторых
групп G такая задача довольно проста. Например, если G — груп­
па целых чисел по модулю N по сложению, то в ПДЛ нам надо
по известным А, S G Z/NZ найти решение уравнения х - А = В.
Как мы уже видели в первой главе, существуют простые методы,
основанные на расширенном алгоритме Евклида, проверяющие раз­
решимость такого уравнения и вычисляющие его корень.
Для других групп, однако, эта задача более сложная. Например,
в мультипликативной группе конечного поля наилучший из извест­
ных алгоритмов, решающий проблему дискретного логарифмиро­
вания, — это метод квадратичного решета в числовом поле. Слож­
ность вычисления дискретных логарифмов в этом случае оценивает­
ся как 1/дг(1/3,с), где с — некоторая константа, зависящая от типа
поля, например, от его характеристики.
Для групп, подобных эллиптической кривой, задача дискретно­
го логарифмирования еще более трудна. Наилучший из доступных
на сегодняшний день методов, вычисляющих дискретные логариф­
мы над общей эллиптической кривой над полем F^, называется р-
методом Полларда. Его сложность — y/q = 1/^(1,1/2). Следователь­
но, это в точности экспоненциальный алгоритм. Поскольку зада­
ча дискретного логарифмирования в случае эллиптической кривой
сложнее аналогичной задачи для мультипликативной группы конеч­
ного поля, мы можем использовать группы не очень большого по­
рядка, что дает преимущества в размере ключа. Поэтому крипто­
системы, основанные на эллиптической кривой, как правило, рабо­
тают с малым ключом, около 160 бит, в то время как системы, от-
Глава 7. Основные алгоритмы шифрования с открытым ключом

талкивающиеся от разложения на множители или вычисления дис­
кретных логарифмов в конечных полях, используют ключи в 1024
бита.
С проблемой дискретного логарифмирования тоже связано не­
сколько близких задач. Для их формулировки предположим, что да­
на конечная абелева группа (G, •) и ее элемент А е G,
- ПДЛ — задача дискретного логарифмирования, о которой мы
говорили выше. А именно, по данным А^ В е G найти такой
X, что В — А^.
- ЗДХ — задача Диффи-Хеллмана, которая состоит в следую­
щем: даны элементы А ^ G^ В = А^ 1л, С = АУ\ требуется
вычислить D — А^У,
- ПВДХ — проблема выбора Диффи-Хеллмана. Дано:
AeG, Б = Л^, С = АУ и D = A'-
требуется определить, является ли z произведением z = х - у.
Важно знать взаимосвязь всех этих сложных задач, в частности
нужно уметь оценивать сложность одной задачи по сравнению с дру­
гой. Допустим, например, что у нас есть две задачи: А и Б , причем
предполагается наличие эффективного алгоритма (оракула)^ реша­
ющего задачу В. Если эти задачи действительно близки по слож­
ности, то мы могли бы свести задачу А к задаче В и, опираясь на
оракул, решающий вторую задачу, получить ответ к первой. Если
сведение задачи А к задаче В занимает не более чем полиномиальное
время, то говорят, что задача А не сложнее задачи В.
Кроме того, имеет смысл ввести понятие полиномиальной экви­
валентности задач, которое означает, что первая не сложнее вто­
рой, а вторая — не сложнее первой, если мы покажем, как свести
одну задачу к другой и наоборот.
В качестве примера покажем, как свести задачу Диффи-Хелл­
мана к проблеме дискретного логарифмирования.

Л е м м а 7.1. В любой конечной абелевой группе G задача Диффи-
Хеллмана не сложнее проблемы дискретного логарифмирования.
Доказательство. Предположим, что существует оракул Одог^ Р^"
шающий задачу дискретного логарифмирования, т. е. по элементам
А и В = А^ он находит показатель х. Для поиска ответа в задаче
Диффи-Хеллмана с данными В = А^ ж С =^ АУ вычисляем
г^о,ог{в) и D = c^,
1.2. Односторонние функции

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

Лемма 7.2. Проблема выбора Диффи-Хеллмана в любой конечной
абелевой группе G не сложнее задачи Диффи-Хеллмана.
Доказательство. Пусть Одх — алгоритм, решающий задачу Диф­
фи-Хеллмана, который по элементам А^ и А^ вычисляет элемент
А^У. Рассмотрим элементы В = А^., С = А^ w. D = А^ и вычислим
Е = Одх{В^С). Если Е — D^ то решение проблемы выбора поло­
жительно, в противном случае — отрицательно.
Как и в предыдущей лемме, сведение одной задачи к другой про­
исходит за полиномиальное время. Поэтому, считая, что алгоритм
Одх работает корректно, получаем решение проблемы выбора Диф-
фи - Хеллмана. •
Мы показали, что проблема выбора Диффи-Хеллмана не труд­
нее прямой задачи Диффи-Хеллмана. Однако существуют группы,
в которых проблема выбора Диффи - Хеллмана решается за полино­
миальное время, а наилучшие алгоритмы для прямой задачи нахо­
дят ответ лишь за суб-экспоненциальное время.
Итак, три разновидности проблемы дискретного логарифмиро­
вания соотносятся между собой следующим образом: проблема вы­
бора Диффи-Хеллмана — самая легкая, затем идет задача Диффи-
Хеллмана, и замьпсает ряд задача вычисления дискретных логарифмов.
Вернемся к сравнению сложностей задач, связанных с разложе­
нием на множители. Наиболее важный результат здесь сформули­
рован в лемме 7.3.

Лемма 7.3. Задачи разложения на множители и вычисления ква­
дратного корня полиномиально эквивалентны.
Доказательство. Сначала сведем задачу извлечения квадратного
корня к разложению на множители. Предположим, у нас есть алго-
Глава 7. Основные алгоритмы шифрования с открытым ключом

ритм, разлагающий число на множители, и мы хотим с его помощью
извлечь квадратный корень по модулю составного числа N, Рассмо­
трим уравнение
Z = x'^ (mod TV)
относительно переменной х. Найдем простые делители Pi числа N^
опираясь на известный оракул, и вычислим
Si = ^/Z {modPi),
что можно сделать за полиномиальное время с помощью алгоритма
Шэнкса. После этого, используя китайскую теорему об остатках,
найдем X как решение системы уравнений:
{x = Si {modPi)}.
При этом необходимо соблюдать осторожность в случае, когда N
делится на более высокую, чем первая, степень числа Р^. Однако
и с этим случаем можно работать, но мы не будем его подробно
разбирать. Итак, вычисление квадратного корня по модулю N не
сложнее задачи факторизации.
Покажем, как разложение на множители может быть сведено к
задаче об извлечении квадратного корня. Предположим, что у нас
есть алгоритм, извлекающий квадратные корни по модулю состав­
ного числа 7V, равного произведению двух простых чисел, что несо­
мненно является самым сложным случаем. Случай общего составно­
го 7V с точки зрения математики чуть более хитрый, но в вычисли­
тельном отношении разложить на множители число, состоящее из
произведения трех и более простых делителей, существенно проще,
чем отыскать делители числа, если их всего два.
Мы намерены использовать алгоритм извлечения корней р^ля опре­
деления делителей числа 7V. Иными словами, дано число N = pq и
требуется найти р. Для этого выберем случайное число х G (Z/iVZ)*
и вычислим
Z = х'^ (modN).
Опираясь на алгоритм извлечения корней, найдем
у = y/z (modTV).
Заметим, что существует ровно четыре квадратных корня, посколь­
ку 7V — произведение двух простых чисел. С пятидесятьюпроцент-
ной вероятностью можно утверждать, что
у ф ±х (modTV).
Если это не так, то можно выбрать другой корень, т. е. в среднем
1.2. Односторонние функции

после двух проходов алгоритма мы наверняка получим требуемое
неравенство.
Теперь, так как х^ = у^ (modTV), то N должно делить число
х^ -у^ = {х-у){х-\-у).
Но N не может делить ни д: — у, ни а: + у, поскольку у ф ±ж (mod Л/^).
Таким образом, делители числа N должны делить как сумму {х-\-у\
так и разность {х — у). Поэтому один из нетривиальных делителей
числа N может быть найден как НОД {х — y^N).
Очевидно, сведения каждой из задач к другой можно осуще­
ствить за полиномиальное время, что доказывает полиномиальную
эквивалентность задач факторизации и извлечения корней. •
В этом доказательстве был применен стандартный прием ал­
горитмов факторизации, использующий разложение на множители
разности квадратов. Мы еще вернемся к нему в главе 8.
Стоит отметить, что задача о квадратичных вычетах безуслов­
но слабее проблемы извлечения корней, поскольку алгоритм, вычи­
сляющий квадратные корни, очевидно способен определить, являет­
ся ли данное число квадратичным вычетом по определенному моду­
лю, или нет.
Закончим параграф доказательством сводимости задачи RSA к
проблеме факторизации. Напомним, что задача RSA состоит в опре­
делении числа т по данным N^ Е и С = т^ {modN).

Л е м м а 7.4. Задача RSA не сложнее проблемы факторизации.
Доказательство. Применяя алгоритм факторизации, разложим
число N на простые множители, вычислим значение функции Эйле­
ра Ф = v{N) и найдем
D = l/E (тоаФ).
Теперь, зная число !?, легко восстановить т г поскольку
т,
С^ = т^^ = т} (^^) = т (modTV).
"^^
Отсюда следует, что задача RSA не сложнее проблемы факторизации.

Существует гипотеза, подтвержденная некоторыми косвенны­
ми соображениями, что задача RSA на самом деле легче проблемы
факторизации, т. е. эти задачи не эквивалентны. В настоящее вре­
мя проверка этой гипотезы — один из главных открытых вопросов
криптологии.
Глава 7. Основные алгоритмы шифрования с открытым ключом

73. RSA
Алгоритм RSA^ первый из алгоритмов шифрования с открытым
ключом, достойно выдержал испытание временем. Этот алгоритм
основывается на задаче RSA^ с которой мы познакомились в преды-
душ;ем параграфе. Как Вы помните, она сводится к поиску простых
делителей больших натуральных чисел. Так что можно утверждать,
что криптостойкость алгоритма RSA базируется на сложности про­
блемы факторизации, хотя и не в полной мере, поскольку задачу
RSA можно решать не прибегал к разложению на множители.
Предположим, Алиса считает нужным разрешить всем желаю­
щим отправлять ей секретные сообщения, расшифровать которые
способна только она. Тогда Алиса подбирает два больших простых
числа р и q. Держа их в секрете, Алиса публикует их произведение
N=p-q,
которое называют модулем алгоритма. Кроме того, Алиса выбира­
ет шифрующую экспоненту Е^ удовлетворяющую условию
Я0Д{Е,{р-1),{д-1)) = 1.
Как правило Е берут равным 3, 17 или 65 537. Пара, доступная
всем желающим, — это {N^E). Для выбора секретного ключа Али­
са применяет расширенный алгоритм Евклида к паре чисел Е и
(р — l)(gf — 1), получая при этом расшифровывающую экспоненту d.
Найденная экспонента удовлетворяет соотношению
E-d=l {mod{p-l){q-l)).
Секретным ключом является тройка {d^p^q). Фактически, можно
было бы выбросить простые делители р и q из ключа и помнить
лишь о d и всем числе N. Но, как мы позже убедимся, это снизит
скорость алгоритма (см. стр.293).
Допустим теперь, что Боб намерен зашифровать сообщение, адре­
сованное Алисе. Он сверяется с открытым ключом и представляет
сообщение в виде числа ттг, строго меньшего модуля N алгоритма.
Шифротекст С получается из т по следующему правилу:
С = т^ (modN).
Алиса, получив шифрограмму, расшифровывает ее, возводя число
С в степень d:
т = С'^ (modTV).
Равенство имеет место в связи с тем, что порядок группы (Z/7VZ)*
l.S. RSA

равен (p{N) = {p — l){q — 1). Поэтому, no теореме Лагранжа,
^(p-i)(q-i) ^ I (modiV)
для любого числа x G (Z/iVZ)*. Поскольку End взаимно обратны
по модулю (р — l)(g — 1), при некотором целом числе s получается
равенство
Ed-s{p-l){q-l) = l.
Следовательно,


= т • ш"(^-1)(^-^) = т (modTV).
]\ля прояснения ситуации рассмотрим детский пример. Пусть р = 1
и ^ = 11. Тогда N = 77^ 3. {р — l){q — 1) = 6 • 10 = 60. В качестве от­
крытой шифрующей экспоненты возьмем число Е = 37, поскольку
ПОД (37,60) = 1. Применяя расширенный алгоритм Евклида, най­
дем d = 13, т. к.
37-13 = 481 = 1 (mod 60).
Предположим, нужно зашифровать сообп];ение, численное предста­
вление которого имеет вид: m = 2. Тогда мы вычисляем
С = т^ (modN) = 2^^ (mod 77) = 51.
Процесс расшифровывания происходит аналогично:
т^С^ (modN) = 51^^ (mod77) = 2.

7.3.1. Шифрование RSA и одноименная задача
При первом знакомстве с алгоритмом RSA можно увидеть, что его
криптостойкость обеспечивается сложностью вычисления расшифровы-
ваюш;ей экспоненты d по открытому ключу, т. е. по известным числу
N (модулю системы) и шифруюш;ей экспоненте.
Мы показали, что задача RSA не сложнее проблемы фактори­
зации. Поэтому, если разложим на множители число JV, т.е. най­
дем j9 и ^, то сможем вычислить d. Следовательно, если проблема
факторизации модуля системы окажется легкой, RSA будет взлома­
на. Самые большие числа, которые к настоящему времени удается
разложить на множители за разумное время, имеют 500 двоичных
знаков. В связи с этим, для обеспечения стойкости систем среднего
срока действия, рекомендуют брать модули шифрования порядка
1024 битов. Для систем большого срока действия следует выбирать
модули, состоящие из 2048 битов.
Глава 7. Основные алгоритмы шифрования с открытым ключом

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

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

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

ОГЛАВЛЕНИЕ

Следующая >>