XVIII Международная студенческая научная конференция Студенческий научный форум - 2026

Введение. Линейный криптоанализ, впервые предложенный Мицуру Мацуи в 1994 году, основан на поиске линейных приближений, связывающих входные и выходные биты шифра с битами ключа. Успех такой атаки напрямую зависит от существования статистически значимых линейных соотношений в нелинейных компонентах шифра, прежде всего в S-блоках. Чем выше корреляция между линейными комбинациями входных и выходных битов S-блока, тем более уязвимым оказывается шифр к линейному криптоанализу. Следовательно, оценка и минимизация такой корреляции становятся критически важными этапами при проектировании криптографических систем.

Для количественного анализа линейных свойств булевых функций, лежащих в основе S-блоков, широко применяются методы спектрального анализа, в частности преобразование Уолша-Адамара и ряды Фурье-Уолша. Эти математические аппараты позволяют перейти от изучения булевых функций в булевом пространстве к анализу их спектральных характеристик в частотной области. Коэффициенты разложения функции в ряд Фурье-Уолша непосредственно отражают степень её корреляции со всеми возможными линейными функциями, что даёт возможность точно оценить такие ключевые криптографические параметры, как нелинейность, устойчивость к корреляционным атакам и расстояние до множества аффинных функций.

Спектральный подход не только предоставляет мощный инструмент для анализа существующих S-блоков, но и открывает пути для синтеза новых, более стойких преобразований. Визуализация спектров Уолша позволяет наглядно идентифицировать «слабые места» булевых функций — пики в спектре, соответствующие высоким корреляциям с определёнными линейными масками. Таким образом, проектировщик шифра может целенаправленно модифицировать функцию, стремясь к максимально равномерному и «плоскому» спектру, что является индикатором высокой нелинейности и, как следствие, криптографической стойкости.

В данной работе мы сосредоточимся на исследовании взаимосвязи между спектральными характеристиками булевых функций, образующих S-блоки, и их уязвимостью к линейному криптоанализу. Будут рассмотрены теоретические основы рядов Фурье-Уолша и преобразования Уолша-Адамара, показано, как коэффициенты этого преобразования связаны с понятием смещения (bias) линейной аппроксимации. На практических примерах, включая анализ упрощённых S-блоков и отсылки к известным шифрам (таким как DES), мы продемонстрируем методику вычисления таблицы линейных приближений, оценки необходимого количества открытых текстов для успешной атаки и, что наиболее важно, — как спектральный анализ позволяет количественно измерить нелинейность и сделать вывод о криптографической прочности S-блока.

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

Материал и методы исследования. Основным объектом исследования являются булевы функции, используемые в качестве компонентов S-блоков современных симметричных криптосистем. В качестве конкретного материала для анализа рассматриваются:

• Булевы функции

• S-блоки известных шифров (AES, DES в качестве примеров)

• Спектральные характеристики функций — коэффициенты разложения в ряд Фурье-Уолша

• Метрики нелинейности: расстояние до множества аффинных функций, показатель нелинейности

Результаты исследования и их обсуждение.

Линейный криптоанализ — особый род атаки на симметричные шифры, направленный на восстановление неизвестного ключа шифрования, по известным открытым сообщениям и соответствующим им шифртекстам [3].

В качестве отличительного признака он использует линейное логическое соотношение между входными и выходными битами S-блоков, а также ключевыми битами сокращенного шифра, которое является смещенным, т.е. выполняется с вероятностью, отличной от 1/2. Другими словами, он использует маски (a, b) ∈ - , где n и m – количество битов информации, поданных на вход и выход соответственно [1, 2].

Например, внутренняя перестановка шифра с 4-битным блоком из в определяется следующим образом [2]:

Для каждого набора масок существует преобразование Фурье-Уолша, которое выглядит следующим образом:

где – коэффициент Уолша.

Смещение (иначе говоря, корреляция или дисбаланс) логической функции f с n переменными равно:

Или другими словами:

Пусть f - булева функция от n переменных. Преобразование Уолша для f - это функция:

Сопоставив формулы выше, мы делаем вывод, что (f + ϕ_a) есть ни что иное, как . В данном случае это называется коэффициентом Уолша для f в точке a, а мультимножество, состоящее из всех коэффициентов Уолша для f, называется спектром Уолша для функции f. Спектр Уолша соответствует смещениям всех аппроксимаций f линейной функцией. Эта величина, особенно ее максимум, играет важную роль в линейном криптоанализе.

Спектр Уолша f соответствует смещениям всех аппроксимаций f линейной функцией. Эта величина, особенно ее максимум, играет важную роль в линейном криптоанализе. Поскольку оно соответствует дискретному преобразованию Фурье, преобразование Уолша обладает всеми математическими свойствами преобразования Фурье. Поскольку в линейном криптоанализе используются линейные аппроксимации с высокой степенью смещения, естественным вопросом для проектировщика, которому необходимо выбрать хорошую нелинейную функцию, является знание наименьшего возможного значения, которое может быть достигнуто для смещения наилучшей линейной аппроксимации. Это значение определяется так называемой линейностью функции в смысле следующего определения [1, 2, 3].

При линейной атаке мы затем ищем наиболее смещенное линейное соотношение между входными и выходными битами S-блока. Для пары масок (a, b) соответствующее смещение определяется коэффициентом Уолша Sb в точках a, (Sb + θa). Эти отклонения обычно представлены в виде двумерной таблицы E(a, b) = (Sb + θa), называемой таблицей линейной аппроксимации. Формальное обозначение смещения линейной аппроксимации S-блока, выраженная через спектр Уолша-Адамара: E(a, b) = (S_b+ ϕ_a).

Таблица линейной аппроксимации для шифра с 4-битным блоком и 8-битным ключом [2]:

Коэффициент Уолша-Адамара связывает со смещением следующее соотношение:

Подход к линейному криптоанализу заключается в нахождении следующего "эффективного" линейного приближенного выражения, которое выполняется с вероятностью p ≠ 1/2 для случайно заданного открытого текста P, соответствующего шифртекста C и фиксированного секретного ключа K (уравнение 1) [3]:

где i, j, k обозначают фиксированные местоположения битов. Это уравнение составляется из множества линейных аппроксимаций S-блоков, «распространенных» через все раунды шифра [3].

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

Допустим, нашем шифре мы разбиваем 16-битный блок данных на четыре 4-битных подблока. Каждый подблок формирует входные данные для S-блока размером 4×4 (подстановка с 4 входными и 4 выходными битами), которая может быть легко реализована с помощью табличного поиска шестнадцати 4-разрядных значений, индексированных целым числом, представленным 4 входными битами. Наиболее фундаментальным свойством S-блока является то, что это нелинейное отображение, т.е. выходные биты не могут быть представлены в виде линейной операции над входными битами [3].

Таблица представления в виде S-блока (в шестнадцатеричном формате):

Прежде чем более подробно рассматривать атаку на общий шифр, необходимо ознакомиться с линейными уязвимостями S-блока. Рассмотрим S-блок с входными данными X = [X1, X2, X3, X4] и соответствующими выходными данными Y = [Y1, Y2, Y3, Y4].

S-блок с входными данными X = [X1, X2, X3, X4] и соответствующими выходными данными Y = [Y1, Y2, Y3, Y4]:

Все линейные аппроксимации могут быть проверены на предмет их полезности путем вычисления вероятности смещения для каждой из них. Следовательно, мы рассматриваем все выражения в виде уравнения (1), где X и Y - входные и выходные данные S-блок, соответственно.

Основная идея состоит в том, чтобы аппроксимировать работу части шифра линейным выражением, где линейность относится к побитовой операции по модулю 2 (т.е. исключающему ИЛИ, обозначающееся как "⊕"). Такое выражение имеет вид [1]:

где Xi представляет i-й бит входных данных X = [X1, X2, ...], а Yj представляет j-й бит выходных данных Y = [Y1, Y2, ...]. Это уравнение представляет собой исключающее значение ИЛИ "сумму" входных и выходных битов [2].

Например, для этого S-блока, используемого в нашем шифре, рассмотрим линейное выражение:

Х2 ⊕ X3 ⊕У1 ⊕У3 ⊕У4 = 0

или, что эквивалентно: Х2 ⊕ Х3 = У1 ⊕ У3 ⊕ У4

Применяя все 16 возможных входных значений для X и исследуя соответствующие выходные значения Y, можно заметить, что ровно в 12 из 16 случаев приведенное выше выражение справедливо. Следовательно, вероятностное смещение составляет 12/16−1/2 = 1/4 [2].

Теперь, найдя смещение, можно посчитать коэффициент Уолша:

, откуда

Видно, что линейное уравнение верно в 75% (P=12/16) случаев, что достаточно много.

Поскольку коэффициент Уолша влияет на значение P, то он влияет и на весь шифр, что видно из уравнения (1):

Это напрямую показывает, что чем больше смещение, тем более уязвим S-блок, а значит, что атакующему понадобится меньше пар открытый текст/шифртекст для нахождения ключа [3].

Если для этого блока найдена аппроксимация вида Х1 ⊕ Х4 = У2 ⊕ У3, можно увидеть, что при переборе всех 16 входов формула выполняется 10 раз, значит смещение составляет 10/16-1/2=1/8, а коэффициент Уолша , что является оптимальным результатом в данном примере.

Создатель криптоанализа, Мицуру Мацуи, показывает, что количество известных открытых текстов, необходимых для атаки, пропорционально смещению в степени -2 и, позволяя N_L представлять требуемое количество известных открытых текстов, разумно приблизить N_L к [1]:

Подставляя в формулу смещения, равные 1/4 и 1/8 (т.е. для коэффициентов Уолша равным 8 и 4 соответственно) количество открытых текстов будет соответственно равно:

,

Если же (нет корреляции), то и смещение будет нулевым, а значит атака невозможна, а шифр – устойчив.

Вывод: ряды Фурье и спектральный анализ используются для анализа свойств булевых функций и S‑блоков. Идея линейного криптоанализа - определить выражения вида (1), которые имеют высокую или низкую вероятность возникновения (т.е. первый шаг - построение соотношений между открытым текстом, шифртекстом и ключом). Для всех входных и выходных значений не должна соблюдаться очевидная линейность, подобная описанной выше, иначе шифр был бы тривиально слабым. Если в шифре наблюдается тенденция к тому, что уравнение (1) выполняется с высокой вероятностью или не выполняется с высокой вероятностью, это свидетельствует о плохой способности шифра к рандомизации. Если вероятность выполнения уравнения (1) равна P, то вероятность смещения P-1/2. Чем больше величина вероятности смещения |P − 1/2|, тем лучше применимость линейного криптоанализа при меньшем количестве известных открытых текстов, необходимых для атаки. S-блоки с более высокой нелинейностью обычно обеспечивают более равномерное распределение зашифрованного текста. Если генерируется слабый S-блок, в зашифрованном тексте могут проявляться закономерности, которые потенциально создают угрозу безопасности [1, 2, 3].

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

[1] Howard M. Heys. A Tutorial on Linear and Differential Cryptanalysis. – Electrical and Computer Engineering Faculty of Engineering and Applied Science Memorial University of Newfoundland St. John’s, NF, Canada, 2002. URL: https://www.engr.mun.ca/~howard/PAPERS/ldc_tutorial.pdf

[2] Anne Canteaut. Lecture Notes on Cryptographic Boolean Functions. - Paris, France, 2016. URL: https://www.rocq.inria.fr/secret/Anne.Canteaut/poly.pdf

[3] Mitsuru Matsui. Linear Cryptanalysis of DES Ciphe. – Osaka, Japan, 1994. URL: https://www.cs.bilkent.edu.tr/~selcuk/teaching/cs519/Matsui-LC.pdf

[4] Олейник Н.П., Трусова И.С., Найдыш А.В. – Информационные технологии как средство осуществления образовательного процесса 2024 URL: https://elibrary.ru/item.asp?id=73805811

Код для цитирования: Скопировать