Система распределение ключей Диффи-Хеллмана

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

f(x) = α ^x(mod p),

где х — целое число. 1< x <р—1, р — k-битовое простое число, α - первообразный корень по модулю р,   [Молдовян Н.А. и др., 2004].

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

у = α ^х (mod p).

Системой Диффи-Хеллмана называется следующий способ использования дискретного возведения в степень для обмена секретными ключами между пользователями сети с применением только открытых сообщений. Выбирается большое простое число р и соответствующий ему первообразный корень а < р. Для обеспечения стойкости рассматриваемой системы открытого шифрования на число р накладывается следующее условие: разложение числа р-1 на множители должно содержать, по крайней мере, один большой простой множитель; размер числа р должен быть не менее 512 бит.

Механизм распределения секретных ключей по открытому каналу состоит в сле­дующем. Каждый абонент выбирает случайный секретный ключ x и вырабатывает открытый ключ у, соответствующий выбранному секретному ключу, в соответствии с формулой

y = α ^x (mod p).

Два абонента А и В могут установить секретную связь без передачи секретного ключа следующим образом. Абонент А берет из справочника открытый ключ у_B або­нента В и, используя свой секретный ключ х_А, вычисляет общий секретный ключ:

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

Таким образом, оба абонента сформировали одинаковый секретный ключ Z_AB   без использования какого-либо заранее оговоренного общего секрета. Владея только им известным секретом и используя его в качестве мастер-ключа, данная пара абонентов может зашифровывать направляемые друг другу сообщения. Указанные выше вычисления легко осуществимы для достаточно больших значений р, а, у и х (например, имеющих в двоичном представлении длину 4096 бит и более). Атакующему известны значения и , но для того чтобы вычислить Z_AB, он должен решить задачу дискретного логарифмирования и определить либо х _A, либо х_B. Легко найти большие значения р (более 1024 бит), для которых задача дискретного логарифмирования является трудно решаемой. Если будут найдены вычислительно эффективные методы решения задачи дискретного логарифмирования, то метод Диффи-Хеллмана окажется несостоятельным — в связи с этим говорят, что данный.метод открытого распределения ключей основан на сложности дискретного логарифмирования. В настоящее время в общем случае задача дискретного логарифмирования практически неразрешима, что дает возможность широкого практического применения метода Диффи-Хеллмана и многочисленных систем ЭЦП, основанных на сложности вычисления дискретных логарифмов.

Не следует упускать из виду проблему аутентификации открытых ключей. Корректность протоколов с использованием асимметричных шифров может быть обеспечена только в случае, если все открытые ключи в справочнике открытых ключей являются подлинными. Если открытый ключ какого-либо абонента нарушителю удастся подменить, то секретные сообщения, посланные данному абоненту, будут доступны нарушителю. Таким образом, двухключевые шифры обеспечивают решение проблемы распределения секретных ключей, однако проблема аутентификации сохраняется и имеет фундаментальный характер, хотя требование подтверждения подлинности (аутентификации) относится уже к открытому, а не к секретному ключу. В неявном виде аутентификация открытого ключа включает в себя аутентификацию секретного ключа,   [Молдовян Н.А. и др., 2004].