§ 2 Открытое распределение ключей 49

Точнее говоря, хотелось бы иметь такой протокол, с помощью которого Алиса и Боб могли обмениваться сообщениями mi (от Алисы к Бобу), газ (от Боба к Алисе), ..., до тех пор пока они оба окончательно не договорятся между собой о некотором совместном ключе к, причем они должны сделать это так, чтобы определить к из знания только mi, гаг, ... было практически невозможно. Подчеркнем еще раз, что этого необходимо добиться даже в том случае, если Алиса и Боб не обменивались заранее никакой информацией, которая не была бы известна нарушителю.

Первый кажущийся абсолютно невозможным протокол, который тем не менее достигает этой цели, был предложен Диффи и Хеллманом [157] в 1976 году. Он основывается на задаче дискретного логарифмирования, рассмотренной в § 1. Пусть п - некоторое большое целое число, и пусть д - другое целое, лежащее строго между 1 и п - 1. В качестве первого шага протокола Диффи-Хеллмана Алиса и Боб уславливаются об п и посредством несекретного канала связи (в качестве альтернативы п и могли бы быть стандартными параметрами, применяемыми всеми пользователями системы). Затем Алиса выбирает некоторое большое целое число х и вычисляет X = mod п. Соответственно, Боб выбирает число у и вычисляет Y = дУ mod п. После этого Алиса и Боб обмениваются числами X иУ по тому же несекретному каналу связи, сохраняя в секрете х и у (Алиса при этом знает только х, а Боб - только у). Наконец, Алиса вычисляет mod п, а Боб, соответственно, вычисляет Х mod п. Оба эти значения, очевидно, равны между собой, так как каждое из них равно 5* mod п. Это как раз и есть тот самый ключ к, который Алиса и Боб хотели совместно выработать.

Нарушитель при таком протоколе сталкивается с задачей вычисления к из пересылаемых по несекретному каналу чисел д, п, X п Y. Очевидным подходом для нарушителя было бы вычислить X яз д, п и X (или по крайней мере некоторое х, такое, что 5* mod п =: X, так как для любого подобного х всегда У* mod п = к). Однако это в точности задача нахождения дискретного логарифма, которая считается практически невыполнимой. Кроме того, никто пока не придумал способа вычислять к эффективно из д, п, X и У, как никто и не смог доказать, что это невозможно, или хотя бы продемонстрировать, что не

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

Выбор д и п может оказывать существенное влияние на эффективность и надежность представленного только что проекта криптосхемы. Для того чтобы сократить размер возможных окончательных значений к, важно чтобы функция модульного возведения в степень /д,„: Z„ Z„ (как она определена в § 1) была настолько почти взаимнооднозначной, насколько это возможно. В том случае, когда п является простым числом, всегда существует такое д, что mod п принимает каждое из значений в промежутке от 1 до п - 1, когда х пробегает значения из того же интервала. Подобные д, которые называются образующими элементами, или генераторами, циклической группы Z„, и

были бы искомыми. При этом надежнее выбрать п таким обра-п - 1

зом, чтобы также было простым [288]. Кроме того, можно было бы все указанные операции проводить в полях Галуа GF(2), описание методов вычисления в которых, к сожалению, выходит далеко за рамки этой книги [41]. Они предоставляют возможность намного более эффективно осуществлять умножение (а следовательно, и возведение в степень), так как позволяют избежать при вычислениях необходимости переносов и приведений по модулю [5, 4]. Однако в этом случае размер ключа будет намного длиннее. С другой стороны, длины всех чисел, участвующих в арифметических операциях можно существенно сократить, если использовать вычисления над эллиптическими кривыми [6].

Несмотря на то, что очень большие дискретные логарифмы возможно и являются трудновычислимыми, хотелось бы предупредить читателя, что для их вычисления существуют алгоритмы намного лучшие, чем исчерпывающий поиск. Самые лучшие из известных в настоящее время алгоритмов, когда п является простым числом, описаны в [124], а при вычислениях в GF{2) - в [281]. При выборе размера ключа такие поля должны тщательно анализироваться. Фирмой Hewlett-Packard однажды бы-

ла разработала злополучная аппаратная реализация, использующая GF(2) [368]. Однако ключи в ней были быстро раскрыты с применением методов, которые изложены в [45].

В предположении, что п и д являются стандартными параметрами, интересной альтернативой описанному ранее интерактивному протоколу является организация и использование некоторого единого для всех пользователей каталога. Каждый пользователь записывает в этот каталог свой собственный открытый ключ X, вычисленный как д mod п в соответствии с личным случайно выбранным секретным ключом х. Это позволяет любым двум пользователям сформировать свой совместный секретный ключ даже до их предварительной договоренности о нем друг с другом. Основной недостаток такого общедоступного каталога состоит в том, что он не поддерживает достаточно частые изменения пользователями личных секретных ключей. Мы намереваемся вернуться к этой теме в § 7.

Другой подход к проблеме распределения ключей обеспечивает предложенная Чарльзом Беннеттом и Жилем Брассаром квантовая криптография [25]. Ее надежность не зависит от недоказанных предположений о вычислительной сложности, основанных на трудности вычислений каких бы то ни было функций. Более того, она остается таковой даже тогда, когда нарушитель имеет неограниченные вычислительные ресурсы, или даже если, все-таки, VMV [27, 26, 28]. Квантовое открытое распределение ключей описывается в последней, седьмой главе этой книги.

§ 3. Теория криптосистем с открытым ключом

Система открытого распределения ключей, так как она описана в § 2, позволяет двум сторонам сформировать совместную часть некоторой распределенной секретной информации. Однако при этом ни одна из сторон не имеет никакого непосредственного влияния на то, какой окажется эта информация. Если бы Алиса захотела передать Вобу единственное специальное сообщение, то за использованием системы открытого распределения ключей должно было бы последовать использование криптосистемы с секретным ключом, в которой первоначальная совместно сформированная ими информация сохранялась бы в качестве их общего секретного ключа.