Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 10 сентября 2017 года; проверки требуют 38 правок.
Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 10 сентября 2017 года; проверки требуют 38 правок.
Односторонняя функция с потайным входом
Односторонняя функция с потайным входом (англ.trapdoor function, TDF) — это односторонняя функция из множества в множество , обладающая свойством (потайным входом, лазейкой), благодаря которому становится возможным найти для любого такое, что , то есть обратить функцию.
В настоящее время доподлинно не установлено, что односторонние функции с потайным входом действительно являются односторонними, то есть нет доказательства того, что, не зная потайной вход, криптоаналитик не сможет обратить функцию.
Понятие односторонней функции с потайным входом было введено в середине 1970-х годов после публикации Уитфилдом Диффи, Мартином Хеллманом и Ральфом Мёрклом статьи об асимметричных методах шифрования (шифрование с открытым ключом). Именно Диффи и Хеллман ввели данный термин[1]. Но первой системой, в которой были использованы такие идеи, считается система, изобретённая в 1973 годуКлиффордом Коксом, работавшим в центре правительственной связи (GCHQ), но эта работа хранилась лишь во внутренних документах центра, поэтому о её существовании не было известно до 1977 года[2].
Статья описывала новый способ для минимизации необходимости передачи ключей по защищённым каналам, а также в ней была разобрана криптографическая система, которая может использоваться в создании цифровой подписи[3].
Авторы показали, что односторонняя функция с потайным входом может быть использована в криптосистемах с открытым ключом и в устройстве цифровой подписи[4]. Криптосистема с открытым ключом — система, в которой открытый ключ передается по незащищённому каналу. Смысл цифровой подписи заключается в том, что при пересылке подписанного сообщения от Алисы к Бобу, Боб может убедиться в том, что сообщение действительно было послано Алисой.
Благодаря односторонним функциям с потайным входом могут быть реализованы различные шифры с потайным входом, которые являются криптозащищёнными[1].
Было предложено несколько классов функций, но скоро стало понятно, что подходящие функции труднее найти, чем считалось изначально.
Например, сначала предполагалось использовать функции, основанные на задаче о сумме подмножеств. Вскоре выяснилось, что этот способ неприемлем. Примером подобной реализации может служить ранцевая криптосистема Меркла — Хеллмана.
В 2008 году были представлены односторонние функции с потайным входом, допускающие потерю информации о изначальном сообщении.
Развитие односторонних функций с потайным входом, допускающих потери[править | править код]
Данный тип функций (lossy trapdoor function), основывающийся на идее повреждения значительной части информации[6], был представлен Крисом Пейкертом и Брентом Уотерсом[7] в частности, как средство построения схемы шифрования с открытым ключом с выбранным-зашифрованным текстом.
Множество данных функций состоит из семейства двух функций:
Повторяют работу односторонней функции с потайным входом без потери части информации, то есть при наличии «лазейки» можно эффективно вычислить по значению .
Теряют часть информации о входе, тогда у выхода существует много прообразов (то есть невозможно однозначно обратить функцию).
Ключевым моментом является то, что выбранные семейства функций — полиномиально неразличимы. Следовательно, ключи могут быть заменены ключами с потерями без уведомления кого-либо. Но как только все ключи потеряны, шифрованный текст больше не содержит (значительную) информацию об зашифрованном сообщении. В то же время, если просто заменить функцию с лазейкой функцией с потерями, то нет возможности ответить даже на правильно сформированный запрос на дешифрование, потому что информация открытого текста будет утеряна. Поэтому используются более полные абстракции
Односторонние функции с потайным входом «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].
Известно, что функции, связанные с задачей дискретного логарифмирования, не являются односторонними функциями с потайным входом, потому что нет никакой информации о «лазейке», которая позволила бы эффективно вычислять дискретный логарифм. Однако, задача дискретного логарифмирования может использоваться в качестве основы для «лазейки», например, вычислительная задача Диффи-Хеллмана (CDH) и его разновидности. Алгоритм цифровой подписи основан на данной вычислительной задаче.
Односторонние функции с потайным входом имеют очень специфическое применение в криптографии и их не нужно путать с бэкдором (часто одно понятие подменяется другим, но это неправильно). Бэкдор — механизм, который намеренно добавляется к шифровальному алгоритму (например, алгоритм генерации ключевых пар, алгоритм цифровой подписи, и т. д.) или к операционным системам, позволяя одному или нескольким посторонним лицам обходить или подрывать безопасность системы.
↑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. — ISSN1571-0661. — doi:10.1016/j.entcs.2005.09.039.
↑ 12Chris 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. — ISSN1571-0661. — doi:10.1145/1374376.1374406.
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.