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

Вычисляется восьмая степень матрицы переходных вероятностей схемы Луби - Ракофф, даются оценки объёма материала j-векторных (j = 1, 2) разностно-спектральных атак различения на 8 раундов схемы Луби - Ракофф в модели независимых двублочных текстов.

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

Исследуются схемы для обработки сигнала, получаемого с кольцевых осцилляторов; преобразованные последовательности тестируются на свойства случайности. Предложено пять вариантов преобразования выходного сигнала. В качестве инструментов преобразования использованы комбинации метода фон Неймана и Математические методы криптографии 71 операции XOR. Тестирование полученных последовательностей выполнено с помощью пакета тестов NIST STS. Последовательность, полученная после преобразования №5, показала наилучший результат по итогам тестирования и была сравнена с последовательностью, зашифрованной алгоритмом AES в режиме счётчика. Сравнение показало, что количество успешно пройденных тестов преобразованной последовательности выше, чем у последовательности, зашифрованной алгоритмом AES.

Приводятся результаты анализа схемы VKO и комбинированной схемы VKO+подпись в моделях обобщённой группы и биективного случайного оракула. Получена верхняя оценка сложности задачи различения выхода схемы VKO от случайной равновероятной строки (в эвристике обобщенной группы), а также показано, что возможности получения подписи сообщений по алгоритму genGOST не даёт никакой дополнительной информации противнику в этой задаче (в эвристике биективного случайного оракула).

Вводится новый класс атак, применимых к низкоресурсным функциям симметричной криптографии. Основная идея атак основана на использовании специальных функций, получаемых из оригинальных за счёт рассмотрения малого числа выходных бит. Задачи обращения специальных функций существенно более просты для используемых в алгебраическом криптоанализе комбинаторных алгоритмов (SAT-решателей), чем задачи обращения функций, из которых они строятся. Однако для специальной функции, ввиду того, что её выход существенно короче входа, задача обращения имеет не единственное решение. Для достижения единственности по ключу описывается процедура клонирования функции, в рамках которой специальные функции строятся для одного ключа и нескольких различных фрагментов открытых данных. Операция клонирования специальных функций выполняется на And-Inverter-графах (AIG), представляющих данные функции. Во многих случаях размер AIG может быть существенно уменьшен за счёт применения алгоритмов AIG-минимизации. Результатом совместного использования перечисленных техник являются алгебраические атаки, которые для ряда поточных шифров могут бытв существенно более эффективными в сравнении с аналогичными атаками на функции, представляющие рассматриваемые шифры стандартным образом.

Описываются атаки на протоколы аутентифицированной выработки общего ключа SIGMA, SIG-DH и TS3-1 при наличии у нарушителя возможности навязывания связанных долговременных ключей честным участникам при их регистрации в сети. Важным условием реализуемости описываемых атак является наличие у схем подписи, используемых в указанных протоколах, уязвимости к атаке со связанными ключами (примером уязвимой схемы подписи является схема EGDSA). В результате каждой из трёх описываемых атак реализуется угроза ложной аутентификации. Атаки отличаются используемым набором возможностей нарушителя, необходимости которых вызвана особенностями конструкции протоколов в части подписываемых сообщений. Если подписывается идентификатор инициатора, передаваемый в первом сообщении, то дополнительно требуется возможности навязывания честному участнику его идентификатора при регистрации в сети. Если подписывается эфемерный ключ ответчика, то требуется возможности компрометации будущих открытых эфемерных ключей.

Изучается множество булевых функций от малого числа переменных с оптимальными показателями алгебраической и корреляционной иммунности. Исследуется возможность использования данных функций в качестве координатных функций S-блока.

Предложены тесты криптоаналитической обратимости для функций от трёх аргументов. Сформулированы алгоритмы построения функции восстановления и генерации обратимых функций.

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

Бент-функции вида F2 → Zq, где q ≥ 2- натуральное число, называются обобщёнными бент-функциями. Обобщённые бент-функции, для которых можно определить дуальную бент-функцию, называются регулярными. Исследуются обобщённые бент-функции, алгебраическая степень которых равна 1. Получены необходимые и достаточные условия того, что обобщённая булева функция алгебраической степени 1 является бент-функцией. Исследованы условия, при которых функция будет регулярной, а также слабо регулярной. Для случая q = 2k получено описание компонентных булевых функций обобщённой бент-функции алгебраической степени 1, из которого следует, что две из них, имеющие наибольший индекс, являются квадратичными, а остальные - постоянными.

Рассматриваются оценки мощности множеств Pn обратимых функций F : F2→F2, для которых любое U ⊆ F2 и его образ F(U) не могут одновременно являться аффинными подпространствами F2 размерности k, где 3 ≤ k ≤ n - 1. Приведены нижние оценки мощности Pn и Pn … ∩ Pn-1, усиливающие результаты 2007 г. (W. Е. Clark и др.)о непустоте данных множеств. Доказано, что почти все подстановки на F2 принадлежат Pn ∩ … ∩ Pn-1. Для мощностей множеств Pn и Pn∩ … ∩ Pn-1 получены асимптотические оценки сверху и снизу с точностью до 0(2n!). Оценено снизу число функций из Pn∩ …∩ Pn-1, которые отображают ровно одно аффинное подпространство F размерности 3 в аффинное подпространство.

Атака методом бумеранга, предложенная в 1999 г., является разновидностью разностной атаки. Её преимущество заключается в том, что даже при невысоком показателе дифференциальной равномерности шифр всё равно может быть уязвим. Данная работа посвящена такому параметру векторной булевой функции, как бумеранговая равномерности, который характеризует стойкости функции к атаке методом бумеранга. В качестве исследуемого класса функций рассматриваются квадратичные подстановки. Изучена зависимости бумеранговой характеристики от дифференциальной для этого класса, основным результатом является выражение, связывающее бумеранговую равномерности функции со значениями её DDT-таблицы и полученное благодаря использованию матричного подхода к работе с квадратичными функциями, а также известных свойств дифференциальной и бумеранговой характеристик. Исследованы некоторые конструкции квадратичных подстановок для малого числа переменных на предмет бумеранговой характеристики и установлены другие их свойства.