Алгебраические методы криптоанализа в учебном курсе "Основы криптоанализа"

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Алгебраические методы криптоанализа в учебном курсе «Основы криптоанализа»

Михляева А.В., Благовисная А.Н. Оренбургский государственный университет

Одной из основных задач освоения дисциплины «Основы криптоанализа» является приобретение навыков решения задач криптоанализа [1]. В учебной литературе [2-6] рассмотрены методы корреляционного, линейного и дифференциального криптоанализа, а также учебные задания, способствующие приобретению навыков раскрытия шифров данными методами.

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

Методы алгебраического анализа применяются к современным симметричным шифрам и конструкциям, их составляющим. Среди первых публикаций, посвященных алгебраическим атакам на поточные шифры и структурные элементы поточных шифров, появились статьи британского криптографа Николя Куртуа [7-9]. В работах описаны атаки на поточные шифры с фильтрующими и комбинирующими генераторами. Показан взлом аппаратно реализуемых генераторов поточных шифров Toyocrypt и LILI-128. В этих же работах описан взлом E0 - поточного шифра протокола Bluetooth. Для решения систем булевых уравнений, возникающих в процессе атак, применялись методы линеаризации.

Исследование поточного алгоритма шифрования в сотовой связи А5 можно найти в работах [10-11]. В [10] показан процесс получения системы булевых уравнений для анализа. В статье [11] представлены результаты алгебраического криптоанализа алгоритма А5/2.

Алгебраический анализ поточных шифров семейства RC4 представлен в статье [12]. Отличительной особенностью шифра RC4 от рассмотренных ранее шифров является отсутствие линейных регистров сдвига в структуре шифра. В работе показана схема составления системы алгебраических уравнений, исследованы облегченные версии шифра RC4 и систем уравнений для них. Отмечено, что для шифра RC4 решить полученные системы известными методами не представляется возможным, то есть шифр RC4 считается стойким к алгебраическим атакам.

Изучение блочных шифров на стойкость к алгебраическим атакам также проводилось исследователями. В работах Николя Куртуа и его соавторов встречаются теоретические схемы описания алгебраических атак на блочные шифры DES, AES и Serpent, а также на российский стандарт шифрования ГОСТ 28147-89. Несмотря на достаточно заметный интерес исследователей к алгебраическим атакам блочных шифров, на данный момент реализация алгебраических атак возможна лишь для упрощенных моделей существующих стандартов блочного шифрования при наличии ряда дополнительных условий, необходимых для анализа шифра.

Разнообразны и методы алгебраических атак на блочные шифры. Например, на упрощенные алгоритмы шифрования Rijndael алгебраические атаки проводились методами линеаризации и релинеаризации. Методами, использующими SAT-решатели и булевы базисы Грёбнера, предлагалось изучение стойкости к алгебраическим атакам алгоритма блочного шифрования SMS4, используемого в Китае в качестве национального стандарта для беспроводных локальных сетей. Также следует отметить появление описания атак на новый российский стандарт блочного шифрования ГОСТ Р 34.12-2015. Например, в статье [13] приведено описание алгебраического метода анализа стойкости шифров ГОСТ Р 34.12-2015 с размером блоков n=64 и n=128 бит методом релинеаризации.

Таким образом, уровень развития алгебраических методов криптоанализа шифров таков, что необходимо рассматривать вопросы алгебраического анализа криптосистем и криптографических примитивов в учебных дисциплинах. В некоторых учебных изданиях [5, 6], предназначенных для студентов вузов, встречаются разделы, посвященные криптографическим свойствам, которыми должны обладать булевы функции для обеспечения стойкости шифров к алгебраическим криптоатакам. В этих же книгах можно найти и формулировки заданий на раскрытие шифров методами алгебраического криптоанализа.

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

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

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

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

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

В качестве функции усложнения выступает булева функция следующего вида

. (1)

Рисунок 1 - Схема фильтрующего генератора

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

.

Пусть известен начальный отрезок гаммы: .

Обозначим неизвестные переменные через . Согласно данной схеме - начальное состояние регистра сдвига, которое является искомой ключевой последовательностью.

Система уравнений для поиска начального состояния генератора имеет вид:

(2)

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

 (3)

Комбинирующие генераторы строятся на основе нескольких линейных регистров сдвига. На вход подаётся последовательность, являющаяся для криптосистемы ключом. На выходе из регистра сдвига последовательность усложняется булевой функцией (рисунок 2). В качестве функции усложнения выступает булева функция вида (1).

Рисунок 2 - Схема комбинирующего генератора

Рассмотрим криптографический генератор с двумя регистрами сдвига длины 2 и 3 соответственно. В качестве функции усложнения выступает булева функция . Пусть известен начальный отрезок гаммы: . Обозначим неизвестные переменные через . Согласно данной схеме, - начальное состояние регистра сдвига, которое является искомой ключевой последовательностью.

Система уравнений для поиска начального состояния генератора имеет вид:

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

В курсе «Основы криптоанализа» рассматриваются следующие методы решения систем булевых уравнений:

- поиск решения путём полного или частичного опробования возможных значений множества переменных;

- методы линеаризации;

- метод, основанный на поиске базисов Грёбнера.

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

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

Продемонстрируем метод линеаризации для решения системы (3). Для упрощения системы нам понадобится понятие аннигилятора.

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

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

С помощью найденных аннигиляторов система (3) упростится до системы

шифр криптографический генератор линеаризация

 (4)

Решение (4) имеет вид: .

Методы решения систем нелинейных булевых уравнений, использующие базисы Грёбнера, являются обобщением метода Гаусса последовательных исключений переменных. Для системы уравнений базис Грёбнера - это набор многочленов, полученных в результате многошаговой редукции из исходных многочленов, которые задают систему.

Основные этапы решения системы на основе базисов Грёбнера:

- составление базиса Грёбнера на основе выбранного алгоритма его постоения (например, алгоритм Бухбергера) для идеала системы булевых уравнений;

- упрощение построенного базиса Грёбнера с помощью опреаций минимизации и редуцирования;

- составление и решение упростившейся системы.

Приведем результаты выполнения основных этапов решения системы (3). Первоначальный набор многочленов имеет вид:

(5)

В процессе поиска зацеплений и редукции к набору (5) добавляются ещё 6 многочленов:

(6)

Совокупность многочленов (5) и (6) представляет собой базис Грёбнера.

Упрощая, получаем следующий базис:

. (7)

Из данного набора составляем систему, решение которой имеет вид: .

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

шифр криптографический генератор линеаризация

Список литературы

1. Рабочая программа дисциплины «Б.1.В.ДВ.6.2 Основы криптоанализа» / сост. А.Н. Благовисная. - Оренбург: ОГУ, 2018.

2. Бабенко, Л.К. Современные алгоритмы блочного шифрования и методы их анализа / Л.К. Бабенко, Е.А. Ищукова. - Москва.: Гелиос АРВ, 2006. - 376 с.

3. Варлатая, С.К. Криптографические методы и средства обеспечения информационной безопасности: учебно-методический комплекс / С.К. Варлатая, М.В. Шаханова. - Москва: Проспект, 2015. - 152 с.

4. Стандарт криптографической защиты - AES. Конечные поля / Под ред. М.А. Иванова - М.: КУДИЦ-ОБРАЗ, 2002. - 176 с.

5. Панкратова, И.А. Булевы функции в криптографии: учебное пособие / И. А. Панкратова. - Томск: Издательский Дом Томского государственного университета, 2014. - 88 с.

6. Токарева, Н. Н. Симметричная криптография. Краткий курс: учебное пособие / Н. Н. Токарева. - Н: Новосибирский государственный университет, 2012. - 232 с.

7. Courtois, N. Fast algebraic attacks on stream ciphers with linear feedback / N. Courtois // Lecture Notes in Computer Science. - Springer-Verlag, 2003. - vol. 2729. - P. 176-194.

8. Courtois, N. Higher Order Correlation Attacks, XL algorithm and Cryptanalysis of Toyocrypt [Электронный ресурс] / N. Courtois. - Springer, 2002.

9. Courtois N., Algebraic Attacks on Stream Ciphers with Linear Feedback / N. Courtois, W. Meier // Eurocrypt 2003,Warsaw, Poland. - P. 345-359.

10. Vцrцs M. Algebraic attack on stream ciphers / Martin Vцrцs // Master's Thesis. - Bratislava, 2007. - 68 p.

11. Mihaita A. Some Results on Algebraic Crypt Analysis of A5/2 Algorithm / A. Mihaita // Journal of Mobile, Embedded and Distributed Systems. - 2010. - vol. II, no. 1.

12. Wong K.KH. An Analysis of the RC4 Family of Stream Ciphers against Algebraic Attack / K. KH. Wong, G. Carter, E. Dawson // Proc. 8th Australasian Information Security Conference, Brisbane, Australia, 2010. - P. 67-74.

13. Маро Е.А. Реализация алгебраической атаки на шифры ГОСТ Р 34.12-2015 / Е.А. Маро // Инженерный вестник Дона, 2015. - № 4.

Размещено на Allbest.ru