Основы современной криптографии

       

Общие положения


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

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

Криптосистема с открытым ключом определяется тремя алгоритмами: генерации ключей, шифрования и расшифрования. Алгоритм генерации ключей открыт, всякий может подать ему на вход случайную строку r

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

 и расшифрования
таковы, что для любого открытого текста m

.

Рассмотрим теперь гипотетическую атаку злоумышленника на эту систему. Противнику известен открытый ключ k1, но неизвестен соответствующий се­кретный ключ k2. Противник перехватил криптограмму d и пытается найти сообщение m, где

.

Поскольку алгоритм шифрования открыт, противник может просто последовательно перебрать все возможные сообщения длины n, вычислить для каждого такого сооб­щения mi криптограмму

 и сравнить di

с d. То сообщение, для которого di = d и будет искомым открытым текстом. Если пове­зет, то открытый текст будет найден достаточно быстро. В худшем же случае перебор будет выполнен за время порядка 2nT(n), где T(n) – время, требуемое для шифрования сообщения длины п. Если сообщения имеют длину порядка 1000 битов, то такой перебор неосуществим на практике ни на каких самых мощных компьютерах.


Мы рассмотрели лишь один из возможных способов атаки на кри­птосистему и простейший алгоритм поиска открытого текста, назы­ваемый обычно алгоритмом полного перебора. Используется также и другое название: «метод грубой силы». Другой простейший алгоритм поиска открытого текста – угадывание. Этот очевидный алгоритм требует небольших вычислений, но срабатывает с пренебрежимо малой вероятностью (при больших длинах текстов). На самом деле противник может пытаться атаковать криптосистему различными способами и использовать различные, более изощренные алгоритмы поиска откры­того текста.

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

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

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



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

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

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

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



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

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

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

В основном, рассматриваются предположения двух типов – общие (или теоретико-сложностные) и теоретико-числовые, т. е. предполо­жения о сложности конкретных теоретико-числовых задач. Все эти предполо­жения в литературе обычно называются криптографическими.



Рассмотрим одно из таких предположений.

Обозначим через S множество всех конечных двоичных слов, а через Sn – множество всех двоичных слов длины n. Под­множества L О S в теории сложности принято называть языками. Говорят, что машина Тьюринга М

работает за полиномиальное время (или просто, что она полиномиальна), если существует полином р такой, что на любом входном слове длины п

машина М останавливается после выполнения не бо­лее, чем р(п) операций. Машина Тьюринга М распознает (другой термин – принимает) язык L, если на всяком входном слове x О L машина М оста­навливается в принимающем состоянии, а на всяком слове х П L – в от­вергающем. Класс Р – это класс всех языков, распознаваемых машинами Тьюринга, работающими за полино­миальное время. Функция f:S ® S вы­числима за полиномиальное время, если существует полиномиальная машина Тьюринга такая, что если на вход ей подано слово x О S, то в момент оста­нова на ленте будет записано значение f(x). Язык L принадлежит классу NP, если существуют предикат Р(х,у): SґS ® {0,1}, вычислимый за поли­но­миальное время, и полином р такие, что L = {x| $ y P(x,y)& |y| Ј р(|x|)}.

То есть язык L принадлежит NP, если для всякого слова из L дли­ны п можно угадать некоторую строку полиномиальной от п длины и за­тем с помощью предиката Р убедиться в правильности догадки. Ясно, что Р Н NP. Является ли это включение строгим – одна из самых известных не­решенных задач математики. Большинство специалистов считают, что оно строгое (так называемая гипотеза P

NP). В классе NP

выделен подкласс максимально сложных языков, называемых NP-полными: любой NP-полный язык распознаваем за полиномиальное время тогда и только тогда, когда P = NP.

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



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

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

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

L = {(k1,d,i)| $ сообщение т:
 и mi = 1}.

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

В предположении P = NP

существует детерминированный полино­ми­альный алгоритм, распознающий язык L.

Зная k1 и d, с помощью это­го алгоритма можно последовательно, по биту, вычислить открытый текст т. Тем самым доказано, что криптосистема нестойкая.

Что же касается вопроса о достаточности предположения P

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

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

NP. А именно, предположение о существовании односторонних функций.


Содержание раздела