Криптосхема Диффи–Хэллмана

 

Асимметричные системы шифрования характеризуются высокой теоретической стойкостью. Однако их внедрение сдерживается недоверием со стороны практиков: всегда существует опасность, что успехи математиков приведут к приемлемому по сложности решению задачи, ранее считавшейся трудной. И история шифрования знает такие примеры. Так, для ранцевой системы шифрования, основанной на одностороннем преобразовании , где a, x – столбцы целых чисел, был найден алгоритм определения x по S с числом операций, меньшим, чем при прямом переборе значений x.

В то же время в асимметричных системах не требуется распределять ключи шифрования. Поэтому считаются перспективными гибридные системы, в которых асимметричная система служит для распределения сеансовых ключей, а шифрование данных выполняется с помощью симметричной системы (см. рис. 13.2). В подобной системе случайный ключ сеанса, формируемый генератором псевдослучайных чисел, шифруется с помощью схемы шифрования с открытым ключом, при этом используется открытый ключ получателя. Затем с помощью сеансового ключа шифруется открытый текст с применением симметричной схемы шифрования. Ключ сеанса и криптограмма, созданная с помощью сеансового ключа, посылается получателю. Первоначально получатель дешифрует зашифрованный ключ сеанса с помощью своего секретного ключа. Затем дешифруется собственно криптограмма с использованием секретного сеансового ключа. Как правило, для шифрования ключа сеанса используются два алгоритма шифрования с открытым ключом: алгоритм Диффи–Хэллмана или алгоритм RSA.

В схеме Диффи–Хэллмана в качестве односторонней используется показательная функция по модулю простого числа вида (13.1). Итак, пусть p – простое число, тогда существует конечное поле , в котором определен примитивный элемент . Секретным ключом некоторого пользователя является конкретное число , служащее показателем степени, в которую возводится примитивный элемент. Значение показательной функции, вычисленной по правилу конечного поля, т.е. по

служит открытым ключом данного пользователя и известно всем его абонентам.

Предположим, что абонент A намеревается послать абоненту B сообщение, шифрованное с помощью некоторого шифра из книги шифров, т.е. обычным шифром с секретным ключом. Это означает, они оба имеют одну и ту же книгу шифров, из которой секретно выбирается некоторый конкретный шифр. Для того чтобы указать номер M этого шифра абонент A воспользуется открытым ключом абонента B и произведет следующие вычисления

и ,

где – секретный ключ абонента A, а y – зашифрованный с помощью номер сеансового ключ, который используется абонентом A как номер шифра из книги шифров, который собственно и шифрует передаваемое сообщение.

Получив зашифрованные сообщение и сеансовый ключ, абонент B, зная отправителя, воспользуется открытым ключом абонента A и произведет аналогичные вычисления с использованием своего секретного ключа , т.е.

.

Однако, учитывая существующие связи между открытым и секретным ключами, получаем, что

и окончательно

.

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

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

.

При использовании достаточно большого p (типичным считается значение в сотни десятичных цифр) данная задача несравненно более сложная, чем прямая, поскольку включает в себя безуспешные попытки как по определению p, так и примитивного элемента .

Пример 13.3.1. (иллюстрирующий сам идею алгоритма, но не ее сложность).

Пусть и в поле выбирается примитивный элемент . Пусть в качестве секретных ключей абонентов A и B используются и . Тогда в качестве открытых ключей выступают и . Шифруя открытое сообщение для B, шифром с номером , абонент A, зная открытый ключ абонента B, производит следующие вычисления

и .

В свою очередь абонент B, зная открытый ключ абонента A, вычисляет номер используемого шифра следующим образом

и .

Таким образом, абонент B правильно определил номер шифра и, значит, сможет корректно расшифровать криптограмму.

В свою очередь криптоаналитик, который имеет доступ лишь к открытым ключам абонентов, для определения секретного ключа должен вычислить логарифм 27 (или 18) в поле , что представляет достаточно трудоемкую работу.