Криптография и свобода

Возьмем-ка теперь парочку блоков открытого текста (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. Все байты в этих парах заменяем по подстановке π^-1

D2 0B 77 52 B6 31 52 F5	68 6E F7 86 2A A7 E8 3F
F5 0B CD 5D 52 4E B6 52	42 74 C0 E0 19 37 D6 3C

D2 0B 77 52 B6 31 52 F5	68 6E F7 86 2A A7 E8 3F
E4 F5 0B 38 CD 6A B6 35	5E 27 F7 F9 3F 7E A0 68

3. Для каждой из этих двух пар составляем и решаем систему линейных уравнений (1)

Первая пара

Открытый текст

	1	2	3	4	5	6	7	8
ui	DD	00	AA	F5	64	E3	9C	A3
vi	E4	00	C2	F4	0B	0E	F5	08

Шифртекст

17	18	19	20	21	22	23	24
26	FA	37	A6	11	70	12	03
D1	72	6D	54	BF	B0	D8	A7

Сначала с помощью уравнений (2) вычисляем промежуточные значения v₁₆,v₁₅,…,v₉

v₁₆ = u₂₄ – v₁₇ –v₂₃ = 03 –D1-D8 = 5A

v₁₅ = u₂₃ – v₁₆ –v₂₂ = 12 –5A-B0 = 08

v₁₄ = u₂₂ – v₁₅ –v₂₁ = 70 – 08-BF =A9

v₁₃ = u₂₁ – v₁₄ –v₂₀ = 11 – A9-54 = 14

v₁₂ = u₂₀ – v₁₃ –v₁₉ = A6 – 14 -6D = 25

v₁₁ = u₁₉ – v₁₂ –v₁₈ = 37 – 25 -72 = A0

v₁₀ = u₁₈ – v₁₁ –v₁₇ = FA – A0 -D1 = 89

v₉ = u₁₇ – v₁₀ –v₁₆ = 26 – 89 -5A = 43

Затем с помощью (1) вычисляем u₉,u₁₀,…,u₁₆

u₉ = v₁+v₂+v₈ = E4+00+08 = EC

u₁₀ = v₂+v₃+v₉ = 00+C2+43 = 05

u₁₁ = v₃+v₄+v₁₀ = C2+F4+89 = 3F

u₁₂ = v₄+v₅+v₁₁ = F4+0B+A0 = 9F

u₁₃ = v₅+v₆+v₁₂ = 0B+0E+25 = 3E

u₁₄ = v₆+v₇+v₁₃ = 0E+F5+14 = 17

u₁₅ = v₇+v₈+v₁₄ = F5+08+A9 = A6

u₁₆ = v₈+v₉+v₁₅ = 08+43+08 = 53

Таким образом, получилась табличка промежуточных значений

Промежуточные значения для первой пары

9	10	11	12	13	14	15	16
EC	05	3F	9F	3E	17	A6	53
43	89	A0	25	14	A9	08	5А

Теперь проделываем все то же самое для второй пары.

Открытый текст

	1	2	3	4	5	6	7	8
ui	EE	16	6C	1A	E9	C7	9C	C0
vi	DF	01	F4	B7	D0	29	F5	05

Промежуточные значения

9	10	11	12	13	14	15	16
E5	В5	85	0C	05	23	1D	07
C0	5F	97	6E	1F	7A	B0	EB

Шифртекст

17	18	19	20	21	22	23	24
0A	47	00	8D	EB	29	48	D7
51	FB	00	52	FF	AD	9B	22

Чуток осталось! Для определения первого знака ключа х₁ надо найти у₉, поскольку

х₁=у₉-π(у₁)- π(у₂)- π(у₈), а все значения у₁,у₂,…,у₈ – известны. Значение же у₉ находим исходя из следующих условий:

π(у₉)- π(у₉-ЕС)= 43 (для первой пары) и

π(у₉)- π(у₉-E5)= C0 (для второй пары)

Честно перебрав все 256 значений, находим: у₉ = 9В, тогда х₁ = 9В – D1 – EE – ED = EF

Далее – все аналогично. Для второго знака ключа

π(у₁₀)- π(у₁₀-05)= 89 (для первой пары) и

π(у₁₀)- π(у₁₀-В5)= 5F (для второй пары)

откуда у₁₀ = 98, тогда х₂ = 98 – ЕЕ – Е2 – В0 = 18

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

π(у₁₉)- π(у₁₉-37)= 6D (для первой пары) и

π(у₉)- π(у₉-00)= 00 (для второй пары)