Русская Википедия:Односторонняя функция с потайным входом
Односторонняя функция с потайным входом (Шаблон:Lang-en, Шаблон:Lang-en2) — это односторонняя функция <math>f</math> из множества <math>X</math> в множество <math>Y</math>, обладающая свойством (потайным входом, лазейкой), благодаря которому становится возможным найти для любого <math>y \in Im{f}, x \in X</math> такое, что <math>f(x) = y</math>, то есть обратить функцию.
Односторонние функции с потайным входом широко используются в асимметричных методах шифрования (шифрование с открытым ключом) таких как: RSA, функция Рабина, схемы Эль-Гамаля, криптосистема McEliece, криптографическая система NTRUEncrypt, Polly Cracker, а также в менее популярной, из-за своей криптографической нестойкости, ранцевой криптосистеме Меркла — Хеллмана.
В настоящее время доподлинно не установлено, что односторонние функции с потайным входом действительно являются односторонними, то есть нет доказательства того, что, не зная потайной вход, криптоаналитик не сможет обратить функцию.
Определение
Функция <math>f:\{0,1\}^{l(n)} \times \{0,1\}^{n} \xrightarrow[]{} \{0,1\}^{m(n)}</math>, где
<math>\{0,1\}^{l(n)}</math> — множество открытых ключей,
<math>\{0,1\}^{m(n)}</math> — отображаемый элемент, состоящий из n битов,
называется односторонней с потайным входом, если
- Она является односторонней;
- Существует эффективный алгоритм, который при заданных открытом ключе <math>Y</math>, сообщении <math>M</math> и значении функции вычисляет <math>M'</math> такое, что <math>f(M) = f(M')</math> для некоторого ключа <math>Z</math>;
- Для данного сообщения <math>M</math> и функции <math>f(M)</math> трудно найти сообщение <math>M' \neq M</math> такое, что <math>f(M) = f(M')</math>.
История
Развитие односторонних функций с потайным входом
Понятие односторонней функции с потайным входом было введено в середине 1970-х годов после публикации Уитфилдом Диффи, Мартином Хеллманом и Ральфом Мёрклом статьи об асимметричных методах шифрования (шифрование с открытым ключом). Именно Диффи и Хеллман ввели данный терминШаблон:Sfn. Но первой системой, в которой были использованы такие идеи, считается система, изобретённая в 1973 году Шаблон:Iw, работавшим в центре правительственной связи (GCHQ), но эта работа хранилась лишь во внутренних документах центра, поэтому о её существовании не было известно до 1977 года[1].
Статья описывала новый способ для минимизации необходимости передачи ключей по защищённым каналам, а также в ней была разобрана криптографическая система, которая может использоваться в создании цифровой подписиШаблон:Sfn.
Авторы показали, что односторонняя функция с потайным входом может быть использована в криптосистемах с открытым ключом и в устройстве цифровой подписиШаблон:Sfn. Криптосистема с открытым ключом — система, в которой открытый ключ передается по незащищённому каналу. Смысл цифровой подписи заключается в том, что при пересылке подписанного сообщения от Алисы к Бобу, Боб может убедиться в том, что сообщение действительно было послано Алисой.
Благодаря односторонним функциям с потайным входом могут быть реализованы различные шифры с потайным входом, которые являются криптозащищённымиШаблон:Sfn.
Было предложено несколько классов функций, но скоро стало понятно, что подходящие функции труднее найти, чем считалось изначально. Например, сначала предполагалось использовать функции, основанные на задаче о сумме подмножеств. Вскоре выяснилось, что этот способ неприемлем. Примером подобной реализации может служить ранцевая криптосистема Меркла — Хеллмана.
В 2005 году самыми подходящими кандидатами в односторонние функции с потайным входом являлись функции из классов RSA и Рабина [2]. Эти функции используют возведение в степень по модулю составного числа, и обе они основаны на задаче факторизации целых чисел.
В 2008 году были представлены односторонние функции с потайным входом, допускающие потерю информации о изначальном сообщении.
Развитие односторонних функций с потайным входом, допускающих потери
Данный тип функций (Шаблон:Lang-en2), основывающийся на идее повреждения значительной части информацииШаблон:Sfn, был представлен Шаблон:Iw и Шаблон:Iw Шаблон:Sfn в частности, как средство построения схемы шифрования с открытым ключом с выбранным-зашифрованным текстом.
Множество данных функций состоит из семейства двух функций:
- Повторяют работу односторонней функции с потайным входом без потери части информации, то есть при наличии «лазейки» можно эффективно вычислить <math>x</math> по значению <math>f(x)</math>.
- Теряют часть информации о входе, тогда у выхода <math>f(x)</math> существует много прообразов (то есть невозможно однозначно обратить функцию).
Ключевым моментом является то, что выбранные семейства функций — Шаблон:Iw. Следовательно, ключи могут быть заменены ключами с потерями без уведомления кого-либо. Но как только все ключи потеряны, шифрованный текст больше не содержит (значительную) информацию об зашифрованном сообщении. В то же время, если просто заменить функцию с лазейкой функцией с потерями, то нет возможности ответить даже на правильно сформированный запрос на дешифрование, потому что информация открытого текста будет утеряна. Поэтому используются более полные абстракции
Односторонние функции с потайным входом «All-but-one»
Функция «All-but-one» (ABO) может быть построена из набора односторонних функций с потайным входом и с достаточной потерей информации.
Набор функций ABO связан с множеством <math>B</math>, элементы которого называются ветвями. Генератор функции ABO принимает дополнительный параметр <math>b^* \in B</math>, называемый ветвью с потерями, и выводит функцию <math>g({\cdot}, {\cdot})</math> и потайной ход t. Функция <math>g</math> обладает тем свойством, что для любой ветви <math>b \not= b^*</math> функция <math>g (b, \cdot)</math> обладает потайным входом (и может быть инвертирована с <math>t</math>), но функция <math>g (b^*, \cdot)</math> — функция с потерями. Более того, ветвь с потерями скрыта (вычислительно) по описанию <math>g</math>.Шаблон:Sfn.
Односторонние функции с потайным входом «All-but-N»
«All-but-N»(ABN) функции имеют ровно <math>N</math> веток с потерями; все другие ветки обладают потайным входом. Это можно использовать для точного определения зашифрованных текстов с помощью веток с потерями — все другие зашифрованные тексты соответствуют функциям с лазейкой и могут быть дешифрованы. Обратите внимание, что ABN кодируют набор веток с потерями по их ключу. То есть вычислительно неограниченный противник всегда может использовать грубую силу, для поиска ветвей, приводящих к функции с потерями.
Следовательно, ABN функции имеют серьезный недостаток: а именно, пространственная сложность ключей линейна в <math>N.</math>[3]
Односторонние функции с потайным входом «All-but-many»
«All-but-many»(ABM) функция имеет суперполиномиальное множество ветвей с потерями, которые требуют наличия специального потайного хода.
Самое важное отличие от ABN-функции: с ABN набор ветвей с потерями указывается первоначально, во время построения, а ABM функции имеют лазейку, позволяющую пробовать дешифровку «на лету» из большого пула ветвей с потерями. Без этого потайного хода и даже при произвольном известном множестве ветвей с потерями нет возможности найти другую ветвь, не принадлежащую известному множеству. Это, в частности, позволяет создавать экземпляры ABM с компактными ключами и изображениями, размер которых не зависит от количества ветвей с потерями.
Данные конструкции можно рассматривать как «замаскированные» варианты сигнальных схем Boneh-Boyen (BB). В частности, ветви с потерями соответствуют действительным сигнатурам. Тем не менее, чтобы метки потерь и метки потайных ходов казались неотличимыми, необходимо делать слепые подписи, путем их шифрования или путем умножения на случайный элемент подгруппы.[3]
Построение односторонних функций с потайным входом с потерями
Чтобы отметить основные принципы, предположим, что общая криптосистема с поддержкой CPA имеет несколько специальных (но неформально описанных) свойств.
Первое свойство предполагает, что лежащая в основе криптосистема аддитивно-гомоморфна. Функция <math>f</math> (односторонняя функция с лазейкой или функция с потерями) на <math>\{0, 1\}^n </math> определяется путем шифрования поэлементно квадратной матрицы <math>M</math>.
Для оценки <math>f(x)</math>, подаем вход <math>x \in \{0, 1\}^n</math> — n-мерный бинарный вектор и вычислим (поэтапно) шифрование линейного произведения <math>x*M</math>, применяя гомоморфные операции к зашифрованным записям <math>M</math>.
Для функции с потайным входом зашифрованная матрица <math>M</math> является единичной матрицей <math>I</math>, а лазейка является ключом дешифрования для криптосистемы. Функция <math>f</math> обратима с помощью потайного входа, потому что <math>f(x)</math> — это входное шифрование <math>x * I = x</math>, которое может быть дешифровано до значения каждого бита <math>x</math>.
Для функции с потерями зашифрованная матрица <math>M</math> является матрицей, состоящей из нулей: <math> M = 0 </math>. Тогда, для каждого входного сообщения <math> x </math>, значение <math>f(x)</math> является поэлементным шифрованием нулевого-вектора, поэтому <math> f </math> "теряет" информацию о <math>x</math> . Однако этого недостаточно для обеспечения полной потери, поскольку выходные зашифрованные сообщения по-прежнему несут некоторую внутреннюю случайную информацию, которая может служить источником данных о входном сообщении. Поэтому необходим дополнительный контроль за их поведением. Для этого существуют специальные свойства криптосистемы:
- случайности можно использовать повторно в комбинациях с различными ключами без ухудшения стойкости.
- гомоморфная операция изолирует случайность, то есть случайность выходного шифротекста зависит только от случайностей во входном сообщении (а не от открытого ключа или зашифрованных сообщений). Многие известные криптосистемы гомоморфны по отношению к случайности.
С этими двумя свойствами зашифровываем матрицу <math>M</math> особым образом. Каждый столбец <math>j</math> матрицы связан с другим ключом <math>p_{kj}</math>, а лазейка — это набор соответствующих ключей расшифровки. Через каждую строку <math>i</math> шифруем запись <math>m_{i,j}</math> под ключ <math>p_{kj}</math> и ту же случайность <math>r_i</math> (используя новую случайность для каждой строки). По условию, повторно использовать случайность в паре с ключом <math>p_{kj}</math> безопасно, поэтому матрица <math>M</math> является вычислительно скрытой. Кроме того, поскольку гомоморфизм изолирует случайность, все зашифрованные тексты в конечном векторе <math>f(x)</math> также зашифровываются под такую же случайность <math>R</math> (которая зависит только от <math>(r_1, r_2 ... r_m)</math>.
Когда <math>M = I</math>, мы все ещё можем инвертировать функцию (с помощью лазейки), расшифровывая каждую зашифрованную запись <math>f(x)</math>. С другой стороны, когда матрица нулевая <math>M = 0</math>, выход функции всегда является вектором зашифрованных нулевых сообщений, где каждая запись зашифровывается по одной и той же случайности (но под разными фиксированными ключами). Поэтому число возможных выходов <math>f</math> ограничено числом возможных случайных строк, которые могут возникнуть. Выбирая размерность <math>n</math> так, что количество входов <math>2^n</math> является значительно больше, чем число случайных строк, мы можем гарантировать, что функция содержит потею информации.
Построение функций с потайным ходом «All-but-one»
Построение функций «All-but-one» с потайным входом несколько более общее. Каждая ветвь <math>b</math> функции просто соответствует другой матрице <math>M_b</math>, шифрование которой может быть получено из публичного описания функции. Функция генерируется так, что <math>M_b</math> является обратимой матрицей (и вычисляется с помощью потайного входа) для всех ветвей <math>b</math>, тогда как <math>M_{b^*} = 0</math> для ветвей с потерями <math>b^*</math>
Примеры односторонних функций с потайным входом
RSA
Возьмём число <math>n = p \cdot q</math>, где <math>p</math> и <math>q</math> принадлежат множеству простых чисел. Считается, что для данного числа <math>n</math> вычисление <math>p</math> и <math>q</math> является математически трудной задачей. Функция шифрования RSA — <math>E(m) = m^e \mod n</math>, где <math>e</math> — взаимнопростое с <math>(p-1)(q-1)</math>. Числа <math>p</math> и <math>q</math> являются потайным входом, зная которые вычислить обратную функцию <math>E^{-1}</math> легко. На сегодняшний день лучшей атакой на RSA является факторизация числа <math>n</math>[4][5].
Функция Рабина
Рассмотрим функцию <math>F(x, n) = x^2 mod(n)</math>, где <math>n = p \cdot q</math>, а p и q принадлежат множеству простых чисел. Рабин показал, что вычислить функцию <math>f^{-1}</math> легко тогда и только тогда, когда разложение на множители составного числа из двух простых является простой задачей[6].
Схема Эль-Гамаля
Данная схема была предложена Тахером Эль-Гамалем в 1984 году. Она основывается на задаче дискретного логарифмированияШаблон:Source-ref.
Алгоритм
- Алиса выбирает простое число p и произвольное число a.
- Алиса вычисляет свой открытый ключ (а, b), где <math>b=a^{c}</math>, <math>1<c<p</math>
- Боб выбирает <math>1<d<p</math> и шифрует сообщение m: <math>(m_1,m_2) = (a^d, m \cdot b^d)</math>
- Алиса расшифровывает сообщение <math>m = m_2 \cdot (m_1^{c})^{-1}.</math>
Криптосистема Polly Cracker
АлгоритмШаблон:Sfn
- Алиса случайным образом выбирает вектор в конечном поле.
- Алиса строит полиномы, которые в точке, задаваемой этим вектором, обращаются в ноль.
- Боб генерирует сумму <math>p=\sum {q_i \cdot b_i}</math>
- Боб посылает <math>p+m</math>
Другие примеры
Известно, что функции, связанные с задачей дискретного логарифмирования, не являются односторонними функциями с потайным входом, потому что нет никакой информации о «лазейке», которая позволила бы эффективно вычислять дискретный логарифм. Однако, задача дискретного логарифмирования может использоваться в качестве основы для «лазейки», например, Шаблон:Iw и его разновидности. Алгоритм цифровой подписи основан на данной вычислительной задаче.
Замечания
Односторонние функции с потайным входом имеют очень специфическое применение в криптографии и их не нужно путать с бэкдором (часто одно понятие подменяется другим, но это неправильно). Бэкдор — механизм, который намеренно добавляется к шифровальному алгоритму (например, алгоритм генерации ключевых пар, алгоритм цифровой подписи, и т. д.) или к операционным системам, позволяя одному или нескольким посторонним лицам обходить или подрывать безопасность системы.
См. также
Примечания
Литература
