Вычислительно стойкие криптосистемы

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

В частности может оказаться, что требуемое время криптоанализа превышает то время, в течение которого рассматриваемое сообщение остается актуальным, либо что даже своевременное получение правильного сообщения не окупает затрат на процедуру криптоанализа.

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

В современной математике существует раздел «Теория сложности алгоритмов», где различают задачи простые и сложные. Задачи полиномиальной сложности, для решения которых необходимое число элементарных операций является полиномиальной функцией от размерности задачи, относят к простым. Время T (N) для их решения пропорционально ~ N ⁿ, где N – размерность задачи. Наиболее сложные (трудные) задачи требуют для своего решения число операций, которое экспоненциально зависит от размерности задачи, т.е. T (N) ~ a ^bN , где a >0 и b >0 – некоторые постоянные, в силу чего весь класс таких задач называется EXPTIME.

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

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

Имеется достаточно широкий класс известных NP задач с многовековой историей попыток их полиномиального решения. Одним из примеров таких задач является нахождение цикла Гамильтона на заданном графе (рис. 3).

Рис. 3. Граф с циклом Гамильтона	Рис. 4. Соотношение между задачами NP и NPC классов

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

Среди NP задач имеется подкласс (рис. 4) наиболее сложных задач, которые называются NP полными (NPC). Эти задачи, обладают следующим свойством: если для какой-то из них найдется алгоритм решения с полиномиальной сложностью, то это будет означать, что существуют алгоритмы с полиномиальной сложностью для решения всех задач из NP класса (что, учитывая огромный список таких задач и многолетние попытки их решения, очень маловероятно).

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

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

Таким образом, основные требования к вычислительно стойким криптосистемам можно сформулировать в следующем виде:

· Число ключей L^N должно быть непереборно большим. Например, при L = 2 нужно иметь N = 128, N = 256 и т.п., поскольку в противном случае, приняв криптограмму длиною больше расстояния единственности (n > n _Р.Е) можно правильно дешифровать переданное сообщение путем полного перебора ключей. Необходимо отметить, что по мере совершенствования вычислительной техники длины ключей не остаются неизменными, а становятся все больше.

· Недопустимо использование какого-либо метода шифрования, который имел бы известный полиномиально сложный от длины ключа метод криптоанализа. Желательно, чтобы сложность была экспоненциальной. Тогда, увеличивая длину ключа всегда можно обеспечить невозможность дешифровки без знания ключа в реальном времени. В частности, из этого следует, что криптоанализ не должен сводиться к решению какой-либо системы линейных уравнений.

Дата добавления: 2015-10-26