А.Винокуров. Серия выпусков по криптографии для электронного журнала "iNFUSED BYTES Online".

Выпуск 6. Архитектура блочных шифров (окончание).

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

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

|K_i| + |L_i||H_i|.

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

|K_i|, |L_i||H_i|.

По указанной причине на практике не так часто встречаются шифры Файстеля, в которых шифрующая часть блока меньше шифруемой по размеру |L_i| < |H_i|, особенно для размеров блока, не превышающих 64 бита. С другой стороны, за один раунд шифруется |H_i| бит блока, и если уменьшить эту величину, то при фиксированном количестве раундов каждый бит блока будет шифроваться меньшее число раз, поэтому шифры Файстеля с размером шифруемой части блока меньше шифрующей, тоже не получили значительного распространения. Таким образом, остаются шифры, в которых размеры обеих частей блока одинаковы: |L_i| = |H_i|. Именно такие шифры, архитектура которых, как было отмечено выше, называется сбалансированной сетью Файстеля, доминируют в современной практической криптографии. Схематически их можно представить двояко, как показано на левой и правой частях следующего ниже рисунка 1. Правая схема определяет в точности то же самое преобразование, что и левая, и сделана в предположении, что число раундов (n) четно.

Рис. 1. Сбалансированная обобщенная сеть Файстеля.

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

X₀ = Hi_|T|/2(T), X₁ = Lo_|T|/2(T),
X_i+1 = X_i-1f(X_i,K_i), для i = 1,2,...,n,
T' = X_n+1 || X_n,

где n - число раундов в процедуре шифрования.

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

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

Рис. 2. Преобразования за- и расшифрования в сбалансированном шифре Файстеля.

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

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

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

H' = HL	T' = TK	T' = P(T)
Рис. 3. Преобразования, используемые в шифрах наряду со стандартными шагами (раундами) шифрования.

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

T = (T₁,T₂,...,T_L),
T_i' = T_iГ,
T' = (T₁',T₂',...,T_L'),

так, чтобы некоторая функция от преобразуемого блока не меняла своего значения:

J(T) = J(T'), или J(T₁,T₂,...,T_L) = J(T₁',T₂',...,T_L'),

где J - функция выработки инварианта.

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

T = (H,L), |H| = |L| = |Г| = |T|/2 = N/2.

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

HL = (H + L) mod 2^N/2 и HL = (H - L) mod 2^N/2.

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

H' = HГ, L' = LГ, J(H,L) = HL,
H' = HГ, L' = LГ, J(H,L) = HL,
H' = HГ, L' = LГ, J(H,L) = HL,
H' = HГ, L' = LГ, J(H,L) = HL.

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

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

H = (H₁,H₂,...,H_K),
L = (L₁,L₂,...,L_K),
Г = (Г₁,Г₂,...,Г_K),
J = (J₁,J₂,...,J_K),

где для всех k = 1, 2,..., K справедливо |H_k| = |L_k| = |Г_k| = |J_k| = z_k. В этом случае модификация фрагментов и выработка инварианта осуществляется по следующим формулам:

H'_k = H_kГ_k,
L'_k = L_kГ_k,
J_k = H_kL_k,

где "" и "" - пара взаимно обратных операций над блоками размера z_k бит. Понятно, что в рамках применения указанных двух операций к фрагментам данных независимо от других фрагментов может быть использована любая из четырех возможных вышеприведенных схем. При этом, однако, указанное деление на фрагменты не должно затрагивать выработки модифицирующего значения (Г) из инварианта (J) с использованием раундового ключевого элемента. Характер зависимости второго от первого должен в полной мере соответствовать принципам перемешивания и рассеивания - все биты Г должны зависеть от всех битов J, и характер этой зависимости должен быть как можно более сложным и запутанным.

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

H' = HГ,  L' = LГ,  J(H,L) = HL.

Именно такой инвариант используется в известном шифре IDEA. Раунд шифра стандартной архитектуры при использовании для получения инварианта операции побитового исключающего ИЛИ выглядит как показано ниже на рисунке 4:

Рис. 4. Способ построения раунда шифрования в шифрующих сетях общего типа с использованием операции исключающего ИЛИ.

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

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

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

Шифр рассмотренной архитектуры имеет структуру, изображенную на рисунке 5.

Рис. 5. Обобщенная шифрующая сеть с использованием операции побитового исключающего ИЛИ для выработки инварианта и модификации блока на раунде. Здесь Fi(Ti,Ki') = TiKi', где "" - операция мультипликативного типа, или Fi(Ti,Ki') = Hi(TiKi'), где "" - операция аддитивного типа, а Hi(...) - перемешивающее преобразование, например, замена по таблице.

На этом рассмотрение данной темы закончим, в заключение подведем итог всех трех последних выпусков:

1. Все современные надежные шифры являются составными, то есть строятся из большого числа относительно несложных шифрующих преобразований так, чтобы в полной мере обеспечить наличие свойств перемешивания и рассеивания.
2. В качестве "строительных элементов" шифров используются битовые перестановки, замены (подстановки) в битовых группах, арифметические и логические операции. При этом наибольшее перемешивание и рассеивание каскада из шифрующих преобразований достигается, если смежные операции в цепочке как можно сильней отличаются друг от друга.
3. Для усложнения шифров и повышения их стойкости обычно их строят на основе шифрующих структур, в которых за один шаг (раунд) шифрования выполняется преобразование данных, оставляющее значение определенной функции шифруемого блока инвариантным, а собственно шифрование состоит в выработке блока кода из инварианта раунда и ключевого элемента раунда с помощью функции шифрования, и модификации с его использованием шифруемого блока данных. Такие шифрующие структуры иногда называют шифрующими сетями.
4. Если два смежных раунда шифрования имеют один и тот же инвариант или если для модификации данных на двух смежных раундах используются бинарные операции одной группы, то между ними необходимо выполнять прямую модификацию шифруемого блока данных с использованием операции, разрушающей этот инвариант для указанной пары раундов.
5. Наиболее простой и популярный способ создать инвариант - оставлять часть шифруемого блока неизменной. В этом случае для межраундовой модификации шифруемого блока используют циклический сдвиг, вырождающийся в обмен его старшей и младшей половин, если их размеры одинаковы. Построенные по этому принципу шифрующие структуры называются сетями Файстеля.
6. Другой используемый иногда способ получения инварианта заключается в модификации половин шифруемого блока согласованным образом с использованием пары взаимно обратных аддитивных бинарных операций. В этом случае между раундами шифрования целесообразно модифицировать шифруемый блок с использованием операций другого типа, например - мультипликативных.
7. Для использование на раундах шифрования обычно требуется больше ключевой информации, чем содержится в ключе шифрования. Для выработки нужного объема ключевой информации для последующего ее применения в раундах используют различные схемы, от самых простых - повторного использования одних и тех же фрагментов ключа, как в ГОСТе, до наиболее сложных - выработки ключевых элементов с использованием тех же самых шифрующих преобразований, что используются при шифровании, как в шифре BLOWFISH.

[Оглавление] [Предыдущий выпуск] [Следующий выпуск]
[Начало осмотра] [Что нового] [Статьи] [Выпуски в "Байтах"] [Что скачать] [Криптоалгоритмы] [Глоссарий] [Ссылки] [Гостевая книга] [Форум] [Напиши мне]

Версия от 23.12.00. (c) 1998-2000 Андрей Винокуров.