На главную | Содержание | Назад | Вперёд
Наши друзья

 

 

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

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

Шифр функциональных преобразований
Заключается в выполнении сдвигов, логических и арифметичес­ких операций над элементами данных.
Ниже дана подробная характеристика каждого из упомянутых типов преобразований.
Шифры перестановок чрезвычайно просто реализуются аппа-ратно - разводкой проводников на плате или в кристалле, при этом совсем не требуется каких-либо дополнительных затрат, так как про­водники, связывающие регистры аппаратуры, так или иначе присутст­вуют в схеме. В то же самое время эти преобразования очень неэффек­тивно реализуются программно на процессорах общего назначения.
Как правило, вычислительные затраты составляют не менее двух машинных команд на каждый двоичный разряд в модифицируемом блоке, если только в перестановках нет согласованности. Этой причи­ной, в частности, объясняется тот факт, что многие шифры, широко использующие операции данного типа, имеют при прочих равных ус­ловиях существенно менее эффективные реализации по сравнению с шифрами, их не использующими.
Например, американский стандарт шифрования криптоалго­ритм DES при вдвое меньшем количестве шагов в цикле шифрования по сравнению с российским стандартом (16 против 32) имеет пример­но вдвое более медленную оптимальную реализацию для процессоров Intelx86. Общие виды замен аппаратно реализуются с помощью запо­минающих устройств, программно - индексированным чтением из оперативной памяти, что, по сути, одно и то же: замена для элемента данных х берется из вектора или узла замен V, являющегося массивом заменяющих значений, индексированным заменяемым элементом данных: х заменяется на у = V [х].
Программно такая операция реализуется за одну команду, не считая операции загрузки индекса в соответствующий регистр. Размер памяти, необходимый для хранения вектора заменяющих, определяет­ся следующим соотношением:
V | = 2|X(-(Y |, где |Х | и |Y | - размеры заменяемого и заменяющего
блоков в битах соответственно, размер вектора замен V также получа­ется в битах.
Из приведенной формулы видно, что он растет экспоненциально
с ростом размера заменяемого блока. В силу этого выполнение подста­новки в масштабах всего шифруемого блока невозможно - потребо-
вался бы слишком большой объем памяти для хранения вектора.
Поэтому преобразуемый блок данных разделяют на фрагменты, обычно одинакового размера, и выполняют замену в этих подблоках независимо друг от друга. Для повышения стойкости шифра замену различных частей шифруемого блока следует выполнять с использо­ванием разных векторов которые все вместе составляют табли­цу подстановок или таблицу замен. Для хранения этой таблицы требу­ется участок памяти следующего размера:
|S - nv|V = nv-2|X|-|Yj, где nv - число подблоков размера |Х |, в которых производятся подстановки.
Как уже отмечалось размер таблицы подстановок быстро
увеличивается с ростом размера заменяющего И, особенно, заменяемо­го блока, что влечет за собой возрастание требований к необходимому для реализации шифра объему памяти. С другой стороны, увеличение этих размеров усложняет криптоанализ и тем самым повышает стой­кость шифра. Поэтому на практике их следует выбирать на границе
разумности, ведь криптоалгоритм проектируется на достаточно дли-срок, а возможности электронной техники увеличиваются очень быстро. В алгоритме DES суммарный объем блоков подстанов­ки равен |SDES| - 8-264 - 211 бит - 256 байт.
В отечественном стандарте это величина того же порядка: ISrOCTI  - ,8?-24«4 = ..29 .68» = 64 байта.
Следует помнить, что указанные шифры разрабатывались в се­мидесятые годы, когда понятие «микросхема» еще только начинало входить в наш обычная емкость микросхемы запоминающего
устройства составляла несколько десятков, максимум сотен битов, а объем памяти считался совсем неплохим вари-
антом для компьютера. Вполне естественно, что созданные в то время криптоалгоритмы отражали суровые реалии тех дней. Сейчас эта проблема практически отсутствует и поэтому современные шифры го­раздо более свободны в данном отношении. Так, в криптоалгоритме BLOWFISH подстановки производятся следующим образом: каждый
из 4-х байтов, составляющих 32-битовое слово, заменяется на 4-байто­вое слово; полученные слова преобразуются в одно с помощью логи­ческих и арифметических операщш. Соответственно, размер одной таблицы замен в этом алгоритме равен |SBLOWFISH| - 4-28-32 - 215
бит - 4 Кбайт.
Функциональные преобразования - это унарные и бинарные ло­гические и арифметические операции, реализуемые аппаратно логическими схемами, а программно - одной-двумя компьютерными командами. Теоретически возможно использовать любую операцию,
которая может быть сформулирована в терминах логических функ­ций. Однако на практике дело всегда ограничивается теми из них, ко­торые имеются в наборах команд универсальных процессоров и реали­зованы аппаратно в виде микросхем. Из логических операций это ос­новные логические функции - инверсия, и бинарные побитовые И, ИЛИ, ИСКЛЮЧАЮЩЕЕ ИЛИ, из арифметических - изменение знака (переход к дополнительному коду), и бинарные — сложение, вы­читание, умножение, деление по модулю некоторого числа, из битовых - сдвиги.
Как же построить надежный шифр из элементарных операций указанного типа?
Не имеет смысла комбинировать две однотипные операции под­ряд. Если чередовать процедуры различного типа, сложность резуль­тирующего преобразования (степень перемешивания и рассеивания) будет выше. Это очень легко объяснить: при комбинировании двух операций их сложности складываются за вычетом некоего «дефекта сложности», который тем больше, чем более схожи две операции. Например, суперпозиция двух битовых перестановок может быть вы­ражена одной перестановкой. То же справедливо для двух подстано­вок, выполняемых в одних и тех же границах заменяемых подблоков. Прибавление к блоку данных двух ключевых элементов равносильно прибавлению одного, равного их сумме. Во всех рассмотренных слу­чая добавление к операции еще одной такой же вообще не приводит к возрастанию сложности, а следовательно и стойкости Даже если комбинируются две различные принадлежащие одной и той же группе, сложность полученного преобразования мень­ше, чем могла бы быть, если бы они были разделены операцией друго­го типа.
Каким же условиям должен удовлетворять шифр, не только об­ладающий необходимой стойкостью, но, в добавок к этому, удобный в реализации и использовании? Рассмотрение начнем с требований, ко­торые были особенно актуальными четверть века назад, когда возмож­ности микроэлектронных приборов были весьма ограничены и сооб­ражения экономичности и самой возможности реализации шифров имеющейся элементной базе играли определяющую роль. Сейчас их актуальность заметно меньше, но, тем не менее, они остаются в доста-
точной степени важными для того, чтобы учитываться и в современ­ных разработках.
1. Операции за- и расшифрования должны быть близкими настолько, чтобы могли быть выполнены одним и тем же аппаратным или программным модулем - это диктуется требованием экономич­ности реализации.
2. Объем ключевой информации должен быть относительно не­большим. Разумным является такой размер ключа, при котором невоз­можно его нахождение путем перебора по всему ключевому прост­ранству, с определенным запасом на возможный прогресс электронной техники. В настоящее время граница практической осуществимости подбора ключа находится где-то в районе 60-64 бит. Соответственно, разумным может считаться размер ключа 80- 256 бит. Данное требо­вание вытекает из необходимости хранить ключи на любых носителях, включая нетрадиционные, например, на персональных миниатюрных
магнитных карточках.
3. Реализация шифра (код программы и постоянные данные) должна быть достаточно компактной для того, чтобы «уместиться» на
микроконтроллерах с относительно невысоким объемом запоминаю­щего устройства - последнее требование также диктуется соображе­ниями экономичности реализации.
Рассмотрим, каким образом можно построить шифр, удовлетво­ряющий указанным требованиям. Начнем с условия обратимости про­цедуры зашифрования. Из него вытекает, что все преобразования, не­посредственно модифицирующие шифруемые данные, должны быть
обратимыми, то есть при их выполнении не должна теряться инфор­мация. Перестановка обратима по определению. Непараметризован-ная замена имеет обратную операцию если она то есть
если каждое возможное заменяющее значение встречается в соот­ветствующем векторе замен ровно один раз. Параметризованная, то есть зависящая от значения ключевого элемента, замена обратима в том случае, если при каждом фиксированном значении параметра со­ответствующая простая замена обратима. Бинарная функциональная операция обратима, если при каждом фиксированном значении второ­го, модифицирующего аргумента задаваемое ей отображение сюрьек-
тивно, это равносильно условию, что уравнение модификации элемен­та данных
Y =  f (Х,К)
всегда однозначно разрешимо относительно модифицируемого эле­мента (X).
Унарные функциональные операции можно рассматривать как некоторые бинарные с фиксированным вторым операндом. Из простых обратимых унарных и бинарных логических операций над числами конечной разрядности следует отметить инверсию и опера­цию побитового исключающего или из арифметических - изменение знака числа, сложение или вычитание в пределах разрядной сетки чис­ла, умножение и деление по модулю простого числа. Если шифрующее преобразование определено как цепочка описанньж выше элементар­ных операций, то достаточно просто построить обратное ему, если только все элементарные операции в цепочке обратимы. Для этого до­статочно выполнить перечисленные ниже требования, которые, хотя и
не являются абсолютно необходимыми, тем не менее исчерпывают практически все случаи эффективно реализуемых преобразований и
потому на практике всегда принимаются во внимание:
L Все шифрующие преобразования должны принимать на входе и выдавать на выходе блок данных одного и того же размера, не считая дополнительных входов для параметра замены и второго операнда
функционального преобразования.
2. Замены, применяемые непосредственно к шифруемым дан­ным, должны быть обратимыми, параметризованные замены должны быть обратимыми при каждом фиксированном значении параметра.
3. Уравнение функционального преобразования шифруемых
данных с помощью бинарной операции должно быть всегда однознач­но разрешимо относительно преобразуемого операнда.
В этом случае для составного шифрующего преобразования, имеющего линейную структуру, можно очевидным образом сконстру­ировать обратное преобразование: оно строится комбинированием об­ращений его составных частей в порядке, обратном тому, в котором они использовались в исходном преобразовании.
Для того, чтобы прямое и обратное преобразование было воз­можно реализовать в одном аппаратном блоке или программном моду­ле, они должны быть идентичны с точностью до используемых ключе­вых элементов. Это означает, что шифрующее преобразование должно быть «антисимметрично» самому себе - для каждого его шага, находя­щегося на определенном расстоянии от начала преобразования, на точно таком же расстоянии от его конца должен располагаться обрат­ный ему шаг, использующий тот же самый ключевой элемент:
Т-1 -Т
Если данное условие выполняется, процедуры за- и расшифро-
ватшя могут осуществляться одним и тем же программным и аппарат­ным модулем и отличаются только порядком использования ключе­вых элементов.
Теперь рассмотрим требование относительно небольшого разме­ра ключа - как было отмечено выше, он не должен быть намного боль­ше размера, достаточного для исключения практической возможности нахождения полным перебором по всему ключевому пространству. Так как этот «критический» размер составляет в настоящее время ве­личину порядка восьми байт, разумный размер ключа не превышает 256 бит. Ясно, что для получения необходимой стойкости шифра при­дется использовать достаточно большое количество элементарных ша­гов нуждающихся в наборе ключевых элементов, на­много (в разы) превосходящем по размеру ключ. Поэтому во всех шифрах подобного типа применяется процедура «развертывания», с помощью которой из небольшого ключа строится массив ключевых элементов нужного размера.
Процедура ключа должна удовлетворять сле-
дующим требованиям:
1. Биты (символы) каждого ключевого элемента должны быть равновероятны и статистически друг от друга.
2. Биты (символы) каждого ключевого элемента должны быть статистически независимы от битов (символов) нескольких соседних ключевых элементов. Это условие должно выполняться в пределах та­кого количества шагов шифрования, на котором еще можно просле­дить статистические зависимости между битами (символами) шифру­емых блоков.
Для любой пары шагов шифрующего образования, не обязатель­но смежных, допускается тем меньшая коррелированность используе­мых ключевых элементов, чем больше коррелированность выхода первого из них со входом второго. Опять же следует отмстить, что данное требование не является абсолютно необходимым. Нет ничего страшного, если оно выполняется не в полной мере для отдельных пар шагов преобразования. Однако систематическое игнорирование этого правила приводит к тому, что криптоанализ шифра значительно об­легчается. Криптостойкость последовательности ключевых элементов
является необязательным, но весьма полезным ее свойством, так как
сама по себе гарантирует выполнение двух вышеприведенных требо­ваний.
Возможны различные подходы к выработке ключевых элемен­тов для шагов шифрования - от самых простых до обладающих слож-
ностью, сопоставимой со сложностью самого шифра. Например, в ка­честве ключевых элементов для шагов шифрования можно просто брать фрагменты ключа, как это делается в отечественном стандарте шифрования. Можно вырабатывать ключевые элементы с помощью генератора псевдослучайных чисел. Здесь спектр возможных решений чрезвычайно широк - от сравнительно несложных схем выработки гаммы на основе сдвиговых регистров с обратной связью до генерации последовательности элементов с помощью того же самого криптоалго­ритма.
Последний подход реализован, например, в шифре BLOWFISH. Конечно, он значительно увеличивает стойкость шифра, но и сущест­венно затрудняет его эффективную реализацию. Например, в упомя­нутом шифре BLOWFISH построение массива ключевых элементов вычислительно эквивалентно выполнению более 500 циклов шифро­вания, что делает его непригодным для реального практического ис­пользования всюду, за исключением систем, в которых смена ключа происходит достаточно редко и объемы массивов, шифруемых на од­ном ключе, велики.
Наконец, требование компактности реализации алгоритма с точ­ки зрения кода и используемых постоянных данных приводит к идео­логии его построения из групп преобразований, повто­ренных нужное число раз.
В этом случае реализация алгоритма работает итеративно — ре­зультат каждой итерации, за исключением последней, является вхо­дом для следующей итерации. Кроме того, очевидно, что каждая повторяющаяся группа преобразований, из которых построен крипто­алгоритм, должна удовлетворять рассмотренному выше антисимметричности прямого и обратного криптопреобразований, ко­торое в данном случае должно выполняться на уровне отдельных групп. Требование компактности вспомогательных массивов данных можно выполнить, используя на разных итерациях преобразования один и тот же комплект векторов замен. Мы рассмотрели базовые тре­бования, в соответствии с которыми строятся современные шифры:
— построение шифров из простых преобразований - перестано­вок, подстановок, элементарных функциональных операций и чередо­вание операций различного типа;
— циклическая, итеративная структура алгоритма - одна итера­ция состоит из нескольких простых преобразований, итерации отли­чаются друг от друга только использованными ключевыми элементами;
— антисимметричная структура алгоритма, до-
стичь структурной эквивалентности процедур за- и расшифрования,
они отличаются друг от друга только последовательностью использо­вания ключевых элементов;
- использование ключа относительно небольшого размера и вы­работка из него массива ключевых элементов для шагов преобразова­ния с помощью процедуры «развертывания» ключа.
Комбинированием простых шифрующих преобразований в ли­нейную цепочку можно создать вполне надежный составной шифр. Однако для достижения приемлемой стойкости такого шифра потре­бовалось бы использовать весьма большое количество элементарных преобразований. Эта схема построения криптографических алгорит­мов не получила сколько-нибудь заметного распространения, потому что была предложена другая схема, имеющая лучшие показатели сложность/трудоемкость преобразования. Более высокая эффектив­ность достигается в ней использованием следующего общего принципа.
Если есть система обработки данных, составленная из относи­тельно простых блоков преобразований, то, в общем случае, ее слож­ность намного выше, если структура этой системы отлична от линей­ной и содержит ветвления и циклы. Вспомните, что в алгоритме с
сильно разветвленной структурой разобраться намного сложнее, чем в
линейном алгоритме. Другой пример, из теории автоматического регу­лирования: системы преобразования аналогового сигнала, содержа­щие петли обратной связи и параллельные ветви, на порядок сложнее анализировать, чем цепи, составленные из тех же самых динамических звеньев, но имеющие линейную структуру. Таким образом, усложнить
шифрующее преобразование при фиксированном количестве элемен­тарных шагов можно, если сделать его структуру нелинейной.
Рассмотрим, как достигнуть этой цели на практике. Вспомним, что ключевые данные могут комбинироваться с шифруемыми данны­ми в преобразованиях двух типов: заменах и функциональных опера­циях. Оказывается, что второй способ использования ключевой ин­формации предпочтительнее. Вместо того, чтобы делить входы векто­ра замены между блоком шифруемых данных и ключевым элементом, оказалось выгоднее скомбинировать данные с ключом посредством подходящей бинарной операции, а затем подвергнуть результат замене.
Предположим, например, что мы преобразуем 32-битовый блок данных, используя 32-битовый ключ и несколько узлов замены с 4-би­товым входом. Если использовать для комбинирования ключа и дан­ных узлы замены, то нам необходимо будет использовать 16 узлов за­мены 4 бита на 2 бита, на вход каждого узла замены будут подаваться
два бита шифруемых данных и два бита ключа. При этом каждый вы­ходной бит такого узла будет зависеть ровно от двух битов данных и от двух битов ключа.
Если же мы подвергнем преобразованию замены побитовую сумму по модулю 2 ключа с данными, то нам необходимо будет ис­пользовать 8 узлов замены 4 бита на 4 бита, и каждый выходной бит узла замен будет зависеть уже от четырех битов ключа и от четырех
битов данных. Тем самым в этом преобразовании может быть достиг­нута большая степень перемешивания и рассеивания.
В результате сказанного выше, в практических шифрах для ком­бинирования шифруемых данных и ключа почти повсеместно исполь­зуются бинарные операции аддитивного и, реже, муль­типликативного типа. В этом случае преобразование осуществляется по следующему уравнению:
Ti+1 = Ti 0 Ki
Бинарная операция использованная для модификации шиф­руемого блока, должна обладать свойством, необходимым для опера­ции наложения гаммы, в частности, должна существовать обратная ей операция такая, что для любых блоков данных Т и К допустимо­го размера должно выполняться следующее условие:
(Т ° К)   •   К = Т
Сложность преобразования существенно повысится, если ком­бинировать с данными не непосредственно ключевой код, а код, выра­ботанный из ключа и зависящий от данных. В этом случае преобразо­вание осуществляется по следующему уравнению:
Ti+1 = Ti ° f(Ti,Ki)
На самом деле понятно, что с математической точки зрения дан­ная запись мало отличается от наиболее общей формы записи преоб­разования:
Ti + l = F(Ti,Ki) , (*)
однако, в отличие от последней, она содержит некоторые указания на
возможный способ своей реализации.
Ее важная особенность заключается в том, что от функции пре­образования f из первого уравнения уже не требуется обратимость, как от функции F из уравнения (*), от нее требуется только как можно большая сложность плюс выполнение некоторых дополнительных ус­ловий, которые в сильно упрощенном виде могут быть сформулирова­ны как отсутствие потерь информации при ее вычислении. Дело в том,
что при создании шифрующего преобразования общего вида бывает
необходимо примирить два противоречащих друг другу требования.
Преобразование должно быть обратимым - иначе расшифрова­ние будет невозможным; преобразование должно быть достаточно сложным и нелинейным - в противном случае оно не может претендо­вать на то, чтобы являться подлинно шифрующим преобразованием. Понятно, почему указанные требования противоречат друг другу -выполнение обратного преобразования есть не что иное, как решение уравнения прямого преобразования относительно одного из его аргу­ментов; однако, если уравнение нелинейное, то не существует об­щих методов его решения.
Обратимость преобразования означает, что должна существо­вать эффективно вычислимая функция g(Ti+l,Ki), обладающая сле­дующим свойством:
f(Ti,Ki)   = g(Ti+l,Ki)   = g(Ti   ' f(Ti,Ki),Ki) (**)
для любых допустимых блоков данных Ti и
Обратное преобразование выполняется в соответствии со сле­дующим уравнением:
Ti = g(Ti + l,Ki)
В общем случае сконструировать пару функций преобразования (f и g), удовлетворяющих уравнению и являющихся при этом сложными и нелинейными, достаточно трудно. Тем не менее это воз­можно, если «отделить» требование сложности функций f и g от требо­вания выполнения условия (**). Это легко можно сделать, если ис­пользовать операцию «°» модификации шифруемого блока, которая
оставляет неизменным значение некоторой функции от преобразуе­мого блока данных.
Ii - J(Ti)   =  J(Ti  "  Ti)   = J(Ti+l)
для любых блоков данных Ti, подходящего размера. Понятно, что в этом случае и обратная ей операция также обладает указанным
свойством:
Ii = J(Ti+l)  - J(Ti+l   • ri)   = J(Ti)
Для определенности будем называть подобное преобразование стандартным шифрующим преобразованием или стандартным шагом шифрования, а архитектуру шифров, им задаваемую, стандартной или базовой архитектурой шифров. Их использование позволяет разде­лить очень сложную в общем случае задачу создания преобразования, обладающего одновременно высокой сложностью и нелинейностью, с одной стороны, и являющегося при этом обратимым, с другой сторо­ны, на две решаемые независимо друг от друга подзадачи: создание функции преобразования данных, обладающей высокой сложностью и
нелинейностью; создание схемы преобразования, использующей за­данную функцию преобразования и при этом обратимой независимо
от примененной функции.
Функция J(Ti), используемая для выделения инвариантного
относительно преобразования блока данных как из самого преобразу­емого блока, так и из результата его преобразования, называется инва­риантом стандартного шифрующего преобразования или инвариан­том стандартного шага шифрования, а функция f(Ii,Ki), предназначен­ная для выработки блока данных, используемого для модификации
шифруемого блока, из инварианта Ii и ключевого элемента Ki, называ­ется функцией шифрования шага преобразования. Сам шаг шифрова­ния в шифрах, построенных в соответствии с изложенными принципа­ми, называется раундом шифрования или просто раундом.
В рассматриваемом случае прямое и обратное шифрующие пре­образования осуществляются в соответствии со следующими уравне­ниями:
Ti + l  - Ti   0   £ (J (Ti),Ki), Ti - Ti+l   •   f (J(Ti + l) ,Ki)
Прежде чем продолжить рассмотрение необходимых свойств стандартных шифрующих преобразований, обсудим возможные соот­ношения между размерами блоков, участвующих в них. Если между размерами преобразуемого блока (Ti), модифицирующего значения и инварианта     выполняется следующее соотношение:
I Ti |      |       | + | Ii |, (***)
то операция модификации данных («°») не должна терять информа­цию о своих аргументах — это, в частности, означает, что изменение любого из аргументов должно приводить к изменению значения функ-
ции. Если равенство (***) не будет выполняться и его левая часть бу­дет больше правой части, то стойкость преобразования будет далеко от оптимума - ее можно будет повысить, увеличив размер модификатора (П). инварианта или их обоих. Если же правая часть окажется больше левой части, то операция модификации обязательно будет те­рять информацию о модифицирующем элементе - это означает, что будут существовать различные элементы Г и такие, что для некото­рого блока данных Т будет выполняться следующее равенство:
т 0 г == т °  г1 в чем также нет особого смысла.
Таким образом, резонно выбирать размеры блоков, участвующих в преобразовании, такими, чтобы выполнялось приведенное выше ра­венство (***). Идем дальше, с точки зрения достижения необходимой
стойкости и эффективности шифрующего преобразования выгодно
взять размеры модификатора (П) и инварианта (П) равными: I  П  |  =   |  Ii  | .
С учетом равенства (***) их размер будет равен половине разме­ра шифруемого блока:
I   Г   |   =   |   I   |   =   |   Т |/2
Данное соотношение выполняется для подавляющего боль­шинства современных практических шифров, построенных в соответ­ствии с описанной архитектурой.
Продолжим рассмотрение стандартной архитектуры шифров: инвариант и функция шифрования могут быть различными для раз­личных шагов шифрования. Вспомним о желательном свойстве крип­тоалгоритмов, обсуждавшемся в предыдущем выпуске, - о возможно­сти реализации прямого и обратного преобразований одним и тем же
аппаратным блоком или программным модулем. Для шифров, имею­щих рассматриваемую архитектуру, это возможно, если они имеют ан­тисимметричную структуру.
Это означает, что операции модификации, используемые на рав­ноотстоящих от начала и конца цепочки преобразований шагах, долж­ны быть обратными друг другу, а их инварианты и функции шифрова­ния должны совпадать. Наиболее простым образом этого можно до-

стигнуть, если для модификации использовать операцию побитового исключающего ИЛИ, изменяющую весь блок или его часть, а все ин­варианты и функции шифрования взять одинаковыми.
Теперь поговорим о том, каким образом можно создать инвари­ант в шифрующем преобразовании. Один из наиболее очевидных спо­собов сделать это заключается в том, чтобы... не менять определенную часть преобразуемого блока, оставить ее неизменной, в буквальном смысле слова, инвариантной. В этом случае эта неизменяемая часть блока и будет являться инвариантом, для определенности, предполо­жим, что это младшая его часть.
Приводим стандартное шифрующее преобразование блока дан­ных, в котором инвариантом является часть шифруемого блока. В этом случае преобразование осуществляется по следующим уравнени­ям:
Hi +    = Hi  °  f(Li,Ki),  Li +     = Li,
где Hi и Li - соответственно, старшая и младшая части преобразуемо­го блока данных. Ту часть блока, которая не изменяется на раунде, да­вайте называть шифрующей частью, а ту, которая подвергается преоб­разованию - шифруемой частью.
Так как одна из частей блока в ходе такого преобразования не
подвергается изменению, понятно, что для построения стойкого шиф­ра перед каждым новым шагом необходимо по-ново­му разделить блок на шифрующую и шифруемую части. Интуитивно ясно, что для обеспечения максимальной стойкости при прочих рав­ных условиях необходимо обеспечить, чтобы все двоичные разряды
блока входили в шифруемую часть одинаковое или почти одинаковое количество раз. Технически этого можно достигнуть различными спо­собами, например, после каждого шага преобразования выполнять
циклический сдвиг блока, выводящий на шифруемую позицию не
подвергавшиеся изменению на предыдущем шаге разряды блока. Пре­образование осуществляется по следующим уравнениям:
Hi+2  = Hi+l      Hi  ° f(Li,Ki),
Li+2  = Li+1   " g(Hi + l,Ki + l)   = Li   °  g(Hi + l,Ki + l)
Архитектура шифров, базирующаяся на описанном выше преоб­разовании, оставляющем неизменной часть шифруемого блока, назы­вается сетью Файстеля, точнее - обобщенной сетью Файстеля. Разни-
ца между ними заключается в том, что в первой для модификации дан­ных используется операция побитового исключающего ИЛИ, а во вто­ром - любая подходящая бинарная операция.
Такая архитектура шифров была предложена в 70-е годы пионе­ром в создании криптографических алгоритмов подобного типа докто­ром Хорстом Файстелем, работавшим в то время в исследовательской лаборатории фирмы IBM и создавшим там криптосистему Люцифер, послужившую прототипом наиболее известного шифра этого типа -американского стандарта шифрования, криптоалгоритма DES, сохра­няющего свой статус стандарта вплоть до настоящего времени, но, оче­видно, доживающего в этом качестве последние месяцы.
В общем случае обе части, на которые делится преобразуемый блок данных, могут иметь неодинаковый размер. Можно всегда представить шифр этого типа таким образом, что шифрующей являет­ся младшая часть блока, а шифруемой - старшая его часть. В этом слу­чае между раундами необходимо выполнить вращение блока в любую
сторону таким образом, чтобы на следующем раунде шифруемой ста­ла часть блока, входившая на предыдущем раунде в его шифрующую часть. Понятно, что для каждого раунда разделение блока на шифрую­щую и шифруемую части будет выполняться заново.
Конечно, размер шифрующей и шифруемой частей блока может изменяться от раунда к раунду, однако особого смысла в этом нет и обычно эти величины постоянны для конкретного криптоалгоритма. Если они равны друг другу, то такая схема называется сбалансирован­ной, а если нет - то несбалансированной сетью Файстеля. Чтобы блок гаммы, вырабатываемый и используемый на раунде шифрования, мог принимать любое возможное значение — это необходимо для обеспе­чения высокой стойкости шифра, — суммарный размер шифрующей части блока и ключа раунда не должен быть меньше размера шифруе­мой части блока. Более того, для усложнения анализа алгоритма целе­сообразно выбирать эти размеры таким образом, чтобы каждый из них в отдельности был не меньше размера шифруемой части блока.
По причине на практике не так часто встречаются
шифры Файстеля, в которых шифрующая часть блока меньше шифру­емой по размеру |Li| < |Hi|, особенно для размеров блока, не превыша­ющих 64 бита, С другой стороны, за один раунд шифруется |Hi бит блока, и если уменьшить эту величину, то при фиксированном количе­стве раундов каждый бит блока будет шифроваться меньшее число раз, поэтому шифры Файстеля с размером шифруемой части блока
меньше шифрующей тоже не получили значительного
ния. Таким образом, остаются в которых размеры обеих час-
тей блока одинаковы: |Li| = |Hi|. Именно такие шифры, архитектура ко­торых, как было отмечено выше, называется сбалансированной сетью Файстеля, доминируют в современной практической криптографии. В сбалансированной сети Файстеля преобразования выполняются по следующим уравнениям:
ХО  =  Hi|T|/2(T),   XI   -  Lo|T|/2(T),
Xi+1 - Xi-l  0 f(Xi,Ki)   , для i - l,2,...,n,
T'  - Xn+1   I I Xn
Если последовательность функций, использованных
в шифре, и, в частности, если на всех раундах ис-
пользуется одна и та же функция шифрования, то процедуры за- и рас­шифрования различаются только порядком использования раундо-вых ключей - они взаимно обратим. В этом случае шифр обладает весьма полезным, с точки зрения удобства реализации, свойством -процедуры за- и расшифрования могут быть выполнены одним и тем же аппаратным или программным модулем. Использование одинако­вых или почти одинаковых функций шифрования позволит достиг­нуть другого весьма желательного свойства шифра - итеративности.
Это означает, что все итерации-раунды может выполнять один и тот же модуль, в результате чего станет возможным получить более ком­пактные реализации шифров.
Следует отметить, что в цепочку преобразований блока в шиф­рах подобной структуры иногда добавляют преобразования, рассмот­ренные в выпуске № 4, так называемые прямые преобразования - пе­рестановки, подстановки, функциональные операции непосредствен­но над шифруемыми данными. Для того, чтобы алгоритмы за- и рас­шифрования были структурно эквивалентны, необходимо, чтобы для каждого включенного в алгоритм прямого преобразования, отстояще­го от начала цепочки на несколько шагов, симметрично ему, то есть точно на таком же расстоянии от конца преобразования, находилось
обратное преобразование - в точности, как это было описано в
выпуске №4.
Обычно прямое преобразование добавляют в начало алгоритма; это делают для того, чтобы «разбить» типовые паттерны, встречающи­еся в шифруемых данных. В соответствии с вышеизложенным прави­лом в этом случае в конце цепочки используется обратное вание. Например, перед первым раундом шифрования в алгоритме
DES выполняется битовая перестановка, а после последнего раунда -обратная ей битовая перестановка. В более поздних шифрах для этой цели используется комбинирование с ключевым элементом, выполня­емое намного быстрее, нежели перестановка битов. Следует отметить,
что раундом шифрования обычно называют цикл преобразования с использованием функции шифрования, нетривиальным образом зави­сящей от ключа раунда и шифрующей части блока. Если преобразова­ние проще и в нем используется только ключевой элемент или только
шифрующая часть блока, такой шаг, хотя формально и мог бы рассма­триваться как раунд, таковым не считается. Например, шаги алгорит­ма, реализующие изображенные на следующем ниже рисунке упрощен­ные преобразования, не считаются раундами:
= Р(Т)
На этом мы с вами закончим рассмотрение сетей и пе-
рейдем к рассмотрению альтернативных решений в построении шиф­ров. Оставлять часть преобразуемого блока неизменной - наиболее простой и очевидный способ получить инвариант относительно пре­образования, но не единственный. Другой способ сделать это состоит
в том, чтобы разделить шифруемый блок на несколько частей и изме­нять их согласованным образом:
Т = (Т1,Т2, . . .,TL) , Ti' = Ti ™i Г, Т' = (T1',T2\...,TL')
так, чтобы некоторая функция от преобразуемого блока не меняла сво­его значения:
J(T) J(T'), или        J(TI,T2, . . . , TL)
J(TI',T2 TL 1 ) ,
где J - функция выработки инварианта.
Блок можно разделить на произвольное число частей. Однако,
поскольку обычно размер блока в битах является степенью двойки, а
размеры частей блока также желательно сделать одинаковыми, то ко­личество частей, на которые он разделяется, тоже могут быть только
степенями двойки. Обычно шифруемый блок делится на две одинако­вые части:
Т  =   (H,L),    |Н|   =    L|   =   |   Г|        |Т|/2  = N/2
В этом случае для модификации данных могут быть использова­ны пары взаимно обратных операций, такие, как сложение и вычита­ние в пределах разрядной сетки блоков, или умножение и деление по модулю простого числа. Мы не будем подробно рассматривать в настоящем выпуске необходимые свойства, которыми должны обла­дать операции этой пары, мы просто отметим, что они должны быть подобны перечисленным выше парам. Предположим, например, что используется пара операций - скажем, сложение и вычитание в преде­лах разрядной сетки чисел, определенные следующим образом. В этом
случае процедуры модификации половин шифруемого блока и функ­ция выработки инварианта могут быть следующими.
Иными словами, для каждой пары операций с указанными свой­ствами возможны четыре варианта их использования для выполнения шага шифрования. Общим в этих четырех вариантах является то, что они исчерпывают все случаи, в которых операция вычитания присут­ствует в уравнениях преобразования нечетное число раз, а операция
сложения - четное. Можно разделить модифицируемые части блока
на «зоны» согласованным образом, так что каждому выделенному фрагменту в одной части будет взаимно однозначно соответствовать фрагмент такого же размера в другой части. В этом случае для каждой пары фрагментов можно использовать свою пару операций для моди­фикации фрагментов и выработки инварианта:
Н (.41,-42, . . ,, НК)
= (LI, L2, . . . ,LK)
Г = ( Г1,Г2,..., ГК)
J = (Л, J2, . . ., JK)
где для всех k    1, 2, ...
Понятно, что в рамках применения указанных двух операций к фрагментам данных независимо от других фрагментов может быть ис­пользована любая из четырех возможных вышеприведенных схем. При этом, однако, указанное деление на фрагменты не должно затра­гивать выработки модифицирующего значения (Г) из инварианта (J) с использованием раундового ключевого элемента. Характер зависи­мости второго от первого должен в полной мере соответствовать прин­ципам перемешивания и рассеивания - все биты Г должны зависеть от всех битов J, и характер этой зависимости должен быть как можно бо­лее сложным и запутанным.
Как всегда, особый случай возникает при использовании опера­ции побитового исключающего так как она является обратной самой себе. В этом случае вместо четырех возможных вариантов ком­бинирования использования мы получаем всего один. Именно такой инвариант используется в известном шифре IDEA. Раунд шифра стан­дартной архитектуры используется для получения инварианта опера­ции побитового исключающего.
Очевидно, что смежные раунды шифра должны использовать различные инварианты или должны быть отделены друг от друга до­полнительным преобразованием иного типа, чем использованное на раунде для модификации блока. В противном случае мы получили бы примерно такой же результат, как если бы между раундами шифра Файстеля отсутствовали перестановки старшей и младшей частей
блока.
Если несколько смежных раундов используют один и тот же ин­вариант, то он будет являться инвариантом всей этой цепочки раун­дов. Это почти тривиальное утверждение очень легко доказывается индукцией по числу раундов. Понятно, что игнорирование данной
особенности шифрующих систем может очень сильно снизить стой­кость шифра.
Чтобы этого избежать между раундами описанного выше типа
необходимо включать прямые преобразования шифруемого блока,
или его модификацию с использованием ключевых элементов, или ра­унды с иным инвариантом и с иной операцией, использованной для
модификации блока на раунде. Другими словами, инварианты смеж­ных раундов в общей шифрующей сети должны как можно меньше по­ходить друг на друга. Если между ними значение частей блока моди­фицируется с использованием ключевых элементов, операция, ис­пользуемая для этого, должна как можно сильнее отличаться от опера­ции комбинирования данных с модифицирующим блоком в раунде. Даже для различных операций одной и той же аддитивной группы от­личий может оказаться недостаточно для получения нужной стойкос­ти. Хорошим выходом в такой ситуации является использование опе­раций иного типа, например, мультипликативных. Именно такой под­ход реализован в уже упоминавшемся выше шифре IDEA.
Понятно, что использование операции умножения может сильно снизить эффективность реализации алгоритма, на тельно несложных микроконтроллерах и однокри-
стальных ЭВМ. Вот почему данный тип шифров является скорее экзо­тикой, чем распространенным явлением; имеется всего один широко
известный и используемый представитель этого класса шифров -IDEA. В качестве альтернативы использованию мультипликативных операций для межраундовых модификаций шифруемого блока можно предложить комбинирование с ключевым элементом с помощью более простой операции аддитивной группы с последующим выполнением подстановок. На этом рассмотрение данной темы закончим. В заклю­чение подведем итог:
1. Все современные надежные шифры являются составными, то есть строятся из большого числа относительно несложных шифрую­щих преобразований так, чтобы в полной мере обеспечить наличие
свойств перемешивания и рассеивания.
2. В качестве «строительных шифров используются
битовые перестановки, замены в битовых группах, арифметические и
логические операции. При этом наибольшее перемешивание и рассеи­вание каскада из шифрующих преобразований достигается, если смежные операции в цепочке как можно отличаются друг от
друга.
3. Для усложнения шифров и повышения их стойкости обычно их строят на основе шифрующих структур, в которых за один шаг
шифрования выполняется преобразование данных, оставляющее зна­чение определенной функции шифруемого блока инвариантным, а
собственно шифрование состоит в выработке блока кода из инвариан­та раунда и ключевого элемента раунда с помощью функции шифро­вания, и модификации с его использованием шифруемого блока дан­ных. Такие шифрующие структуры иногда называют «шифрующими сетями».
4. Если два смежных раунда шифрования имеют один и тот же инвариант или если для модификации данных на двух смежных раун­дах используются бинарные операции одной группы, то между ними
необходимо выполнять прямую модификацию шифруемого блока
данных с использованием операции, разрушающей этот инвариант для указанной пары раундов.
5. Наиболее простой и популярный способ создать инвариант -
оставлять часть шифруемого блока неизменной. В этом случае для межраундовой модификации шифруемого блока используют цикли­ческий сдвиг, вырождающийся в обмен его старшей и младшей поло­вин, если их размеры одинаковы. Построенные по этому принципу шифрующие структуры называются сетями Файстеля.
6. Другой используемый иногда способ получения инварианта заключается в модификации половин шифруемого блока согласован-
образом с использованием пары взаимно обратных аддитивных бинарных операций. В этом случае между раундами шифрования це­лесообразно модифицировать шифруемый блок с использованием операций другого типа, например, мультипликативных.
7. Для использования на раундах шифрования обычно требуется больше ключевой информации, чем содержится в ключе шифрования. Для выработки нужного объема ключевой информации для последую­щего ее применения в раундах используют различные схемы, от самых простых -- повторного использования одних и тех же фрагментов ключа, как в ГОСТе, до наиболее сложных - выработки ключевых эле­ментов с использованием тех же самых шифрующих преобразований, что используются при шифровании, как в шифре BLOWFISH.

 

На главную | Содержание | Назад | Вперёд
 
Яндекс.Метрика