Основные типы шифров 31

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

2.2.4. Блочные шифры

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

Блочным шифром называется система шифрования, использующая на каждом такте постоянный, выбранный до начала шифрования, в зависимости от ключей, алгоритм [2,5,8].

Поскольку зашифрование должно быть взаимно однозначным преобразованием, то блочные шифры являются шифрами замены с очень большим алфавитом. Знаки алфавита представляются в виде двоичных блоков данных фиксированной длины. Например, алгоритм ГОСТ 28147-89 предназначен для работы с блоками длиной 64 бита. В режиме простой замены этот шифр взаимнооднозначно отображает множество мощности 264 на себя.

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

Например, в режимах шифрования алгоритм ГОСТ 28147-89 работает как шифр гаммирования по модулю два, используя двоичную гамму, выработанную в режиме, соответствующем блочному шифру.

32 Глава 2. ОБЩИЕ АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ АНАЛИЗА ОСНОВНЫХ ТИПОВ ШИФРОВ

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

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

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

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

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

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

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

Рассмотрим, например,	степенную функцию вида g(x)= xemod n , где
n = pq, p, q - различные	простые числа. Для обращения этой функции

достаточно решить задачу разложения числа n на сомножители. Эта задача

f (x)= axmod p

Основные типы шифров 33

является алгоритмической проблемой, на которой основана стойкость распространенной криптосистемы RSA.

Аналогичная ситуация имеет место с дискретной экспонентой, т.е.

функцией вида f (x)= axmod p , где p - большое простое число. Эта функция

часто используется в процедурах аутентификации.

Вследствие конечности множества вычетов по модулю p,

последовательность ak mod p , k =1,2K, периодична. Наименьший период

называется показателем (порядком) числа a по модулю p и обозначается

ordpa .

Известно, что функция при больших значениях x и

ord p a ведет себя как односторонняя.

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

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

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

Очевидно, модульное гаммирование можно рассматривать как процедуру искажения гаммы знаками открытого текста.

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

34 Глава 2. ОБЩИЕ АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ АНАЛИЗА ОСНОВНЫХ ТИПОВ ШИФРОВ

Данный подход приводит к общей проблеме решения систем уравнений с искаженными параметрами.

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