Дверь — имя прилагательное

В развитии нашего криптографического хозяйства за последнее время достигнуты значительные успехи. Перевыполнен план по выпуску криптографической литературы. На прилавки наших книжных магазинов хлынул поток изданий, посвященных криптографии и защите информации вообще.

Вместе с тем имеются еще отдельные недостатки.

Просмотрев с десяток книг по криптографической тематике, я обнаружил, что по крайней мере в половине из них предпринята попытка объяснить (неформально), что такое функция с секретом, и среди этих объяснений нет ни одного (!!!) корректного. Все сочинители наступают, в общем-то, на одни и те же грабли.

Но сначала о терминологии. Англоязычный термин trapdoor function у нас переводят по-разному. Варианты типа “функция с ловушкой” безусловно неприемлемы, поскольку не отражают суть понятия. Если и существуют какие-то ловушки, связанные с этими функциями, то только те, о которых речь пойдет ниже (у нас их принято называть “граблями”). Термины “функция с лазейкой” и “функция с потайной дверью” в принципе неплохо отражают смысл понятия. Но разве не режет слух всякого математика словосочетание “функция с дверью”? В описаниях криптосистемы RSA обычно говорится, что trapdoor используется как секретный ключ. Попробуйте-ка при данном переводе этого термина произнести вслух, что именно используется в качестве секретного ключа. Мы предлагаем термин “функция с секретом”. Его достоинства в том, что во-первых, подчеркивается очевидная аналогия между понятиями trapdoor function и “замок с секретом”, и во-вторых, используется родственность понятий “секрет” и “секретный ключ”.

Отметим также, что в литературе, в том числе и на английском языке встречается и такой вариант: “односторонняя функция с секретом”. Здесь, безусловно, все корректно, но эпитет “односторонняя” просто лишний. Если функция не является односторонней, то о каком секрете вообще может идти речь?

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

Рассуждения о функциях с секретом, которые встречаются в литературе на русском языке, не отличаются разнообразием. Фактически, имеются всего два варианта.

Вариант 1. Беллетристический. Это фраза следующего типа: “Функцией с секретом называется односторонняя функция, которая, тем не менее, становится легко инвертируемой, если известна некоторая дополнительная информация (секрет)”.

Словесные формулировки в математике вообще-то допустимы, но лишь в том случае, когда подразумеваемая формализация вполне очевидна. Данное же предложение вообще никаким образом не может быть формализовано. В самом деле, функция $f\colon X \to Y$ является односторонней, если она легко вычислима, но трудно инвертируема. Первое из этих требований означает, что существует эффективный алгоритм $F$, который получает на вход $x\in X$ и вычисляет $f(x)\in Y$. Функция $f$ трудно инвертируема, если не существует эффективного алгоритма $A$, вычисляющего $x\in f^{-1}(y)$ на входе $y\in Y$.

Попытаемся теперь записать, что означает, что функция $f$ становится легко инвертируемой, если известен секрет: существует эффективный алгоритм $B$, который получает на вход два слова — секрет $k$ и $y=f(x)$, где $x\in X$, и вычисляет $x’\in X$ такое, что $f(x’)=y$. Проблема в том, что понимается под секретом $k$. Если это слово универсально для всей функции $f$, то алгоритм $B$ ничем не отличается от алгоритма$A$ и получаем противоречие. Если же секрет $k$ может зависеть от второго входного слова $y$, то вопрос в том, как избежать тривиальности. Ведь можно положить $k=x’\in f^{-1}(y)$ и тогда всякая односторонняя функция будет функцией с секретом.

Вариант 2. Параметрический. Функцией с секретом называется семейство функций ${f_k}$ такое, что функция $f_k$

a) легко вычислима; b) трудно инвертируема при неизвестном $k$; c) легко инвертируема при известном $k$.

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

Попробуем формализовать п. a). Получим следующее утверждение. Существует эффективный алгоритм $F$, который на входе $x\in X$ вычисляет $f_k(x)$. Известно ли алгоритму $F$ значение секрета $k$? Если нет, то функция $f_k$ не зависит от $k$, семейство вырождается и мы возвращаемся к варианту 1. С другой стороны, всякое использование функции с секретом в качестве примитива для построения криптографических схем (криптосистем с открытым ключом, схем электронной подписи и т. п.) предполагает, что алгоритм $F$ становится общедоступным. Следовательно, секрет $k$ не может быть ему известен.

Данное противоречие разрешается относительно просто. Рассмотрим семейство функций $f\colon K_2 \times X \to Y$. Здесь $k_2\in K_2$ — описание функции $f_{k_2}$ из семейства. Иными словами, $k_2$ — открытый ключ. Секрет $k_1$ выбирается из множества $K_1$. Теперь можно сформулировать следующие требования.

  1. Существует эффективный алгоритм $F$, который на входе $(k_2,x)$, где $k_2\in K_2$, $x\in X$, вычисляет $y=f(k_2,x)$.
  2. Не существует эффективного алгоритма $A$, вычисляющего на входе $(y,k_2)$, где $y\in Y$, $k_2\in K_2$, значение $x\in X$ такое, что$f(k_2,x)=y$.
  3. Существует эффективный алгоритм $B$, который на входе $(k_1,k_2,y)$, где $k_1\in K_1$, $k_2\in K_2$, $y\in Y$, вычисляет значение$x\in X$ такое, что $f(k_2,x)=y$.

Являются ли эти требования (при надлежащей формализации) корректным определением функции с секретом? Все еще нет. Во-первых, неясно каким образом связаны между собой секрет $k_1$ и открытый ключ $k_2$. Во-вторых, необходимо избежать тривиальности, когда секрет в принципе существует, но нет никакого эффективного способа его найти.

Но теперь нам осталось сделать лишь последний шаг.

Генератором функций с секретом для семейства $f$ называется тройка эффективных алгоритмов $(G,F,B)$, где $F$ и $B$ такие как указано выше, а алгоритм $G$ генерирует пары $(k_1,k_2)$, где $k_1\in K_1$, $k_2\in K_2$. При этом требуется, чтобы $G$ выбирал $k_1$ из $K_1$равновероятным образом. Кроме того, требования пп. 1–3 должны выполняться для любой пары $(k_1,k_2)$, которая может появиться на выходе алгоритма $G$.

Подчеркнем еще раз, что математически строго можно определить лишь понятие генератора функций с секретом. Разумеется, если такой генератор существует для некоторого семейства $f$, то последнее допустимо называть семейством функций с секретом или, для краткости, просто функцией с секретом.

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

  • центральным в математической криптографии является понятие односторонней функции;
  • несмотря на значительные усилия на протяжении уже более чем четверти века, единственным гипотетическим примером функции с секретом остается на сегодняшний день функция RSA (плюс некоторые ее модификации);
  • существование функций с секретом не критично для криптографии в том смысле, что даже доказательство теоремы “функции с секретом не существуют”, само по себе еще не приведет ни к каким катастрофическим последствиям. Хорошо известны, например, конструкции криптосистем с открытым ключом и схем электронной подписи, не использующие функции с секретом.

Адрес редакции сайта: dialogus@cryptography.ru
© При копировании материалов ссылка на авторов,
© а при их отсутствии — на сайт, обязательна