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

Линейный криптоанализ изобрел японский криптолог Мицуру Мацуи (Mitsuru Matsui). Предложенный им в 1993 г. метод изначально был направлен на вскрытие того же алгоритма DES. Впоследствии линейный криптоанализ был распространен и на другие алгоритмы. Однако есть источники, которые утверждают, что линейный криптоанализ был изобретен для вскрытия алгоритма FEAL в 1992 г., а уже затем перенесен на DES.

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

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

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

Помимо DES и упомянутого выше алгоритма FEAL, известны и другие алгоритмы, подверженные линейному криптоанализу, например (отметим, что линейному криптоанализу подвержено существенно меньше известных алгоритмов, чем дифференциальному):
линейный криптоанализ действует против алгоритма RC5 в случае, если искомый ключ шифрования попадает в класс слабых ключей;
алгоритмы NUSH и Noekeon, известные своим участием в конкурсе криптоалгоритмов Евросоюза NESSDE, также вскрываются методом линейного криптоанализа;
некоторые варианты алгоритма DES (DESX, DES с независимыми подключами и Biham-DES) вскрываются линейным криптоанализом.

Алгоритмы шифрования