Стойкость криптосистем

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

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

Пример 1 (Криптосистема с открытым ключом). Криптосис­тема с открытым ключом полностью определяется тремя алгоритма­ми: генерации ключей, шифрования и дешифрования. Алгоритм гене­рации ключей G общедоступен; всякий желающий может подать ему на вход случайную строку r надлежащей длины и получить пару ключей (K1,K2). Открытый ключ K1публикуется, а секретный ключ K2 и случайная строка rхранятся в секрете. Алгоритмы шифрования Ек1 и дешифрования DK2 таковы, что если (К1, К2) — пара ключей, сгенери­рованная алгоритмом G, то DK₂(EK1(m)) = т Д^ля любого открытого текста т. Для простоты изложения предполагаем, что открытый текст и криптограмма имеют одинаковую длину п. Кроме того, считаем, что открытый текст, криптограмма и оба ключа являются строками в дво­ичном алфавите.

Предположим теперь, что противник атакует эту криптосистему. Ему известен открытый ключ К1, но неизвестен соответствующий се­кретный ключ K2. Противник перехватил криптограмму d и пытается найти сообщение m, где d = EK1 (m). Поскольку алгоритм шифрования общеизвестен, противник может просто последовательно перебрать все возможные сообщения длины n, вычислить для каждого такого сооб­щения mi криптограмму di = EK1(mi) и сравнить di с d. To сообщение, для которого di = d, и будет искомым открытым текстом. Если пове­зет, то открытый текст будет найден достаточно быстро. В худшем же случае перебор будет выполнен за время порядка 2^n*Т(n), где Т(п) -время, требуемое для вычисления функции Ek1 _л от сообщений длины n. Если сообщения имеют длину порядка 1000 битов, то такой перебор неосуществим на практике ни на каких самых мощных компьютерах.

Мы рассмотрели лишь один из возможных способов атаки на кри­птосистему и простейший алгоритм поиска открытого текста, назы­ваемый обычно алгоритмом полного перебора. Используется также и другое название: “метод грубой силы”. Другой простейший алгоритм поиска открытого текста — угадывание. Этот очевидный алгоритм требует небольших вычислений, но срабатывает с пренебрежимо малой вероятностью (при больших длинах текстов). На самом деле противник может пытаться атаковать криптосистему различными способами и использовать различные, более изощренные алгоритмы поиска откры­того текста. Естественно считать криптосистему стойкой, если любой такой алгоритм требует практически неосуществимого объема вычи­слений или срабатывает с пренебрежимо малой вероятностью. (При этом противник может использовать не только детерминированные, но и вероятностные алгоритмы.) Это и есть теоретико-сложностной под­ход к определению стойкости. Для его реализации в отношении того или иного типа криптографических схем необходимо выполнить следу­ющее:

1)дать формальное определение схемы данного типа;

2)дать формальное определение стойкости схемы;

3)доказать стойкость конкретной конструкции схемы данного ти­
па.

Здесь сразу же возникает ряд проблем.

Во-первых, в криптографических схемах, разумеется, всегда ис­пользуются фиксированные значения параметров. Например, крипто-системы разрабатываются для ключей длины, скажем, в 256 или 512 байтов. Для применения же теоретико-сложностного подхода необхо­димо, чтобы задача, вычислительную сложность которой предполага­ется использовать, была массовой. Поэтому в теоретической крипто­графии рассматриваются математические модели криптографических схем. Эти модели зависят от некоторого параметра, называемого пара­метром безопасности, который может принимать сколь угодно большие значения (обычно для простоты предполагается, что параметр безопас­ности может пробегать весь натуральный ряд).

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

В-третьих, необходимо уточнить, какой объем вычислений можно считать “практически неосуществимым”. Из сказанного выше следу­ет, что эта величина не может быть просто константой, она должна быть представлена функцией от растущего параметра безопасности. В соответствии с тезисом Эдмондса алгоритм считается эффективным, если время его выполнения ограничено некоторым полиномом от длины входного слова (в нашем случае — от параметра безопасности). В про­тивном случае говорят, что вычисления по данному алгоритму прак­тически неосуществимы. Заметим также, что сами криптографические схемы должны быть эффективными, т. е. все вычисления, предписанные той или иной схемой, должны выполняться за полиномиальное время.

В-четвертых, необходимо определить, какую вероятность можно считать пренебрежимо малой. В криптографии принято считать та­ковой любую вероятность, которая для любого полинома р и для всех достаточно больших п не превосходит 1/р(п), где n — параметр безо­пасности.

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

Ниже мы кратко рассмотрим несколько интересных математиче­ских объектов, возникших на стыке теории сложности и криптографии.

Криптография и гипотеза P ≠ NP

Как правило, знакомство математиков-неспециалистов с теорией сложности вычислений ограничивается классами Р и NP и знаменитой гипотезой

Для дальнейшего нам потребуется еще понятие вероятностной машины Тьюринга. В обычных машинах Тьюринга (их называют детерминированны­ми, чтобы отличить от вероятностных) новое состояние, в которое машина переходит на очередном шаге, полностью определяется текущим состояни­ем и тем символом, который обозревает головка на ленте. В вероятностных машинах новое состояние может зависеть еще и от случайной величины, ко­торая принимает значения 0 и 1 с вероятностью 1/2 каждое. Альтернативно, можно считать, что вероятностная машина Тьюринга имеет дополнительную случайную ленту, на которой записана бесконечная двоичная случайная строка. Случайная лента может читаться только в одном направлении и пе­реход в новое состояние может зависеть от символа, обозреваемого на этой ленте.

Рассмотрим теперь следующий естественный вопрос: не является ли гипотеза P≠NP необходимым и достаточным условием для существо­вания стойких криптографических схем?

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

L = {(K1,d,i) | существует сообщение m такое, что Ек₁(т) = d и его i-ый бит равен 1}.

Ясно, что L NP: вместо описанного во введении полного перебора можно просто угадать открытый текст m и проверить за полиномиаль­ное время, что Ek1 (m) = d и i-ый бит m равен 1. Если да, то входное слово (K1,d,i) принимается, в противном случае — отвергается.

В предположении P=NP существует детерминированный полиноми­альный алгоритм, распознающий язык L. Зная К1 и d, с помощью это­го алгоритма можно последовательно, по биту, вычислить открытый текст m. Тем самым криптосистема нестойкая.

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

Что же касается вопроса о достаточности предположения P≠NP, то здесь напрашивается следующий подход: выбрать какую-либо NP-полную задачу и построить на ее основе криптографическую схему, задача взлома которой (т. е. задача, стоящая перед противником) была бы NP-полной. Такие попытки предпринимались в начале 80-х годов, в особенности в отношении криптосистем с открытым ключом, но к успеху не привели. Результатом всех этих попыток стало осознание сле­дующего факта: даже если P≠NP, то любая NP-полная задача может оказаться трудной лишь на некоторой бесконечной последовательно­сти входных слов. Иными словами, в определение класса NP заложе­на мера сложности “в худшем случае”. Для стойкости же криптогра­фической схемы необходимо, чтобы задача противника была сложной “почти всюду”. Таким образом, стало ясно, что для криптографиче­ской стойкости необходимо существенно более сильное предположение, чем P≠NP. А именно, предположение о существовании односторонних функций.

Поиск по сайту: