Криптография и свобода — страница 26 из 64

B1B2B3B4B5B6B7B8B9BABBBCBDBEBFD2ABC4A96E41F0AA42AC195B1E4F945D

C0

C1

C2

C3

C4

C5

C6

C7

C8

C9

CA

CB

CC

CD

CE

CF

16

8C

FD

5E

95

B5

97

6C

AD

08

BB

AE

96

20

7F

23

D0

D1

D2

D3

D4

D5

D6

D7

D8

D9

DA

DB

DC

DD

DE

DF

D5

43

D1

47

49

02

99

80

D9

60

61

65

70

AF

62

63

E0

E1

E2

E3

E4

E5

E6

E7

E8

E9

EA

EB

EC

ED

EE

EF

9B

DF

03

67

F2

68

69

6F

71

72

D7

73

74

75

76

79

F0

F1

F2

F3

F4

F5

F6

F7

F8

F9

FA

FB

FC

FD

FE

FF

EC

D3

82

E1

7A

ED

DA

83

84

9D

9E

9F

B6

BC

E6

E7

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

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

Давайте сначала выпишем уравнения зашифрования, реализуемые этой схемой. Если (y₁,y₂,…,y₈) – блок, записанный в первом регистре сдвига «Ангстрем-3», то за один такт работы схемы он перейдет в блок (y₂,y₃,…,y₉), где y₉ = π(y₁+y₂+y₈+x₁), х₁ – первый байт неизвестного ключа. В общем случае, если последовательность всех заполнений первого регистра сдвига обозначить как у₁,у₂,….,у₂₃,у₂₄, где (y₁,y₂,…,y₈) – блок открытого текста, (y₁₇,y₁₈,…,y₂₄) – блок шифртекста, то для любого 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⁶⁴. Тогда все преобразование, осуществляемое схемой «Ангстрем-3», будет выглядеть как произведение подстановок:

δ_{х1,х2,…,х16} = δ_x1δ_x2…δ_x16

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

θ^-1(у₁,у₂,…у₈) = (π^-1 (у₁), π^-1 (у₂),…, π^-1 (у₈)).

Имеем

θ^-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₁,y₂,…,y₈) переходит в блок шифртекста (y₁₇,y₁₈,…,y₂₄) с помощью преобразования δ_{х1,х2,…,х16}, т.е.

δ_{х1,х2,…,х16}(y₁,y₂,…,y₈) = (y₁₇,y₁₈,…,y₂₄),

то

θ^-1δ_{х1,х2,…,х16}(y₁,y₂,…,y₈) = θ^-1 (y₁₇,y₁₈,…,y₂₄) = (π^-1 (у₁₇), π^-1 (у₁₈),…, π^-1 (у₂₄)).

Тогда

(π^-1(у₁₇), π^-1(у₁₈),…, π^-1(у₂₄)) = θ^-1δ_{х1,х2,…,х16} θθ^-1 (y₁,y₂,…,y₈) = θ^-1δ_{х1,х2,…,х16}θ (π^-1 (у₁), π^-1 (у₂),…, π^-1 (у₈))

Итак, вот она, первая зацепка для анализа «Ангстрем-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₁,y₂,…,y₈) (z₁,z₂,…,z₈) и соответствующие им блоки шифртекста (y₁₇,y₁₈,…,y₂₄) (z₁₇,z₁₈,…,z₂₄) и выпишем уравнения одни под другими…

у_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₁,u₂,…u₈, v₁,v₂,…v₈ – известны – это открытый текст

u₁₇,u₁₈,…u₂₄, v₁₇,v₁₈,…v₂₄ – известны – это шифртекст

Из (2) последовательно находим:

v₁₆ = u₂₄-v₁₇-v₂₃

v₁₅ = u₂₃-v₁₆-v₂₂

…………

v₉ = u₁₇-v₁₀-v₁₆

а затем уже из (1) – все u_i. Система (1) полностью решена!

Дальше – раздолье. Ключ опробуем позначно. Для первого байта ключа x₁ оставляем допустимыми только те значения, при которых пара (y₉,z₉) является решением системы

y₉-z₉ = u₉

π(y₉)- π(z₉) = v₉

Если таких значений будет несколько, то возьмем еще одну пару и истинным будут только те значения, которые содержатся в пересечении этих множеств и так поштучно определяем весь ключ.

Вот теперь пора и почитать, что там наша доблестная армия нашифровала. Военный приказ будем взламывать по-военному четко: делай раз, делай два, делай три.

1. Берем первые 24 знака известного нам открытого текста, соответствующие им знаки шифртекста и составляем две пары переходов из открытого текста в шифрованный.

Первая пара

Открытый текст	Шифртекст
D1 EE E2 E5 F0 F8 E5 ED	D8 C7 83 EF F9 CA 71 FA
ED EE 20 F1 E5 EA F0 E5	07 55 16 9B 3A 1A 99 53

Вторая пара

D1 EE E2 E5 F0 F8 E5 ED	D8 C7 83 EF F9 CA 71 FA
F2 ED EE 2E 20 CF F0 E8	87 CC 83 9D FA 1D D6 D8

2. Все байты в этих парах заменяем по подстановке π