Стойкие алгоритмы шифрования
Теоретически существуют абсолютно стойкие алгоритмы шифрования. Математическое доказательство данного факта было предложено в работах К. Шеннона. Для того чтобы алгоритм считался абсолютно стойким, он должен удовлетворять следующим условиям:
• длина ключа и длина открытого сообщения должны быть одинаковы;
• ключ должен использоваться только один раз;
• выбор ключа из ключевого пространства должен осуществляться равновероятно.
Данные требования приводят к тому, что абсолютно стойкие алгоритмы с практической точки зрения являются труднореализуемыми. Например, осуществление первого и второго условий приводит к тому, что необходимо иметь запас ключей большой длины, что практически невыполнимо. В результате применение современной аппаратно-программной базы приводит к неабсолютной стойкости используемых алгоритмов шифрования.
Рассмотрим самые распространенные на сегодняшний день причины осуществления успешных атак на алгоритмы шифрования:
• наличие статистической структуры исторически сложившихся языков. То есть существуют определенные символы или комбинации символов, наиболее часто встречающиеся в естественной речи. Таким образом, при перехвате зашифрованного сообщения для некоторых типов алгоритмов шифрования можно подсчитать частоту появления определенных символов и сопоставить их с вероятностями появления определенных символов или их комбинаций (биграммы, триграммы и т.д.), что в некоторых случаях может привести к однозначному дешифрованию отдельных участков зашифрованного сообщения;
• наличие вероятных слов. Речь идет о словах или выражениях, появление которых можно ожидать в перехваченном сообщении. Так, в деловой переписке присутствуют шаблонные слова; в английском языке, например, наиболее часто встречаются «and», «the», «are» и т.д.
Следует учесть, что существует ряд методов, позволяющих сделать зашифрованные сообщения практически непригодными для статистического анализа и анализа посредством вероятных слов. К ним относятся:
• рассеивание. Влияние одного символа открытого сообщения распространяется на множество символов зашифрованного сообщения. Этот метод хотя и приводит к увеличению количества ошибок, однако с его помощью удается скрыть статистическую структуру открытого сообщения;
• запутывание. Развитием принципа рассеивания стал принцип запутывания, в котором влияние одного символа ключа распространяется на множество символов зашифрованного сообщения;
• перемешивание. Принцип перемешивания основывается на использовании особых преобразований исходного сообщения, в результате чего вероятные последовательности как бы рассеиваются по всему пространству возможных открытых сообщений. В качестве примера эффективного перемешивания можно привести произведение двух простых некоммутирующих операций. Развитием метода перемешивания явилось применение составных алгоритмов шифрования, состоящих из последовательности простых операций перестановки и подстановки.
Примерами изложенных выше методов могут служить стандарты шифрования, такие как DES (Data Encryption Standard) и ГОСТ 28147-89, подробнее о которых будет сказано далее.
Хотелось бы отметить, что получение строгих оценок стойкости алгоритмов шифрования является достаточно сложной проблемой, решение которой невозможно без рассмотрения самого алгоритма шифрования.
В последнее время с развитием теоретико-сложностных и теоретико-числовых направлений в математике наметился новый подход к построению и оценкам стойкости криптографических алгоритмов. Суть его сводится к выбору в качестве основы алгоритма сложной математической задачи и оценке стойкости в соответствии со сложностью решения этой задачи. С таким подходом мы познакомимся в разделе «Асимметричные алгоритмы шифрования».