Метод полного перебора ключей

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

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

Применение метода полного перебора для определения ключа расшифрования по шифртексту предполагает наличие статистических характеристик неизвестного открытого текста.

Схема опробования ключей без возвращения

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

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

7 Г = 1.

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

При этом истинный ключ может быть любым из них с вероятностью Пусть? — случайная величина, принимающая значения? = j с вероятностью pj = j = 1.2, и. Тогда среднее число опробований ключа до нахождения истинного будет равно математическому ожиданию величины ?

Схема опробования ключей с возвращением

При данной схеме опробования, если истинный ключ найден на шаге j, значит, опробовавшиеся до этого на шагах 1,2,…, j — 1 ключи были ложными. Поэтому среднее число опробований до нахождения истинного ключа будет равно математическому ожиданию случайной величины ?, принимающей значение (= j с вероятностью.

Таким образом,.

Для вычисления выражения (4.7) воспользуемся известными из курса математического анализа формулами.

При этом формула (4.9) получена дифференцированием обеих частей равенства (4.8). С учетом формулы (4.9) выражение (4.7) преобразуется к виду.