Композиции шифров. 
Криптографические методы защиты информации

Шифры, близкие к совершенным. Пусть, А = А, А₉ = (X, К, X К₂, Y₂, f) — композиция шифров А, и А., такая, что А, = (X, /С, У,/,), А₂ = (Х₂, К₂, У₂,/₂), У, = X, т. е. множество выходных значений первого шифра является множеством входных значений второго шифра. Композиция шифров, не являющихся совершенными, может дать шифр, «близкий» к совершенному шифру.

Пусть, например, А = (X, К, Y, f) — шифр гаммирования (X = У) и распределение вероятностей Р (К) = (Р (к), к е К) таково, что Р (к) > 0 для любого к е К.

В частности, к-я степень шифра А: А^к = (X, К, У, f)^k представляет собой шифр, переходные вероятности которого стремятся к величине 1/|Х| при к —* °°, _т.е. шифрА* = (X, К, Y, f)^k близок к совершенному шифру при достаточно большом k.

Можно ввести понятия шифров, близких к совершенным.

Шифр А^т_г с условием Р (х/у) Р (х) < г для любых х е X, у е У называется г-совершенпым по тексту, к-я степень шифра А: А* = (X, К, У, /)^к является ?(&)-совершенным шифром (т.е. е зависит от к).

Ясно, что совершенный по тексту шифр является близким к совершенному, но тексту А[ для любого е > 0; обратное, вообще говоря, неверно. Однако можно построить последовательность {А⁷}^ шифров со свойством 8−0.

Интересной является задача построения «шкалы» шифров, т. е. е-отклонений шифров от совершенного по тексту.

Точно так же можно ввести понятие шифра А?, Ь-совершенного по ключу. Теперь шифр являющийся е-совершенным по тексту и 8-совершенным по ключу, является обобщением шифра, близкого к совершенному по тексту и по ключу.

Известно, что свойства шифра быть совершенным по тексту и по ключу являются независимыми. При переходе от совершенного шифра к близкому к совершенному шифру эта независимость сохраняется. Меру отклонения шифра от совершенного можно изучать по тому, насколько распределения Р (х)> P (k) отличаются от равномерных.

Как известно, совершенные шифры используются крайне редко. Причина тому — требуемая большая длина ключа. Шифры Апредставляются разумным компромиссом в соотношении «цена — качество».

Можно задавать необходимые s_max и 5_тах, одновременно вычислив возможные для шифров данного вида e_min и 8_min. Тогда множество допустимых шифров изображается точками прямоугольника {(в, 8): e_min < в < в_тах, 8, шп ^ 8 < 8_тах}. Целевой функцией является стоимость реализации А%[. После этого задача выбора оптимального при заданных условиях шифра может быть сформулирована как задача нахождения экстремума функции двух переменных в области^[1].

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

при этом А = А _{A₂.A_r1 шифры A_i имеют общие пространства входных и выходных значений У- = X_i+V Ключом является вектор (k_v k_v …, k_r) е К_{ х К₂ X… х К_г

Преобразование / называется г-м раундом шифрования, i = 1,…, г; ключ kj — раундовым ключом.

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

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

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

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

Рис. 2.2. Обобщенная схема подстановочно-перестановочной сети

подстановочно-перестановочными сетями (SP-сетями, SPN — substitutionpermutation network), упрощенно показаны на рис. 2.2.

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

В качестве примера SP-сетей можно привести алгоритмы Serpent и SAFER+, а также отечественный шифр «Кузнечик». В некоторых литературных источниках к SP-сетям относят также алгоритмы со структурой «квадрат».

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

Рассеивание предполагает распространение влияния одного знака открытого текста, а также одного знака ключа на значительное количество знаков шифротекста.

Наличие у шифра этого свойства:

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

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

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

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

В современных блочных криптосистемах раундовые шифры строятся в основном с использованием операций замены двоичных кодов небольшой^[2]

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

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

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

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

В общем виде раундовое преобразование при шифровании описывается следующей формулой:

где Е — раундовая функция шифрования; В, — выходной блок; В_{} {} — входной блок для г-го раунда; K_t — раундовый ключ, используемый на i-м раунде; i=l, г, где г — число раундов.

Преобразование? должно быть обратимо, т. е. должно существовать преобразование D = Е

Пусть D — раундовая функция дешифрования. Тогда раунд обратного преобразования описывается как.

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

Схема Фейстеля. Для разработки итерационных блочных шифров широко используется схема, предложенная в начале 1970;х гг. X. Фейстелем (Horst Feistel) — сеть Фейстеля (рис. 2.3), где левый подблок содержит старшие биты входного блока, правый — младшие. Фейстель являлся одним из создателей шифра Lucifer и разработанного на его основе алгоритма DES.

В отличие от SP-сети схема Фейстеля подразумевает разбиение обрабатываемого блока данных на два подблока: левый — L и правый — R. Один из подблоков обрабатывается некоторой раундовой функцией, зависящей от ключа раунда, а затем накладывается на другой подблок. После наложения подблоки меняются местами, т. е. в следующем раунде будет обрабатываться уже другой подблок данных.

Наложение обработанного подблока па необработанный чаще всего осуществляется с помощью функции «исключающее ИЛИ» (XOR). Иногда используется сложение по модулю 2″, где п — размер подблока в битах. Досто;

Рис. 23. Сеть Фейстеля (шифрование).

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

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

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

Прямое преобразование (при шифровании сообщения) осуществляется в соответствии со следующими соотношениями:

где ® — операция побитного сложения по модулю 2 (операция XOR).

Из свойств операции ® (XOR) следует, что для всех возможных значений операндов будет выполняться соотношение: (X © Y) ® У = X. Именно это свойство и позволяет при преобразовании использовать в числе прочих необратимые функции F и, несмотря на это, иметь возможность провести обратное преобразование. Обратное преобразование (при расшифровании) по схеме Фейстеля (рис. 2.4) описывается формулами.

Рис. 2.4. Сеть Фейстеля (расшифрование)

Схема Фейстеля лежит в основе многих современных алгоритмов шифрования: бывшего стандарта США DES (Data Encryption Standart), российского ГОСТ 28 147–89 («Магма»), шифров RC5, Blowfish, TEA CAST-128 и др.

Алгоритмы на основе сети Фейстеля являются наиболее изученными — таким алгоритмам посвящено огромное количество криптоаналитических исследований, что является несомненным преимуществом как при разработке алгоритма, так и при его анализе.

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

Рис. 2.5. Пример расширенной сети Фейстеля.

Алгоритмы со структурой «квадрат». Для структуры «квадрат» (Square) характерно представление шифруемого блока данных в виде двумерного байтового массива. Криптографические преобразования могут выполняться как над отдельными байтами массива, так и над его строками или столбцами.

Эта структура получила название от алгоритма Square, разработанного В. Рэйменом (Vincent Rijment) и Й. Дайменом (.Joan Daemen) — авторами алгоритма Rinjdael («рэндал»), принятого в США в качестве нового стандарта симметричного шифрования AES (Advanced Encryption Standart). AES, а также другой алгоритм этих авторов — SHARK, и корейский Crypton являются примерами структуры «квадрат».

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

Строгие границы между различными структурами также не определены, поэтому зачастую разные эксперты относят один и тот же алгоритм к разным типам. Например, алгоритм CAST-256 отнесен его автором к SPсети, а многими экспертами называется расширенной сетью Фейстеля. Другой пример — алгоритм НРС, названный автором сетью Фейстеля, но отнесенный многими экспертами к алгоритмам с нестандартной структурой.

• [1] 2 Жданов О. Золотарев В. В. Методы и средства криптографической защиты информации: учеб, пособие. Красноярск: Сибирский государственный аэрокосмический университет, 2008.
• [2] Шеннон К. Теория связи в секретных системах. С. 333—369.