Архитектура блочных шифров

🕛 02.04.2009, 13:12

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

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

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

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

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

Ниже дана подробная характеристика каждого из упомянутых типов преобразований:

Шифры перестановок чрезвычайно просто реализуются аппаратно - разводкой проводников на плате или в кристалле, при этом совсем не требуется каких-либо дополнительных затрат, так как проводники, связывающие регистры аппаратуры, так или иначе присутствуют в схеме. В то же самое время эти преобразования очень неэффективно реализуются программно на процессорах общего назначения. Как правило, вычислительные затраты составляют не менее двух машинных команд на каждый двоичный разряд в модифицируемом блоке, если только в перестановках нет согласованности. Этой причиной, в частности, объясняется тот факт, что многие шифры, широко использующие операции данного типа, имеют при прочих равных условиях существенно менее эффективные реализации по сравнению с шифрами, их не использующими. Например, американский стандарт шифрования криптоалгоритм DES при вдвое меньшем количестве шагов в цикле шифрования по сравнению с Российским стандартом (16 против 32) имеет примерно вдвое более медленную оптимальную реализацию для процессоров Intel x86.

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

x заменяется на y = V [x].

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

|V | = 2|X|·|Y |,

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

|S | = nv|V | = nv·2|X|·|Y |,

где nv - число подблоков размера |X |, в которых производятся подстановки. Как уже отмечалось выше, размер таблицы подстановок быстро увеличивается с ростом размера заменяющего, и, особенно, заменяемого блока, что влечет за собой возрастание требований к необходимому для реализации шифра объему памяти. С другой стороны, увеличение этих размеров усложняет криптоанализ и, тем самым, повышает стойкость шифра, поэтому на практике их следует выбирать на границе разумности, ведь криптоалгоритм проектируется на достаточно длительный срок, а возможности электронной техники увеличиваются очень быстро. В алгоритме DES суммарный объем блоков подстановки равен |SDES| = 8·26·4 = 211 бит = 256 байт. В отечественном стандарте это величина того же порядка: |SГОСТ| = 8·24·4 = 29 бит = 64 байта. Следует помнить, что указанные шифры разрабатывались в семидесятые годы, когда понятие "микросхема" еще только начинало входить в наш обиход, обычная емкость микросхемы запоминающего устройства составляла несколько десятков, максимум сотен битов, а объем оперативной памяти 32Кбайта считался совсем неплохим вариантом для компьютера. Вполне естественно, что созданные в то время криптоалгоритмы отражали суровые реалии тех дней. Сейчас эта проблема практически отсутствует, и поэтому современные шифры гораздо более свободны в данном отношении. Так, в криптоалгоритме BLOWFISH подстановки производятся следующим образом: каждый из 4-х байтов, составляющих 32-битовое слово, заменяется на 4-байтовое слово, полученные слова преобразуются в одно с помощью логических и арифметических операций. Соответственно размер одной таблицы замен в этом алгоритме равен |SBLOWFISH| = 4·28·32 = 215 бит = 4 Кбайт.

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

Функциональные преобразования - это унарные и бинарные логические и арифметические операции, реализуемые аппаратно логическими схемами, а программно -одной-двумя компьютерными командами. Теоретически, возможно использовать любую операцию, которая может быть сформулирована в терминах логических функций. Однако на практике дело всегда ограничивается теми из них, которые имеются в наборах команд универсальных процессоров и реализованы аппаратно в виде микросхем. Из логических операций это основные логические функции - инверсия, и бинарные - побитовые И, ИЛИ, ИСКЛЮЧАЮЩЕЕ ИЛИ, из арифметических - изменение знака (переход к дополнительному коду), и бинарные - сложение, вычитание, умножение, деление по модулю некоторого числа, из битовых манипуляций - циклические сдвиги.

Как же построить надежный шифр из элементарных операций указанного типа? Наиболее очевидная идея - каскадировать их, как это показано на рисунке 1. Символами P, S, F на нем обозначены операции перестановок (Permutation), замен (Substitution), функциональных преобразований (Function) соответственно. Ключевые элементы (Ki) могут комбинироваться с преобразуемыми данными в операциях подстановок и функциональных преобразований.

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

Даже если комбинируются две различные операции, принадлежащие одной и той же группе, сложность полученного преобразования меньше, чем могла бы быть, если бы они были разделены операцией другого типа. На рисунке 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, или f1.gif (220 bytes)

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

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

Процедура "развертывания" ключа должна удовлетворять следующим требованиям:

1. Биты (символы) каждого ключевого элемента должны быть равновероятны и статистически независимы друг от друга.

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

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

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

f2.gif (768 bytes)

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

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

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

Требование компактности вспомогательных массивов данных можно выполнить, используя на разных итерациях преобразования один и тот же комплекта векторов замен.

Таким образом, в настоящем выпуске мы с вами рассмотрели базовые требования, в соответствии с которыми строятся современные шифры:

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

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

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