Глава 5. Принципы построения блочных шифров на примере алгоритма des

5.1. Криптосхема алгоритма des

В 1972 году Национальным бюро стандартов США (ныне подразделение Департамента торговли США NIST – National Institute of Standards and Technology), с учетом возрастающих потребностей обеспечения безопасности информации, была разработана программа защиты данных.

В качестве составной части программа предусматривала создание единого алгоритма для безопасной передачи и хранения информации.

Унификация алгоритма имела целью экономию затрат на создание надежных систем защиты. Окончательная версия алгоритма DES была принята в ноябре 1976 года

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

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

– высокий уровень безопасности;

– наличие полной спецификации алгоритма и простота понимания;

– безопасность алгоритма должна базироваться на секретности ключа;

– широкая доступность алгоритма;

– простота адаптации алгоритма для использования в различных прило-жениях;

– экономичность в реализации алгоритма;

– эффективность алгоритма;

– возможность верификации алгоритма;

– отсутствие экспортных ограничений.

Алгоритм DES [1,11] относится к классу блочных шифров, для которых исходные данные и результаты шифрования представляются в виде 64-битовых строк - блоков.

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

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

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

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

Перед шифрованием исходный 64-битный ключ сужается до 56 битов (убираются биты четности) и разбивается на два подблока по 28 битов каждый.

После начальной перестановки (initial permutation –), блок исходных данных разбивается на левую, и правуюполовины (полублоки) по 32 бита каждая.

Затем происходит 16 раундов идентичных операций, входом и выходом которых якляются пары полублоков ,.

На каждой итерации полублоки комбинируются с ключом соответствующего раунда (нумерация ключей, принятая в стандарте Fips 46 для раундов и ключей, начинается с единицы, а полублоков – с нуля).

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

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

Рис. 5.1. Общая схема алгоритма DES

Для получения очередного раундового ключа половины предыдущего ключа независимо друг от друга циклически сдвигаются. Величина и направление сдвига для каждого раунда фиксированы (заданы в описании криптоалгоритма).

Затем сдвинутые полублоки объединяются в 56-битовую последовательность, из которой выбираются 48 битов с помощью постоянной перестановки сжатия (compression permutation или permuted choice).

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

Полученные 28 битов заменяются на блок из 32 битов с помощью восьми -блоков (таблиц замены, преобразующих 6 битов в четыре).

Полученные 32 бита переставляются по фиксированной подстановке, в результате чего получается правый полублок новой пары полублоков.

В качестве принимается блок. Таким образом, преобразование полублоков имеет вид,.

Рис. 5.2. Схема преобразований одного раунда

Отметим особую роль расширяющей перестановки (expansion permutation), с применением которой правый полублокрасширяется с 32 до 48 битов одновременно с их перестановкой (рис. 5.3).

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

32,	1,	2,	3,	4,	5,	4,	5,	6,	7,	8,	9,
8,	9,	10,	11,	12,	13,	12,	13,	14,	15,	16,	17,
16,	17,	18,	19,	20,	21,	20,	21,	22,	23,	24,	25,
24,	25,	26,	27,	28,	29,	28,	29,	30,	31,	32,	1

Рис. 5.3. Расширяющая перестановка

Не менее важная роль в алгоритме отведена восьми -блокам (-box substitution), на вход которых подается 48-битов результата сложения раундового ключа и расширенного полублока текста (рис. 5.4), а на выходе получается 32-х битовая строка.

Каждая подстановка представлена таблицей из 4 строк и 16 колонок. Блок в 48 бит делится на шестибитовые комбинации так, что первая комбинация заменяется по 1-ой подстановке, и т.д., восьмая комбинация – по 8-ой подстановке.

В каждой комбинации двухбитовое число обозначает строку таблицы замены (от 0 до 3). Аналогично, оставшиеся четыре бита определяют номер столбца. По строке и столбцу находится тетрада битов, которая заменяет исходную комбинацию, в итоге получим восемь тетрад, объединенных в 32-битовый блок.-блоки (узлы замены) обеспечивают нелинейность и стойкость преобразования (другие операции – линейны и легко поддаются криптоанализу).

Рис. 5.4. Схема реализации замен (S-блоков)

Результат применения подстановок вновь перемешивается (переставляется) с помощью постоянной перестановки . Операции, начиная си заканчивая, образуют раундовую (цикловую) функцию(см. рис. 5.1, 5.2).

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

Первоначально, когда были неизвестны принципы формирования узлов замены, Агентство Национальной Безопасности США обвиняли во встраивании скрытых лазеек в их алгоритм.

В последующем, на 2-м семинаре, посвященном DES, АНБ раскрыло несколько критериев построения блоков замены.

1. Ни один -блок не является линейной (аффинной) функцией входных данных, т.е. не существует системы линейных уравнений, которыми можно выразить 4 выходных бита в терминах 6 входных.

2. Изменение одного бита на входе изменяет, как минимум, два бита на выходе, следовательно, достигается максимизация диффузии.

3. S-блоки должны минимизировать разницу между числом нулей и единиц.

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