Функция люка

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

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

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

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

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

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

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

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

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

Примечания

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

[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.