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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Односторонние функции с потайным входом широко используются в асимметричных методах шифрования (шифрование с открытым ключом) в таких как: RSA, функция Рабина, схемы Эль-Гамаля, криптосистема McEliece, криптографическая система NTRUEncrypt, Polly Cracker, а также в менее популярной, из-за своей криптографической нестойкости, Ранцевой криптосистеме Меркла — Хеллмана.

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

Определение[править | править код]

Функция , где

- множество открытых ключей,

- отображаемый элемент, состоящий из n битов,

называется односторонней с потайным входом, если

  1. Она является односторонней;
  2. Существует эффективный алгоритм, который при заданных открытом ключе , сообщении и значении функции вычисляет такое, что для некоторого ключа ;
  3. Для данного сообщения и функции трудно найти сообщение такое, что .

История[править | править код]

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

Понятие односторонней функции с потайным входом было введено в середине 1970-х годов после публикации Уитфилдом Диффи, Мартином Хеллманом и Ральфом Мёрклом статьи об асимметричных методах шифрования (шифрование с открытым ключом). Именно Диффи и Хеллман ввели данный термин[1]. Но первой системой, в которой были использованы такие идеи, считается система, изобретенная в 1973 году Клиффордом Коксом (англ. Clifford Cocks), работавшим в центре правительственной связи (GCHQ), но эта работа хранилась лишь во внутренних документах центра, поэтому о её существовании не было известно до 1977 года[2]

Статья описывала новый способ для минимизации необходимости передачи ключей по защищенным каналам, а также в ней была разобрана криптографическая система, которая может использоваться в создании цифровой подписи[3].

Авторы показали, что односторонняя функция с потайным входом может быть использована в криптосистемах с открытым ключом. Криптосистема с открытым ключом — система, в которой открытый ключ передается по защищенному каналу. Смысл цифровой подписи же заключается в том, что при пересылке подписанного сообщения от Алисы к Бобу, Боб может убедиться в том, что сообщение действительно было послано Алисой. Ин

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

В 2005 году самыми подходящими кандидатами в односторонние функции с потайным входом являлись функции из классов RSA и Рабина [4]. Эти функции используют возведение в степень по модулю составного числа, и обе они основаны на задаче факторизации целых чисел.

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

Развитие односторонних функций с потайным входом, допускающих потери[править | править код]

Данный тип функций (lossy trapdoor function), основывающийся на идее повреждения значительной части информации[5], был представлен Крисом Пейкертом (англ. Chris Peikert) и Брентом Уотерсом (англ. Brent Waters) [6] в частности, как средство построения схемы шифрования с открытым ключом с выбранным-зашифрованным текстом.

Множество данных функций состоит из семейства двух функций:

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

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

Односторонние функции с потайным входом "All-but-one"[править | править код]

Функция «All-but-one» (ABO) может быть построена из набора односторонних функций с потайным входом и с достаточной потерей информации.

Набор функций ABO связан с множеством , элементы которого называются ветвями. Генератор функции ABO принимает дополнительный параметр , называемый ветвью с потерями, и выводит функцию и потайной ход t. Функция обладает тем свойством, что для любой ветви функция обладает потайным входом (и может быть инвертирована с ), но функция - функция с потерями. Более того, ветвь с потерями скрыта (вычислительно) по описанию .[7].

Односторонние функции с потайным входом "All-but-N"[править | править код]

"All-but-N"(ABN) функции имеют ровно веток с потерями; все другие ветки обладают потайным входом. Это можно использовать для точного определения зашифрованных текстов с помощью веток с потерями - все другие зашифрованные тексты соответствуют функциям с лазейкой и могут быть дешифрованы. Обратите внимание, что ABN кодируют набор веток с потерями по их ключу. То есть вычислительно неограниченный противник всегда может использовать грубую силу, для поиска ветвей, приводящих к функции с потерями.

Следовательно, ABN функции имеют серьезный недостаток: а именно, пространственная сложность ключей линейна в [8]

Односторонние функции с потайным входом "All-but-many"[править | править код]

"All-but-many"(ABM) функция имеет суперполиномиальное множество ветвей с потерями, которые требуют наличия специального потайного хода.

Самое важное отличие от ABN-функции: с ABN набор ветвей с потерями указывается первоначально, во время построения, а ABM функции имеют лазейку, позволяющую пробовать дешифровку «на лету» из большого пула ветвей с потерями. Без этого потайного хода и даже при произвольном известном множестве ветвей с потерями нет возможности найти другую ветвь, не принадлежащую известному множеству. Это, в частности, позволяет создавать экземпляры ABM с компактными ключами и изображениями, размер которых не зависит от количества ветвей с потерями.

Данные конструкции можно рассматривать как «замаскированные» варианты сигнальных схем Boneh-Boyen (BB). В частности, ветви с потерями соответствуют действительным сигнатурам. Тем не менее, чтобы метки потерь и метки потайных ходов казались неотличимыми, необходимо делать слепые подписи, путем их шифрования или путем умножения на случайный элемент подгруппы.[9]

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

Чтобы отметить основные принципы, предположим, что общая криптосистема с поддержкой CPA имеет несколько специальных (но неформально описанных) свойств.

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

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

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

Для функции с потерями зашифрованная матрица является матрицей, состоящей из нулей: . Тогда, для каждого входного сообщения  , значение является поэлементным шифрованием нулевого-вектора, поэтому «теряет»информацию о . Однако этого недостаточно для обеспечения полной потери, поскольку выходные зашифрованные сообщения по-прежнему несут некоторую внутреннюю случайную информацию, которая может служить источником данных о входном сообщении. Поэтому необходим дополнительный контроль за их поведением. Для этого существуют специальные свойства криптосистемы:

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

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

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

Построение функций с потайным ходом "All-but-one"[править | править код]

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

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

RSA[править | править код]

Возьмем число , где и принадлежат множеству простых чисел. Считается, что для данного числа вычисление и является математически трудной задачей. Функция шифрования RSA — , где — взаимнопростое с . Числа и являются потайным входом, зная которые вычислить обратную функцию легко. На сегодняшний день лучшей атакой на RSA является факторизация числа [10][11].

Функция Рабина[править | править код]

Рассмотрим функцию , где , а p и q принадлежат множеству простых чисел. Рабин показал, что вычислить функцию легко тогда и только тогда, когда разложение на множители составного числа из двух простых является простой задачей[12].

Схема Эль-Гамаля[править | править код]

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

Алгоритм

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

Криптосистема Polly Cracker[править | править код]

Алгоритм[14]

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

Другие примеры[править | править код]

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

Замечания[править | править код]

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

См. также[править | править код]

Примечания[править | править код]

  1. Diffie, Hellman, 1976, p. 652.
  2. Cliff Cocks. Cliff Cocks papper.
  3. Diffie, Hellman, 1976, p. 644.
  4. Katja Schmidt-Samoa A New Rabin-type Trapdoor Permutation Equivalent to Factoring and Its Applications (англ.) // Electronic notes in theoretical computer science. — Elsevier, 2006. — Vol. 157. — P. 79-94. — ISSN 1571-0661. — DOI:10.1016/j.entcs.2005.09.039.
  5. Peikert, Waters, 2008, pp. 8.
  6. Peikert, Waters, 2008, pp. 6.
  7. Peikert, Waters, 2008, pp. 13-14.
  8. Chris Peikert, Brent Waters Lossy Trapdoor Functions and Their Applications∗ (англ.) // Proceeding STOC '08 Proceedings of the fortieth annual ACM symposium on Theory of computing. — 2008. — Vol. 41. — P. 79-94. — ISSN 1571-0661. — DOI:10.1145/1374376.1374406.
  9. Chris Peikert, Brent Waters Lossy Trapdoor Functions and Their Applications∗ (англ.) // Proceeding STOC '08 Proceedings of the fortieth annual ACM symposium on Theory of computing. — 2008. — Vol. 41. — P. 79-94. — ISSN 1571-0661. — DOI:10.1145/1374376.1374406.
  10. Daniel Lerch Hostalot (2007). «Factorization Attack to RSA» (en). Hakin9.
  11. S. Goldwasser, M. Bellaret (2008). «Lecture Notes on Cryptography» (en).
  12. Katja Schmidt-Samoa (2005). «A New Rabin-type Trapdoor Permutation Equivalent to Factoring and Its Applications» (en).
  13. Taher ElGamal (1985). «A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms». IEEE Transactions on Information Theory 31 (4): 469-472. DOI:10.1109/TIT.1985.1057074.
  14. Neal Koblitz, 2004, pp. 105-106.

Литература[править | править код]