Методы шифрования информации

Все действия, производимые над данными блочным криптоалгоритмом, основаны на том факте, что преобразуемый  блок может быть представлен в  виде целого неотрицательного числа  из диапазона, соответствующего его разрядности. Так, например, 32-битный блок данных можно интерпретировать как число из диапазона 0..4'294'967'295. Кроме того, блок, разрядность которого обычно является "степенью двойки", можно трактовать как несколько независимых неотрицательных чисел из меньшего диапазона (рассмотренный выше 32-битный блок можно также представить в виде 2 независимых чисел из диапазона 0..65535 или в виде 4 независимых чисел из диапазона 0..255).

Над этими числами  блочным криптоалгоритмом и производятся по определенной схеме следующие действия (см. таблицу 2.1. слева даны условные обозначения этих операций на графических схемах алгоритмов) :

 

Биективные математические функции
	Сложение	X'=X+V
	Исключающее ИЛИ	X'=X XOR V
	Умножение по модулю 2N+1	X'=(X*V) mod (2N+1)
	Умножение по модулю 2N	X'=(X*V) mod (2N)
Битовые сдвиги
	Арифметический сдвиг  влево	X'=X SHL V
	Арифметический сдвиг  вправо	X'=X SHR V
	Циклический сдвиг влево	X'=X ROL V
	Циклический сдвиг вправо	X'=X ROR V
Табличные подстановки
	S-box (англ. substitute)	X'=Table[X,V]

 

Таблица 2.1. Схема блочного криптоалгоритма

 

В качестве параметра V для  любого из этих преобразований может  использоваться:

• фиксированное число (например, X'=X+125);
• число, получаемое из ключа (например, X'=X+F(Key));
• число, получаемое из независимой части блока (например, X₂'=X₂+F(X₁)) .

Последний вариант используется в схеме, названной по имени ее создателя сетью Фейштеля (нем. Feistel).

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

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

Поскольку операция зашифровки или расшифровки отдельного блока  в процессе кодирования пакета информации выполняется многократно (иногда до сотен тысяч раз), а значение ключа  и, следовательно, функций V_i(Key) остается неизменным, то иногда становится целесообразно заранее однократно вычислить данные значения и хранить их в оперативной памяти совместно с ключом. Поскольку эти значения зависят только от ключа, то они в криптографии называются материалом ключа. Необходимо отметить, что данная операция никак не изменяет ни длину ключа, ни криптостойкость алгоритма в целом. Здесь происходит лишь оптимизация скорости вычислений путем кеширования (англ. caching) промежуточных результатов. Описанные действия встречаются практически во многих блочных криптоалгоритмах и носят название расширение ключа (англ. key scheduling)[]7,33].

Сеть Фейштеля

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

Независимые потоки информации, порожденные из исходного блока, называются ветвями сети. В классической схеме их две. Величины V_i именуются параметрами сети, обычно это функции от материала ключа. Функция F называется образующей. Действие, состоящее из однократного вычисления образующей функции и последующего наложения ее результата на другую ветвь с обменом их местами, называется циклом или раундом (англ. round) сети Фейштеля. Оптимальное число раундов K – от 8 до 32. Важно то, что увеличение количества раундов значительно увеличивает криптоскойстость любого блочного шифра к криптоанализу. Возможно, эта особенность и повлияла на столь активное распространение сети Фейштеля – ведь при обнаружении, скажем, какого-либо слабого места в алгоритме, почти всегда достаточно увеличить количество раундов на 4-8, не переписывая сам алгоритм. Часто количество раундов не фиксируется разработчиками алгоритма, а лишь указываются разумные пределы (обязательно нижний, и не всегда – верхний) этого параметра.

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

 
Рис.2.3. Сеть Фейштеля

Более того, как нетрудно заметить, сеть Фейштеля симметрична. Использование операции XOR, обратимой  своим же повтором, и инверсия последнего обмена ветвей делают возможным раскодирование блока той же сетью Фейштеля, но с инверсным порядком параметров V_i. Заметим, что для обратимости сети Фейштеля не имеет значение является ли число раундов четным или нечетным числом. В большинстве реализаций схемы, в которых оба вышеперечисленные

 

 

 

 

 

 

 

 

 

 

Рисунок 2.4. Модификация  сети Фейштеля.

 

условия (операция XOR и  уничтожение последнего обмена) сохранены, прямое и обратное преобразования производятся одной и той же процедурой, которой в качестве параметра передается вектор величин V_i либо в исходном, либо в инверсном порядке.

С незначительными доработками  сеть Фейштеля можно сделать и  абсолютно симметричной, то есть выполняющей  функции шифрования и дешифрования одним и тем же набором операций. Математическим языком это записывается как "Функция EnCrypt тождественно равна функции DeCrypt". Если мы рассмотрим граф состояний криптоалгоритма, на котором точками отмечены блоки входной и выходной информации, то при каком-то фиксированном ключе для классической сети Фейштеля мы будем иметь картину, изображенную на рис.2.4а, а во втором случае каждая пара точек получит уникальную связь, как изображено на рис. 2.4б. Модификация сети Фейштеля, обладающая подобными свойствами приведена на рисунке 2.4. Как видим, основная ее хитрость в повторном использовании данных ключа в обратном порядке во второй половине цикла. Необходимо заметить, однако, что именно из-за этой недостаточно исследованной специфики такой схемы (то есть потенциальной возможности ослабления зашифрованного текста обратными преобразованиями) ее используют в криптоалгоритмах с большой осторожностью.

Модификацию сети Фейштеля для большего числа ветвей применяют  гораздо чаще. Это в первую очередь  связано с тем, что при больших  размерах кодируемых блоков (128 и более бит) становится неудобно работать с математическими функциями по модулю 64 и выше. Как известно, основные единицы информации обрабатываемые процессорами на сегодняшний день – это байт и двойное машинное слово 32 бита. Поэтому все чаще и чаще в блочных криптоалгоритмах встречается сеть Фейштеля с 4-мя ветвями. Самый простой принцип ее модификации изображен на рисунке 2.5а. Для более быстрого перемешивания информации между ветвями (а это основная проблема сети Фейштеля с большим количеством ветвей) применяются две модифицированные схемы, называемые "type-2" и "type-3". Они изображены на рисунках 2.5б и 2.5в.

 
Рис.2.5. модифицированные схемы, называемые "type-2" и "type-3

 

Сеть Фейштеля надежно  зарекомендовала себя как криптостойкая  схема произведения преобразований, и ее можно найти практически  в любом современном блочном  шифре. Незначительные модификации  касаются обычно дополнительных начальных и оконечных преобразований (англоязычный термин – whitening) над шифруемым блоком. Подобные преобразования, выполняемые обычно также либо "исключающим ИЛИ" или сложением имеют целью повысить начальную рандомизацию входного текста. Таким образом, криптостойкость блочного шифра, использующего сеть Фейштеля, определяется на 95% функцией F и правилом вычисления V_i из ключа. Эти функции и являются объектом все новых и новых исследований специалистов в области криптографии.

Блочный шифр TEA

Рассмотрим один из самых простых в реализации, но признанно стойких криптоалгоритмов – TEA (Tiny Encryption Algorithm).

Параметры алгоритма :

Размер блока – 64 бита.

Длина ключа – 128 бит.

В алгоритме использована сеть Фейштеля с двумя ветвями  в 32 бита каждая. 
Образующая функция F обратима.

Сеть Фейштеля несимметрична  из-за использования в качестве операции наложения не исключающего "ИЛИ", а арифметического сложения².

Отличительной чертой криптоалгоритма TEA является его размер. Простота операций, отсутствие табличных подстановок и оптимизация под 32-разрядную архитектуру процессоров позволяет реализовать его на языке ASSEMBLER в предельно малом объеме кода. Недостатком алгоритма является некоторая медлительность, вызванная необходимостью повторять цикл Фейштеля 32 раза (это необходимо для тщательного "перемешивания данных" из-за отсутствия табличных подстановок).

 

 

AES -RC6 : cтандарт блочных шифров США c 2000 года

Алгоритм является продолжением криптоалгоритма RC5, разработанного Рональдом  Ривестом (англ. Ron Rivest) – очень известной личностью в мире криптографии. RC5 был незначительно изменен для того, чтобы соответствовать требованиям AES по длине ключа и размеру блока. При этом алгоритм стал еще быстрее, а его ядро, унаследованное от RC5.

Преобразование T(x) очень просто : T(X)=(X*(X+1)) mod 2^N. Оно используется в качестве нелинейного преобразования с хорошими показателями перемешивания битового значения входной величины.

Шифр Rijndael

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

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

Алгоритм состоит из некоторого количества раундов (от 10 до 14 – это зависит от размера  блока и длины ключа), в которых  последовательно выполняются следующие  операции:

ByteSub – табличная подстановка  8х8 бит (рис.2.6),

 
Рис.2.6. ByteSub

ShiftRow – сдвиг строк  в двумерном массиве на различные  смещения (рис.2),

 
Рис.2.7. ShiftRow

MixColumn – математическое  преобразование, перемешивающее данные  внутри столбца (рис.7),

 
Рис.2.8. MixColumn

AddRoundKey – добавление  материала ключа операцией XOR (рис.8).

 
Рис.2.9. AddRoundKey

В последнем раунде операция перемешивания столбцов отсутствует, что делает всю последовательность операций симметричной.

2.3. Блочный шифр DES

 

Процесс шифрования

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

Длина ключа равна 56 битам. Ключ обычно представляется 64 - битовым числом, но каждый восьмой бит используется для проверки чётности и игнорируется. Биты чётности являются наименьшими значащими битами байтов ключа. Ключ, который может быть любым 56 - битовым числом, можно изменить в любой момент времени. Ряд чисел считаются слабыми ключами, но их можно легко избежать. Безопасность полностью определяется ключом.

На простейшем уровне алгоритм не представляет ничего большего, чем комбинация двух основных методов  шифрования: смещения и диффузии. Фундаментальным строительным блоком DES является применение к тексту единичной комбинации этих методов(подстановка, а за ней перестановка), зависящей от ключа. Такой блок называется этапом. DES состоит из 16 этапов, одинаковая комбинация методов применяется к открытому тексту 16 раз.

Процесс шифрования данных поясняется рисунком 1. Сначала 64 бита входной последовательности перестанавливаются в соответствии с таблицей 1. Таким образом, бит 58 входной последовательности становится битом 1, бит 50 – 2 и т.д.