2. Криптосистемы с открытым ключом. Односторонние функции.

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

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

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

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

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

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

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

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

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

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

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

Криптографические системы с открытым ключом используют так называемые необратимые или односторонние функции, которые обладают следующим свойством: при заданном значении хотноси-тельно просто вычислить значение у =f(x), однако если известно у, то нет простого пути для вычисления значения х.

Вообще же, все предлагаемые сегодня криптосистемы с открытым ключом опираются на один из следующих типов необратимых преобразований:

• разложение больших чисел на простые множители;

• вычисление дискретного логарифма;

• алгоритмы на основе задачи об укладки ранца;

• криптосистемы на эллиптических кривых.

Здесь же следует отметить, что двухключевые криптосистемы имеют многоцелевое назначение:

1. как состоятельные средства шифрации передаваемых и хранимых данных;

2. как средства для распределения ключей;

3. как средства аутентификации пользователей, включая создание электронной цифровой подписи.