Функция люка

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

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

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

В этом примере обратная функция по модулю ( функция Эйлера ) представляет собой люк: ${\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 г.). «Функции-люки «многие к одному» и их связь с криптосистемами с открытым ключом». Достижения криптологии — КРИПТО '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.

Рекомендации

• Диффи, В .; Хеллман, М. (1976), «Новые направления в криптографии» (PDF) , Транзакции IEEE по теории информации , 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 г.