'

Разработка и исследование алгоритмов алгебраического криптоанализа

Понравилась презентация – покажи это...





Слайд 0

Разработка и исследование алгоритмов алгебраического криптоанализа Маро Е.А. Руководитель: д.т.н., профессор Бабенко Л.К. Факультет Информационной Безопасности Таганрогский Технологический Институт Южного Федерального Университета


Слайд 1

Задача алгебраического криптоанализа Алгебраические атаки используют внутреннюю структуру шифра, то есть для получения ключа шифрования необходимо представить преобразования шифрования в виде системы многомерных многочленных уравнений и впоследствии решить данную систему. Несмотря на то, что данный метод может быть применим к некоторому числу алгоритмов шифрования, в данной работе анализ алгебраический методов сфокусирован на применении их к алгоритму шифрования Rijndael, а точнее его упрощенному варианту - BabyRijndael.


Слайд 2

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


Слайд 3

Алгоритм одного раунда упрощенного варианта шифра Rijndael Размер блоков и ключей составляет 16 бит. Число раундов равно 4. Замена в S-блоках имеет вид: Столбцы раундового ключа получаем следующим образом: , где


Слайд 4

Алгоритм шифрования для упрощенной модели Rijndael


Слайд 5

Система уравнений S-блоков Уравнения, описывающие работу S-блоков, имеют вид: Максимальное число одночленов равно t=( )+2n+1 Для составления уравнений необходимо получить таблицу истинности вида:


Слайд 6

Получение системы уравнений Можно выделить три этапа: Получение уравнений для S-блоков Получение дополнительных уравнений, учитывающих алгоритм работы S-блоков Уменьшение числа переменных


Слайд 7

Разработка алгоритма получения уравнений для S-блоков Рассматриваем вариантов уравнений и отбираем уравнения, удовлетворяющие таблице истинности. Из полученных уравнений выбираем уравнения, содержащие только один квадратный элемент (то есть элемент вида xiyj, xixj или yiyj) Определяем, какие из квадратных элементов не встречаются в данных уравнениях Находим уравнение, в котором присутствует недостающий квадратный элемент Производим сложение по модулю 2 данного уравнения с другим уравнением, таким чтобы при сложении произошло обнуление уже встречавшихся квадратных элементов. Отбрасываем уравнения содержащие два и более квадратных элемента.


Слайд 8

Получение дополнительных уравнений, учитывающих алгоритм работы S-блоков Учитывая, что в S-блоках сначала находится обратный входному значению элемент и лишь потом применяется аффинное преобразование, обозначим его через h, можем получить дополнительные уравнения из выражения: или X*h(Y)=(0,0,0,1). Таким образом, путем приравнивания каждого бита с левой стороны к биту с правой стороны, получим 4 дополнительных уравнения.


Слайд 9

Алгоритм уменьшения числа переменных Исходя из схемы алгоритма шифрования BabyRijndael и алгоритма выработки ключей, возможно произвести следующие замены: Входное значение S-блока равно открытый текст XOR начальный ключ. Выходное значение S-блока равно шифротекст XOR раундовый ключ. Второй столбец раундового ключа представляет собой сумму по модулю 2 второго столбца начального ключа и первого столбца раундового ключа.


Слайд 10

XL атака XL (eXtended Linearization) метод предложили Николя Куртуа, Александр Климов и Ади Шамир в 2000 году. Обозначим через D параметр алгоритма XL, причем , где n- число переменных, а m- количество уравнений. Данный алгоритм базируется на перемножении каждого возможного уравнения 1…m на все возможные значения переменных в степени D-2.


Слайд 11

Алгоритм реализации XL метода Multiply: составление всех произведений вида , где k?D-2; Linearize: рассмотрение каждого одночлена хi в степени ? D как новой переменной и применение Гауссовского исключения к уравнениям, полученным в пункте 1. Solve: повторение пункта 2 до тех пор, пока в результате не будет получено по крайней мере одно уравнение с единственной переменной. Repeat: упростить уравнения и повторить процесс для нахождения значений других переменных.


Слайд 12

XSL атака В 2002 году вместо техники XL был создан алгоритм, использующий преимущества особой структуры уравнений и их разреженность. Эта атака была названа XSL-атака, что расшифровывается как «eXtended Sparse Linearization» или «multiply(X) by Selected monomials and Linearize». Алгоритм XSL предложен для работы только со специальными типами шифров, для который выполняются условия: S-блоки должны быть такими, чтобы их можно было описать с помощью сверхопределенной системы квадратных уравнений. Алгоритм получения ключей должен иметь схожую структуру с алгоритмом зашифрования.


Слайд 13

Алгоритм реализации XSL метода Обработка имеющейся системы уравнений путем выбора конкретного набора одночленов и уравнений, которые будут использоваться в дальнейших этапах алгоритма Выбор значения параметра Р и умножение выбранных на предыдущем этапе уравнений на результаты произведений (Р-1) выбранных одночленов При недостаточном числе уравнений применение Т’ метода, в котором некоторые выбранные уравнения умножаются на одиночные переменные. Цель данного метода – создание новых уравнений без получения каких-либо новых одночленов. Применение линеаризации, путем представления каждого одночлена в виде новой переменной и выполнения Гауссовского исключения.


Слайд 14

Оценка сложности атаки для алгоритма шифрования BabyRijndael Для метода XL сложность Гауссовского преобразования составляет: , где n - число переменных, m - количество уравнений, ??3 - показатель Гауссовского преобразования. Для XSL атаки сложность составляет , где t – число одночленов, P – параметр алгоритма XSL атаки, S - число S-блоков, ? - показатель Гауссовского преобразования.


Слайд 15

Заключение В данной работе были рассмотрены основные алгебраические методы криптоанализа, а именно XL (eXtended Linearization) и XSL (eXtended Sparse Linearization) атаки, рассчитана сложность их реализации для алгоритма шифрования BabyRijndael. Также был разработан алгоритм получения системы уравнений, описывающей процесс шифрования. В заключении можно отметить, что для алгоритма шифрования BabyRijndael система будет содержать 792 уравнения с 96 переменными. Число различных одночленов, встречающихся в данных уравнениях, составляет 2332. На практике последующее применение к данной системе алгебраических методов криптоанализа приводит к получению ключа шифрования.


×

HTML:





Ссылка: