Глава 3.

ТЕСТИРОВАНИЕ УЗЛОВ КРИПТОСХЕМ КАК МЕТОД КОМПРОМЕТАЦИИ ШИФРОВ

Основное в этой главе…

Компрометация шифров..……...36

Задача тестирования линейной рекуррентной составляющей криптоузла……………..……....…...37

Качественная характеристика задачи восстановления параметров искаженной линейной рекур-

ренты…..……………………………..45

36 Глава 3. ТЕСТИРОВАНИЕ УЗЛОВ КРИПТОСХЕМ КАК МЕТОД КОМПРОМЕТАЦИИ ШИФРОВ

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

Обычно криптоалгоритм представляется в виде графической схемы и ее описания. По традиции, графическое представление криптоалгоритма называется криптосхемой, а ее описание – описанием криптосхемы.

Криптосхемы состоят из элементов – криптоузлов, которые могут объединяться в блоки.

Вописании криптосхемы дается также механизм взаимодействия узлов.

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

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

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

3.1. Компрометация шифров

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

Компрометация шифров 37

последовательность символов в результате зашифрования конкретным шифром, либо нет [31].

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

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

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

3.2. Задача тестирования линейной рекуррентной составляющей криптоузла

При синтезе криптосхем потоковых шифров широко применяются криптоузлы, основанные на т.н. регистрах сдвига с обратной связью [30,32].

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

38 Глава 3. ТЕСТИРОВАНИЕ УЗЛОВ КРИПТОСХЕМ КАК МЕТОД КОМПРОМЕТАЦИИ ШИФРОВ

Двоичный регистр сдвига с обратной связью – это последовательность битовых ячеек. Их количество называется длиной регистра. Во время работы содержимое ячеек изменяется. Исходное состояние регистра называется его начальным заполнением. Содержимое ячейки называется разрядом (с соответствующим номером).

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

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

Простейшим случаем подобного регистра является уже знакомый нам регистр сдвига с линейной обратной связью (РСЛОС). Функция обратной связи такого регистра является суммой по модулю два содержимого ячеек обратной связи.

В результате нескольких тактов работы РСЛОС длины n с точками съема (0, k1, k2, …, kr) и начальным заполнением s0 = (a0, a1, …, an-1) возникает т.н. рекуррентная последовательность R(s0) = a0,a1, …, ai…, для которой выполняется линейное рекуррентное соотношение вида

ai ak1+i K akr +i =an+i , (i=0, 1, 2…).

Напомним, что эта последовательность является периодической. Период не превосходит числа 2n-1 и зависит от длины и набора точек съема регистра.

Тестирование линейной рекуррентной составляющей криптоузла 39

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

Заметим, что нашу рекуррентную последовательность можно записать через все элементы текущего заполнения регистра в виде

n	(mod 2), где bj+i =1, при j {0, k1, k2,…, kr} и bj+i = 0 в
an+i + ∑bj+iaj+i = 0
j=0
противном случае.

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

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

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

Как следствие, при положительном результате тестирования уже нельзя утверждать, что тестируемый узел является РСЛОС.

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

Например, последнее слагаемое в последовательности

a~n+i = ai ak1+i K akr +i ai+1 ai+2 ai+3 ai+4