ПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА. ПРИЛОЖЕНИЕ

Исследуются системы некоммутативных символьных линейных однородных уравнений, которые интерпретируются как линейные грамматики формальных языков. Такие системы решаются в виде формальных степенных рядов (ФСР), выражающих нетерминальные символы через терминальные символы алфавита и рассматриваемых как линейные языки. Всякому ФСР поставлен в соответствие его коммутативный образ, который получается в предположении, что все символы обозначают коммутативные переменные, действительные или комплексные. Рассматриваются системы уравнений, которые могут иметь бесконечное множество решений, параметризуемых не произвольными числами, а произвольными ФСР. Оценено количество таких параметров, что даёт некоммутативный аналог известного факта теории линейных уравнений.

С использованием матрично-графового подхода исследуются перемешивающие свойства регистровых преобразований поточных алгоритмов шифрования ТЕА1 и ТЕА2 стандарта цифровой транкинговой радиосвязи ТЕТRА. Получены значения экспонентов перемешивающих матриц, соответствующих регистровым преобразованиям исследуемых алгоритмов. Результаты могут быть использованы для оценки числа тактов работы регистров преобразования ключа в алгоритмах поточного шифрования, необходимых для обеспечения существенной зависимости каждого бита выходной последовательности от всех битов ключа.

Работа посвящена анализу параметров постквантовых схем подписи на основе хешей без сохранения состояния (SPHINCS+, SPHINCS+C и Гиперикум). Предлагаются новые наборы параметров, обеспечивающие 120-битную стойкость к подделке против квантового злоумышленника. Выбор наборов осуществлялся с учётом прикладных характеристик и возможных областей применения рассматриваемых схем.

Работа посвящена истории развития Международной олимпиады по криптографии Non-Stop University CRYPTO, её открытым проблемам и результатам.

Анализируется класс XSL-алгоритмов блочного шифрования с алгоритмом развертывания ключа на основе рекуррентного соотношения второго порядка и матрицей линейного преобразования, у которой существуют хотя бы два равных элемента в некоторой строке обратной матрицы. Предложена атака на 6-раундовый XSL-алгоритм блочного шифрования на основе комбинирования методов встречи посередине, невозможных разностей, а также модификации подхода «уоуо». Сначала на основе обобщения метода встречи посередине формируется множество кандидатов в раундовые ключи первого раунда. Далее для получения множества кандидатов в раундовые ключи шестого раунда строится различитель, основанный на комбинации невозможных разностей и соотношений из модифицированного подхода «уоуо». Вероятность успеха равна 0,7. Полученные результаты подтверждены на модельном XSL-алгоритме блочного шифрования с 16-битным блоком открытого текста.

КБ-256 - алгоритм блочного шифрования, рекомендованный для защиты больших объёмов данных. Рассматриваются вопросы криптографической стойкости КБ-256 в модели атакующего, имеющего доступ к квантовому компьютеру. Оценивается трудоёмкости применения алгоритма Гровера - сложности квантовой схемы, в которой необходимо реализовать оракул алгоритма КБ-256, а также количество необходимого материала. Помимо этого, рассматривается возможность атаки с помощью алгоритмов поиска скрытого сдвига.

Работа является обзорной, она посвящена алгоритмам аутентифицированного шифрования с присоединёнными данными, а также функционально аналогичным режимам работы алгоритмов блочного симметричного шифрования. Рассмотрены стандартизованные режимы работы Galois/Counter Mode и Multilinear Galois Mode, a также алгоритмы шифрования, изначально разработанные для реализации подобных преобразований, на примере алгоритма Ascon. Показана оптимальность аутентифицированного шифрования с присоединёнными данными для использования в низкоресурсных устройствах на примере радиочастотных меток, взаимодействующих со считывателем по радиоканалу. Обозначены некоторые из возможных критериев выбора конкретного алгоритма и/или режима работы для реализации на целевой низкоресурсной платформе.

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

В 2022 г. в Российской Федерации приняты рекомендации по стандартизации, определяющие режим работы блочных шифров DEC, используемый для защиты носителей информации с блочно-ориентированной структурой. Данный режим представляет собой модификацию режима гаммирования со специальным алгоритмом выработки синхропосылки и начальным значением счётчика из номера раздела и номера сектора носителя информации. В работе представлена модель доказуемой (редукционистской) стойкости, формализующая обеспечение конфиденциальности в условиях наличия у нарушителя доступа к квантовому оракулу. В рамках данной модели предложена атака различения на режим DEC, требующая единственный запрос к оракулу. Атака основана на возможности перехода к незапутанному состоянию регистров открытого и шифрованного текстов в случае зашифрования непосредственно открытого текста, переданного нарушителем, и невозможности такого перехода при зашифровании результата применения случайной подстановки к открытому тексту.

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

Основным компонентом криптографической хеш-функции MD4 является 48-шаговая функция сжатия. В 2007 г. прообраз 39-шаговой функции сжатия MD4 был найден с помощью CDCL - основного полного алгоритма решения проблемы булевой выполнимости (SAT). В 2022г. с помощью параллельного SAT-алгоритма Cube-and-Conquer был найден прообраз 43-шаговой функции сжатия MD4. В настоящей работе исследуется 44-шаговая версия функции сжатия MD4, такая, что 44-й шаг ослаблен разными способами. С помощью Cube-and-Conquer найдены прообразы нескольких таких функций. На основе решённых задач предложена оценка времени, необходимого для нахождения прообраза 44-шаговой функции сжатия MD4.

Введён класс разностно-линейных атак различения на блочные шифры. Построена атака (названная разностно-сингулярной), оптимальная в данном классе. Проведены вероятностно-статистические эксперименты с шифрсистемами семейства SmallPresent с длинами блока n ∈ {8,12,16} и R ∈ {3,…, 9} раундами.