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

В 1976 г. Диффи и Хеллман опубликовали статью, которая ознаменовала собой рождении асимметричной криптографии и привела к сильному росту числа открытых исследований в области криптографии. Она содержала ошеломляющий результат: возможно построение практически стойких секретных систем, которые не требуют передачи секретного ключа. Диффи и Хеллман ввели понятие односторонней функции с потайным ходом. Под односторонней функцией f понимается функция f (x), которая легко вычислима для любого значения аргумента x из области определения, однако для данного y из области ее значений вычислительно сложно нахождение значения аргумента x, для которого f (x) = y. Применение таких функций для защиты входа в вычислительную систему путем одностороннего преобразования паролей было известно. Но как применить одностороннюю функцию в криптографических системах, когда даже законный получатель не сможет выполнить дешифрования? Для шифрования была предложена односторонняя функция с потайным ходом (секретом).

Под односторонней функцией с потайным ходом понимается семейство обратимых функций f _z с параметром z, таких, что для данного z можно найти алгоритмы E_z и D_z, позволяющие легко вычислить значение f _z(x) для всех x из области определения, а также вычислить значение f _z^-1(y) для всех y из области значений, однако практически для всех значений параметра z и практически для всех значений y из области значений f _z нахождение f _z^-1(y) вычислительно неосуществимо даже при известном E_z.

В качестве односторонней функции Диффи и Хеллман предложили функцию дискретного возведения в степень

f (x) = g ^x (mod n),

где x – целое число, 1£ x £ n – 1,

n – k -битовое простое число.

Причем выбирается такое число g < n, степени которого по модулю n представляют собой упорядоченное множество чисел {g¹, g², …, g ^{n -1}}, являющееся некоторой перестановкой чисел {1, 2, …, n -1}. (Такое число g называется первообразным корнем по модулю n.)

Даже для очень больших модулей n (например, при k = 1024 бит) для данного x легко вычислить значение этой функции. Процедура вычисления этой функции называется дискретным возведением в степень. Для выполнения этой процедуры достаточно выполнение около 2log₂ n операций умножения k -битовых чисел (или log₂ n умножений и log₂ n делений 2 k -битовых чисел на k -битовые). Процедура дискретного возведения в степень основана на предварительном вычислений значений (по модулю n)

Обратной к функции дискретного возведения в степень является функция f ^-1(y), которая ставит в соответствие заданному значению y такое значение x, для которого выполняется условие g ^x = y (mod n). Задача нахождения такого x называется задачей дискретного логарифмирования (нахождения дискретных логарифмов). Дискретные логарифмы сложно вычисляются, когда число n -1 содержит один большой простой множитель, например, когда оно представимо в виде n -1 = 2 n ¢, где n ¢ - простое число. При этом условии трудоемкость задачи нахождения дискретного логарифма равна примерно Ö n умножений по модулю n. Решение такой задачи является вычислительно неосуществимым при больших значениях k (например, при k ³ 512), а следовательно при указанных условиях, накладываемых на выбор чисел n и g, функция дискретного возведения в степень является односторонней.

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

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

y = g ^x (mod n).

Для любого значения x легко вычислить y, однако при размере числа n, равном 512 бит и более, вычислительно неосуществимо выполнение дискретного логарифмирования, а следовательно и определение числа x, для которого значение g ^x mod n равно заданному значению y.

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

Общий секретный ключ может использоваться абонентами для шифрования сеансовых секретных ключей, а последние – для шифрования сообщений с использованием симметричных методов шифрования. Решение задачи дискретного логарифмирования существует, но оно вычислительно неосуществимо. Таким образом, стойкость метода Диффи – Хеллмана основана на сложности дискретного логарифмирования.

В симметричных криптосистемах существуют две принципиальные проблемы:

· распределение секретных ключей по защищенному каналу;

· аутентификация секретного ключа.

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