Метод экспоненциального ключевого обмена Диффи-Хеллмана

Одни из авторов идеи криптосистем с открытым ключом, Диффи и Хеллман предложили новую идею - открытое распределение ключей.

Они задались вопросом: можно ли организовать такую процедуру взаимодействия абонентов А и В по открытым каналам связи, чтобы решить следующие задачи:

1) вначале у А и В нет никакой общей секретной информации, но в конце процедуры такая общая секретная информация (общий ключ) у А и В появляется, т. е. вырабатывается;

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

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

Криптостойкость данного метода определяется трудоемкостью вычисления дискретного логарифма:

f (х) = g^х mod р,

где р — большое простое число, х — произвольное натуральное число, g — некоторый примитивный элемент поля Галуа GF (р). Общепризнано, что инвертирование функции g^х mod р, т.е. дискретное логарифмиро­вание, является трудной математической задачей.

Сама процедура или протокол выработки общего ключа заключается в следующем. Значения р и g являются общедоступными параметрами протокола. Абоненты A и В независимо друг от друга случайно выбирают по одному большому натуральному числу x _а и x_b. Это их секретные ключи. Далее каждый из них вычисляет открытые ключи:

y _а = g^{x а} mod р и у _В = g^xB mod р.

Потом они обмениваются этими элементами по каналу связи. Теперь абонент А, получив y _В и зная свой секретный элемент х _а, вычисляет новый элемент:

у _В ^{x а} mod р = (g^xB) ^{x а} mod р.

Аналогично поступает абонент В:

y_A^xB mod р = (g^{x а}) ^xB mod р.

Тем самым у А и В появился общий элемент поля, равный g^{x а xB}. Этот элемент и объявляется общим ключом абонентов A и В.

Необратимость преобразования в этом случае обеспечивается тем, что достаточно легко вычислить показательную функцию в конечном поле Галуа, состоящем из р элементов (р — простое число). Обратная задача вычисления x из y будет достаточно сложной. Если р выбрано достаточно правильно, то извлечение логарифма потребует вычислений, пропорциональных L(р) = exр { (ln р ln ln р)^0.5}.

При всей простоте алгоритма Диффи-Хелмана его недостатком по сравнению с системой RSA является отсутствие гарантированной нижней оценки трудоемкости раскрытия ключа.

Алгоритмы практической реализации криптосистем с открытым ключом

Возведение в степень по модулю m

В криптографии используются вычисления по mod m, так как алфавит любой криптографической системы представляет собой конечное множество целых чисел. Арифметика вычетов к тому же легче реализуется на компьютерах, поскольку она ограничивает диапазон промежуточных значений и результата. Для k -битовых вы­четов m промежуточные результаты любого сложения, вычитания или умножения будут не длиннее, чем 2 k бит. Поэтому в арифметике вычетов мы можем выполнить возведение в степень без огромных промежуточных результатов. Вычисление степени некоторого числа по модулю другого числа,

a^d mod m,

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

Например, для того, чтобы вычислить а⁸ mod m, не выполняйте семь умножений и одно приведение по модулю; вместо этого выполните три меньших умножения и три меньших приведения по модулю:

а⁸ mod m = ((a² mod m)² mod m)² mod m.

Точно также, а¹⁶ mod m = (((a² mod m)² mod m)² mod m)² mod m.

Вычисление a^d mod m, где d не является степенью 2, не намного труднее. Двоичная запись представляет х в виде суммы степеней 2: число 25 — это бинарное 11001, поэтому 25 = 16 + 8 + 1. Тогда

a ²⁵ mod m = (a a⁸ a¹⁶)mod m= (a *(((a*a²) ²) ²) ²) mod m.

С продуманным сохранением промежуточных результатов нам понадобится только шесть умножений:

(((((((a² mod m)* a)²mod m)²mod m)²mod m)²mod m)²mod m *a)mod m.

Такой прием называется методом двоичных квадратов и умножений. Он использует простую и очевидную цепочку сложений, в основе которой лежит двоичное представление числа. Увеличение скорости вычислений при умножении 200-битовых чисел будет очень заметным.

Алгоритм вычисления a^d mod m.

Пусть натуральные числа a и d не превосходят по величине т.

1. Представим d в двоичной системе счисления:

d = d_o2^r + … + d_r-12 + d_r,

где r – число двоичных разрядов, d_i - цифры в двоичном представле­нии, равные 0 или 1, и d_o = 1.

2. Положим a_o=a и затем для i = 1,.... r вычислим

a_iº a²_i-1 a^di  mod т.

Тогда a_r есть искомый вычет a^d mod m.

Справедливость этого алгоритма вытекает из легко доказываемого индукцией по i сравнения:

a_iº a^do2i+…+di  mod т.

Так как каждое вычисление на шаге 2 требует не более трех умноже­ний по модулю т и этот шаг выполняется r £ lo g ₂ т раз, то сложность алгоритма может быть оценена величиной 0(ln m). Говоря о сложности алгорит­мов, мы имеем в виду количество арифметичес­ких операций.

Второй алгоритм — это классический алгоритм Евклида вычисле­ния наибольшего общего делителя целых чисел. Мы предполагаем за­данными два натуральных числа а и b и вычисляем их наибольший общий делитель НОД(а, b).