16.8. Классы сложности задач

Данный раздел поясняет обоснованность стойкости криптосистем с открытым ключом и имеет лишь косвенное отношение к дискретной математике.

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

неограниченная лента, разделённая на клетки; в каждой клетке содержится символ из конечного алфавита, содержащего пустой символ blank; если символ ранее не был записан на ленту, то он считается blank;
печатающая головка, которая может считать, записать символ $a_i$ и передвинуть ленту на 1 клетку влево или вправо $d_k$;
конечная таблица действий
$$ (q_i, a_j) \rightarrow (q_{i1}, a_{j1}, d_k), $$
где $q$ – состояние машины.

Если таблица переходов однозначна, то машина Тьюринга называется детерминированной. Детерминированная машина Тьюринга может имитировать любую существующую детерминированную ЭВМ. Если таблица переходов неоднозначна, то есть $(q_i, a_j)$ может переходить по нескольким правилам, то машина недетерминированная.

Класс задач ${\mathbb{P}}$ – задачи, которые могут быть решены за полиномиальное время на детерминированной машине Тьюринга. Пример полиномиальной сложности (количество битовых операций)

$$ O(k^{\textrm{const}}), $$

где $k$ – длина входных параметров алгоритма. Операция возведения в степень в модульной арифметике $a^b \mod n$ имеет кубическую сложность $O(k^3)$, где $k$ – двоичная длина чисел $a,b,n$.

Класс задач ${\mathbb{NP}}$ – обобщение класса ${\mathbb{P}} \subseteq {\mathbb{NP}}$, включает задачи, которые могут быть решены за полиномиальное время на недетерминированной машине Тьюринга. Пример сложности задач из ${\mathbb{NP}}$ – экспоненциальная сложность

$$ O(\textrm{const}^k). $$

Алгоритм Гельфонда — Шенкса решения задачи дискретного логарифмирования (нахождения $x$ для заданных основания $g$, модуля $p$ и $a = g^x \mod p$), описанный в разделе криптостойкости системы Эль-Гамаля, имеет сложность $O(e^{k/2})$, где $k$ – двоичная длина чисел.

В криптографии полиномиальные задачи (относящиеся к классу ${\mathbb{P}}$) считаются лёгкими и вычислимыми на ЭВМ, которые являются детерминированными машинами Тьюринга. Для них, по определению, существуют алгоритмы, работающие за время, полиномиальное относительно размера входных данных. Задачи, относящиеся к классу ${\mathbb{NP}}$, считаются трудными и невычислимыми на ЭВМ, так как все известные на сегодняшний день алгоритмы решения таких задач (в общем случае) требуют экспоненциального времени, а значит всегда можно выбрать такой размер входных данных (читай – размер ключа шифрования), что время вычисления станет сравнимым с возрастом Вселенной.

Класс ${\mathbb{NP}}$-полных задач – подмножество задач из ${\mathbb{NP}}$, для которых не известен полиномиальный алгоритм для детерминированной машины Тьюринга, и все задачи могут быть сведены друг к другу за полиномиальное время на детерминированной машине Тьюринга. Например, задача об укладке рюкзака является ${\mathbb{NP}}$-полной.

Стойкость криптосистем с открытым ключом, как правило, основана на ${\mathbb{NP}}$ или ${\mathbb{NP}}$-полных задачах:

RSA – ${\mathbb{NP}}$-задача факторизации (строго говоря, основана на трудности извлечения корня степени $e$ по модулю $n$).
Криптосистемы типа Эль-Гамаля – ${\mathbb{NP}}$-задача дискретного логарифмирования.

Нерешённой проблемой является доказательство неравенства

$$ {\mathbb{P}} \neq {\mathbb{NP}}. $$

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