Система Діффі-Хеллмана обміну ключами

Пример 8.4

Определение 8.1

Пример 8.3

Возьмем. Его двоичным представлением, служит, как показывает функция IntegerDigits пакета "Mathematica".

IntegerDigits[171,2]

|| {1, 0, 1, 0, 1, 0, 1, 1}

Получается. Это вычисление можно сделать "на лету". Самая левая единица в двоичном представлении заменяется на. Каждый последующий символ влечет возведение в квадрат предыдущего результата, но если этот символ есть 1, то полученный квадрат дополнительно умножается на.

Clear[a];

((((((((a)²)²a)²)²a)²)²a)²a

|| a¹⁷¹

Если модулярное возведение в одну и ту же степень нужно выполнять много раз, например, в smart-карте, то имеются способы делать это с меньшим числом умножений.

Аддитивной цепочкой для натурального называется последовательность натуральных чисел с тем свойством, что каждое, есть сумма каких-то двух предыдущих чисел (или удвоением какого-то предыдущего числа). Число называют длиной цепочки.

Способ использования аддитивных цепочек для (модулярного) возведения в степень следующий. Если, то =. Следовательно, можно вычислять рекурсивно. Но, вообще говоря, не очевидно, как находить кратчайшую аддитивную цепочку для натурального.

Последовательность является аддитивной цепочкой для. Заметим, что вычисление с этой аддитивной цепочкой включает 5 умножений, а с помощью описанного ранее бинарного метода 6 умножений.

Функция PowerMod пакета "Mathematica" реализует быстрый способ модулярного возведения в степень.

a = 2; m = 171111111; p = 197888888;

PowerMod[a,m,p]

|| 55895160

Обратная задача нахождения, удовлетворяющего (8.1), по данному не столь легка. Она называется проблемой дискретных логарифмов, потому что в показатель можно записать как. В [4] можно найти алгоритм, решающий проблему логарифмов. Он требует грубо операций и битов памяти (где и — некоторые константы). В теореме 8.1 будет дан более точный анализ этого алгоритма. Напомним, что быстрое возведение в степень осуществляется за умножений, тогда записывая (и забывая о константах), получаем следующую экспоненциальную связь между возведением в степень и взятием логарифмов.

Таблица 8.1. Экспоненциальное расхождение между количеством операций при возведении в степень и взятием логарифма в поле целых чисел.

Возведение в степень
Взятие логарифмов

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

Формирование системы:

1) Все участники разделяют в качестве системных параметров простое число и примитивный элемент в.

2) Каждый участник выбирает случайное целое число, вычисляет и помещает его в книгу публичных ключей. Участник держит в секрете.

Использование системы:

Допустим теперь, что Алиса (для краткости) и Боб () хотят общаться друг с другом, используя традиционную криптосистему, но у них нет безопасного канала для обмена ключом. С помощью книги публичных ключей они могут согласовать общий секретный ключ

Алиса может вычислить возводя публично известное в степень, известную лишь ей одной. В самом деле,

Аналогично Боб находит, вычисляя.

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

Нет никаких очевидных причин ограничивать размер конечного поля простым числом. Впредь размер поля может быть произвольной степенью простого числа. В [5], гл. XIII, описаны эффективные алгоритмы нахождения примитивных элементов в конечных полях. Резюмируем систему распределения ключей в табл. 8.2.

Таблица 8.2. Система Диффи-Хеллмана обмена ключами.

Системные параметры	Размер поля
Примитивный элемент
Секретный ключ
Публичный ключ
Общий ключ и
Алиса вычисляет
Боб вычисляет

Пример 8.5 (часть 1)

Пусть u. Алиса случайным образом выбирает секретный показатель, а Боб аналогично выбирает секретный показатель. Они вычисляют свои публичные ключи с помощью функции PowerMod:

cA = PowerMod[2, 56, 197]

cB = PowerMod[2, 111, 197]

|| 178

|| 82

Алиса может вычислить общий с Бобом ключ, возводя публично известное в степень, известную только ей, и получая

PowerMod[82, 56, 197]

|| 114

Боб получает тот же самый общий ключ, возводя в степень. В самом деле,

PowerMod[178, 111, 197]

|| 114

Дата добавления: 2013-12-12