Основные принципы построения блочных шифров
Под простым шифрующим преобразованием здесь и далее понимается такое преобразование, который реализуется аппаратно относительно несложной логической схемой или программно несколькими компьютерными командами. Можно выделить следующие группы простых шифров: 
•	шифр перестановок - заключается в перестановках структурных элементов шифруемого блока данных - битов, символов, цифр; 
•	шифр замен - заключается в замене одних значений на другие по индексной таблице, замене подвергаются группы элементов шифруемого блока - битов или символов; 
•	шифр функциональных преобразований - заключается в выполнении сдвигов, логических и арифметических операций над элементами данных. 
Ниже дана подробная характеристика каждого из упомянутых типов преобразований: 
Шифры перестановок чрезвычайно просто реализуются аппаратно - разводкой проводников на плате или в кристалле, при этом совсем не требуется каких-либо дополнительных затрат, так как проводники, связывающие регистры аппаратуры, так или иначе присутствуют в схеме. В то же самое время эти преобразования очень неэффективно реализуются программно на процессорах общего назначения. Как правило, вычислительные затраты составляют не менее двух машинных команд на каждый двоичный разряд в модифицируемом блоке, если только в перестановках нет согласованности. Этой причиной, в частности, объясняется тот факт, что многие шифры, широко использующие операции данного типа, имеют при прочих равных условиях существенно менее эффективные реализации по сравнению с шифрами, их не использующими. Например, американский стандарт шифрования криптоалгоритм DES при вдвое меньшем количестве шагов в цикле шифрования по сравнению с Российским стандартом (16 против 32) имеет примерно вдвое более медленную оптимальную реализацию для процессоров Intel x86. 
Общие виды замен аппаратно реализуются с помощью запоминающих устройств, программно - индексированным чтением из оперативной памяти, что, по сути, одно и то же: замена для элемента данных x берется из вектора или узла замен V, являющегося массивом заменяющих значений, индексированным заменяемым элементом данных: x заменяется на 
y = V[x]. 
Программно такая операция реализуется за одну команду, не считая операции загрузки индекса в соответствующий регистр. Размер памяти, необходимый для хранения вектора заменяющих, определяется следующим соотношением: 
|V| = 2|X||Y|, 
где |X| и |Y| - размеры заменяемого и заменяющего блоков в битах соответственно, размер вектора замен V также получается в битах. Из приведенной формулы видно, что он растет экспоненциально с ростом размера заменяемого блока. В силу этого выполнение подстановки в масштабах всего шифруемого блока невозможно - потребовался бы слишком большой объем памяти для хранения вектора. Поэтому преобразуемый блок данных разделяют на фрагменты, обычно одинакового размера, и выполняют замену в этих подблоках независимо друг от друга. Для повышения стойкости шифра замену различных частей шифруемого блока следует выполнять с использованием разных векторов замен, которые все вместе составляют таблицу подстановок или таблицу замен. Для хранения этой таблицы требуется участок памяти следующего размера: 
|S| = nv|V| = nv2|X||Y|, 
где nv - число подблоков размера |X|, в которых производятся подстановки. Как уже отмечалось выше, размер таблицы подстановок быстро увеличивается с ростом размера заменяющего, и, особенно, заменяемого блока, что влечет за собой возрастание требований к необходимому для реализации шифра объему памяти. С другой стороны, увеличение этих размеров усложняет криптоанализ и, тем самым, повышает стойкость шифра, поэтому на практике их следует выбирать на границе разумности, ведь криптоалгоритм проектируется на достаточно длительный срок, а возможности электронной техники увеличиваются очень быстро. В алгоритме DES суммарный объем блоков подстановки равен |SDES| = 8264 = 211бит = 256 байт. В отечественном стандарте это величина того же порядка: |SГОСТ| = 8244 = 29бит = 64 байта. Следует помнить, что указанные шифры разрабатывались в семидесятые годы, когда понятие "микросхема" еще только начинало входить в наш обиход, обычная емкость микросхемы запоминающего устройства составляла несколько десятков, максимум сотен битов, а объем оперативной памяти 32Кбайта считался совсем неплохим вариантом для компьютера. Вполне естественно, что созданные в то время криптоалгоритмы отражали суровые реалии тех дней. Сейчас эта проблема практически отсутствует, и поэтому современные шифры гораздо более свободны в данном отношении. Так, в криптоалгоритме BLOWFISH подстановки производятся следующим образом: каждый из 4-х байтов, составляющих 32-битовое слово, заменяется на 4-байтовое слово, полученные слова преобразуются в одно с помощью логических и арифметических операций. Соответственно размер одной таблицы замен в этом алгоритме равен |SBLOWFISH| = 42832 = 215бит = 4 Кбайт. 
Функциональные преобразования - это унарные и бинарные логические и арифметические операции, реализуемые аппаратно логическими схемами, а программно - одной-двумя компьютерными командами. Теоретически, возможно использовать любую операцию, которая может быть сформулирована в терминах логических функций. Однако на практике дело всегда ограничивается теми из них, которые имеются в наборах команд универсальных процессоров и реализованы аппаратно в виде микросхем. Из логических операций это основные логические функции - инверсия, и бинарные - побитовые И, ИЛИ, ИСКЛЮЧАЮЩЕЕ ИЛИ, из арифметических - изменение знака (переход к дополнительному коду), и бинарные - сложение, вычитание, умножение, деление по модулю некоторого числа, из битовых манипуляций - циклические сдвиги. 
Как же построить надежный шифр из элементарных операций указанного типа? Наиболее очевидная идея - каскадировать их, как это показано на рисунке 1. Символами P, S, F на нем обозначены операции перестановок (Permutation), замен (Substitution), функциональных преобразований (Function) соответственно. Ключевые элементы (Ki) могут комбинироваться с преобразуемыми данными в операциях подстановок и функциональных преобразований. 
	Рис. 1. Фрагмент составного шифра - комбинация большого числа элементарных шифрующих преобразований.	
Не имеет смысла комбинировать две однотипные операции подряд. Если чередовать процедуры различного типа, сложность результирующего преобразования (степень перемешивания и рассеивания) будет выше. Это очень легко объяснить: при комбинировании двух операций их сложности складываются за вычетом некоего "дефекта сложности", который тем больше, чем более схожи две операции. Например, суперпозиция (результат последовательного выполнения) двух битовых перестановок может быть выражен одной перестановкой. То же справедливо для двух подстановок, выполняемых в одних и тех же границах заменяемых подблоков. Прибавление к блоку данных двух ключевых элементов равносильно прибавлению одного, равного их сумме. Во всех рассмотренных случая добавление к операции еще одной такой же вообще не приводит к возрастанию сложности, а следовательно и стойкости преобразования. 
Даже если комбинируются две различные операции, принадлежащие одной и той же группе, сложность полученного преобразования меньше, чем могла бы быть, если бы они были разделены операцией другого типа. На рисунке 2 изображены два трехзвенных шифрующих преобразования, составленных из одних и тех же операций. Сложность и стойкость преобразования, изображенного справа, по только что изложенным соображениям выше, чем у левого. 
		Рис. 2. Пара шифрующих преобразований из трех элементарных операций, использованных в различном порядке.	
Каким же условиям должен удовлетворять шифр, не только обладающий необходимой стойкостью, но, в добавок к этому удобный в реализации и использовании. Рассмотрение начнем с требований, которые были особенно актуальными четверть века назад, когда возможности микроэлектронных приборов были весьма ограничены и соображения экономичности и самой возможности реализации шифров на имеющейся элементной базе играли определяющую роль. Сейчас их актуальность заметно меньше, но, тем не менее, они остаются в достаточной степени важными для того, чтобы учитываться и в современных разработках. 
1.	Операции за- и расшифрования должны быть близкими настолько, чтобы могли быть выполнены одним и тем же аппаратным или программным модулем - это диктуется требованием экономичности реализации. 
2.	Объем ключевой информации должен быть относительно небольшим. Разумным является такой размер ключа, при котором невозможно его нахождение путем перебора по всему ключевому пространству, с определенным запасом на возможный прогресс электронной техники. В настоящее время граница практической осуществимости подбора ключа находится где-то в районе 60-64 бит. Соответственно, разумным может считаться размер ключа 80-256 бит. Данное требование вытекает из необходимости хранить ключи на любых носителях, включая нетрадиционные, например - на персональных миниатюрных магнитных карточках. 
3.	Реализация шифра (код программы и постоянные данные) должна быть достаточно компактной для того, чтобы "уместиться" на микроконтроллерах с относительно невысоким объемом запоминающего устройства - последнее требование также диктуется соображениями экономичности реализации. 
Рассмотрим, каким образом можно построить шифр, удовлетворяющий указанным требованиям. Начнем с условия обратимости процедуры зашифрования. Из него вытекает, что все преобразования, непосредственно модифицирующие шифруемые данные, должны быть обратимыми, то есть при их выполнении не должна теряться информация. Перестановка обратима по определению. Непараметризованная замена имеет обратную операцию если она сюрьективна, то есть если каждое возможное заменяющее значение встречается в соответствующем векторе замен ровно один раз. Параметризованная, то есть зависящая от значения ключевого элемента, замена обратима в том случае, если при каждом фиксированном значении параметра соответствующая простая замена обратима. Бинарная функциональная операция обратима, если при каждом фиксированном значении второго, модифицирующего, аргумента задаваемое ей отображение сюрьективно, это равносильно условию, что уравнение модификации элемента данных Y = f(X,K) всегда однозначно разрешимо относительно модифицируемого элемента (X). Унарные функциональные операции можно рассматривать как некоторые бинарные с фиксированным вторым операндом. Из простых обратимых унарных и бинарных логических операций над числами конечной разрядности следует отметить инверсию и операцию побитового исключающего или, из арифметических - изменение знака числа, сложение или вычитание в пределах разрядной сетки числа, умножение и деление по модулю простого числа. Если шифрующее преобразование определено как цепочка описанных выше элементарных операций, то достаточно просто построить обратное ему, если только все элементарные операции в цепочке обратимы. 
Для этого достаточно выполнить перечисленные ниже требования, которые, хотя и не являются абсолютно необходимыми, тем не менее исчерпывают практически все случаи эффективно реализуемых преобразований, и потому на практике всегда принимаются во внимание: 
1.	Все шифрующие преобразования должны принимать на входе и выдавать на выходе блок данных одного и того же размера, не считая дополнительных входов для параметра замены и второго операнда функционального преобразования. 
2.	Замены, применяемые непосредственно к шифруемым данным, должны быть обратимыми, параметризованные замены должны быть обратимыми при каждом фиксированном значении параметра. 
3.	Уравнение функционального преобразования шифруемых данных с помощью бинарной операции должно быть всегда однозначно разрешимо относительно преобразуемого (первого) операнда. 
В этом случае для составного шифрующего преобразования, имеющего линейную структуру, можно очевидным образом сконструировать обратное преобразование: оно строится комбинированием обращений его составных частей в порядке, обратном тому, в котором они использовались в исходном преобразовании, как это показано на рисунке 3. 
Если прямое преобразование определяется формулой 
, 
то обратное ему преобразование задается следующей формулой: 
. 
В данных формулах обозначает одну из перечисленных выше простых операций преобразования (перестановку, подстановку или функциональную перацию), возможно, зависящую от параметра - ключевого элемента Ki. Операции группируются справа налево, то есть (T2T1)(X) обозначает T2(T1(X)). 
		Рис. 3. Шифрующее преобразование с линейной структурой и обратное ему шифрующее преобразование.	
Для того, чтобы прямое и обратное преобразование было возможно реализовать в одном аппаратном блоке или программном модуле, они должны быть идентичны с точностью до используемых ключевых элементов. Это означает, что шифрующее преобразование должно быть "антисимметрично" самому себе - для каждого его шага, находящегося на определенном расстоянии от начала преобразования, на точно таком же расстоянии от его конца должен располагаться обратный ему шаг, использующий тот же самый ключевой элемент: 
T-1 ~ T, 
если для всех i справедливо следующее условие: 
, для всех Ki, или Ti-1Tn-i. 
Если данное условие выполняется, процедуры за- и расшифрования могут осуществляться одним и тем же программным и аппаратным модулем и отличаются только порядком использования ключевых элементов. 
Теперь рассмотрим требование относительного небольшого размера ключа - как было отмечено выше, он не должен быть намного больше размера, достаточного для исключения практической возможности его нахождения полным перебором по всему ключевому пространству. Так как этот "критический" размер составляет в настоящее время величину порядка восьми байт, разумный размер ключа не превышает 256 бит. Ясно, что для получения необходимой стойкости шифра придется использовать достаточно большое количество элементарных шагов преобразования, нуждающихся в наборе ключевых элементов, намного (в разы) превосходящем по размеру ключ. Поэтому во всех шифрах подобного типа применяется процедура "развертывания", с помощью которой из небольшого ключа строится массив ключевых элементов нужного размера. 
Процедура "развертывания" ключа должна удовлетворять следующим требованиям: 
1.	Биты (символы) каждого ключевого элемента должны быть равновероятны и статистически независимы друг от друга. 
2.	Биты (символы) каждого ключевого элемента должны быть статистически независимы от битов (символов) нескольких соседних ключевых элементов. Это условие должно выполняться в пределах такого количества шагов шифрования, на котором еще можно проследить статистические зависимости между битами (символами) шифруемых блоков. 
	Рис. 4. Шаги шифрующего преобразования.	
Данное требование проиллюстрировано на рисунке 4. Для любой пары шагов шифрующего образования, не обязательно смежных, допускается тем меньшая коррелированность используемых ими ключевых элементов, чем больше коррелированность выхода первого из них со входом второго: 
|C(Xi+1,Xi+n)||C(Ki,Ki+n)|, 
где С - некоторая мера коррелированности. Понятно, что данная зависимость не является количественно строгой, она отражает суть вопроса лишь качественно. Опять же следует отметить, что данное требование не является абсолютно необходимым. Нет ничего страшного, если оно выполняется не в полной мере для отдельных пар шагов преобразования. Однако систематическое игнорирование этого правила приводит к тому, что криптоанализ шифра значительно облегчается. 
Криптостойкость последовательности ключевых элементов является необязательным, но весьма полезным ее свойством, так как сама по себе гарантирует выполнение двух вышеприведенных требований. Возможны различные подходы к выработке ключевых элементов для шагов шифрования - от самых простых, до обладающих сложностью, сопоставимой со сложностью самого шифра. Например, в качестве ключевых элементов для шагов шифрования можно просто брать фрагменты ключа, как это делается в отечественном стандарте шифрования. Можно вырабатывать ключевые элементы с помощью генератора псевдослучайных чисел. Здесь спектр возможных решений чрезвычайно широк - от сравнительно несложных схем выработки гаммы на основе сдвиговых регистров с обратной связью до генерации последовательности элементов с помощью того же самого криптоалгоритма. Последний подход реализован, например, в шифре BLOWFISH. Конечно, он значительно увеличивает стойкость шифра, но и существенно затрудняет его эффективную реализацию. Например, в упомянутом шифре BLOWFISH построение массива ключевых элементов вычислительно эквивалентно выполнению более 500 циклов шифрования, что делает его непригодным для реального практического использования всюду за исключением систем, в которых смена ключа происходит достаточно редко, и объемы массивов, шифруемых на одном ключе, велики. 
Наконец, требование компактности реализации алгоритма с точки зрения кода и используемых постоянных данных приводит к идеологии его построения из одинаковых групп преобразований, повторенных нужное число раз. В этом случае реализация алгоритма работает итеративно - результат каждой итерации, за исключением последней, является входом для следующей итерации. Кроме того, очевидно, что каждая повторяющаяся группа преобразований, из которых построен криптоалгоритм, должна удовлетворять рассмотренному выше требованию антисимметричности прямого и обратного криптопреобразований, которое в данном случае должно выполняться на уровне отдельных групп. 
Требование компактности вспомогательных массивов данных можно выполнить, используя на разных итерациях преобразования один и тот же комплекта векторов замен. 
Таким образом, в настоящем выпуске мы с вами рассмотрели базовые требования, в соответствии с которыми строятся современные шифры: 
•	построение шифров из простых преобразований - перестановок, подстановок, элементарных функциональных операций и чередование операций различного типа; 
•	циклическая, итеративная структура алгоритма - одна итерация состоит из нескольких простых преобразований, итерации отличаются друг от друга только использованными ключевыми элементами; 
•	антисимметричная структура алгоритма, позволяющая достичь структурной эквивалентности процедур за- и расшифрования, они отличаются друг от друга только последовательностью использования ключевых элементов; 
•	использование ключа относительно небольшого размера и выработка из него массива ключевых элементов для шагов преобразования с помощью процедуры "развертывания" ключа.
Комбинированием простых шифрующих преобразований в линейную цепочку можно создать вполне надежный составной шифр. Однако для достижения приемлемой стойкости такого шифра потребовалось бы использовать весьма большое количество элементарных преобразований. Эта схема построения криптографических алгоритмов не получила сколько-нибудь заметного распространения, потому что была предложена другая схема, имеющая лучшие показатели сложность/трудоемкость преобразования. Более высокая эффективность достигается в ней использованием следующего общего принципа: 
Если есть система обработки данных, составленная из относительно простых блоков преобразований, то, в общем случае, ее сложность намного выше, если структура этой системы отлична от линейной и содержит ветвления и циклы.	
Вспомните, что в алгоритме с сильно разветвленной структурой разобраться намного сложнее, чем в линейном алгоритме. Другой пример, из теории автоматического регулирования: системы преобразования аналогового сигнала, содержащие петли обратной связи и параллельные ветви, на порядок сложнее анализировать, чем цепи, составленные из тех же самых динамических звеньев, но имеющие линейную структуру. Таким образом, усложнить шифрующее преобразование при фиксированном количестве элементарных шагов можно, если сделать его структуру нелинейной. И настоящий и следующий выпуски будут посвящены обсуждению того, как достигнуть этой цели на практике. 
Прежде чем перейти непосредственно к рассмотрению предмета настоящего выпуска, вернемся к теме выпуска предыдущего, и рассмотрим один вопрос, который остался в нем без необходимого освещения. Вспомним, что ключевые данные могут комбинироваться с шифруемыми данными в преобразованиях двух типов: заменах и функциональных операциях. Оказывается, что второй способ использования ключевой информации предпочтительнее. Вместо того, чтобы делить входы вектора замены между блоком шифруемых данных и ключевым элементом, оказалось выгоднее скомбинировать данные с ключом посредством подходящей бинарной операции, а затем подвергнуть результат замене. Предположим, например, что мы преобразуем 32-битовый блок данных, используя 32-битовый ключ и несколько узлов замены с 4-битовым входом. Если использовать для комбинирования ключа и данных узлы замены, то нам необходимо будет использовать 16 узлов замены 4 бита на 2 бита, на вход каждого узла замены будут подаваться два бита шифруемых данных и два бита ключа. При этом каждый выходной бит такого узла будет зависеть ровно от двух битов данных и от двух битов ключа. Если же мы подвергнем преобразованию замены побитовую сумму по модулю 2 ключа с данными, то нам необходимо будет использовать 8 узлов замены 4 бита на 4 бита, и каждый выходной бит узла замен будет зависеть уже от четырех битов ключа и от четырех битов данных. Тем самым в этом преобразовании может быть достигнута большая степень перемешивания и рассеивания. 
В результате сказанного выше в практических шифрах для комбинирования шифруемых данных и ключа почти повсеместно используются бинарные операции аддитивного и, значительно реже, мультипликативного типа. Рассмотрим указанную процедуру, соответствующий блок преобразования показан на рисунке 1: 
	Рис. 1. Комбинирование ключевого элемента с данными с использованием бинарной операции "".	
В этом случае преобразование осуществляется по следующему уравнению: 
Ti+1 = TiKi. 
Бинарная операция "", использованная для модификации шифруемого блока, должна обладать свойством, необходимым для операции наложения гаммы, в частности, должна существовать обратная ей операция , такая, что для любых блоков данных T и K допустимого размера должно выполняться следующее условие: 
(TK)K = T. 
Сложность преобразования существенно повысится, если комбинировать с данными не непосредственно ключевой код, а код, выработанный из ключа и зависящий от данных, как показано на рисунке 2: 
	Рис. 2. Шифрующее преобразование блока данных с использованием кода, выработанного из ключевого элемента Ki и шифруемого блока Ti.	
В этом случае преобразование осуществляется по следующему уравнению: 
Ti+1 = Tif(Ti,Ki). 
На самом деле понятно, что с математической точки зрения данная запись мало отличается от наиболее общей формы записи преобразования: 
Ti+1 = F(Ti,Ki),	(*)	
однако, в отличие от последней, она содержит некоторые указания на возможный способ своей реализации. Ее важная особенность заключается в том, что от функции преобразования f из первого уравнения уже не требуется обратимость, как от функции F из уравнения (*), от нее требуется только как можно большая сложность плюс выполнение некоторых дополнительных условий, которые в сильно упрощенном виде могут быть сформулированы как отсутствие потерь информации при ее вычислении. Дело в том, что при создании шифрующего преобразования общего вида бывает необходимо примирить два противоречащих друг другу требования: 
•	преобразование должно быть обратимым - иначе расшифрование будет невозможным; 
•	преобразование должно быть достаточно сложным и нелинейным - в противном случае оно не может претендовать на то, чтобы являться подлинно шифрующим преобразованием. 
Понятно, почему указанные требования противоречат друг другу - выполнение обратного преобразования есть не что иное, как решение уравнения прямого преобразования относительно одного из его аргументов, однако, если это уравнение нелинейное, то не существует общих методов его решения. 
Обратимость изображенного на рисунке 2 преобразования означает, что должна существовать эффективно вычислимая функция g(Ti+1,Ki), обладающая следующим свойством: 
f(Ti,Ki) = g(Ti+1,Ki) = g(Tif(Ti,Ki),Ki)	(**)	
для любых допустимых блоков данных Ti и Ki. В этом случае обратное преобразование будет иметь вид, изображенный на рисунке 3: 
	Рис. 3. Обращение шифрующего преобразования.	
Обратное преобразование выполняется в соответствии со следующим уравнением: 
Ti = Ti+1g(Ti+1,Ki). 
В общем случае сконструировать пару функций преобразования (f и g), удовлетворяющих уравнению (**) и являющихся при этом сложными и нелинейными, достаточно трудно. Тем не менее, это возможно, если "отделить" требование сложности функций f и g от требования выполнения условия (**). Это легко можно сделать, если использовать операцию "" модификации шифруемого блока, которая оставляет неизменным значение некоторой функции от преобразуемого блока данных: 
Ii = J(Ti) = J(TiГi) = J(Ti+1) 
для любых блоков данных Ti, Гi подходящего размера. Понятно, что в этом случае и обратная ей операция "" также обладает указанным свойством: 
Ii = J(Ti+1) = J(Ti+1Гi) = J(Ti). 
В случае построения шифрующего преобразования по указанному принципу прямое и обратное преобразование будут иметь структуру, изображенную на следующем ниже рисунке 4: 
		
Рис. 4. Стандартные шифрующие преобразования: прямое (слева) и обратное (справа)	
Для определенности будем называть подобное преобразование стандартным шифрующим преобразованием или стандартным шагом шифрования, а архитектуру шифров, ими задаваемую, стандартной или базовой архитектурой шифров. Их использование позволяет разделить очень сложную в общем случае задачу создания преобразования, обладающего одновременно высокой сложностью и нелинейностью с одной стороны, и являющегося при этом обратимым с другой стороны, на две решаемые независимо друг от друга подзадачи: 
•	создание функции преобразования данных, обладающей высокой сложностью и нелинейностью; 
•	создание схемы преобразования, использующей заданную функцию преобразования и при этом обратимой независимо от примененной функции. 
Функция J(Ti), используемая для выделения инвариантного относительно преобразования блока данных как из самого преобразуемого блока, так и из результата его преобразования, называется инвариантом стандартного шифрующего преобразования или инвариантом стандартного шага шифрования, а функция f(Ii,Ki), предназначенная для выработки блока данных, используемого для модификации шифруемого блока, из инварианта Ii и ключевого элемента Ki, называется функцией шифрования шага преобразования. Сам шаг шифрования в шифрах, построенных в соответствии с изложенными принципами, называется раундом шифрования или просто раундом. 
В рассматриваемом случае прямое и обратное шифрующие преобразования осуществляются в соответствии со следующими уравнениями: 
Ti+1 = Tif(J(Ti),Ki),
Ti = Ti+1f(J(Ti+1),Ki). 
Прежде чем продолжить рассмотрение необходимых свойств стандартных шифрующих преобразований, обсудим возможные соотношения между размерами блоков, участвующих в них. Если между размерами преобразуемого блока (Ti), модифицирующего значения (Гi) и инварианта (Ii) выполняется следующее соотношение 
|Ti| = |Гi| + |Ii|,	(***)	
то операция модификации данных ("") не должна терять информацию о своих аргументах, - это, в частности, означает, что изменение любого из аргументов должно приводить к изменению значения функции. Если равенство (***) не будет выполняться и его левая часть будет больше правой части, то стойкость преобразования будет далеко от оптимума - ее можно будет повысить, увеличив размер модификатора (Гi), инварианта (Ii), или их обоих. Если же правая часть окажется больше левой части, то операция модификации обязательно будет терять информацию о модифицирующем элементе - это означает, что будут существовать различные элементы Г и Г', такие, что для некоторого блока данных T будет выполняться следующее равенство: 
TГ = TГ', 
в чем также нет особого смысла. Таким образом, резонно выбирать размеры блоков, участвующих в преобразовании, такими, чтобы выполнялось риведенное выше равенство (***). Идем дальше, с точки зрения достижения необходимой стойкости и эффективности шифрующего преобразования выгодно взять размеры модификатора (Гi) и инварианта (Ii) равными: |Гi| = |Ii|. С учетом равенства (***) их размер будет равен половине размера шифруемого блока: 
|Г| = |I| = |T|/2. 
Данное соотношение выполняется для подавляющего большинства современных практических шифров, построенных в соответствии с описанной архитектурой. 
Продолжим рассмотрение стандартной архитектуры шифров: инвариант и функция шифрования могут быть различными для различных шагов шифрования. Вспомним о желательном свойстве криптоалгоритмов, обсуждавшимся в предыдущем выпуске - о возможности реализации прямого и обратного преобразований одним и тем же аппаратным блоком или программным модулем. Для шифров, имеющих рассматриваемую архитектуру, это возможно, если они имеют антисимметричную структуру. Это означает, что операции модификации, используемые на равноотстоящих от начала и конца цепочки преобразований шагах, должны быть обратными друг другу, а их инварианты и функции шифрования должны совпадать: 
[i]-1n-i+1,
fifn-i+1,
JiJn-i+1. 
Наиболее простым образом этого можно достигнуть, если для модификации использовать операцию побитового исключающего ИЛИ, изменяющую весь блок или его часть, а все инварианты и функции шифрования взять одинаковыми. 
Теперь поговорим о том, каким образом можно создать инвариант в шифрующем преобразовании. Один из наиболее очевидных способов сделать это заключается в том, чтобы ... не менять определенную часть преобразуемого блока, оставить ее неизменной, в буквальном смысле слова инвариантной, как показано ниже на рисунке 5. В этом случае эта неизменяемая часть блока и будет являться инвариантом, для определенности, предположим, что это младшая его часть. 
	Рис. 5. Стандартное шифрующее преобразование блока данных, в котором инвариантом является часть шифруемого блока.	
В этом случае преобразование осуществляется по следующим уравнениям: 
Hi+1 = Hif(Li,Ki),
Li+1 = Li, 
где Hi и Li - соответственно старшая и младшая части преобразуемого блока данных. Ту часть блока, которая не изменяется на раунде, давайте называть шифрующей частью, а ту, которая подвергается преобразованию - шифруемой частью. Так как одна из частей блока в ходе такого преобразования не подвергается изменению, понятно, что для построения стойкого шифра перед каждым новым шагом преобразования необходимо по-новому разделить блок на шифрующую и шифруемую части. Интуитивно ясно, что для обеспечения максимальной стойкости при прочих равных условиях необходимо обеспечить, чтобы все двоичные разряды блока входили в шифруемую часть одинаковое или почти одинаковое число раз. Технически этого можно достигнуть различными способами, например, после каждого шага преобразования выполнять циклический сдвиг блока, выводящий на шифруемую (старшую) позицию не подвергавшиеся изменению на предыдущем шаге разряды блока. Или чередовать шаги преобразования, как это показано на рисунке 6 - на нечетных шагах модифицировать старшую часть блока с использованием младшей, а на четных шагах - наоборот, младшую часть с помощью старшей. 
	Рис. 6. Пара взаимодополняющих шифрующих преобразований.	
Преобразование осуществляется по следующим уравнениям: 
Hi+2 = Hi+1 = Hif(Li,Ki),
Li+2 = Li+1g(Hi+1,Ki+1) = Lig(Hi+1,Ki+1), 
Архитектура шифров, базирующаяся на описанном выше преобразовании, оставляющем неизменной часть шифруемого блока, называется сетью Файстеля, точнее - обобщенной сетью Файстеля. Разница между ними заключается в том, что в первой для модификации данных используется операция побитового исключающего ИЛИ, а во втором - любая подходящая бинарная операция. Данная архитектура шифров была предложена в 70-е годы пионером в создании криптографических алгоритмов подобного типа доктором Хорстом Файстелем, работавшим в то время в исследовательской лаборатории фирмы IBM и создавший там криптосистему Люцифер, послужившую прототипом наиболее известного шифра этого типа - американского стандарта шифрования, криптоалгоритма DES, сохраняющего свой статус стандарта вплоть до настоящего времени, но, очевидно, доживающего в этом качестве последние месяцы. 
В общем случае обе части, на которые делится преобразуемый блок данных, могут иметь неодинаковый размер. Можно всегда представить шифр этого типа таким образом, что шифрующей является младшая часть блока, а шифруемой - старшая его часть. В этом случае между раундами необходимо выполнить вращение блока в любую сторону таким образом, чтобы на следующем раунде шифруемой стала часть блока, входившая на предыдущем раунде в его шифрующую часть. Понятно, что для каждого раунда разделение блока на шифрующую и шифруемую части будет выполняться заново. 
	Рис. 7. Раунд шифрования в обобщенном шифре Файстеля.	
Если представлять преобразуемый блок данных как целое беззнаковое число, то уравнение преобразования одного раунда будет следующим: 
, 
если же его интерпретировать как массив битов, то уравнение будет следующим: 
, 
где через Lon(X) и Hin(X) обозначен блок из n соответственно младших и старших битов блока X, через X || Y - конкатенация блоков X и Y, - их объединение в один блок данных таким образом, что X является старшей частью объединенного блока, а Y - его младшей частью, через - целую часть действительного числа x, nH и nL - размер соответственно старшей (шифруемой) и младшей (шифрующей) частей преобразуемого блока. 
Конечно, размер шифрующей и шифруемой части блока может изменяться от раунда к раунду, однако особого смысла в этом нет и обычно эти величины постоянны для конкретного криптоалгоритма. Если они равны друг другу, то такая схема называется сбалансированной, а если нет - то несбалансированной сетью Файстеля. 
Чтобы блок гаммы, вырабатываемый и используемый на раунде шифрования, мог принимать любое возможное значение, - это необходимо для обеспечения высокой стойкости шифра, - суммарный размер шифрующей части блока и ключа раунда не должен быть меньше размера шифруемой части блока: 
|Ki| + |Li||Hi|. 
Более того, для усложнения анализа алгоритма целесообразно выбирать эти размеры таким образом, чтобы каждый из них в отдельности был не меньше размера шифруемой части блока: 
|Ki|, |Li||Hi|. 
По указанной причине на практике не так часто встречаются шифры Файстеля, в которых шифрующая часть блока меньше шифруемой по размеру |Li| < |Hi|, особенно для размеров блока, не превышающих 64 бита. С другой стороны, за один раунд шифруется |Hi| бит блока, и если уменьшить эту величину, то при фиксированном количестве раундов каждый бит блока будет шифроваться меньшее число раз, поэтому шифры Файстеля с размером шифруемой части блока меньше шифрующей, тоже не получили значительного распространения. Таким образом, остаются шифры, в которых размеры обеих частей блока одинаковы: |Li| = |Hi|. Именно такие шифры, архитектура которых, как было отмечено выше, называется сбалансированной сетью Файстеля, доминируют в современной практической криптографии. Схематически их можно представить двояко, как показано на левой и правой частях следующего ниже рисунка 1. Правая схема определяет в точности то же самое преобразование, что и левая, и сделана в предположении, что число раундов (n) четно. 
		
Рис. 1. Сбалансированная обобщенная сеть Файстеля.	
В сбалансированной сети Файстеля преобразования выполняются по следующим уравнениям: 
X0 = Hi|T|/2(T), X1 = Lo|T|/2(T), 
Xi+1 = Xi-1f(Xi,Ki), для i = 1,2,...,n, 
T' = Xn+1 || Xn, 
где n - число раундов в процедуре шифрования. 
В сбалансированном шифре Файстеля за один раунд шифруется половина блока данных, поэтому для того, чтобы обе части блока шифровались одинаковое число раз, выбирают число раундов четным. 
Если в раундах шифрования для наложения гаммы использовать операцию побитового исключающего ИЛИ, то индукцией по числу раундов очень легко доказать, что процедуры за- и расшифрования будут отличаться друг от друга только порядком использования ключевых элементов и функций шифрования раунда, как это показано на следующем рисунке 2: 
		
Рис. 2. Преобразования за- и расшифрования в сбалансированном шифре Файстеля.	
Если последовательность раундовых функций, использованных в шифре, палиндромиальна (т.е. если ), и, в частности, если на всех раундах используется одна и та же функция шифрования, то процедуры за- и расшифрования различаются только порядком использования раундовых ключей - они взаимно обратны. В этом случае шифр обладает весьма полезным с точки зрения удобства реализации свойством - процедуры за- и расшифрования могут быть выполнены одним и тем же аппаратным или программным модулем. Использование одинаковых или почти одинаковых функций шифрования позволит достигнуть другого весьма желательного свойства шифра - итеративности. Это означает, что все итерации-раунды может выполнять один и тот же модуль, в результате чего станет возможным получить более компактные реализации шифров. 
Следует отметить, что в цепочку преобразований блока в шифрах подобной структуры иногда добавляют преобразования, рассмотренные в выпуске 4 - так называемые прямые преобразования - перестановки, подстановки, функциональные операции непосредственно над шифруемыми данными. Для того, чтобы алгоритмы за- и расшифрования были структурно эквивалентны, необходимо, чтобы для каждого включенного в алгоритм прямого преобразования, отстоящего от начала цепочки на несколько шагов, симметрично ему, то есть точно на таком же расстоянии от конца преобразования находилось обратное преобразование - в точности, как это было описано в выпуске 4. Обычно прямое преобразование добавляют в начало алгоритма, это делают для того, чтобы "разбить" типовые паттерны, встречающиеся в шифруемых данных. В соответствии с вышеизложенным правилом в этом случае в конце цепочки используется обратное преобразование. Например, перед первым раундом шифрования в алгоритме DES выполняется битовая перестановка, а после последнего раунда - обратная ей битовая перестановка. В более поздних шифрах для этой цели используется комбинирование с ключевым элементом, выполняемое намного быстрее, нежели перестановка битов. 
Следует отметить, что раундом шифрования обычно называют цикл преобразования с использованием функции шифрования, нетривиальным образом зависящей от ключа раунда и шифрующей части блока. Если преобразование проще, и в нем используется только ключевой элемент или только шифрующая часть блока, такой шаг, хотя формально и мог бы рассматриваться как раунд, таковым не считается. Например, шаги алгоритма, реализующие изображенные на следующем ниже рисунке упрощенные преобразования, не считаются раундами: 
			
H' = HL	T' = TK	T' = P(T)	
Рис. 3. Преобразования, используемые в шифрах наряду со стандартными шагами (раундами) шифрования.	
На этом мы с вами закончим рассмотрение сетей Файстеля и перейдем к рассмотрению альтернативных решений в построении шифров. Оставлять часть преобразуемого блока неизменной - наиболее простой и очевидный способ получить инвариант относительно преобразования, но не единственный. Другой способ сделать это состоит в том, чтобы разделить шифруемый блок на несколько частей и изменять их согласованным образом: 
T = (T1,T2,...,TL),
Ti' = TiГ,
T' = (T1',T2',...,TL'), 
так, чтобы некоторая функция от преобразуемого блока не меняла своего значения: 
J(T) = J(T'), или J(T1,T2,...,TL) = J(T1',T2',...,TL'), 
где J - функция выработки инварианта. 
Блок можно разделить на произвольное число частей. Однако, поскольку обычно размер блока в битах является степенью двойки, а размеры частей блока также желательно сделать одинаковыми, то количество частей, на которые он разделяется, тоже могут быть только степенями двойки. Обычно шифруемый блок делится на две одинаковые части: 
T = (H,L), |H| = |L| = |Г| = |T|/2 = N/2. 
В этом случае для модификации данных могут быть использованы пары взаимно обратных операций, такие, как сложение и вычитание в пределах разрядной сетки блоков, или умножение и деление по модулю простого числа. Мы не будем подробно рассматривать в настоящем выпуске необходимые свойства, которыми должны обладать операции этой пары, мы просто отметим, что они должны быть подобны перечисленным выше парам. Предположим, например, что используется пара операций "", "" - скажем, сложение и вычитание в пределах разрядной сетки чисел, определенные следующим образом: 
HL = (H + L) mod 2N/2 и HL = (H - L) mod 2N/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 = (H1,H2,...,HK),
L = (L1,L2,...,LK),
Г = (Г1,Г2,...,ГK),
J = (J1,J2,...,JK), 
где для всех k = 1, 2,..., K справедливо |Hk| = |Lk| = |Гk| = |Jk| = zk. В этом случае модификация фрагментов и выработка инварианта осуществляется по следующим формулам: 
H'k = HkГk,
L'k = LkГk,
Jk = HkLk, 
где "" и "" - пара взаимно обратных операций над блоками размера zk бит. Понятно, что в рамках применения указанных двух операций к фрагментам данных независимо от других фрагментов может быть использована любая из четырех возможных вышеприведенных схем. При этом, однако, указанное деление на фрагменты не должно затрагивать выработки модифицирующего значения (Г) из инварианта (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.