Криптография и свобода - страница 57

Эта шифровка в 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

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