Односторонняя функция

Односторонняя функция — это функция, которая легко вычисляется для любого входного значения, но для которой нахождение обратного значения (прообраза) по заданному результату является вычислительно сложной задачей. Иными словами, для любого x вычислить y = f(x) можно за полиномиальное время, а для почти любого y найти такой x, что f(x) = y, невозможно за приемлемое время с использованием существующих алгоритмов и вычислительных мощностей. Односторонние функции являются фундаментальным понятием в теории сложности вычислений и криптографии, хотя их существование строго не доказано и является одной из важнейших открытых проблем современной информатики.

Определение и формальные свойства

Формально, функция f: {0,1} → {0,1} называется односторонней, если она удовлетворяет следующим условиям:

1. Простота вычисления: Существует детерминированный алгоритм A, который для любого входного x длины n вычисляет f(x) за время, полиномиально зависящее от n (то есть O(n^k) для некоторой константы k).
2. Сложность обращения: Для любого вероятностного полиномиального алгоритма B, для любого полинома p(n) и для всех достаточно больших n вероятность того, что B по заданному y = f(x), где x выбран случайно равномерно из {0,1}^n, найдёт любой x' такой, что f(x') = y, меньше 1/p(n). Эта вероятность берётся по случайному выбору x и по внутренним случайным битам алгоритма B.

Требование «для почти любого y» в неформальном определении означает, что обращение должно быть сложным в среднем, а не в худшем случае. Функция может быть легко обратима для некоторых y (например, для y, полученных из x с большим количеством нулей), но для подавляющего большинства возможных значений y обращение должно быть практически невозможным.

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

Кандидаты на роль односторонних функций

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

Умножение и факторизация

• Прямая функция: Умножение двух больших простых чисел p и q для получения составного числа N = p × q.
• Обратная задача: Факторизация (разложение на множители) числа N, то есть нахождение p и q по заданному N.
• Сложность: Умножение выполняется за доли секунды даже для чисел длиной в тысячи бит. Факторизация же числа длиной 2048 бит (рекомендованный размер для RSA) с помощью лучших известных алгоритмов (например, общего метода решета числового поля) требует астрономических вычислительных ресурсов и времени. Эта задача лежит в основе криптосистемы RSA.

Возведение в степень и дискретное логарифмирование

• Прямая функция: Вычисление y = g^x mod p, где p — большое простое число, g — образующая мультипликативной группы по модулю p (примитивный корень), а x — случайное число.
• Обратная задача: Дискретное логарифмирование — нахождение x по заданным y, g и p.
• Сложность: Возведение в степень по модулю выполняется быстро с помощью алгоритма быстрого возведения в степень. Нахождение дискретного логарифма в конечных полях большого размера является вычислительно сложной задачей. На этой основе построены криптосистема Эль-Гамаля и протокол Диффи-Хеллмана.

Вычисление квадратного корня по модулю

• Прямая функция: Вычисление квадрата числа по модулю составного числа N (y = x^2 mod N), где N = p × q, а p и q — большие простые числа, известные только создателю функции.
• Обратная задача: Извлечение квадратного корня по модулю N без знания разложения N на множители.
• Сложность: Если факторизация N неизвестна, задача извлечения квадратного корня по модулю N эквивалентна по сложности самой факторизации. Эта функция лежит в основе криптосистемы Рабина.

Хеш-функции

Криптографические хеш-функции (например, SHA-256, SHA-3) являются практическими реализациями односторонних функций, хотя их теоретическая стойкость не доказана. Они преобразуют сообщение произвольной длины в хеш-значение фиксированной длины (например, 256 бит). Основные свойства:

• Однонаправленность: По заданному хешу вычислительно невозможно найти сообщение, которое его порождает (свойство preimage resistance).
• Стойкость к коллизиям: Вычислительно невозможно найти два различных сообщения с одинаковым хешем.

Хеш-функции широко применяются для проверки целостности данных, хранения паролей и в цифровых подписях.

Применение в криптографии

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

Шифрование с открытым ключом

В асимметричной криптографии открытый ключ представляет собой описание прямой функции (легко вычислимой), а секретный ключ — «лазейку» или дополнительную информацию, которая делает обращение функции вычислительно простым. Такие функции называются односторонними функциями с потайным входом (trapdoor one-way function). Например, в RSA открытый ключ (e, N) задаёт функцию шифрования, а секретный ключ (d) позволяет легко выполнить расшифрование, зная факторизацию N.

Цифровые подписи

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

Протоколы аутентификации и обмена ключами

Протокол Диффи-Хеллмана, основанный на сложности дискретного логарифмирования, позволяет двум сторонам безопасно установить общий секретный ключ по незащищённому каналу связи.

Хранение паролей

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

Теоретическое значение и открытые проблемы

Односторонние функции тесно связаны с проблемой равенства классов сложности P и NP. Если P = NP, то любая задача, решение которой можно проверить за полиномиальное время (класс NP), может быть и решена за полиномиальное время. Поскольку задача обращения односторонней функции, очевидно, лежит в NP (дан y и x, можно проверить, что f(x) = y за полиномиальное время), то из P = NP следовало бы, что односторонних функций не существует. Таким образом, доказательство существования односторонних функций было бы доказательством того, что P ≠ NP, что является одной из величайших нерешённых задач математики и информатики.

Обратное утверждение (P ≠ NP ⇒ существование односторонних функций) не является доказанным. Существуют гипотезы о том, что даже при P ≠ NP односторонние функции могут не существовать.

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

Основная критика концепции односторонних функций связана с отсутствием строгого доказательства их существования. Все используемые на практике кандидаты могут быть взломаны в будущем при появлении новых математических методов или создании достаточно мощных квантовых компьютеров.

Например, квантовый компьютер, использующий алгоритм Шора, способен эффективно решать задачи факторизации и дискретного логарифмирования, что сделает RSA и криптосистему Эль-Гамаля небезопасными. В связи с этим активно развивается постквантовая криптография, которая ищет односторонние функции, устойчивые к атакам с использованием квантовых вычислений (например, на основе решёток, кодов, хешей).

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

Источники

• Голдрейх О. Основы криптографии. Том 1. Основные инструменты. — М.: Вильямс, 2007.
• Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. — М.: Триумф, 2002.
• Менезес А., ван Ооршот П., Ванстон С. Справочник по прикладной криптографии. — М.: Техносфера, 2006.
• Arora S., Barak B. Computational Complexity: A Modern Approach. — Cambridge University Press, 2009.
• Papadimitriou C. H. Computational Complexity. — Addison-Wesley, 1994.