Главная | Обратная связь

Однонаправленные функции, построение однонаправленных функций с секретами.

В основе идей, изложенных в статье Уитфилда Диффи и Мартина Хеллмана лежало понятие однонаправленной функции.

Пусть X, Y - произвольные равномощные множества, F - биективная функция, отображающая X в Y. Обозначим через Q(F) - сложность вычисления значения F(x) для произвольного xÎX, через Q(F^-1) - сложность вычисления по произвольному yÎY значения x, такого, что F(x)=y (сложность вычисления понимается в стандартном смысле теории сложности).

В данных терминах будем говорить, что функция F является однонаправленной, если Q(F^-1) много больше Q(F). Как видно, данное определение не является достаточно строгим. Под термином «много больше» можно подразумевать весьма разные понятия, например то, что вычисление F имеет полиномиальную сложность, а F^-1- экспоненциальную.

Для того, чтобы под понятием однонаправленная функция понимался вполне конкретный класс объектов считают, что под термином «много больше», понимается следующее:

1. Сложность вычисления F такова, что алгоритм ее вычисления реализуем на современной технике и выдает ответ за приемлемое время

2. Сложность вычисления F^-1 такова, что алгоритм ее вычисления либо не реализуем на современной технике, либо не дает ответ за приемлемое время.

Что считать приемлемым временем следует из практических соображений - вычисление F не должно замедлять скорости обработки информации, а сложность вычисления F^-1 должна быть столь велика, чтобы не допускать обращения функции F злоумышленником.

На момент опубликования статьи авторы не имели конкретной системы ЭЦП и по этой причине их система ОРК повисла в воздухе, так как в ней не решался вопрос аутентификации отправителя сообщения. Такое решение появилось значительно позднее - в 1984 году. Пока же авторы предложили еще одну абстрактную схему с использованием так называемых однонаправленных функций с секретом (trapdoor one-way function). Строгое определения однонаправленной функции с секретом дать весьма затруднительно.

Попробуем сформулировать его следующим образом.

Однонаправленной функцией с секретом S называется биективная функция F отображающая произвольное множество X в множество Y, зависящая от параметров T₁,...,T_L и обладающая следующим свойствами:

1_. Существует некоторая функция S, зависящая от параметров T₁,...,T_L

2. По виду функции F значение функции S для конкретных параметров T₁,...,T_L не восстанавливается

3. Сложность вычисления значения F^-1(y) " yÎY при знании значения S(T₁,...,T_L) не превосходит сложности вычисления прямого преобразования F

4. Сложность вычисления преобразования F^-1 без знания значения S(T₁,...,T_L) много больше сложности вычисления прямого преобразования F.

Иными словами, без знания дополнительной информации о функции F она является однонаправленной, при наличии некоторой дополнительной информации (которую нельзя получить по функции F) обратное преобразование эффективно вычисляемо.

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

44)