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

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

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

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

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

Виды задач:

• Массовая - ее формулировка состоит из следующих пунктов:

1. Формулировка списка параметров
2. Формулировка свойств ответа

• Индивидуальная - получается из массовой, если каким-либо параметрам присвоить конкретные значения.

Пример Пример массовой задачи
Задача о коммивояжере. Формулировка: Список параметров: $~C=\{c_{1},\ldots ,c_{n}\}-$ города, $~\{d(c_{i},c_{j})\}-$ расстояния между городами. Формулировка свойств ответа: $~c_{\pi _{1}},\ldots ,c_{\pi _{n}}$ - то есть ответ представляет собой перестановку, на которой достигается $~min\sum d(c_{\pi _{i}},c_{\pi _{j}}).$

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

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

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

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

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

Типы задач

• Решаемые (tractable): трудоемкость составляет $~O(n^{t})$ (полиномиальная сложность), $~t$ может быть огромным.
• Трудные (hard): например, $P(x_{1},\ldots ,x_{n})=0$, т. е. решение уравнения от $~n$ переменных.
• Неразрешимые (untractable): например, 10-я проблема Гильберта.

Пример Пример трудной задачи
Решение уравнения от $n\,\!$ переменных: $P(x_{1},\dots ,x_{n})=0.\,\!$

Табл. 1. Характеристика классов вычислительной сложности Класс Сложность Число операций Реальное время линейный $~O(n)$ $~10^{6}$ 1 мс квадратичный $~O(n^{2})$ $~10^{12}$ 10 дней кубический $~O(n^{3})$ $~10^{18}$ 27397 дней экспоненциальный $~O(2^{n})$ $~10^{O}$ $~10^{301016}$ лет

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

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

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

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

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

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

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

Пример Пример NP-задачи
Задача о рюкзаке (knapsack problem) $~A=\{a_{1},\ldots ,a_{n}\}$ $~S$ - объем рюкзака $~S=a_{i_{1}}+\ldots +a_{i_{k}}$, то есть ищем подмножество. Все подмножества можем пронумеровать: $~{\begin{array}{c|c|c|}1\cdots n\\0\cdots 0\\0\cdots 1\\~0\cdots 10\\~0\cdots 11\\\vdots ~~\vdots ~~\vdots \\1\cdots 1\\\end{array}}2^{n}$ Т.о. $~a_{i}=2^{i-1}$, т.е. ищем двоичное представление $~S$

Пример Пример NP-complete-задачи
Решение системы булевых уравнений: $~{\begin{cases}f_{1}(x_{1},\ldots ,x_{n})=0\\\cdots \\f_{m}(x_{1},\ldots ,x_{n})=0.\end{cases}}$

В настоящее время не доказана гипотеза: $~P{\stackrel {?}{=}}NP$ (предполагается, что $~P\neq NP$.)

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

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

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

$~T=exp(\beta +O(1))\ln n^{\alpha }\ln \ln n^{1-\alpha }.$

Положим $~\alpha =0\Rightarrow T=(\ln n)^{\beta +O(1)}\Rightarrow$ полиномиальный алгоритм, где $\ln n-\,\!$ размер входа.

Положим $~\alpha =1\Rightarrow T=e^{\ln N^{\beta +O(1)}}.$

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

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

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

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

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

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

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

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

Передаваемое сообщение: $~M_{i}=(\underbrace {K_{i}} _{64},\underbrace {0\ldots 0} _{30}),i={\overline {1,10^{6}}}$, т.е. состоит из ключа, длиной в 64 бита, и серии из 30 нулей. Т.к. $~2^{64}=10^{19}\cdot 1,6>>10^{6},$ то ключи выбираются случайным образом.

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

$\color {Magenta}A\,\!$		$\color {Blue}B\,\!$
Формирование шарады: $~E_{X_{i}}(M_{i})=C_{i},$ $~\{C_{i}\}$ - набор текстов (шарад)	$~{\overrightarrow {\{C_{i}\}}}$	$~\{C_{i}\}$
	открытый канал
	$~\downarrow$	Выбирает какую-либо одну шараду $~C_{i_{0}}$ Вычисляет значения на всех ключах $~K_{i}:$
	Злоумышленник перехватывает одну шараду: $~Z:\{C_{i}\}.$ Теоретически он тоже может перебрать все множество ключей $~\{K_{i}\}$ и "вскрыть" шараду.	$~D_{X_{i}}(C_{i_{0}})=(K_{i_{0}},0^{30})$
	$~\uparrow$
		$~\uparrow$ Перебирает ключи $~\{K_{i}\}$; критерий верности выбранного ключа - серия из 30 нулей; расшифровка дает $~K_{i_{0}}.$
Перебирает ключи $~\{K_{i}\}$ и восстанавливает открытый текст: $M=D_{K_{i_{0}}}(C).$ Кроме того, так осуществляется согласование секретного ключа.	$~\longleftarrow$	Затем шифрует открытый текст на ключе $~K_{i_{0}}:$ $~C=E_{K_{i_{0}}}(M),M-$ открытый текст.

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

Участник Количество операций Сложность A $~C_{1}\cdot 10^{6}+C_{2}\cdot 10^{6}$ $~O(n)$ B $~C_{2}\cdot 10^{6}$ $~O(n)$ Z $~{\frac {1}{2}}\cdot 10^{6}\cdot C_{2}\cdot 10^{6}=C_{3}\cdot 10^{12}$ $~O(n^{2})$

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