Функция люка

Односторонний криптографический инструмент

Идея функции-ловушки. Функция-ловушка f с ее ловушкой t может быть сгенерирована алгоритмом Gen . f может быть эффективно вычислена, т. е. за вероятностное полиномиальное время . Однако вычисление обратной функции f обычно сложно, если только не задана ловушка t . ^[1]

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

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

Примером простого математического ловушки является «6895601 — произведение двух простых чисел. Что это за числа?» Типичным решением « грубой силы » будет попытка разделить 6895601 на множество простых чисел, пока не будет найден ответ. Однако, если кому-то скажут, что 1931 — одно из чисел, можно найти ответ, введя «6895601 ÷ 1931» в любой калькулятор. Этот пример не является надежной функцией ловушки — современные компьютеры могут угадать все возможные ответы в течение секунды — но эту задачу-образец можно улучшить, используя произведение двух гораздо больших простых чисел .

Функции с секретом приобрели известность в криптографии в середине 1970-х годов с публикацией асимметричных (или с открытым ключом) методов шифрования Диффи , Хеллмана и Меркла . Действительно, Диффи и Хеллман (1976) ввели этот термин. Было предложено несколько классов функций, и вскоре стало очевидно, что функции с секретом сложнее найти, чем изначально считалось. Например, одним из первых предложений было использовать схемы, основанные на задаче суммы подмножества . Довольно быстро это оказалось неподходящим.

По состоянию на 2004 год ^{[обновлять]}наиболее известными кандидатами на роль функций-лазеек (семейств) являются семейства функций RSA и Рабина . Оба записываются как возведение в степень по модулю составного числа, и оба связаны с проблемой разложения на простые множители .

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

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

Определение

Функция -ловушка — это набор односторонних функций { f _k  : D _k → R _k } ( k ∈ K ), в которых все K , D _k , R _k являются подмножествами двоичных строк {0, 1} ^* , удовлетворяющих следующим условиям:

• Существует вероятностный полиномиальный алгоритм выборки (PPT) Gen st Gen(1 ⁿ ) = ( k , t _k ) с k ∈ K ∩ {0, 1} ⁿ и t _k ∈ {0, 1} ^* удовлетворяет | t _k | < p ( n ), в котором p — некоторый полином. Каждое t _k называется ловушкой, соответствующей k . Каждая ловушка может быть эффективно выбрана.
• При наличии входных данных k также существует алгоритм PPT, который выводит x ∈ D _k . То есть, каждый D _k может быть эффективно отобран.
• Для любого k ∈ K существует алгоритм PPT, который правильно вычисляет f _k .
• Для любого k ∈ K существует алгоритм PPT A st для любого x ∈ D _k , пусть y = A ( k , f _k ( x ), t _k ), и тогда мы имеем f _k ( y ) = f _k ( x ). То есть, учитывая лазейку, его легко инвертировать.
• Для любого k ∈ K , без лазейки t _k , для любого алгоритма PPT вероятность правильно инвертировать f _k (т.е., при заданном f _k ( x ), найти прообраз x' такой, что f _k ( x' ) = f _k ( x )) пренебрежимо мала. ^{[3] [4] [5]}

Если каждая функция в приведенном выше наборе является односторонней перестановкой, то набор также называется перестановкой с люком . ^[6]

Примеры

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

предположение RSA

В этом примере обратная функция по модулю ( функция Эйлера от ) является лазейкой: ${\displaystyle d}$ ${\displaystyle e}$ ${\displaystyle \phi (n)}$ ${\displaystyle n}$

${\displaystyle f(x)=x^{e}\mod n.}$

Если факторизация известна, то можно вычислить. При этом можно вычислить обратную величину , а затем, учитывая , можно найти . Его сложность следует из предположения RSA. ^[7] ${\displaystyle n=pq}$ ${\displaystyle \phi (n)=(p-1)(q-1)}$ ${\displaystyle d}$ ${\displaystyle e}$ ${\displaystyle d=e^{-1}\mod {\phi (n)}}$ ${\displaystyle y=f(x)}$ ${\displaystyle x=y^{d}\mod n=x^{ed}\mod n=x\mod n}$

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

Пусть будет большим составным числом, таким что , где и — большие простые числа, такие что , и хранятся в тайне от противника. Задача состоит в том, чтобы вычислить заданное таким образом, что . Секрет — это факторизация . С секретом решения z могут быть заданы как , где . Подробнее см. китайскую теорему об остатках . Обратите внимание, что для заданных простых чисел и мы можем найти и . Здесь условия и гарантируют, что решения и могут быть хорошо определены. ^[8] ${\displaystyle n}$ ${\displaystyle n=pq}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle p\equiv 3{\pmod {4}},q\equiv 3{\pmod {4}}}$ ${\displaystyle z}$ ${\displaystyle a}$ ${\displaystyle a\equiv z^{2}{\pmod {n}}}$ ${\displaystyle n}$ ${\displaystyle cx+dy,cx-dy,-cx+dy,-cx-dy}$ ${\displaystyle a\equiv x^{2}{\pmod {p}},a\equiv y^{2}{\pmod {q}},c\equiv 1{\pmod {p}},c\equiv 0{\pmod {q}},d\equiv 0{\pmod {p}},d\equiv 1{\pmod {q}}}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle x\equiv a^{\frac {p+1}{4}}{\pmod {p}}}$ ${\displaystyle y\equiv a^{\frac {q+1}{4}}{\pmod {q}}}$ ${\displaystyle p\equiv 3{\pmod {4}}}$ ${\displaystyle q\equiv 3{\pmod {4}}}$ ${\displaystyle x}$ ${\displaystyle y}$

Смотрите также

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

Примечания

1. Островский, стр. 6–9
2. Беллар, М. (июнь 1998 г.). «Функции-ловушки «многие к одному» и их связь с криптосистемами с открытым ключом». Достижения в криптологии — CRYPTO '98 . Конспект лекций по информатике. Том 1462. С. 283–298. doi :10.1007/bfb0055735. ISBN 978-3-540-64892-5. S2CID  215825522.
3. Заметки Пасса, деф. 56.1
4. Заметки лекций Гольдвассера, определение 2.16
5. Островский, стр. 6–10, деф. 11
6. Заметки Пасса, определение 56,1; определение Додиса 7, лекция 1.
7. Заметки лекций Голдвассера, 2.3.2; заметки Линделла, стр. 17, пример 1.
8. Конспект лекций Гольдвассера, 2.3.4.

Ссылки

• Диффи, В.; Хеллман , М. (1976), «Новые направления в криптографии» (PDF) , Труды IEEE по теории информации , 22 (6): 644–654, CiteSeerX  10.1.1.37.9720 , doi :10.1109/TIT.1976.1055638
• Пасс, Рафаэль, Курс криптографии (PDF) , получено 27 ноября 2015 г.
• Goldwasser, Shafi, Lecture Notes on Cryptography (PDF) , получено 25 ноября 2015 г.
• Островский, Рафаил, Основы криптографии (PDF) , получено 27 ноября 2015 г.
• Додис, Евгений, Введение в криптографию Lecture Notes (осень 2008 г.) , получено 17 декабря 2015 г.
• Линделл, Йехуда, Основы криптографии (PDF) , получено 17 декабря 2015 г.