Односторонняя функция с потайным входом

Односторонняя функция с потайным входом (также функция с потайной дверцей, лазейкой, от англ. trapdoor function) — это математическая функция, которая легко вычисляется в одном направлении (прямая задача), но трудно обратима (обратная задача) без знания специальной секретной информации — «потайного входа» (лазейки). При наличии этой информации обратное вычисление становится эффективным. Данное понятие является фундаментальным в криптографии с открытым ключом.

Определение

Формально, односторонняя функция с потайным входом — это семейство функций \( f_k : X \to Y \), где \( k \) — параметр (открытый ключ), для которых выполняются следующие условия:

1. Легкость вычисления: для любого \( x \in X \) значение \( f_k(x) \) вычисляется за полиномиальное время.
2. Трудность обращения без лазейки: для почти всех \( y \in Y \) задача нахождения \( x \) такого, что \( f_k(x) = y \), является вычислительно сложной (например, требует экспоненциального времени) без знания дополнительной информации \( t \) (потайного входа).
3. Легкость обращения с лазейкой: существует алгоритм, который при знании \( t \) за полиномиальное время находит \( x \) по \( y \).

Потайной вход \( t \) обычно является секретным ключом, соответствующим открытому ключу \( k \). Классическим примером служит функция умножения двух больших простых чисел: произведение вычислить легко, а разложение на множители (факторизация) без знания одного из сомножителей — трудно. Однако если известно одно из простых чисел (лазейка), то обратная задача решается тривиально.

История

Концепция односторонней функции с потайным входом была впервые предложена Уитфилдом Диффи и Мартином Хеллманом в 1976 году в их новаторской работе «Новые направления в криптографии» (англ. New Directions in Cryptography). Они ввели идею криптосистемы с открытым ключом, где для шифрования используется открытый ключ, а для расшифрования — секретный. Однако Диффи и Хеллман не смогли предложить конкретную реализацию такой функции.

Первая практическая реализация была предложена в 1978 году Рональдом Ривестом, Ади Шамиром и Леонардом Адлеманом — это криптосистема RSA. В её основе лежит задача факторизации больших целых чисел. Позднее были разработаны другие схемы, основанные на различных вычислительно сложных задачах.

Примеры

RSA (Rivest–Shamir–Adleman)

Наиболее известная и широко применяемая односторонняя функция с потайным входом. В основе лежит модульная арифметика:

• Прямая задача: возведение в степень по модулю \( n \): \( c = m^e \mod n \), где \( n = p \cdot q \) — произведение двух больших простых чисел, \( e \) — открытая экспонента.
• Обратная задача: извлечение корня степени \( e \) по модулю \( n \) (вычисление \( m \) по \( c \)) без знания разложения \( n \) на множители.
• Потайной вход: секретный ключ \( d \), такой что \( e \cdot d \equiv 1 \mod \varphi(n) \), где \( \varphi(n) = (p-1)(q-1) \). Зная \( d \), расшифрование выполняется как \( m = c^d \mod n \).

Безопасность RSA основана на предположении, что задача факторизации больших целых чисел (длиной 2048 бит и более) является вычислительно сложной.

Криптосистема Рабина

Предложена Майклом Рабином в 1979 году. Основана на задаче извлечения квадратного корня по модулю составного числа \( n = p \cdot q \):

• Прямая задача: \( c = m^2 \mod n \).
• Обратная задача: нахождение \( m \) по \( c \) без знания \( p \) и \( q \) эквивалентно по сложности факторизации \( n \).
• Потайной вход: простые множители \( p \) и \( q \). Зная их, можно вычислить квадратные корни по модулю \( p \) и \( q \) по отдельности, а затем восстановить \( m \) с помощью китайской теоремы об остатках.

Криптосистема Рабина доказуемо столь же безопасна, как и задача факторизации, что делает её теоретически более надёжной, чем RSA (для которого такая эквивалентность не доказана). Однако она имеет недостаток: одному шифротексту соответствуют четыре возможных открытых текста, что требует дополнительных механизмов для устранения неоднозначности.

Криптосистема Эль-Гамаля

Основана на задаче дискретного логарифмирования в мультипликативной группе конечного поля или на эллиптической кривой:

• Прямая задача: для фиксированного генератора \( g \) группы и открытого ключа \( h = g^x \) вычисление \( c = g^k \) и \( m \cdot h^k \) для случайного \( k \).
• Обратная задача: нахождение \( m \) по \( c \) без знания секретного ключа \( x \) требует решения задачи Диффи-Хеллмана или дискретного логарифмирования.
• Потайной вход: секретный ключ \( x \). Зная \( x \), можно вычислить \( h^k = (g^k)^x \) и восстановить \( m \).

Криптосистема Эль-Гамаля является вероятностной: один и тот же открытый текст при разных \( k \) даёт разные шифротексты.

Применение

Односторонние функции с потайным входом лежат в основе большинства современных криптографических систем с открытым ключом:

• Шифрование данных: обеспечение конфиденциальности при передаче информации по незащищённым каналам (например, протоколы TLS/SSL, PGP).
• Цифровые подписи: аутентификация отправителя и целостность сообщения (алгоритмы RSA, DSA, ECDSA).
• Обмен ключами: протокол Диффи-Хеллмана, хотя сам по себе не является функцией с потайным входом, использует одностороннюю функцию (дискретное возведение в степень).
• Криптовалюты: в блокчейне биткоина и других криптовалют используются схемы цифровых подписей на основе эллиптических кривых (ECDSA, EdDSA).
• Электронное голосование: системы, обеспечивающие анонимность и проверяемость голосов.

Критика и ограничения

• Квантовая угроза: алгоритм Шора (1994) показывает, что на квантовом компьютере задачи факторизации и дискретного логарифмирования решаются за полиномиальное время. Это означает, что RSA, Эль-Гамаль и схемы на эллиптических кривых станут небезопасными при появлении достаточно мощного квантового компьютера. В связи с этим активно разрабатываются постквантовые криптосистемы, основанные на других математических задачах (например, на решётках, кодах, хэш-функциях).
• Теоретическая недоказанность: существование односторонних функций (с потайным входом или без) не доказано математически. Если будет доказано, что \( P = NP \), то такие функции не существуют. Однако большинство криптографов полагают, что \( P \neq NP \), и на практике используются функции, которые считаются односторонними.
• Практические атаки: реализация может быть уязвима из-за побочных каналов (время выполнения, потребление энергии, электромагнитное излучение), неправильного выбора параметров (например, слишком короткие ключи) или уязвимостей в протоколах.

Интересные факты

• Термин «потайной вход» (trapdoor) происходит от люка в полу или потолке, который позволяет быстро попасть в подвал или на чердак, минуя обычный путь. В криптографии это метафора секретного способа обойти вычислительную сложность.
• В 1990-х годах Агентство национальной безопасности США (АНБ) продвигало использование чипа Clipper с алгоритмом Skipjack, который содержал встроенный потайной вход для правоохранительных органов. Это вызвало широкую критику со стороны криптографического сообщества, и проект был закрыт.
• В 2013 году стало известно, что АНБ тайно ослабляло стандарты шифрования (например, в генераторе псевдослучайных чисел Dual_EC_DRBG), внедряя в них математические потайные входы, известные только агентству.

Источники

• Diffie, W., Hellman, M. E. «New Directions in Cryptography», IEEE Transactions on Information Theory, 1976.
• Rivest, R. L., Shamir, A., Adleman, L. «A Method for Obtaining Digital Signatures and Public-Key Cryptosystems», Communications of the ACM, 1978.
• Rabin, M. O. «Digitalized Signatures and Public-Key Functions as Intractable as Factorization», MIT Laboratory for Computer Science, 1979.
• ElGamal, T. «A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms», IEEE Transactions on Information Theory, 1985.
• Шор, П. «Algorithms for Quantum Computation: Discrete Logarithms and Factoring», Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994.
• Менезес, А., ван Ооршот, П., Ванстон, С. «Handbook of Applied Cryptography», CRC Press, 1996.