Практическая стойкость шифров

В своей работе [Шен63] К.Шеннон, помимо исследований по теоретической стойкости, рассматривал также вопрос о практической стойкости шифров. Он рассуждал следующим образом (рассматривая, как и ранее, криптоатаку на основе одного шифртекста на шифр, не являющийся совершенным).

После того как объем перехвата (у) превзойдет расстояние единственности (естественно, предполагается, что для рассматриваемого шифра оно существует!), обычно будет существовать единственное решение (х или k) криптограммы. Задача дешифрования и состоит в нахождении этого единственного решения, имеющего высокую вероятность (p(x/y) или p(k/y)). До того как объем перехвата достигнет расстояния единственности, задача состоит в нахождении всех решений, имеющих большую вероятность (по сравнению с остальными решениями), и, конечно, в определении вероятностей этих решений.

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

Рис. 20

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

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

Наибольший интерес представляет предельное значение W(N) при N (то есть W()), которое можно рассматривать как среднюю работу по дешифрованию при неограниченном объеме шифртекста. Практическое вычисление W() представляет собой весьма сложную задачу. В связи с этим практическую стойкость шифра обычно оценивают с помощью величины W_Д(), которую можно назвать достигнутой

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

Большое значение имеет математическая модель вычис­лений, используемая при оценке практической стойкости шифра. По сути, речь идет о модели гипотетической ЭВМ, которой располагает потенциальный противник и которая способна реализовать крупный фрагмент алгоритма вскрытия как одну элементарную операцию. Например, опробование одного ключа k К и проверку результата расшифрования по критерию открытого текста (выполняется ли включение ?), в принципе, можно принять за одну элементар­ную операцию.

Более детальное исследование вопросов практической стойкости (выходящее за рамки данной книги) выводит на серьезные проблемы теории сложности алгоритмов и разработки методов криптоанализа.