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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 14:23, 29 апреля 2016.

Вычислительная сложность

Стойкость криптосистемы определяется сложностью вычислений (вычислительной сложностью) алгоритмов дешифрования.

Типы вычислительной сложности:

  • временная:
  • емкостная: , где размер задачи (количество бит), записываемый оптимальным образом в двоичном виде.

Виды задач:

  • Массовая - ее формулировка состоит из следующих пунктов:
  1. Формулировка списка параметров
  2. Формулировка свойств ответа
  • Индивидуальная - получается из массовой, если каким-либо параметрам присвоить конкретные значения.
TemplateExampleIcon.svg Пример Пример массовой задачи

Задача о коммивояжере. Формулировка:

  1. Список параметров: города, расстояния между городами.
  2. Формулировка свойств ответа: - то есть ответ представляет собой перестановку, на которой достигается


TemplateExampleIcon.svg Пример Пример индивидуальной задачи
Требуется найти минимальный среди всех, приведенных на рисунке ниже, маршрутов.
L3p3 new.PNG


Для временной вычислительной сложности оценивается сложность в среднем.

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

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

В качестве модели вычислений принята детерминированная Машина Тьюринга (Turing Machine)[1].

Типы задач

  • Решаемые (tractable): трудоемкость составляет (полиномиальная сложность), может быть огромным.
  • Трудные (hard): например, , т. е. решение уравнения от переменных.
  • Неразрешимые (untractable): например, 10-я проблема Гильберта.
TemplateExampleIcon.svg Пример Пример трудной задачи
Решение уравнения от переменных:


Табл. 1. Характеристика классов вычислительной сложности[2]
Класс Сложность Число операций Реальное время
линейный 1 мс
квадратичный 10 дней
кубический 27397 дней
экспоненциальный лет

Классификация задач по сложности

L3p4 new.PNG

P, P-TIME (Polynomial) - класс задач, решаемых за полиномиальное время (например, решение СЛАУ методом Гаусса - или - при более оптимальном подходе).

NP, NP-TIME (Non-deterministic Polynomial) - класс задач, решаемых за полиномиальное время на недетерминированной машине Тьюринга.

NP-complete - класс самых сложных NP-задач.

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

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

EXPTIME - класс задач, решаемых за экспоненциальное время.

TemplateExampleIcon.svg Пример Пример NP-задачи
Задача о рюкзаке (knapsack problem)[3]

- объем рюкзака

, то есть ищем подмножество.

Все подмножества можем пронумеровать:

Т.о. , т.е. ищем двоичное представление


TemplateExampleIcon.svg Пример Пример NP-complete-задачи
Решение системы булевых уравнений:


В настоящее время не доказана гипотеза: (предполагается, что .)

Если решение одной задачи можно получить из решения другой задачи за полиномиальное время, то такие задачи эквивалентны. Т.о., если решить NP-полную (NP-complete) за полиномиальное время, то .


Субэкспоненциальный алгоритм

Трудоемкость субэкспоненциального алгоритма:

Положим полиномиальный алгоритм, где размер входа.

Положим

TemplateExampleIcon.svg Пример Пример субэкспоненциального алгоритма
Задача дискретного логарифмирования.


Вероятностные алгоритмы

Вероятностные (стохастические) алгоритмы характеризуются тем, что на некоторых определенных шагах алгоритма делается выбор ("подбрасывается монета").[4]

Классификация вероятностных алгоритмов

  1. Типа "Монте-Карло" (могут приводить к неверным результатам в некоторых случаях).
  2. Типа "Лас-Вегас" (всегда дают правильный ответ, но в некоторых случаях могут "остановиться", "не зная", что делать дальше).
  3. Типа "Атлантик-Сити" (промежуточный тип алгоритмов между первым и вторым типами).

Открытое распределение ключей. Шарады Merkle[5]

Условие: протокол с двумя участниками. По открытому каналу ключ/сообщение передаются так, чтобы не был возможен перехват. Предполагается, что А, В не имеют общего секретного ключа.

Цель: передача сообщения от В к А.

Передаваемое сообщение: , т.е. состоит из ключа, длиной в 64 бита, и серии из 30 нулей. Т.к. то ключи выбираются случайным образом.

Механизм шифрования:




Формирование шарады:
- набор текстов (шарад)
открытый канал

Выбирает какую-либо одну шараду
Вычисляет значения на всех ключах
Злоумышленник перехватывает одну шараду:
Теоретически он тоже может перебрать все множество ключей и "вскрыть" шараду.

Перебирает ключи ; критерий верности выбранного ключа - серия из 30 нулей; расшифровка дает
Перебирает ключи и восстанавливает открытый текст:
Кроме того, так осуществляется согласование секретного ключа.
Затем шифрует открытый текст на ключе
открытый текст.

Ниже рассматривается сложность перебора всех ключей для каждого из участников протокола в отдельности.

Участник Количество операций Сложность
A
B
Z

Таким образом, сложность перебора злоумышленника Z до успеха - квадратичная, что значительно осложняет быстрый им подбор верного ключа.

Примечания

  1. Далее рассматриваются вопросы, касающиеся детерминированных алгоритмов.
  2. Таблица из книги 1980 г. изд.; тестирование проводилось на ЭВМ со скоростью операций в секунду,
  3. На основе задачи о рюкзаке создана первая криптоситсема с открытым ключом
  4. Стоит отметить, что большинство алгоритмов дешифрования - вероятностные.
  5. Один из изобретателей криптографии с открытым ключом.