 |
Базовые шифрующие преобразования
|
|
|
|
Алфавитом, на котором действует блочный шифр, является множество двоичных векторов-блоков открытого текста одинаковой длины (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.
· Сложение по модулю 2n (n – длина блока в битах) – (X 
Y) двоичное сложение подблоков с отбрасыванием значений старших регистров переноса.
· Умножение по модулю 2n+ 1 – (XY) двоичное умножение с отбрасыванием значений старших регистров переноса, причем нулевое значение подблока принимается равным 0 = 2n.
· Сложные операции (нелинейние подстановки, логарифмирование и экспоненцирование в конечном поле и пр.).
Сеть Файстеля.
Сеть Файстеля служит структурной основой построения большинства современных блочных криптоалгоритмов и является по сути методом смешивания текущей части шифруемого блока с результатом некоторой функции, вычисленной от другой независимой части того же блока. Эта методика получила широкое распространение, поскольку обеспечивает выполнение требования о многократном использовании ключа и материала исходного блока информации.
Действие, состоящее из однократного вычисления образующей функции и последующего наложения ее результата на другую ветвь с обменом их местами, называется циклом или раундом (англ. round) сети Файстеля. Оптимальное число раундов N – от 8 до 32. Важно то, что увеличение количества раундов значительно увеличивает криптостойстость любого блочного шифра к криптоанализу.
|
|
|
Классическая схема одного раунда сети Файстеля имеет следующую структуру:
Зашифрование:
Расшифрование:
Рис.13. Сеть Файстеля
Независимые потоки информации, порожденные из исходного блока, называются ветвями сети. В классической схеме их две. Функция f называется образующей.
Данная схема является обратимой. Сеть Файстеля обладает тем свойством, что даже если в качестве образующей функции f будет использовано необратимое преобразование, то и в этом случае вся цепочка будет восстановима. Это происходит вследствие того, что для обратного преобразования сети Файстеля не нужно вычислять функцию f -1.
Благодаря применению финального преобразования (перестановка левой и правой частей блока) сеть Файстеля симметрична. Использование операции XOR, обратимой своим же повтором, и инверсия последнего обмена ветвей делают возможным раскодирование блока той же сетью Файстеля, но с инверсным порядком применения подключей ki. Заметим, что для обратимости сети Файстеля не имеет значение является ли число раундов четным или нечетным числом. В большинстве реализаций схемы, в которых оба вышеперечисленные условия (операция XOR и уничтожение последнего обмена) сохранены, прямое и обратное преобразования производятся одной и той же процедурой.
В настоящее время чаще применяют модификацию сети Фейстеля для большего числа ветвей. Это в первую очередь связано с тем, что при больших размерах кодируемых блоков (128 и более бит) становится неудобно работать с математическими функциями по модулю 64 и выше. Как известно, основные единицы информации обрабатываемые процессорами на сегодняшний день – это байт и двойное машинное слово 32 бита. Поэтому все чаще и чаще в блочных криптоалгоритмах встречается сеть Фейштеля с 4-мя ветвями. Самый простой принцип ее модификации изображен на рисунке а). Для более быстрого перемешивания информации между ветвями (а это основная проблема сети Фейштеля с большим количеством ветвей) применяются две модифицированные схемы, называемые "type-2" и "type-3". Они изображены на рис.14.
|
|
|
Рис.14. Сеть Файстеля на четыре ветви.
|
|
|
