Односторонняя функция с потайным входом

Односторонняя функция с потайным входом  — это функция,которая легко вычисляется в одном направлении, но трудно вычисляется вобратном без специальной информации (секрета), называемой «лазейкой» или«потайным входом». Односторонние функции с потайным входом широкоиспользуются в криптографии.
 Данная функция была введена в 1976 году Уитфилдом Диффи, МартиномХеллманом и Ральфом Мёрклом. Главное отличие от обычной одностороннейфункции заключается в том, что функции с потайным входом не обязательнотеряют информацию. Примерами применения таких функций могут служитьалгоритм RSA, функция Рабина, схемы Эль-Гамаля и другие.
 В настоящее время доподлинно не установлено, что односторонние функции спотайным входом действительно являются односторонними, т.е. нетдоказательства того, что, не зная потайной вход, криптоаналитик несможет обратить функцию.

Определение


 Функция
F:{0,1}l(n)×{0,1}n{0,1}m(n)

{0,1}l(n) - множество открытых ключей.
{0,1}m(n) - отображаемый элемент, состоящий из n битов.
 называется односторонней с потайным входом, если

  1. Она является односторонней.
  2. Существует эффективный алгоритм, который при заданных открытом ключе Y, сообщении M и значении функции вычисляет M` такое, что F(M) = F(M`) для некоторого ключа Z.
  3. Для данного сообщения M и функции F(M) трудно найти сообщение M`≠M такое, что F(M) = F(M`).

 Иначе говоря, если F — односторонняя функция с потайным входом, тогдасуществует секретная информация Y, такая, что при известных F(х) и Yлегко вычислить x. Рассмотрим замок и его ключ. Можно изменить состояниезамка с открытого на закрытое, не прибегая к использованию ключа,защелкнув дужку замка. Это простая задача. Однако, чтобы легко открытьзамок, требуется ключ. В данном примере ключом является «лазейка».

История


 Понятие односторонней функции с потайным входом было введено в середине1970-х годов после публикации Уитфилдом Диффи, Мартином Хеллманом иРальфом Мёрклом статьи об асимметричных методах шифрования (шифрование соткрытым ключом). Именно Диффи и Хеллман ввели данный термин.
 Статья описывала новый способ для минимизации необходимости передачиключей по защищенным каналам, а также в ней была разобранакриптографическая система, которая может использоваться в созданиицифровой подписи.
 Авторы также показали, что одностороняя функция с потайным входомиспользуется в криптосистемах с открытым ключом и в устройстве цифровойподписи. Криптосистема с открытым ключом — система, в которой открытыйключ передается по незащищённому каналу. Смысл цифровой подписизаключается в том, что при пересылке подписанного сообщения от Алисы кБобу, Боб может убедиться в том, что сообщение действительно былопослано Алисой.
 Благодаря односторонним функциям с потайным входом могут бытьреализованы различные шифры с потайным входом. Эти шифры являютсякриптозащищенными.
 Было предложено несколько классов функций, но скоро стало понятно, чтоподходящие функции труднее найти, чем считалось изначально. Например,сначала предполагалось использовать функции, основанные на задаче суммыподмножества. Вскоре выяснилось, что этот способ неприемлем.
 В 2005 году самыми подходящими кандидатами в односторонние функции спотайным входом являлись функции из классов RSA и Рабина . Эти функциииспользуют возведение в степень по модулю составного числа, и обе ониоснованы на задаче факторизации целых чисел.

Развитие односторонних функций с потайнымвходом


Односторонние функции с потайным входом, допускающиепотери


 Данную функцию впервые ввели Крис Пейкерт и Брент Уотерс . Ониоснованы на идее повреждения значительной части информации.
 Такие функции имеют два свойства:

  1. Повторяют работу обычной односторонней функции с потайным входом, то есть при наличии «лазейки» позволяет эффективно вычислить x по значению F(x).
  2. Теряют часть информации о входе, тогда у выхода F(x) существует много прообразов.

 Основная особенность в том, что эти два свойства становятся фактическинеразличимыми. Зная только зашифрованное сообщение F(x), ни одинкриптоаналитик не может сказать, какая функция была использована — спотерями или без.
 Односторонние функции с потайным входом, допускающие потери применяютсяво многих схемах шифрования. В их число входят: детерминированноешифрование с открытым ключом, защита от атак выборочного открытоготекста и другие. Также эти функции могут использоваться впсевднослучайных генераторах.

Односторонние функции с потайным входом «Все, кромеодного»


 Для исследований атак, проводимых на основе подобранного шифротекста,были введены односторонние функции с потайным входом «Все, кромеодного».
 Каждая функция имеет дополнительный аргумент, называемый ветвью. Всеветви являеются односторонними функциями с потайным входом с одной«лазейкой», за исключением одной — которая является ветвью с потерями.Данная ветвь определяется как параметр функции, причём его значение —скрыто (с точки зрения вычисления) описанием полученной функции.

Применение односторонних функций с потайнымвходом


RSA


 Возьмем число n=pq, где p и q принадлежат множествупростых чисел. Считается, что для данного числа n вычисление p и qявляется математически трудной задачей. Функция шифрования RSA —E(m)=memodn, где e — взаимнопростое с (p1)(q1). Числаp и q являются потайным входом, зная которые вычислить обратнуюфункцию E1 легко. На сегодняшний день лучшей атакой на RSAявляется факторизация числа n.

ФункцияРабина


 Рассмотрим функцию F(x,n)=x2mod(n), где n=pq, а p и qпринадлежат множеству простых чисел. Рабин показал, что вычислитьфункцию f1 легко тогда и только тогда, когда разложение намножители составного числа из двух простых является простой задачей.

СхемаЭль-Гамаля


 Данная схема была предложена Тахером Эль-Гамалем в 1984 году. Онаосновывается на задаче дискретного логарифмирования.
 Алгоритм

  1. Алиса выбирает простое чисто p и произвольное число a.
  2. Алиса вычисляет свой открытый ключ (а, b), где b=ac, $1
  3. Боб выбирает $1m: (m1,m2)=(ad,mbd)
  4. Алиса расшифровывает сообщение m=m2(m1c)1.

Криптосистема PollyCracker


 Алгоритм

  1. Алиса случайным образом выбирает вектор в конечном поле.
  2. Алиса строит полиномы, которые в точке, задаваемой этим вектором, обращаются в ноль.
  3. Боб генерирует сумму p=qibi
  4. Боб посылает p+m

Другиепримеры


 Известно, что функции, связанные с задачей дискретного логарифмирования,не являются односторонними функциями с потайным входом, потому что нетникакой информации о «лазейке», которая позволила бы эффективновычислять дискретный логарифм. Однако, задача дискретногологарифмирования может использоваться в качестве основы для «лазейки»,например, вычислительная задача Диффи-Хеллмана (CDH) и егоразновидности. Алгоритм цифровой подписи основан на CDH.
 Односторонние функции с потайным входом имеют очень специфическоеприменение в криптографии и их не нужно путать с бэкдором (часто однопонятие подменяется другим, но это неправильно). Бэкдор — механизм,который намеренно добавляется к шифровальному алгоритму (например,алгоритм генерации ключевых пар, алгоритм цифровой подписи, и т. д.) илик операционным системам, позволяя одному или нескольким постороннимлицам обходить или подрывать безопасность системы.