Линейный криптоанализ

В криптографии основанная линейный криптоанализ — это общая форма криптоанализа, на нахождении аффинных приближений к действию шифра . Атаки были разработаны для блочных и потоковых шифров . Линейный криптоанализ — одна из двух наиболее широко используемых атак на блочные шифры; другой — дифференциальный криптоанализ .

Открытие приписывается Мицуру Мацуи , который первым применил эту технику к шифру FEAL (Мацуи и Ямагиши, 1992). ^[1] Впоследствии Мацуи опубликовал атаку на стандарт шифрования данных (DES), что в конечном итоге привело к первому экспериментальному криптоанализу шифра, о котором сообщалось в открытом сообществе (Мацуи, 1993; 1994). ^[2]^[3] Атака на DES, как правило, непрактична и требует 2 ⁴⁷ известные открытые тексты . ^[3]

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

Обзор [ править ]

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

Построение линейных уравнений [ править ]

Для целей линейного криптоанализа линейное уравнение выражает равенство двух выражений, состоящих из двоичных переменных, объединенных с операцией исключающее ИЛИ (XOR). Например, следующее уравнение гипотетического шифра устанавливает сумму XOR первого и третьего битов открытого текста (как в блоке блочного шифра), а первый бит зашифрованного текста равен второму биту ключа:

P_{1}\oplus P_{3}\oplus C_{1}=K_{2}.

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

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

Получение ключевых битов [ править ]

Получив линейную аппроксимацию вида:

P_{i_{1}}\oplus P_{i_{2}}\oplus \cdots \oplus C_{j_{1}}\oplus C_{j_{2}}\oplus \cdots =K_{k_{1}}\oplus K_{k_{2}}\oplus \cdots

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

Для каждого набора значений ключевых битов в правой части (называемого частичным ключом ) подсчитайте, сколько раз аппроксимация справедлива для всех известных пар открытый текст-зашифрованный текст; назовите этот T. счетчик Частичный ключ, T которого имеет наибольшее абсолютное отличие от половины количества пар открытый текст-зашифрованный текст, обозначается как наиболее вероятный набор значений для этих ключевых битов. Это связано с тем, что предполагается, что правильный частичный ключ приведет к тому, что аппроксимация будет выполняться с большим смещением. Здесь важна величина систематической ошибки, в отличие от величины самой вероятности.

Эту процедуру можно повторить с другими линейными аппроксимациями, получая предположения о значениях ключевых битов, пока количество неизвестных ключевых битов не станет достаточно низким, чтобы их можно было атаковать методом грубой силы .

См. также [ править ]

Ссылки [ править ]

^ Мацуи М. и Ямагиши А. «Новый метод атаки шифра FEAL по известному открытому тексту». Достижения в криптологии – EUROCRYPT 1992 .
^ Мацуи, М. «Первый экспериментальный криптоанализ стандарта шифрования данных». Достижения в криптологии – КРИПТО 1994 .
^ Перейти обратно: ^а ^б Мацуи, М. «Метод линейного криптоанализа для шифрования DES» (PDF) . Достижения в криптологии – EUROCRYPT 1993 . Архивировано из оригинала (PDF) 26 сентября 2007 г. Проверено 22 февраля 2007 г.

Внешние ссылки [ править ]

[FEAL_linear-1] Мацуи М. и Ямагиши А. «Новый метод атаки шифра FEAL по известному открытому тексту». Достижения в криптологии – EUROCRYPT 1992 .

[experimental_cryptanalysis-2] Мацуи, М. «Первый экспериментальный криптоанализ стандарта шифрования данных». Достижения в криптологии – КРИПТО 1994 .

[DES_linear-3] Перейти обратно: ^а ^б Мацуи, М. «Метод линейного криптоанализа для шифрования DES» (PDF) . Достижения в криптологии – EUROCRYPT 1993 . Архивировано из оригинала (PDF) 26 сентября 2007 г. Проверено 22 февраля 2007 г.

[1]

[2]

[3]