Эта статья требует дополнительных ссылок для проверки . ( июль 2013 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон ) |
Функция- лазейка - это функция, которую легко вычислить в одном направлении, но трудно вычислить в противоположном направлении (найти обратное ) без специальной информации, называемой "лазейкой". Функции-лазейки широко используются в криптографии .
С математической точки зрения, если f - функция-лазейка, то существует некоторая секретная информация t , такая, что при заданных f ( x ) и t легко вычислить x . Рассмотрим замок и его ключ. Заменить замок с открытого на закрытый без использования ключа - тривиальная задача, вставив дужку в механизм замка. Однако для легкого открытия замка требуется ключ. Здесь ключ - это люк, а замок - функция люка.
Пример простой математической ловушки: «6895601 - произведение двух простых чисел. Что это за числа?» Типичным решением " грубой силы " было бы попытаться разделить 6895601 на несколько простых чисел, пока не найдешь ответ. Однако, если кому-то говорят, что 1931 - одно из чисел, ответ можно найти, введя «6895601 ÷ 1931» в любой калькулятор. Этот пример не является надежной функцией-лазейкой - современные компьютеры могут угадать все возможные ответы за секунду, - но этот пример задачи можно было бы улучшить, используя произведение двух гораздо более крупных простых чисел .
Функции-лазейки приобрели известность в криптографии в середине 1970-х годов, когда Диффи , Хеллман и Меркл опубликовали методы асимметричного (или открытого ключа) шифрования . Действительно, термин был придуман Диффи и Хеллманом (1976) . Было предложено несколько классов функций, и вскоре стало очевидно, что функции-лазейки труднее найти, чем предполагалось изначально. Например, раннее предложение состояло в том, чтобы использовать схемы, основанные на проблеме суммы подмножества . Это оказалось - довольно быстро - непригодным.
По состоянию на 2004 год [Обновить]наиболее известными кандидатами на функцию (семейство) секретных функций являются семейства функций RSA и Rabin . Оба записываются как возведение в степень по модулю составного числа, и оба связаны с проблемой разложения на простые множители .
Функции, связанные со сложностью задачи дискретного логарифмирования (либо по простому модулю, либо в группе, определенной над эллиптической кривой ), не известны как функции-лазейки, потому что нет известной "секретной" информации о группе, которая обеспечивает эффективное вычисление. дискретных логарифмов.
Люк в криптографии имеет очень специфическое вышеупомянутое значение, и его не следует путать с бэкдором (они часто используются взаимозаменяемо, что неверно). Бэкдор - это преднамеренный механизм, который добавляется к криптографическому алгоритму (например, алгоритму генерации пары ключей, алгоритму цифровой подписи и т. Д.) Или операционной системе, например, который позволяет одной или нескольким неавторизованным сторонам обойти или подорвать безопасность система каким-то образом.
Определение [ править ]
Функция люка - это набор односторонних функций { f k : D k → R k } ( k ∈ K ), в котором все K , D k , R k являются подмножествами двоичных строк {0, 1} * , удовлетворяющие следующим условиям:
- Существует алгоритм выборки с вероятностным полиномиальным временем (PPT) Gen st Gen (1 n ) = ( k , t k ) с k ∈ K ∩ {0, 1} n и t k ∈ {0, 1} * удовлетворяет | т к | < 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 ( х ). То есть, имея люк, его легко перевернуть.
- Для любого k ∈ K , без люка t k , для любого алгоритма PPT вероятность правильно инвертировать f k (т. Е. При заданном f k ( x ) найти прообраз x ' такой, что f k ( x' ) = f k ( x )) незначительно. [2] [3] [4]
Если каждая функция в коллекции выше является односторонней перестановкой, то эта коллекция также называется перестановкой лазейки . [5]
Примеры [ править ]
В следующих двух примерах мы всегда предполагаем, что факторизовать большое составное число сложно (см. Целочисленное разложение ).
Предположение RSA [ править ]
В этом примере, имеющий обратную е по модулю ф ( п ), в totient функции Эйлера от п , является люком:
Если разложение известно, φ ( п ) может быть вычислен, так что то обратный д из е можно вычислить д = е -1 моды φ ( п ), а затем с учетом у = ф ( х ) можно найти х = у d mod n = x ed mod n = x mod n . Его твердость следует из предположения RSA. [6]
Предположение Рабина о квадратичном остатке [ править ]
Пусть n - большое составное число, такое что n = pq , где p и q - большие простые числа, такие, что p 3 mod 4, q ≡ 3 mod 4, и конфиденциально для злоумышленника. Проблема состоит в том, чтобы вычислить z при таком a , что a ≡ z 2 mod n . Люк - это факторизация n . С люком решения z могут быть представлены как cx + dy , cx - dy , - cx +dy , - cx - dy , где a ≡ x 2 mod p , a ≡ y 2 mod q , c ≡ 1 mod p , c ≡ 0 mod q , d ≡ 0 mod p , d ≡ 1 mod q . См. Китайскую теорему об остатках для более подробной информации. Обратите внимание, что для простых чисел p и q можно найти x ≡ a ( p +1) / 4 modp и y ≡ a ( q +1) / 4 mod q . Здесь условия p ≡ 3 mod 4 и q ≡ 3 mod 4 гарантируют, что решения x и y могут быть корректно определены. [7]
См. Также [ править ]
- Односторонняя функция
Заметки [ править ]
- ↑ Островский, стр. 6-9
- ^ Заметки Pass, def. 56,1
- ^ Конспекты Голдвассером,опр. 2,16
- Перейти ↑ Ostrovsky, pp. 6-10, def. 11
- ^ Заметки Пасса, def 56.1; Додиса деф 7, лекция 1.
- ^ Конспекты Голдвассером в, 2.3.2; Примечания Линделла, стр. 17, Исх. 1.
- ^ Конспекты Голдвассером в 2.3.4
Ссылки [ править ]
- Диффи, В .; Hellman, М. (1976), "Новые направления в криптографии" (PDF) , IEEE Transactions по теории информации , 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 г.
- Додис, Евгений, Краткие сведения о лекциях по криптографии (осень 2008 г.) , получено 17 декабря 2015 г.
- Линделл, Иегуда, Основы криптографии (PDF) , получено 17 декабря 2015 г.