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

Вся концепция криптосистем с открытым ключом основана на применении однонаправленных функций (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

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

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

10. Электронная подпись в системах с открытым ключом Электронная подпись в системах с открытым ключом

Пусть пользователь N1 должен передать сообщение m пользователю N2 так, чтобы пользователь N2 в случае надобности мог доказать, что сообщение послано пользователем N1.

Для этого пользователь N1 разрабатывает систему шифрации

      E1(D1(X)) = X

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

Получив от N2 общий ключ шифрования D2 открытой системы

      E2(D2(X)) = X,

пользователь N1 вычисляет сигнатуру сообщения

      S = D1(m),

затем шифрует ее открытым ключом D2

      C = D2(S)

и передает его пользователю N2, который расшифровывает сообщение процедурой

      S = E2(C)       m*= E1(S).

Теперь при возникновении спорной ситуации N1 должен предстиавить арбитру свой личный ключ подписи D1, удовлетворяющий соотношению

      E1(D1(X)) = X.

Арбитру необходимо лишь проверить, что

      D1(m*) = S,

и следовательно, сообщение мог послать только пользователь N1. Кроме того и пользователь N2 не может исказить сообщение m, т.к. для доказательства в суде ему необходимо изменить и сигнатуру S, а для этого ему нужно знать личный ключ подписи пользователя N1, а его то и нет!