Михаил Масленников - Криптография и свобода

Эта шифровка в ASCII-символах, т.е. в элементах по модулю 256, представленных в шестнадцатиричной записи. Известно, что она была получена с помощью схемы «Ангстрем-3» при Т=16 и известна подстановка π:

Что известно об открытом тексте? Это военная телеграмма, в которой содержится какой-то приказ. Начало телеграммы – стандартное: «Совершенно секретно. Приказ №», или в шестнадцатиричной записи соответствующих ASCII-символов

D1 EE E2 E5 F0 F8 E5 ED ED EE 20 F1 E5 EA F0 E5 F2 ED EE 2E 20 CF F0 E8 EA E0 E7 20 B9

Приступим к взлому, т.е. к определению неизвестного ключа х 1,х 2,…х 16, записанного во втором регистре сдвига.

Давайте сначала выпишем уравнения зашифрования, реализуемые этой схемой. Если (y 1,y 2,…,y 8) – блок, записанный в первом регистре сдвига «Ангстрем-3», то за один такт работы схемы он перейдет в блок (y 2,y 3,…,y 9), где y 9= π(y 1+y 2+y 8+x 1), х 1– первый байт неизвестного ключа. В общем случае, если последовательность всех заполнений первого регистра сдвига обозначить как у 1,у 2,….,у 23,у 24, где (y 1,y 2,…,y 8) – блок открытого текста, (y 17,y 18,…,y 24) – блок шифртекста, то для любого i≥9 будет справедливо:

yi = π(y i-8+y i-7+y i-1+x i-8)

Преобразование блока (y i, y i+1,…y i+7) в блок (y i+1,y i+2,…,y i+8) за один такт обозначим как δ xi. Очевидно, что это взаимно-однозначное преобразование, поскольку π - подстановка:

δ xi(y i, y i+1,…y i+7) = (y i+1,y i+2,…, π(y i+y i+1+y i+7+x i))

δ xi- это подстановка на множестве Z/2 64. Тогда все преобразование, осуществляемое схемой «Ангстрем-3», будет выглядеть как произведение подстановок:

δ х1,х2,…,х16= δ x1δ x2…δ x16

Рассмотрим преобразование θ(у 1,у 2,…у 8) = (π (у 1), π (у 2),…, π (у 8)). Заметим, что

θ -1(у 1,у 2,…у 8) = (π -1(у 1), π -1(у 2),…, π -1(у 8)).

Имеем

θ -1δ х1,х2,…,х16θ = θ -1δ x1δ x2…δ x16θ = θ -1δ x1θθ -1δ x2θθ -1 …θθ -1δ x16θ = φ х1φ х2…φ х16= φ х1,х2,…х16,

где φ хi= θ -1δ xiθ

Если блок открытого текста (y 1,y 2,…,y 8) переходит в блок шифртекста (y 17,y 18,…,y 24) с помощью преобразования δ х1,х2,…,х16, т.е.

δ х1,х2,…,х16(y 1,y 2,…,y 8) = (y 17,y 18,…,y 24),

то

θ -1δ х1,х2,…,х16(y 1,y 2,…,y 8) = θ -1(y 17,y 18,…,y 24) = (π -1(у 17), π -1(у 18),…, π -1(у 24)).

Тогда

(π -1(у 17), π -1(у 18),…, π -1(у 24)) = θ -1δ х1,х2,…,х16θθ -1(y 1,y 2,…,y 8) = θ -1δ х1,х2,…,х16θ (π -1(у 1), π -1(у 2),…, π -1(у 8))

Итак, вот она, первая зацепка для анализа «Ангстрем-3»: заменяем позначно все буквы шифрованного и известного открытого текста по подстановке π -1и дальше используем вместо δ xiпреобразования φ хi. А теперь давайте посмотрим на эти преобразования повнимательнее.

φ хi(y i, y i+1,…y i+7)= θ -1δ xiθ(y i, y i+1,…y i+7) = θ -1δ xi(π (y i), π (y i+1),… π (y i+7)) =

θ -1(π(y i+1), π(y i+2),….,π(π(y i)+π(y i+1)+π(y i+7)+х i) = (y i+1, y i+2,…., π (y i)+π (y i+1)+π (y i+7)+х i)

Жизнь прекрасна и удивительна! Какие уравнения получились!

у i+8= π (y i)+π (y i+1)+π (y i+7)+х i

Возьмем-ка теперь парочку блоков открытого текста (y 1,y 2,…,y 8) (z 1,z 2,…,z 8) и соответствующие им блоки шифртекста (y 17,y 18,…,y 24) (z 17,z 18,…,z 24) и выпишем уравнения одни под другими…

у i+8= π (y i)+π (y i+1)+π (y i+7)+х i

z i+8= π (z i)+π (z i+1)+π (z i+7)+х i

Это же криптографический Клондайк! Вычитаем одно уравнение из другого и ключ пропадает!

u i+8= v i+v i+1+v i+7(1)

где u i= y i-z i, v i= π(y i)- π(z i).

Из (1) имеем:

v i= u i+8–v i+1-v i+7(2)

Линейное уравнение – мечта криптографа! Тут только надо найти все такие решения, при которых для каждой пары (u i,v i) соответствующий элемент р ui,viв матрице Р(π) был бы ненулевым. Поехали!

При Т=16 из (1) и (2) имеем:

u 1,u 2,…u 8, v 1,v 2,…v 8– известны – это открытый текст