Линейный криптоанализ
В криптографии линейным криптоанализом называется метод криптоанализа, использующий линейные приближения для описания работы шифра.
Линейный криптоанализ был изобретён японским криптологом Мицуру Мацуи (яп. 松井 充 Мацуи Мицуру). Предложенный им в 1993 году (на конференции Eurocrypt '93) алгоритм был изначально направлен на вскрытие DES и FEAL[1]. Впоследствии линейный криптоанализ был распространён и на другие алгоритмы. На сегодняшний день наряду с дифференциальным криптоанализом является одним из наиболее распространённых методов вскрытия блочных шифров[2]. Также пригоден для атак на потоковые шифры.
Криптоанализ происходит в два шага. Первый — построение соотношений между открытым текстом, шифртекстом и ключом, которые справедливы с высокой вероятностью. Второй — использование этих соотношений вместе с известными парами открытый текст — шифртекст для получения битов ключа.
где — n-ые биты текста, шифртекста и ключа соответственно.
Данные соотношения называются линейными аппроксимациями. Вероятность P справедливости такого соотношения для произвольно выбранных битов открытого текста, шифртекста и ключа примерно равна 1/2. Такими соотношениями, вероятность которых заметно отличается от 1/2, можно пользоваться для вскрытия алгоритма.
Идея линейного криптоанализа — определить выражения вида (1), которые имеют высокую или низкую вероятность возникновения. Если алгоритм шифрования имеет высокую частоту выполнения уравнения (1), или напротив, уравнение выполняется с низкой частотой, то это свидетельствует о бедной способности рандомизации шифра. Если вероятность выполнения уравнения (1) равна p, то вероятность смещения p − 1/2. Чем больше величина вероятности смещения |p − 1/2|, тем лучше применимость линейного криптоанализа с меньшим количеством открытых текстов, необходимых для атаки[1][4].