3.3. Теоретическая стойкость, совершенно стойкий шифр

Теоретико-информационный подход к оценке стойкости шифров в 1949 году предложил американский инженер К.Шеннон [38].

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

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

Для коммерческих сделок сумма тендерного предложения, «угаданная» по порядку величины может сыграть решающую роль.

Например, перехватив сообщение (АБВВГ…), зашифрованное простой заменой, злоумышленник получит информацию о совпадении третьего и четвертого символов в открытом тексте, что делает весьма вероятным предположение об открытом тексте (СУММА…). После чего он может попытаться отождествить последующий шифрованный текст с тем или иным числовым выражением стоимости сделки.

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

Шифр называется совершенно стойким по Шеннону, если открытый и шифрованный тексты статистически независимы, то есть, для , в случае, имеет место равенство условной и безусловной вероятности:.

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

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

Доказательство. Пусть – множество всех открытых текстов длины,,. Так как ключвыбирается случайно и равновероятно, то.

Для -граммы открытого текстаи-граммы шифртекста-граммаопределяется однозначно из уравнения шифрования. Таким образом, все значения гаммы и шифртекста разрешены,.

При фиксированном вероятность парыравна

.

Откуда, используя определение условной вероятности, получим: .

Априорные вероятности открытых текстов, т.е., когда шифртекст не известен, равны между собой.

По формуле Байеса для из последнего равенства следует:

, что и требовалось доказать.

3.4. Понятие практической стойкости

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

В этом случае количественной мерой надежности шифра является вычислительная сложность решения задачи дешифрования.

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

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

Таблица 3.1. Среднее время вскрытия ключа методом полного перебора

Алгоритм	Число ключей	Среднее время вскрытия ключа (лет)
		(I)	(II)
DES	7.2·1016	0.45	0.45
DVP	2.4·1021	1.5·103	14
DVP-XL	7.9·1028	4.9·1011	39
IDEA	2.5·1038	1.6·1021	70
ГОСТ 28147-89	6.3·1076	3.9·1059	198

Таким образом, для оценки практической стойкости шифрсистемы целесообразно использовать характеристику:.

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

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

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

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

Важным фактором оценки стойкости является объема материала, необходимого для вскрытия шифрсистемы.

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

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

Если длина сообщения равна одному символу в коде АSCII (8 битов), то количество пар возможных пар достигает 256. При возрастании длины сообщения, в силу избыточности реальных языков, количество ложных вариантов несколько сокращается.

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

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

где – величина избыточности языка с алфавитом, содержащимзнаков.

Упражнение. Рассчитать расстояние единственности для шифра простой замены на алфавите ,.

Указание: воспользоваться формулой Стирлинга для оценки числа .

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

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

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

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

Рис. 3.2. Рабочая характеристика шифра

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

Определенный интерес представляет предельное значение рабочей характеристики при неограниченном объеме шифрованных сообщений .

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

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

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

Исходя из этих допущений необходимо:

– определить и точно сформулировать математические и вычислительные задачи, которые необходимо решить для восстановления ключа;

– проанализировать возможность применения наилучших из числа известных к моменту анализа алгоритмов решения поставленных задач;

– провести всестороннее исследование тенденции развития обычных вычислительных средств и оценить стоимость создания специальных вычислителей (см. «Принципы построения и использования блочных алгоритмов шифрования»).

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