Введение

Односторонняя криптографическая функция, математическая криптографическая функция.

В теоретической информатике и криптографии функция с люком (trapdoor function) – это функция, которую легко вычислить в одном направлении, но трудно вычислить в противоположном (найти её обратную) без специальной информации, называемой «люком». Функции с люком являются частным случаем односторонних функций и широко используются в криптографии с открытым ключом. В математических терминах, если f является функцией с люком, то существует некоторая секретная информация t, такая, что, имея f(x) и t, можно легко вычислить x. Рассмотрим навесной замок и его ключ. Тривиально изменить замок с открытого на закрытый без использования ключа, задвинув дужку в механизм замка. Однако, чтобы легко открыть замок, необходимо использовать ключ. Здесь ключ t – это люк, а навесной замок – функция с люком. Примером простой математической задачи с люком является: «6895601 является произведением двух простых чисел. Какие это числа?». Типичное решение методом «грубой силы» заключалось бы в попытках разделить 6895601 на множество простых чисел, пока не будет найден ответ. Однако, если кому-то сообщить, что 1931 является одним из чисел, то ответ можно найти, введя «6895601 ÷ 1931» в любой калькулятор. Этот пример не является надежной функцией с люком – современные компьютеры могут угадать все возможные ответы менее чем за секунду – но эту примерную задачу можно улучшить, используя произведение двух гораздо больших простых чисел. Функции с люком приобрели известность в криптографии в середине 1970-х годов с публикацией асимметричных (или криптографии с открытым ключом) методов шифрования Диффи, Хеллмана и Меркла. Именно Меркл ввел этот термин. Было предложено несколько классов функций, и вскоре стало очевидно, что функции с люком найти сложнее, чем предполагалось изначально. Например, одним из ранних предложений было использование схем, основанных на задаче о сумме подмножества. Это оказалось довольно быстро непригодным. По состоянию на 2004 год наиболее известными кандидатами на функцию с люком (семейство функций) являются семейства функций RSA и Rabin. Обе представлены как возведение в степень по модулю составного числа и обе связаны с задачей факторизации простых чисел. Функции, связанные со сложностью задачи дискретного логарифмирования (либо по модулю простого числа, либо в группе, определенной на эллиптической кривой), не считаются функциями с люком, поскольку нет известных сведений о группе, которые позволили бы эффективно вычислять дискретные логарифмы. Люк в криптографии имеет очень специфическое, вышеупомянутое значение и не должен путаться с бэкдором (эти термины часто используются как взаимозаменяемые, что неверно). Бэкдор – это преднамеренный механизм, добавляемый к криптографическому алгоритму (например, алгоритму генерации пары ключей, алгоритму цифровой подписи и т. д.) или операционной системе, который позволяет одной или нескольким неавторизованным сторонам обходить или подрывать безопасность системы.

Примеры

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

Предположение о квадратическом остатке Рабина

Пусть N — большое составное число, такое, что N = p * q, где p и q — большие простые числа, такие, что p ≠ q, и они известны только доверенной стороне. Задача состоит в вычислении z по N, такому, что z² ≡ N (mod N). "Скрытая дверь" (trapdoor) — это факторизация N на простые множители. Зная "скрытую дверь", решения уравнения z можно представить как z ≡ ±√N (mod N), где √N вычисляется по модулю p и q. Подробнее см. Китайскую теорему об остатках. Отметим, что зная простые числа p и q, можно найти N и N-1. Условия p ≠ q гарантируют, что решения z и -z определены однозначно.