Лазейка» в односторонней функции

Главная идея асимметрично-ключевой криптографии – понятие «лазейки» в односторонней функции.

Хотя понятие функции знакомо из математики, мы дадим неофициальное определение здесь. Функция – правило, по которому связывают (отображают) один элемент во множестве A, называемый доменом, и один элемент во множестве B, называемый диапазоном, как показано на рис.3.

Рис. 3. Функция отображения домена в диапазон

Обратимая функция – функция, которая связывает каждый элемент в диапазоне с точно одним элементом в домене.

Односторонняя функция – функция, которая обладает следующими двумя свойствами:

1. f вычисляется просто. Другими словами, при данном x может быть легко вычислен y = f (x).

2. f ^-1 вычисляется трудно. Другими словами, при данном y, вычислить x= f ^~1 (y) неосуществимо.

«Лазейка» в односторонней функции – односторонняя функция с третьим свойством:

3. При данном y и ловушке (секретной) x может быть легко вычислен.

Пример 1

Когда n является большим,  – односторонняя функция. Обратите внимание, что в этой функции x – кортеж (p, q) двух простых чисел, а y в данном случае– это n. При заданных p и q всегда просто вычислить n. При данном n очень трудно вычислить p и q. Это – проблема разложения на множители. В этом случае для нахождения функции f ^-1 нет решения с полиномиальным временем.

Пример 2

Когда n является большим, функция y = x^k mod n – «лазейка» в односторонней функции. При заданных x, k и n просто вычислить y, используя алгоритм быстрого возведения в степень. При заданных y, k и n очень трудно вычислить y. Это – проблема дискретного логарифма. В этом случае нет решения с полиномиальным временем для функции f ^-1. Однако если мы знаем «лазейку» и k’, такое, что , мы можем использовать x = y^k mod n, чтобы найти x. Это – известный алгоритм (RSA – Riverst-Shamir-Adelman), который будет рассмотрен позже.