Введение
Форма криптоанализа
В криптографии линейный криптоанализ — это общий вид криптоанализа, основанный на поиске аффинных приближений к функционированию шифра. Разработаны атаки для блочных и потоковых шифров. Линейный криптоанализ является одним из двух наиболее широко используемых методов атак на блочные шифры; другим является дифференциальный криптоанализ. Открытие этого метода приписывается Мицуру Мацуи, который впервые применил его к шифру FEAL (Matsui и Yamagishi, 1992). Впоследствии Мацуи опубликовал атаку на стандарт шифрования данных (DES), что в конечном итоге привело к первому публично представленному экспериментальному криптоанализу этого шифра (Matsui, 1993; 1994). Атака на DES обычно непрактична, поскольку требует 247 известных открытых текстов. Было предложено множество усовершенствований этой атаки, включая использование нескольких линейных приближений или включение нелинейных выражений, что привело к развитию обобщенного криптоанализа на основе разбиения. От новых конструкций шифров обычно ожидается устойчивость к линейному криптоанализу.
In cryptography, linear cryptanalysis is a general form of cryptanalysis based on finding affine approximations to the action of a cipher. Attacks have been developed for block ciphers and stream ciphers. Linear cryptanalysis is one of the two most widely used attacks on block ciphers; the other being differential cryptanalysis. The discovery is attributed to Mitsuru Matsui, who first applied the technique to the FEAL cipher (Matsui and Yamagishi, 1992). Subsequently, Matsui published an attack on the Data Encryption Standard (DES), eventually leading to the first experimental cryptanalysis of the cipher reported in the open community (Matsui, 1993; 1994). The attack on DES is not generally practical, requiring 247 known plaintexts. A variety of refinements to the attack have been suggested, including using multiple linear approximations or incorporating non linear expressions, leading to a generalized partitioning cryptanalysis. Evidence of security against linear cryptanalysis is usually expected of new cipher designs.
Обзор
Линейный криптоанализ состоит из двух частей. Первая – построение линейных уравнений, связывающих открытый текст, шифротекст и биты ключа, обладающих высокой степенью смещения, то есть, вероятность истинности которых (во всём пространстве возможных значений их переменных) максимально близка к 0 или 1. Вторая – использование этих линейных уравнений совместно с известными парами открытый текст – шифротекст для вывода битов ключа.
Построение линейных уравнений
Для целей линейного криптоанализа линейное уравнение выражает равенство двух выражений, состоящих из бинарных переменных, объединенных операцией исключающего ИЛИ (XOR). Например, следующее уравнение, взятое из гипотетического шифра, утверждает, что сумма XOR первого и третьего битов открытого текста (как в блоке блочного шифра) и первого бита шифротекста равна второму биту ключа:
В идеальном шифре любое линейное уравнение, связывающее биты открытого текста, шифротекста и ключа, выполнялось бы с вероятностью 1/2. Поскольку уравнения, используемые в линейном криптоанализе, различаются по вероятности, их точнее называть линейными аппроксимациями. Процедура построения аппроксимаций различна для каждого шифра. В наиболее простом типе блочного шифра – сети подстановок-перестановок – анализ сосредоточен главным образом на S-блоках, единственной нелинейной части шифра (то есть операцию S-блока нельзя представить в виде линейного уравнения). Для достаточно малых S-блоков можно перечислить все возможные линейные уравнения, связывающие входные и выходные биты S-блока, вычислить их смещения и выбрать наилучшие. Линейные аппроксимации для S-блоков затем необходимо комбинировать с другими операциями шифра, такими как перестановка и перемешивание ключа, чтобы получить линейные аппроксимации для всего шифра. Лемма накопления является полезным инструментом для этого этапа комбинирования. Существуют также методы итеративного улучшения линейных аппроксимаций (Matsui 1994).