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

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

В этом случае количественной мерой надежности шифра является вычислительная сложность решения задачи дешифрования. Пусть ÂE – множество применимых к шифрсистеме E алгоритмов дешифрования. Обозначим T(r) – среднее количество элементарных операций некоторого вычислителя, необходимых для успешной реализации алгоритма rÎÂE.

Тогда время τ на реализацию алгоритма rÎÂE оценивается величиной:

   

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

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

Таблица 1

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

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

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

   

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

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

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

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

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

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

   

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

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

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

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

   

где RL ‑ величина избыточности языка, N – мощность алфавита открытого текста, |K| ‑ мощность множества ключей.

Упражнение. Рассчитать расстояние единственности для шифра простой замены на алфавите N=33, RL=0,7. Указание: воспользоваться формулой Стирлинга для оценки числа 33!

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

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

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

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


 

 

W(L)
L

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

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

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

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

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

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

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

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

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