4.1.5. Комбинированные методы.

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

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

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

1) подстановка + гаммирование;

2) перестановка + гаммирование;

3) подстановка + перестановка.

Эти приемы были использованы в методе DES. Суть алгоритма (алгоритм разработан для блока данных длиной 64 бит) заключается в преобразовании, которое состоит из серии перестановок (правая половина блока становится левой половиной “следующего” блока), операций запутывания (из правой половины блока длиной 32 бит формируется код длиной 48 бит, а каждый бит ключа размножается и превращается в подключ длиной 48 бит) и логических операций (с помощью функций ИСКЛЮЧАЮЩЕЕ ИЛИ производится обработка кода длиной 48 бит и подключа такой же длины, затем из получившегося сегмента длиной 48 бит выбираются 32 бит и, наконец, с помощью функции ИСКЛЮЧАЮЩЕЕ ИЛИ производится совместная обработка отобранных на втором этапе 32 бит и левой половины блока длиной 32 бит). Этот процесс перестановок в половине блока, повторных операций запутывания и многократных логических операций выполняется 16 раз (или говорят 16 раундов). Ключ состоит из 56 бит, из которого генерируется 16 подключей длины 48 бит (за счет выполнения операций запутывания). Каждый подключ используется в своем раунде.

Свое развитие DES получил в ГОСТ 281478-89 (отечественный стандарт на шифрование данных), который увеличил длину ключа до 256 бит, число раундов до 32, и допустил произвольные перестановки.

4.2. Потоковые шифры на основе сдвиговых регистров.

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

Сдвиговый регистр с обратной связью состоит из двух частей: сдвигового регистра и функции обратной связи. Сдвиговый регистр представляет собой последовательность битов фиксированной длины. Число битов называется длиной сдвигового регистра. Функция обратной связи является булевой функцией из множества L-мерных векторов с координатами из множества {0, 1} в множество {0, 1}, L – длина сдвигового регистра. В начальный момент работы сдвиговый регистр заполняется некоторым начальным значением. На каждом последующем шаге вычисляется значение , где x_i – значение ячейки с номером s_i, содержимое регистра сдвигается вправо, а в освободившееся место помещается значение y.

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

Простейшим видом сдвигового регистра с обратной связью является линейный сдвиговый регистр с обратной связью (linear feedback shift register LFSR). Функция обратной связи является в этом случае просто суммой по модулю 2 нескольких фиксированных разрядов .

Пример. Рассмотрим линейный сдвиговый регистр R длины L=4 и функцией обратной связи (отвод от первого и четвертого вывода).

Пусть исходное значение регистра равно <1,1,1,1>, тогда этот регистр будет порождать следующую последовательность

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

Последовательность максимальной длины называется M-последовательностью. Не всякий регистр LFSR может обладать такой последовательностью. Проблема определения по заданному регистру LFSR, будет ли он обладать M-последовательностью, является нетривиальной. Для ее решения сопоставим произвольному регистру LFSR длины L следующий многочлен (*), где коэффициент принимает значение 1 или 0 в зависимости от того, присутствует ли соответствующее слагаемое в функции обратной связи. Например, регистру LFSR в рассмотренном выше примере соответствует многочлен .

Теорема. Произвольный LFSR регистр обладает M-последовательностью тогда и только тогда, когда соответствующий многочлен является неприводимым (неразложимым) над полем F₂={0, 1}.

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

В общем случае, нет простого способа генерировать многочлены заданной степени по модулю 2, однако можно легко проверить, является ли заданный многочлен приводимым или нет над заданным конечным полем. Для этого используется алгоритм Берлекампа (Berlekamp) (см. Лидл, Нидеррайтер[7], т.1, гл.3.). В разделе 4.3.2 данного пособия мы рассматриваем упрощенную версию этого алгоритма.