Методы оценки надежности шифров
Методы оценки качества криптоалгоритмов, используемые на практике:
1. всевозможные попытки их вскрытия;
2. анализ сложности алгоритма дешифрования;
3. оценка статистической безопасности шифра.
В первом случае многое зависит от квалификации, опыта, интуиции крип-тоаналитика и от правильной оценки возможностей противника. Обычно считается, что противник знает шифр, имеет возможность его изучения, знает некоторые характеристики открытых защищаемых данных, например тематику сообщений, их стиль, стандарты, форматы и т. п. Рассмотрим следующие примеры возможностей противника:
· противник может перехватывать все зашифрованные сообщения, но не имеет соответствующих им открытых текстов;
· противник может перехватывать все зашифрованные сообщения и добывать соответствующие им открытые тексты;
· противник имеет доступ к шифру (но не ключам!) и поэтому может зашифровывать и расшифровывать любую информацию.
Во втором случае оценку стойкости шифра заменяют оценкой минимальной сложности алгоритма его вскрытия. Однако получение строго доказуемых оценок нижней границы сложности алгоритмов рассматриваемого типа не представляется возможным. Иными словами, всегда возможна ситуация, когда алгоритм вскрытия шифра, сложность которого анализируется, оказывается вовсе не самым эффективным.
Сложность вычислительных алгоритмов можно оценивать числом выполняемых элементарных операций, при этом, естественно, необходимо учитывать их стоимость и затраты на их выполнение. В общем случае это число должно иметь строгую нижнюю оценку и выходить за пределы возможностей современных компьютерных систем. Качественный шифр невозможно раскрыть способом более эффективным, чем полный перебор по всему ключевому пространству, при этом криптограф должен рассчитывать только на то, что у противника не хватит времени и ресурсов, чтобы это сделать.
Алгоритм полного перебора по всему ключевому пространству- это пример так называемого экспоненциального алгоритма. Если сложность алгоритма выражается неким многочленом (полиномом) от п, где п - число элементарных операций, такой алгоритм носит название полиномиального.
В третьем случае считается, что надежная криптосистема с точки зрения противника является "черным ящиком", входная и выходная информационные последовательности которого взаимно независимы, при этом выходная зашифрованная последовательность является псевдослучайной. Поэтому смысл испытаний заключается в проведении статистических тестов, устанавливающих зависимость изменений в зашифрованном тексте от изменений символов или битов в исходном тексте или ключе, а также анализирующих, насколько выходная зашифрованная последовательность по своим статистическим свойствам приближается к истинно случайной последовательности. Случайность текста шифровки можно приближенно оценивать степенью ее сжатия при использовании алгоритма Лемпела-Зива, применяемого в архиваторах IBM PC. Если степень сжатия больше 10%, то можно считать криптосистему несостоятельной.