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

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

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

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

Определение

править

Функция  , где

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

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

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

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

История

править

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

править

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

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

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

Благодаря односторонним функциям с потайным входом могут быть реализованы различные шифры с потайным входом, которые являются криптозащищёнными[1].

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

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

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

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

править

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

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

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

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

Односторонние функции с потайным входом «All-but-one»

править

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

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

Односторонние функции с потайным входом «All-but-N»

править

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

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

Односторонние функции с потайным входом «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 является факторизация числа  [10][11].

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

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

Алгоритм

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

Криптосистема Polly Cracker

править

Алгоритм[14]

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

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

править

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

Замечания

править

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

См. также

править

Примечания

править
  1. 1 2 Diffie, Hellman, 1976, p. 652.
  2. Cliff Cocks. Cliff Cocks papper. Дата обращения: 23 ноября 2017. Архивировано из оригинала 16 февраля 2017 года.
  3. Diffie, Hellman, 1976, p. 644.
  4. Diffie, Hellman, 1976, pp. 647—649.
  5. 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.
  6. Peikert, Waters, 2008, pp. 8.
  7. Peikert, Waters, 2008, pp. 6.
  8. Peikert, Waters, 2008, pp. 13—14.
  9. 1 2 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. Factorization Attack to RSA (англ.) // Hakin9 : journal. — 2007. Архивировано 9 ноября 2011 года.
  11. S. Goldwasser, M. Bellaret. Lecture Notes on Cryptography (англ.) : journal. — 2008. Архивировано 8 октября 2011 года.
  12. Katja Schmidt-Samoa. A New Rabin-type Trapdoor Permutation Equivalent to Factoring and Its Applications (англ.) : journal. — 2005. Архивировано 9 апреля 2016 года.
  13. Elgamal T. A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms (англ.) // IEEE Transactions on Information Theory / F. KschischangIEEE, 1985. — P. 10—18. — ISSN 0018-9448; 1557-9654doi:10.1109/TIT.1985.1057074; doi:10.1007/3-540-39568-7_2
  14. Neal Koblitz, 1998, pp. 105—106.

Литература

править
  • Xavier Boyen, Xiaofeng Chen. General Construction of Chameleon All-But-One Trapdoor Functions // Provable Security: 5th International Conference (англ.). — Springer, 2011. — P. 257—261. — ISBN 9783642243158.
  • Giuseppe Longo. Section 4.2: Cryptographic functions // Secure digital communications (неопр.). — 1983. — С. 29—30. — ISBN 0-387-81784-0.
  • Chris Peikert, Brent Waters. Lossy Trapdoor Functions and Their Applications (англ.). — 2008. — ISBN 978-1-60558-047-0.
  • Julien Cathalo, Christophe Petit. One-time trapdoor one-way functions (англ.). — Springer, 2011. — ISBN 9783642181771.
  • Ronald C. Mullin, Gary L. Mullen. Finite fields : theory, applications, and algorithms : Fourth International Conference on Finite Fields: Theory, Applications, and Algorithms (англ.). — Providence, R.I. : American Mathematical Society, 1998. — ISBN 0821808176.
  • Neal Koblitz. Algebraic aspects of cryptography. — Springer. — 1998. — ISBN 3540634460.
  • Diffie W., Hellman M. E. New Directions in Cryptography (англ.) // IEEE Transactions on Information Theory / F. KschischangIEEE, 1976. — Vol. 22, Iss. 6. — P. 644—654. — ISSN 0018-9448; 1557-9654doi:10.1109/TIT.1976.1055638