Функция люка
Функция - лазейка — это функция , которую легко вычислить в одном направлении, но которую трудно вычислить в противоположном направлении (найдя обратную ) без специальной информации, называемой «лазейкой». Функции-лазейки широко используются в криптографии . [2]
С математической точки зрения, если f является функцией-лазейкой, то существует некоторая секретная информация t , такая, что при заданных f ( x ) и t легко вычислить x . Рассмотрим висячий замок и его ключ. Легко переключить замок с открытого на закрытый без использования ключа, вставив дужку в механизм замка. Однако для легкого открытия замка требуется ключ. Здесь ключ — это люк, а замок — функция люка.
Пример простой математической лазейки: «6895601 — это произведение двух простых чисел. Что это за числа?» Типичным решением « грубой силы » будет попытка разделить 6895601 на несколько простых чисел, пока не будет найден ответ. Однако, если кому-то говорят, что 1931 является одним из чисел, можно найти ответ, введя «6895601 ÷ 1931» в любой калькулятор. Этот пример не является надежной функцией-лазейкой — современные компьютеры могут угадать все возможные ответы за секунду — но этот образец задачи можно улучшить, используя произведение двух гораздо больших простых чисел .
Функции-лазейки получили известность в криптографии в середине 1970-х годов с публикацией методов асимметричного (или с открытым ключом) шифрования Диффи , Хеллмана и Меркла . Действительно, этот термин придумали Диффи и Хеллман (1976) . Было предложено несколько классов функций, и вскоре стало очевидно, что функции-лазейки найти труднее, чем предполагалось изначально. Например, раннее предложение состояло в том, чтобы использовать схемы, основанные на проблеме суммы подмножества . Это оказалось — довольно быстро — неподходящим.
По состоянию на 2004 [Обновить]год наиболее известными кандидатами на функции (семейства) с лазейками являются семейства функций RSA и Рабина . Оба записываются как возведение в степень по модулю составного числа, и оба связаны с проблемой простой факторизации .
Функции, связанные со сложностью задачи дискретного логарифмирования (либо по модулю простого числа, либо в группе, определенной на эллиптической кривой ), не известны как функции с лазейкой, потому что нет известной информации о лазейке о группе, которая позволяет эффективное вычисление дискретных логарифмов.
