Криптографические свойства блочных шифров регистрового типа, построенных на основе обобщения раундовой функции Фейстеля Исполнитель: студентка гр. Б10-04 Коренева А.М. Научный руководитель: д.ф.-м.н., проф. Фомичев В.М. Москва 2012 г.

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

Используемые обозначения и сокращения СБШ – симметричный блочный шифр; МСЗ – матрица существенной зависимости; Г( ) – перемешивающий орграф раундовой подстановки алгоритма шифрования; n – длина регистра сдвига; r – длина двоичного слова в ячейке регистра сдвига. 3

Основные этапы работы Систематизация результатов по применению теоретико-графового подхода к исследованию перемешивающих свойств композиций преобразований Исследование перемешивающих свойств раундовой подстановки с использованием теоретико-графового подхода Построение критерия инволютивности СБШ регистрового типа и исследование криптографических свойств таких СБШ 4

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

Преимущества шифров Фейстеля Высокая производительность шифрования Простота программной и аппаратной реализации Обеспечение инволютивности алгоритма шифрования Широта применения: DES, ГОСТ , Lucifer, IDEA, TEA, LOKI, Kasumi, Khufu, Skipjack, Blowfish и других 6

7 Итеративные СБШ регистрового типа Рисунок 1 – Схема функционирования СБШ Преимущества: Возможность увеличить размер входного блока данных без существенного усложнения реализации функций => увеличение производительности шифрования Больший выбор комбинаций базовых элементов для построения раундовой функции Сохранение хороших перемешивающих свойств за счет ключевого расписания

8 Инволютивность алгоритма шифрования Подстановка f является инволюцией, если f(f(x))=x, для любого х. Построен критерий инволютивности h-раундовых шифров, h>1, основанных на регистрах сдвига длины n, с функцией усложнения ψ(y 2,…,y n,z), инвариантной относительно инволюции степени n-1.

Необходимые условия полного перемешивания раундовой подстановки 9 1. Сильная связность орграфа Г( ): Теорема. Перемешивающий граф Г( ) сильно связен тогда и только тогда, когда сильно связен граф Г. 2. Наличие в Г( ) простых циклов длины l 1,…,l k, где k>1 и НОД(l 1,…,l k )=1: Теорема. Граф Г( ) примитивен, если координатная функция m зависит существенно от переменной x m при некотором m {(n-1)r+1,(n-1)r+2,…,nr} Степень преобразования, при которой достигается полное перемешивание, оценивается экспонентом орграфа Г( ): expГ( )2nr-2

10 Пример раундовой подстановки на основе регистра длины 4

11 Слои функции усложнения Слой расширения 16-битового вектора x i (j) до 24-битового вектора E(x i (j)):V 16 V 24 Слой подмешивания M(E(x i (j)),z) 48-битового циклового ключа z путем XOR-суммирования. Цикловой ключ z разбивается на две части по 24 бита: z=(z 1,z 2 ), где: M(E(x i (j)),z)={E(x 2 (j)) z 1, E(x 3 (j)) z 2, E(x 4 (j)) z 1 } Слой нелинейной замены S(M(E(x i (j)),z)) 24-битового вектора на 16- битовый вектор с помощью s-блоков: S 1 (E(x 2 (j)) z 1 ), S 2 (E(x 3 (j)) z 2 ), S 3 (E(x 4 (j)) z 1 ) Слой перемешивания координат 16-битового вектора с помощью перестановки T 5 – циклического левого сдвига на 5: T 5 (a 1,a 2,…,a 16 )=(a 6,…,a 16,a 1 …,a 5 ), где a l – один бит вектора.

12 Алгоритм получения оценки наименьшего числа раундов шифрования

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

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