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

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

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

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

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

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

Прежде чем перейти непосредственно к рассмотрению предмета настоящего выпуска, вернемся к теме выпуска предыдущего, и рассмотрим один вопрос, который остался в нем без необходимого освещения. Вспомним, что ключевые данные могут комбинироваться с шифруемыми данными в преобразованиях двух типов: заменах и функциональных операциях. Оказывается, что второй способ использования ключевой информации предпочтительнее. Вместо того, чтобы делить входы вектора замены между блоком шифруемых данных и ключевым элементом, оказалось выгоднее скомбинировать данные с ключом посредством подходящей бинарной операции, а затем подвергнуть результат замене. Предположим, например, что мы преобразуем 32-битовый блок данных, используя 32-битовый ключ и несколько узлов замены с 4-битовым входом. Если использовать для комбинирования ключа и данных узлы замены, то нам необходимо будет использовать 16 узлов замены 4 бита на 2 бита, на вход каждого узла замены будут подаваться два бита шифруемых данных и два бита ключа. При этом каждый выходной бит такого узла будет зависеть ровно от двух битов данных и от двух битов ключа. Если же мы подвергнем преобразованию замены побитовую сумму по модулю 2 ключа с данными, то нам необходимо будет использовать 8 узлов замены 4 бита на 4 бита, и каждый выходной бит узла замен будет зависеть уже от четырех битов ключа и от четырех битов данных. Тем самым в этом преобразовании может быть достигнута большая степень перемешивания и рассеивания.

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

Рис. 1. Комбинирование ключевого элемента с данными с использованием бинарной операции "".

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

T_i+1 = T_iK_i.

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

(TK)K = T.

Сложность преобразования существенно повысится, если комбинировать с данными не непосредственно ключевой код, а код, выработанный из ключа и зависящий от данных, как показано на рисунке 2:

Рис. 2. Шифрующее преобразование блока данных с использованием кода, выработанного из ключевого элемента Ki и шифруемого блока Ti.

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

T_i+1 = T_if(T_i,K_i).

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

Ti+1 = F(Ti,Ki),

(*)

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

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

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

Обратимость изображенного на рисунке 2 преобразования означает, что должна существовать эффективно вычислимая функция g(T_i+1,K_i), обладающая следующим свойством:

f(Ti,Ki) = g(Ti+1,Ki) = g(Tif(Ti,Ki),Ki)

(**)

для любых допустимых блоков данных T_i и K_i. В этом случае обратное преобразование будет иметь вид, изображенный на рисунке 3:

Рис. 3. Обращение шифрующего преобразования.

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

T_i = T_i+1g(T_i+1,K_i).

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

I_i = J(T_i) = J(T_iГ_i) = J(T_i+1)

для любых блоков данных T_i, Г_i подходящего размера. Понятно, что в этом случае и обратная ей операция "" также обладает указанным свойством:

I_i = J(T_i+1) = J(T_i+1Г_i) = J(T_i).

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

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

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

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

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

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

T_i+1 = T_if(J(T_i),K_i),
T_i = T_i+1f(J(T_i+1),K_i).

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

|Ti| = |Гi| + |Ii|,

(***)

то операция модификации данных ("") не должна терять информацию о своих аргументах, - это, в частности, означает, что изменение любого из аргументов должно приводить к изменению значения функции. Если равенство (***) не будет выполняться и его левая часть будет больше правой части, то стойкость преобразования будет далеко от оптимума - ее можно будет повысить, увеличив размер модификатора (Г_i), инварианта (I_i), или их обоих. Если же правая часть окажется больше левой части, то операция модификации обязательно будет терять информацию о модифицирующем элементе - это означает, что будут существовать различные элементы Г и Г', такие, что для некоторого блока данных T будет выполняться следующее равенство:

TГ = TГ',

в чем также нет особого смысла. Таким образом, резонно выбирать размеры блоков, участвующих в преобразовании, такими, чтобы выполнялось риведенное выше равенство (***). Идем дальше, с точки зрения достижения необходимой стойкости и эффективности шифрующего преобразования выгодно взять размеры модификатора (Г_i) и инварианта (I_i) равными: |Г_i| = |I_i|. С учетом равенства (***) их размер будет равен половине размера шифруемого блока:

|Г| = |I| = |T|/2.

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

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

[_i]^-1_n-i+1,
f_if_n-i+1,
J_iJ_n-i+1.

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

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

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

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

H_i+1 = H_if(L_i,K_i),
L_i+1 = L_i,

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

Рис. 6. Пара взаимодополняющих шифрующих преобразований.

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

H_i+2 = H_i+1 = H_if(L_i,K_i),
L_i+2 = L_i+1g(H_i+1,K_i+1) = L_ig(H_i+1,K_i+1),

Архитектура шифров, базирующаяся на описанном выше преобразовании, оставляющем неизменной часть шифруемого блока, называется сетью Файстеля, точнее - обобщенной сетью Файстеля. Разница между ними заключается в том, что в первой для модификации данных используется операция побитового исключающего ИЛИ, а во втором - любая подходящая бинарная операция. Данная архитектура шифров была предложена в 70-е годы пионером в создании криптографических алгоритмов подобного типа доктором Хорстом Файстелем, работавшим в то время в исследовательской лаборатории фирмы IBM и создавший там криптосистему Люцифер, послужившую прототипом наиболее известного шифра этого типа - американского стандарта шифрования, криптоалгоритма DES, сохраняющего свой статус стандарта вплоть до настоящего времени, но, очевидно, доживающего в этом качестве последние месяцы.

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

Рис. 7. Раунд шифрования в обобщенном шифре Файстеля.

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

,

если же его интерпретировать как массив битов, то уравнение будет следующим:

,

где через Lo_n(X) и Hi_n(X) обозначен блок из n соответственно младших и старших битов блока X, через X || Y - конкатенация блоков X и Y, - их объединение в один блок данных таким образом, что X является старшей частью объединенного блока, а Y - его младшей частью, через - целую часть действительного числа x, n_H и n_L - размер соответственно старшей (шифруемой) и младшей (шифрующей) частей преобразуемого блока.

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

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

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