Иванов М.А. КМЗИ сети

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

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

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

Пусть F:x ο y, x, y M , и на множестве M определены преобразования g и h. Если F g x h y , F прозрачно для g, а g –

для F.

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

61

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

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

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

Рассмотрим структуру раунда блочного шифра, получившую название петли Фейстеля (рис. 1.8). Представим шифруемый блок данных (открытого mi или закрытого ci текста) длиной n

в виде пары полублоков в два раза меньшего размера:

mi ci n, mi ci L, R , L R n2.

Зашифруем старший полублок L (Left) блока mi с помощью младшего R (Right), используя некоторую функцию fi , зависящую от раундового ключа ki , и обратимую бинарную операциюнад n2 -битовыми блоками данных. Для подготовки к следующему аналогичному раунду осуществимим перестановку частей блока mi : L fi R R. Таким образом, раундовая функ-

ция зашифрования (рис. 1.9) будет иметь вид

Fi mi Fi L, R R, L fi R ,

для которой легко построить обратное, или расшифровывающее

преобразование Fi 1 c :

Fi 1 ci Fi 1 L, R R,L fi R ,

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

62

(АНБ), во-первых, размер ключа был уменьшен до 64 битов, из которых только 56 – секретные, во-вторых, в алгоритме определены перестановки лишь специального вида, не зависящие от ключа. А это наводило критиков данного алгоритма на мысль, что АНБ могла использовать известные ей слабости алгоритма для его взлома. На протяжении последних десятилетий DES подвергался интенсивному и всестороннему исследованию и по современным понятиям уже не считается надежным.

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

1.9. Абсолютно стойкий шифр. Гаммирование

Простейшей и в то же время наиболее надежной из всех схем шифрования является так называемая схема однократного использования (рис. 1.10), изобретение которой чаще всего связывают с именем Г.С. Вернама [10, 27]. Формируется t-разрядная случайная двоичная последовательность – ключ шифра, известный отправителю и получателю сообщения. Отправитель производит побитовое сложение по модулю два ключа и t-разрядной двоичной последовательности, соответствующей пересылаемому сообщению:

ci mi ki , i 1, t,

где mi , ki , ci – очередные i-е биты соответственно исходного со-

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

mi ci ki , i 1, t.

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

64

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

щения m, т. е. криптоалгоритм не дает никакой информации об открытом тексте.

Рис. 1.9. Схемы трехкратного использования алгоритма DES: а – с двумя ключами; б – с тремя ключами

65

не может считать, что это сообщение «HELLO», поскольку имеются и другие возможные сообщения, например «TEDDY». Однако апостериорные вероятности этих открытых текстов возрастают относительно их априорных вероятностей. В то же время апостериорная вероятность таких открытых текстов, как «PEACE» или «GATES», снижается до нуля вне зависимости от их априорной вероятности. По Шеннону, в совершенно секретных криптосистемах после анализа закрытых текстов апостериорные вероятности возможных открытых текстов остаются такими же, какими были их априорные вероятности [3].

Необходимые и достаточные условия абсолютной стойкости шифра:

полная случайность ключа; равенство длин ключа и открытого текста; однократное использование ключа.

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

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

67

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

тельности с выходов генератора псевдослучайных чисел. По-

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

Различают гаммирование с конечной и бесконечной гаммами. В первом случае источник гаммы – аппаратный или программный генератор ПСЧ. В качестве примера бесконечной гаммы можно привести последовательность цифр в десятичной записи числа Σ 3,1415926 … .

Если множеством используемых для шифрования знаков является алфавит, отличный от бинарного ( Z2 0, 1`), напри-

мер, алфавит Z33 русские буквы и пробел, то его символы и

символы гаммы заменяются цифровыми эквивалентами, которые затем суммируются по модулю N:

ci mi ϑi modN, i 1, t,

где mi , ϑi , ci – очередной i-й знак исходного сообщения, гаммы

и шифротекста соответственно; t – число знаков открытого текста; N – число символов в алфавите. Возможно использование при гаммировании и других логических операций.

68

69