Базовые шифрующие преобразования

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

Требования к базовым преобразованиям :

· возможность простой реализации (как аппаратной, так и программной);

· способность давать при небольшом числе итераций аналитически сложные преобразования;

· соответствие критериям рассеивания и перемешивания;

· соотвествие критерию лавинного эффекта.

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

Принцип перемешивания (diffusion)- криптографические преобразования должны обеспечивать максимальное усложнение статистической и аналитической взаимосвязи между открытым текстом и шифртектсом.

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

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

Рассеивающие преобразования – простые преобразования, переставляющие между собой части блоков текста.

Применяемые математические преобразования (операции):

· Перестановки –смена местами битовых значений разрядов подблоков на основе фиксированных подстановок.

· Битовые сдвиги – (X >>Y) сдвиг вправо и (X<<Y) сдвиг влево битовых значений разрядов подблока X (соответствует умножению на 2 и целочисленному делению на 2 ) на величину, определяемую значением подблока Y.

· Циклические битовые сдвиги – (X>>>Y) циклический сдвиг вправо и (X<<<Y) циклический сдвиг влево битовых значений разрядов подблока X (ключа, шифртекста) на величину, определяемую значением подблока Y.

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

· Побитовая инверсия – (~X) инверсия всех битовых регистров блока X.

· Побитовое сложение по модулю 2 – (XÅY) операция XOR над всеми битовыми регистрами подблоков X и Y.

· Сложение по модулю 2ⁿ (n – длина блока в битах) – (X Y) двоичное сложение подблоков с отбрасыванием значений старших регистров переноса.

· Умножение по модулю 2^{n+ 1} – (XY) двоичное умножение с отбрасыванием значений старших регистров переноса, причем нулевое значение подблока принимается равным 0 = 2ⁿ.

· Сложные операции (нелинейние подстановки , логарифмирование и экспоненцирование в конечном поле и пр.).

Сеть Файстеля.

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

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

Классическая схема одного раунда сети Файстеля имеет следующую структуру:

Зашифрование:

Расшифрование:

Рис.13. Сеть Файстеля

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

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

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

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

Рис.14. Сеть Файстеля на четыре ветви.