Trapdoor One-Way Function

односторонняя функция с секретом, функция-ловушка, «лазейка» в односторонней функции
 Односторонняя функция, эффективное вычисление обратного значения которой возможно при знании дополнительной (секретной — такая секретная информация называется «лазейкой») информации. Функция f_k(x), зависящая от параметра k, такая что, при известном k можно найти полиномиальные алгоритмы E_k и D_k, позволяющие легко вычислить f_k(x) для всех x и f_k^–1(y) для всех y, а нахождение f_k^–1(y) без знания k трудно вычислимо (полиномиального алгоритма не существует) даже при известном алгоритме E_k. На основе понятия односторонней функции с секретом был предложен принцип открытого распределения ключей и, как следствие, криптосистемы с открытым ключом. Исследования таких функций проводится в основном по следующим направлениям:
 • дискретное возведение в степень — алгоритм Диффи-Хеллмана и др.;
 • факторизация простых чисел — алгоритм RSA и др.;
 • коды, исправляющие ошибки — алгоритм МакЭллиса и др.;
 • задачи NP-полноты — задача об «укладке ранца» и др.
Смотри также RSA, Diffie-Hellman Algorithm

— Игорь Мостицкий (обсуждение) 16:02, 9 января 2026 (MSK)