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

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

С математической точки зрения, если 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]

См. Также [ править ]

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

Заметки [ править ]

  1. ↑ Островский, стр. 6-9
  2. ^ Заметки Pass, def. 56,1
  3. ^ Конспекты Голдвассером,опр. 2,16
  4. Перейти ↑ Ostrovsky, pp. 6-10, def. 11
  5. ^ Заметки Пасса, def 56.1; Додиса деф 7, лекция 1.
  6. ^ Конспекты Голдвассером в, 2.3.2; Примечания Линделла, стр. 17, Исх. 1.
  7. ^ Конспекты Голдвассером в 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 г.