Функция люка

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

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

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

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

По состоянию на 2004 год ^[update], наиболее известными кандидатами на функции (семейства) с «лазейками» являются 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} ^* удовлетворяет | т _к | < p ( n ), в котором p — некоторый полином. Каждый t _k называется люком, соответствующим k . Из каждого люка можно эффективно взять пробу.
Учитывая входные данные k , также существует алгоритм PPT, который x ∈ Dk _. выводит То есть каждый D _k может быть эффективно дискретизирован.
Для любого k ∈ K существует алгоритм PPT, который правильно fk _{вычисляет} .
Для любого k ∈ K существует алгоритм PPT A st для любого x ∈ D _k , пусть y = A ( k , f _k ( x ), t _k ), и тогда f _k ( y ) = f _k ( х ). То есть, имея люк, его легко перевернуть.
Для любого k ∈ K , без лазейки , _tk для любого алгоритма PPT вероятность правильно инвертировать fk ₍ т.е. при заданном ( _fk x ) , найти прообраз x' такой, что ( _fk x ' ) = f _k ( x )) незначительно. ^{[ 3 ]}^{[ 4 ]}^{[ 5 ]}

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

Примеры

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

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

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

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

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

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

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

См. также

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

Примечания

^ Островский, стр. 6–9.
^ Белларе, М. (июнь 1998 г.). «Функции-люки «многие к одному» и их связь с криптосистемами с открытым ключом». Достижения криптологии — КРИПТО '98 . Конспекты лекций по информатике. Том. 1462. стр. 283–298. дои : 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 Transactions on Information Theory , 22 (6): 644–654, CiteSeerX 10.1.1.37.9720 , doi : 10.1109/TIT.1976.1055638
Пасс, Рафаэль, Курс криптографии (PDF) , получено 27 ноября 2015 г.
Гольдвассер, Шафи, Конспекты лекций по криптографии (PDF) , получено 25 ноября 2015 г.
Островский, Рафаил, Основы криптографии (PDF) , получено 27 ноября 2015 г.
Додис, Евгений, Конспект лекций «Введение в криптографию» (осень 2008 г.) , получено 17 декабря 2015 г.
Линделл, Иегуда, Основы криптографии (PDF) , получено 17 декабря 2015 г.

[1] Островский, стр. 6–9.

[2] Белларе, М. (июнь 1998 г.). «Функции-люки «многие к одному» и их связь с криптосистемами с открытым ключом». Достижения криптологии — КРИПТО '98 . Конспекты лекций по информатике. Том. 1462. стр. 283–298. дои : 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.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]