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

• Автор: Буряков, Михаил Леонидович
• Шифр специальности: 05.13.19
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Москва
• Количество страниц: 114 с.

Оглавление
Введение

1 Общие свойства уровня аффинности

1.1 Обозначения, определения и общие сведения.

1.2 Уровень аффинности некоторых классов булевых функций .

1.3 Класс функций с максимально возможным уровнем аффинности .

1.4 Уровень аффинности булевой функции и преобразование Мбиуса .

1.5 Уровень аффинности булевой функции и спектральные коэффициенты

2 Связь с криптографическими параметрами

2.1 Уровень аффинности и нелинейность.

2.2 Уровень аффинности и корреляционная иммунность

2.3 Уровень аффинности и алгебраическая иммунность
Оглавление
2.4 Другие криптографические параметры.
3 Асимптотические оценки уровня аффинности
3.1 Нижняя асимптотическая оценка обобщнного уровня аффинности
3.2 Верхняя асимптотическая оценка частичного уровня аффинности для функций с заданной степенью .
3.3 Асимптотическое значение уровня аффинности квадратичных булевых функций
4 Алгоритмы определения уровня аффинности
4.1 Алгоритм определения уровня аффинности для булевых функций общего вида
4.2 Алгоритм определения уровня аффинности для симметрических булевых функций.
4.3 Сложность задачи определения уровня аффинности.
Заключение
Приложение 1
Анализ фильтрующей функции шифра ЫЫ8
Приложение 2
Анализ фильтрующей функции шифра БбпкБ
Оглавление
Приложение 3
Некоторые статистические оценки уровня аффинности
Список литературы


Качество криптографических методов защиты определяется криптографической стойкостью системы защиты. Основной количественной мерой стойкости является вычислительная сложность решения задачи преодоления криптографической защиты. Количественная оценка уровня защиты информации с использованием криптосистемы определяется как вычислительная сложность наиболее эффективного из известных алгоритмов вскрытия криптосистемы. Разработка алгоритмов преодоления криптографической защиты основана на использовании математических моделей, адекватно описывающих процесс функционирования системы защиты. Математическая формализация работы криптосистем в процессе криптоанализа во многих случаях приводит к задачам решения уравнений в различных алгебраических системах. Системы нелинейных булевых уравнений являются одной из распространённых моделей описания функционирования различных дискретных устройств. Необходимость изучения и решения систем булевых уравнений возникает в ряде задач теории конечных автоматов, теории кодирования и криптологии. В частности, в криптологии это направление относится к синтезу и анализу традиционных криптографических систем с секретным ключом, где системы нелинейных булевых уравнений, связывают элементы неизвестного ключа криптосистемы с известными данными. Б-боксы блоковых шифров. На этих рисунках: РСЛОС-г, г = 1,. РСЛОС — регистры сдвига с линейными обратными связями; / — комбинирующая (фильтрующая) булева функция от п переменных; 0«( у), г = 1/2,. Рис. Х2 . Рис. Задача решения произвольной системы нелинейных булевых уравнений является ТУР-трудной (см. ГДж]) и на данный момент для решения подобных систем в общем случае не известно алгоритма со сложностью, по порядку меньше, чем 2°(п где п — число неизвестных в системе. ЭТНЕАМ]). В криптоанализе разработаны различные подходы к решению нелинейных систем булевых уравнений. В ряде случаев для нахождения решения системы используются теоретико-вероятностные, статистические методы (см. Sieg, М]) и теоретико-кодовые методы (см. СЫоЬЗтОО]). В ряде случаев предлагается погружать систему уравнений в действительную область (см. БН, Нат, Рыб, РХ]) и находить её решение системы с помощью соответствующей системы псевдобулевых неравенств. Кроме того, в случае использования итераций в процессе шифрования возможна линеаризация исходной криптографической задачи (например, определения ключа) с использованием определённых степеней итерируемого отображения, являющихся аффинными отображениями (см. ФомОб, Фом]). В работах |КЛО’ШиОО, АПК4] рассматриваются алгебраические методы решения систем нелинейных булевых уравнений над конечными полями на основе базисов Грёбнера. Наиболее эффективными, как показывает практика криптоанализа, являются методы, использующие линеаризацию исходной системы. Эти методы можно условно разбить на два класса. В практике криптоанализа этот метод называют алгебраической атакой (algebraic attack). Подробную библиографию, относящуюся к этому методу, можно найти, например, в [Баев]. Второй класс объединяет методы линеаризации нелинейных систем булевых уравнений без введения новых переменных. В этом случае речь идёт о рассмотрении ограничений булевых функций (иногда этот приём называют сужением), обладающих свойствами аффинных функций. Подфункцией данной булевой функции (см. ЛСЯ]) называют ограничение этой функции на некоторое подмножество её области определения (формальное определение нужного нам понятия подфункции будет дано позднее). Тесно связано с понятием подфункции булевой функции понятие частично определённой булевой функции. Использование в криптоанализе подфункции определило интерес исследователей к изучению совместных криптографических свойств булевых функции и их подфункций (см. ССЬОЗ, DDL, CDDL, КЯщОО, КЯщ, Куз-1, Куз-2, Саг|), а также к наследованию свойств булевой функции её подфункциями (см. ЛСЯ]). Как было отмечено выше, в настоящей работе рассматриваются ограничения булевых функций, совпадающие с аффинными функциями. При этом характер области ограничения определят конкретный вид рассматри-ваехмого нами параметра.