7.1. Концепция криптосистем с открытым ключом, однонаправленные функции.

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

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

Однонаправленные функции

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

Пусть X и Y - произвольные множества. Функция

f(X) -> Y, является однонаправленной, если для всех х, входящих в Х, легко вычислить функцию f(x), и в то же время для большинства y, входящих в Y, получить любое значение x, входящее в X, такое что f(x) = y достаточно сложно (при этом полагают, что существует, по крайней мере, одно такое значение x).

Простейший пример однонаправленной функции - целочисленное умножение.

Вторым важным классом функций, используемых в практике построения систем с открытым ключом, являются так называемые однонаправленные функции с черным ходом (trapdooronewayfunction). Для порядка введем определение.

Функция f(X) -> Y относится к классу однонаправленных функций с черным ходом в том случае, если она является однонаправленной и, кроме того, возможно эффективное вычисление инверсной функции, если известен "черный ход" (или, говоря по-русски, секретная строка, число или другая информация, ассоциирующаяся с данной функцией).

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

Эта система позволяет пользоателям обмениваться секретными ключами по незащищенным каналам связи. Разработана в 1976г и основана на задаче о дискретном логарифмировании.

Пусть N - некоторое большое целое число, а G - другое целое, такое что

Рассмотрим процедуру обмена ключами по шагам.

Вначале Алекс и Юстас достигают соглашения о значениях N и G (как правило, эти значения являются стандартными для всех пользователей системы).

Затем Алекс выбирает некоторое большое целое число X и вычисляет       XX = G^X MOD N. Аналогичным образом Юстас выбирает число Y и вычисляет       YY = G^Y MOD N. После этого Алекс и Юстас обмениваются значениями XX и YY. (Мы считаем, что все данные, которые передаются по каналу связи, могут быть перехвачены злоумышленником - стариной Мюллером). Числа X и Y Алекс и Юстас хранят в секрете.

Получив от Юстаса число YY, Алекс вычисляет       K(1) = YY^X MOD N, а Юстас -       K(2) = XX^Y MOD N.

Но (!)

YY^XMODN = G^(X*Y) MODN = XX^YMODN, а следовательно,

K(1) = K(2) = K.

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

Злоумышленник, перехвативший G, N, XX и YY, тоже должен определить значение ключа K.Вычислении значение X по G, N, XX и есть задача дискретного логарифмирования в чистом виде, которая считается неразрешимой.

Система Диффи-Хеллмана позволяет двум пользователям прийти к соглашению относительно общего секретного ключа. Однако система никак не влияет на то, как потом будет шифроваться сама информация. И если Алекс хочет передать Юстасу секретное сообщение M, то после установления ключа по Диффи-Хеллману может быть использована любая система шифрования.

Но системы с открытым ключом создавались не только и даже не столько для решения задачи распределения ключей. При грамотном подходе возможно эффективное их использование для шифрования информации. Ведь, по определению, система с открытым ключом отличается тем, что тот, кто знает ключ для шифрования, не может дешифровать текст за практически приемлемое время.

Рассмотрим, как же используются системы с открытым ключом.

Пользователь Алекс имеет в своем распоряжении два алгоритма: E для шифрования и D для расшифровки сообщений. При этом алгоритм E делается общедоступным, например, через использование каталога ключей, а алгоритм D  хранится Алексом в секрете Расшифровать сообщение сможет только тот, укого есть алгоритм D.

D(E(M)) = M,

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

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