|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Математические методы криптографии
Поиск линеаризующих множеств в алгебраическом криптоанализе как задача псевдобулевой оптимизации
А. А. Семёновa, К. В. Антоновb, И. В. Отпущенниковa a Институт динамики систем и теории управления имени В.М. Матросова Сибирского отделения Российской академии наук, г. Иркутск
b Институт математики, экономики и информатики Иркутского государственного университета
Аннотация:
Вводится понятие линеаризующего множества, которое можно рассматривать как обобщение известного понятия линеаризационного множества. Линеаризующие множества используются в основе алгебраических атак, относящихся к классу «угадывай и определяй» (guess-and-determine). В таких атаках угадываются значения переменных из некоторого множества, затем эти значения подставляются в систему алгебраических уравнений, которая связывает входные и выходные данные рассматриваемого шифра. В некоторых случаях результатом такой подстановки является линейная система, которая решается эффективно. Рассматриваются алгебраические уравнения над полем GF(2). Значения переменных из линеаризующего множества (в отличие от линеаризационного) линеаризуют систему уравнений с некоторой вероятностью, которая, вообще говоря, может быть существенно меньше 1. Оценка трудоёмкости атаки на основе конкретного линеаризующего множества строится через специально определяемую псевдобулеву функцию. Минимальное значение этой функции даёт оценку трудоёмкости лучшей по эффективности атаки. Для минимизации таких функций используется метаэвристический алгоритм из класса «поиск с запретами». На данном этапе построены атаки описанного типа для ряда криптографических генераторов. В частности, для известного генератора A5/1 построена атака с оценкой трудоёмкости в 4,5 раз ниже трудоёмкости известной атаки Андерсона.
Ключевые слова:
атаки из класса «угадывай и определяй», линеаризующие множества, псевдобулева оптимизация.
Образец цитирования:
А. А. Семёнов, К. В. Антонов, И. В. Отпущенников, “Поиск линеаризующих множеств в алгебраическом криптоанализе как задача псевдобулевой оптимизации”, ПДМ. Приложение, 2019, № 12, 130–134
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdma453 https://www.mathnet.ru/rus/pdma/y2019/i12/p130
|
Статистика просмотров: |
Страница аннотации: | 158 | PDF полного текста: | 51 | Список литературы: | 7 |
|