Основные принципы построения блочных шифров - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1страница 2
Похожие работы
Название работы Кол-во страниц Размер
Лабораторная работа №5 Режимы работы блочных шифров. Схемы кратного... 1 157.97kb.
«Композиции шифров» 3 856.93kb.
Изучить блочные алгоритмы шифрования: алгоритм перестановки, алгоритм... 1 82.65kb.
1. Джон фон Нейман включил в основные принципы построения циф­ровой... 1 20.01kb.
Программа экзамена по рпкс. Весна 2011 1 16.85kb.
Принципы коррекционного обучения 2 442.4kb.
Принципы построения бизнес-процессов на промышленном предприятии 1 38.84kb.
Принципы построения и основы конструирования приборов индивидуальной... 3 707.87kb.
Должностная инструкция системного программиста 1 45.24kb.
Вопросы для подготовки к экзамену по дисциплине "Организация, принципы... 1 21.94kb.
Исследование инвариантов нелинейной динамики речи и принципы построения... 1 293.65kb.
Сидоров 1000 Петров 3000 Сидоров 5000 Петров 1500 Чижиков 1500 Петров... 1 75.11kb.
Викторина для любознательных: «Занимательная биология» 1 9.92kb.

Основные принципы построения блочных шифров - страница №1/2

Основные принципы построения блочных шифров

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



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

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

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

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

Шифры перестановок чрезвычайно просто реализуются аппаратно - разводкой проводников на плате или в кристалле, при этом совсем не требуется каких-либо дополнительных затрат, так как проводники, связывающие регистры аппаратуры, так или иначе присутствуют в схеме. В то же самое время эти преобразования очень неэффективно реализуются программно на процессорах общего назначения. Как правило, вычислительные затраты составляют не менее двух машинных команд на каждый двоичный разряд в модифицируемом блоке, если только в перестановках нет согласованности. Этой причиной, в частности, объясняется тот факт, что многие шифры, широко использующие операции данного типа, имеют при прочих равных условиях существенно менее эффективные реализации по сравнению с шифрами, их не использующими. Например, американский стандарт шифрования криптоалгоритм 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|.

По указанной причине на практике не так часто встречаются шифры Файстеля, в которых шифрующая часть блока меньше шифруемой по размеру |следующая страница >>