-
Итак, вот наше решение -- прежде всего Алиса и Боб публично договариваются о простом модуле и генераторе.
-
В нашем случае 17 и 3.
-
Затем Алиса выбирает личное случайное число (скажем, 15) и вычисляет значение 3 в степени 15 по модулю 17. И открыто передает этот результат Бобу.
-
Потом Боб выбирает для себя случайное число (13, скажем) и вычисляет значение 3 в степени 13 по модулю 17. И открыто передает этот результат Алисе.
-
И вот суть фокуса -- Алиса берет число, полученное от Боба и возводит его в степень своего личного числа для получения общего секретного числа (в данном случае 10).
-
Боб берет число, полученное от Алисы и возводит его в степень своего личного числа для получения того же общего секретного числа.
-
Заметим, что они выполняли одинаковые вычисления, которые могут сперва не показаться одинаковыми.
-
Рассмотрим вычисления Алисы.
-
12, полученное от Боба, было получено как 3 в степени 13 по модулю 17. То есть ее вычисления -- это 3 в степени 13 в степени 15 по модулю 17.
-
Теперь Боб. 6, полученное от Алисы, было получено как 3 в степени 15 по модулю 17.
-
То есть его вычисления -- это то же, что 3 в степени 15 в степени 13 по модулю 17.
-
Заметим, что они провели одинаковые вычисления степеней в разной последовательности. Если поменять местами возведение в степень, результат не изменится.
-
Таким образом, они оба выполнили возведение тройки в степени их личных чисел.
-
Не имея у себя одного из этих личных чисел (15 или 13), Ева не сможет найти решения.
-
Вот так это делается.
-
А Еве придется перебирать все решения задачи нахождения дискретного логарифма. При достаточно большом их количестве, мы сможем быть уверены, что практически невозможно взломать шифр в разумные сроки.
-
Это решает проблему обмена ключами. В сочетании с генератором псевдослучайных чисел это может быть использовано для шифрования сообщений между людьми, которые никогда не встречались.
