Классические алгоритмы шифрования

Раздел 4. СИММЕТРИЧНЫЕ КРИПТОСИСТЕМЫ

 

ОСНОВНЫЕ КЛАССЫ СИММЕТРИЧНЫХ КРИПТОСИСТЕМ

 

Все мно­го­об­ра­зие су­ще­ст­вую­щих симметричных криптографических ме­то­дов мож­но све­сти к сле­дую­щим клас­сам пре­об­ра­зо­ва­ний:

 

 

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

 

Моно- и многоалфавитные подстановки.

 

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

 

Перестановки.

 

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

 

Блочные шифры.

 

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

 

Гаммирование.

 

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

 

Каким же условиям должен удовлетворять стойкий блочный шифр? Эти условия сформулировал Шеннон в ряде своих основополагающих работ по теории шифрования: такой шифр должен обладать свойствами перемешивания и рассеивания:

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

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

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

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

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

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

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

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

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

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

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

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

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

| S | = n_v | V | = n_v ·2^{| X |}·| Y |,

где n_v - число подблоков размера |X|, в которых производятся подстановки. Как уже отмечалось выше, размер таблицы подстановок быстро увеличивается с ростом размера заменяющего и, особенно, заменяемого блока, что влечет за собой возрастание требований к необходимому для реализации шифра объему памяти. С другой стороны, увеличение этих размеров усложняет криптоанализ и, тем самым, повышает стойкость шифра, поэтому на практике их следует выбирать на границе разумности, ведь криптоалгоритм проектируется на достаточно длительный срок, а возможности электронной техники увеличиваются очень быстро. В алгоритме DES суммарный объем блоков подстановки равен | S _DES| = 8·2⁶·4 = 2¹¹ бит = 256 байт. В российском стандарте это величина того же порядка: | S _ГОСТ| = 8·2⁴·4 = 2⁹ бит = 64 байта. Следует помнить, что указанные шифры разрабатывались в семидесятые годы, когда понятие "микросхема" еще только начинало входить в наш обиход, обычная емкость микросхемы запоминающего устройства составляла несколько десятков, максимум сотен битов, а объем оперативной памяти 32Кбайта считался совсем неплохим вариантом для компьютера. Вполне естественно, что созданные в то время криптоалгоритмы отражали суровые реалии тех дней. Сейчас эта проблема практически отсутствует, и поэтому современные шифры гораздо более свободны в данном отношении. Так, в криптоалгоритме BLOWFISH подстановки производятся следующим образом: каждый из 4-х байтов, составляющих 32-битовое слово, заменяется на 4-байтовое слово, полученные слова преобразуются в одно с помощью логических и арифметических операций. Соответственно размер одной таблицы замен в этом алгоритме равен | S _BLOWFISH| = 4·2⁸·32 = 2¹⁵ бит = 4 Кбайт.

 

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

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

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

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

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

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

 

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

 

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

 

2. Объем ключевой информации должен быть относительно небольшим. Разумным является такой размер ключа, при котором невозможно его нахождение путем перебора по всему ключевому пространству, с определенным запасом на возможный прогресс электронной техники. В настоящее время граница практической осуществимости подбора ключа находится где-то в районе 60-64 бит. Соответственно, разумным может считаться размер ключа 80-256 бит. Данное требование вытекает из необходимости хранить ключи на любых носителях, включая нетрадиционные, например - на персональных миниатюрных магнитных карточках.

 

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

 

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

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

2. Замены, применяемые непосредственно к шифруемым данным, должны быть обратимыми, параметризованные замены должны быть обратимыми при каждом фиксированном значении параметра.

3. Уравнение функционального преобразования шифруемых данных с помощью бинарной операции должно быть всегда однозначно разрешимо относительно преобразуемого (первого) операнда.

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

Если прямое преобразование определяется формулой

,

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

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

Рис. 3, Шифрующее преобразование с линейной структурой и обратное ему шифрующее преобразование.

 

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

T ^-1 ~ T,

если для всех i справедливо следующее условие:

, для всех , или

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

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

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

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

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

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

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

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

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

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

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

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

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

 

Классические алгоритмы шифрования

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

На сегодня реализовано довольно много различных алгоритмов криптографической защиты информации. Среди них можно назвать алгоритмы DES, Rainbow (США); FEAL-4 и FEAL-8 (Япония); B-Crypt (Великобритания); алгоритм шифрования по ГОСТ 28147-89 (Россия) и ряд других, реализованных зарубежными и отечественными поставщиками программных и аппаратных средств защиты. Рассмотрим основные из них, наиболее широко применяемые в зарубежной и отечественной практике.