Обмен ключами по схеме Диффи-Хеллмана

Эффективность данного алгоритма опирается на трудность вычисления дискретных логарифмов. Формально дискретный алгоритм можно определить следующим образом. Сначала определяется первообразный корень простого числа p как число, степени которого порождают все целые числа от 1 до p-1. Это значит, что если a является первообразным корнем простого числа p, то все числа должны быть разными и представлять все целые числа от 1 до p-1 в некоторой перестановке.

Для любого целого числа b и любого первообразного корня a простого числа p однозначно определяется показатель степени i, при котором . Этот показатель степени называется дискретным логарифмом.

Рассмотрим теперь обмен ключами по схеме Диффи-Хеллмана. В этой схеме имеются два открытых для всех числа: простое число q и целое число , являющееся первообразным корнем q. Предположим, что пользователи A и B намерены обменяться ключами. Пользователь A выбирает случайное целое число и вычисляет . Аналогично пользователь B независимо выбирает случайное целое число и вычисляет . Каждая сторона сохраняет X в тайне, а значение Y делает свободно доступным другой стороне. Пользователь A вычисляет ключ по формуле , а пользователь B – по формуле . Эти две формулы при вычислении дают одинаковый результат. Защищенность обмена ключами по схеме Диффи-Хеллмана опирается на то, что в то время, как степени по модулю некоторого простого числа вычисляются относительно легко, вычислять дискретные логарифмы оказывается очень трудно. Для больших простых чисел эта задача считается практически неразрешимой.

Пример. Обмен ключами строится на использовании простого числа q=71 и его первообразного корня . Пользователи A и B выбирают секретные ключи . Каждый вычисляет свой открытый ключ: и . После того как пользователи обменяются открытыми ключами, каждый из них сможет вычислить общий секретный ключ: и . Имея {51,4}, противнику не удастся с легкостью вычислить 30.