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

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

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

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

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

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

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

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

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

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

Процедура построения приближений для каждого шифра разная. В самом базовом типе блочного шифра, в сети замещения-перестановки , анализ сосредоточен в первую очередь на S-блоках , единственной нелинейной части шифра (т.е. операция S-блока не может быть закодирована в линейном уравнении). Для достаточно маленьких S-блоков можно перечислить все возможные линейные уравнения, связывающие входные и выходные биты S-блока, вычислить их смещения и выбрать лучшие. Затем линейные аппроксимации для S-блоков должны быть объединены с другими действиями шифра, такими как перестановка и смешивание ключей, чтобы получить линейные аппроксимации для всего шифра. Свайные вверх лемма- полезный инструмент для этого комбинированного шага. Существуют также методы итеративного улучшения линейных приближений (Matsui 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 .
^ Мацуи, М. «Первый экспериментальный криптоанализ стандарта шифрования данных». Достижения в криптологии - CRYPTO 1994 .
^ ^a ^b Мацуи, М. "Метод линейного криптоанализа для шифра DES" (PDF) . Достижения в криптологии - EUROCRYPT 1993 . Архивировано из оригинального (PDF) 26 сентября 2007 года . Проверено 22 февраля 2007 .

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

Линейный криптоанализ DES
Учебное пособие по линейному и дифференциальному криптоанализу
Демоверсия линейного криптоанализа
Учебное пособие по линейному (и дифференциальному) криптоанализу блочных шифров
«Повышение временной сложности линейного криптоанализа Мацуи», улучшает сложность благодаря быстрому преобразованию Фурье.

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

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

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

[1]