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

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

Пусть для шифра с n -битовыми блоками открытого и шифрованного текста и m -битовым ключом блок открытого текста будет обозначен Р[1],...,Р[ n ], блок шифрованного текста - С[1],..., С[ n ], а ключ - К[1],..., K[ n ]. Тогда определим

A[ i,j,…,k ] = A[ i ] Å A[ j ] Å...ÅA[ k ].

Целью линейного криптоанализа является нахождение подходящего линейного уравнения вида

Р[α₁, α₂„..., α_a] Å С[β₁, β₂,..., β_b] = К[γ₁, γ₂,..., γ_c],

выполняющегося с вероятностью р ¹0,5 (где х = 0 или 1, 1 ≤ а, b ≤ n, 1 ≤ с ≤ т, а α, βи γпредставляют фиксированные битовые позиции в блоках). Чем больше значение р отклоняется от 0,5, тем более подходящим считается уравнение. После этого вычисляются значения левой части данного уравнения для большого числа пар соответствующих фрагментов открытого и шифрованного текста. Если результат оказывается равным 0 более чем в половине случаев, полагают, что K[γ₁, γ₂,..., γ_c] = 0. Если же в большинстве случаев получается 1, полагают, что K[γ₁, γ₂,..., γ_c] = 1. Достаточное количество полученных таким образом равенств образуют систему, решением которой определяется ключ. Ввиду линейности получаемых уравнений, проблему можно решать для каждого раунда шифрования в отдельности, а полученные результаты затем объединить.