Михаил Масленников - Криптография и свобода
Рассмотрим преобразование θ(у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θ
Если блок открытого текста (y1,y2,…,y8) переходит в блок шифртекста (y17,y18,…,y24) с помощью преобразования δх1,х2,…,х16, т.е.
δх1,х2,…,х16(y1,y2,…,y8) = (y17,y18,…,y24),
то
θ-1δх1,х2,…,х16(y1,y2,…,y8) = θ-1 (y17,y18,…,y24) = (π-1 (у17), π-1 (у18),…, π-1 (у24)).
Тогда
(π-1(у17), π-1(у18),…, π-1(у24)) = θ-1δх1,х2,…,х16 θθ-1 (y1,y2,…,y8) = θ-1δх1,х2,…,х16θ (π-1 (у1), π-1 (у2),…, π-1 (у8))
Итак, вот она, первая зацепка для анализа «Ангстрем-3»: заменяем позначно все буквы шифрованного и известного открытого текста по подстановке π-1 и дальше используем вместо δxi преобразования φхi. А теперь давайте посмотрим на эти преобразования повнимательнее.
φхi (yi, yi+1,…yi+7)= θ-1δxiθ(yi, yi+1,…yi+7) = θ-1δxi(π (yi), π (yi+1),… π (yi+7)) =
θ-1(π(yi+1), π(yi+2),….,π(π(yi)+π(yi+1)+π(yi+7)+хi) = (yi+1, yi+2,…., π (yi)+π (yi+1)+π (yi+7)+хi)
Жизнь прекрасна и удивительна! Какие уравнения получились!
уi+8 = π (yi)+π (yi+1)+π (yi+7)+хi
Возьмем-ка теперь парочку блоков открытого текста (y1,y2,…,y8) (z1,z2,…,z8) и соответствующие им блоки шифртекста (y17,y18,…,y24) (z17,z18,…,z24) и выпишем уравнения одни под другими…
уi+8 = π (yi)+π (yi+1)+π (yi+7)+хi
zi+8 = π (zi)+π (zi+1)+π (zi+7)+хi
Это же криптографический Клондайк! Вычитаем одно уравнение из другого и ключ пропадает!
ui+8 = vi+vi+1+vi+7 (1)
где ui = yi-zi, vi = π(yi)- π(zi).
Из (1) имеем:
vi = ui+8 –vi+1-vi+7 (2)
Линейное уравнение – мечта криптографа! Тут только надо найти все такие решения, при которых для каждой пары (ui,vi) соответствующий элемент рui,vi в матрице Р(π) был бы ненулевым. Поехали!
При Т=16 из (1) и (2) имеем:
u1,u2,…u8, v1,v2,…v8 – известны – это открытый текст
u17,u18,…u24, v17,v18,…v24 – известны – это шифртекст
Из (2) последовательно находим:
v16 = u24-v17-v23
v15 = u23-v16-v22
…………
v9 = u17-v10-v16
а затем уже из (1) – все ui. Система (1) полностью решена!
Дальше – раздолье. Ключ опробуем позначно. Для первого байта ключа x1 оставляем допустимыми только те значения, при которых пара (y9,z9) является решением системы
y9-z9 = u9
π(y9)- π(z9) = v9
Если таких значений будет несколько, то возьмем еще одну пару и истинным будут только те значения, которые содержатся в пересечении этих множеств и так поштучно определяем весь ключ.
Вот теперь пора и почитать, что там наша доблестная армия нашифровала. Военный приказ будем взламывать по-военному четко: делай раз, делай два, делай три.
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 D82. Все байты в этих парах заменяем по подстановке π-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 3CD2 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) вычисляем промежуточные значения v16,v15,…,v9
v16 = u24 – v17 –v23 = 03 –D1-D8 = 5A
v15 = u23 – v16 –v22 = 12 –5A-B0 = 08
v14 = u22 – v15 –v21 = 70 – 08-BF =A9
v13 = u21 – v14 –v20 = 11 – A9-54 = 14
v12 = u20 – v13 –v19 = A6 – 14 -6D = 25
v11 = u19 – v12 –v18 = 37 – 25 -72 = A0
v10 = u18 – v11 –v17 = FA – A0 -D1 = 89
v9 = u17 – v10 –v16 = 26 – 89 -5A = 43
Затем с помощью (1) вычисляем u9,u10,…,u16
u9 = v1+v2+v8 = E4+00+08 = EC
u10 = v2+v3+v9 = 00+C2+43 = 05
u11 = v3+v4+v10 = C2+F4+89 = 3F
u12 = v4+v5+v11 = F4+0B+A0 = 9F
u13 = v5+v6+v12 = 0B+0E+25 = 3E
u14 = v6+v7+v13 = 0E+F5+14 = 17
u15 = v7+v8+v14 = F5+08+A9 = A6
u16 = v8+v9+v15 = 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Чуток осталось! Для определения первого знака ключа х1 надо найти у9, поскольку
х1=у9-π(у1)- π(у2)- π(у8), а все значения у1,у2,…,у8 – известны. Значение же у9 находим исходя из следующих условий:
π(у9)- π(у9-ЕС)= 43 (для первой пары) и
π(у9)- π(у9-E5)= C0 (для второй пары)
Честно перебрав все 256 значений, находим: у9 = 9В, тогда х1 = 9В – D1 – EE – ED = EF
Далее – все аналогично. Для второго знака ключа
π(у10)- π(у10-05)= 89 (для первой пары) и
π(у10)- π(у10-В5)= 5F (для второй пары)
откуда у10 = 98, тогда х2 = 98 – ЕЕ – Е2 – В0 = 18
Точно таким же путем можно вычислить и все остальные знаки ключа. Небольшое затруднение возникнет лишь при определении х11, поскольку в этом случае система получится такая:
π(у19)- π(у19-37)= 6D (для первой пары) и
π(у9)- π(у9-00)= 00 (для второй пары)
Вторая пара здесь ничего не дает, но зато первая отсеяла все отлично, только одно допустимое значение остается: F7.
Вот он, полностью вычисленный ключ к «Ангстрему-3» при Т=16:
EF 18 9E C8 7B B9 0F A1 8E BC 71 6F D1 07 94 92
А вот и телеграмма, расшифрованная с его помощью:
Совершенно секретно. Приказ №362 по Дальнему военному округу. Все воины Дальнего военного округа, активно включившись в борьбу за достойную встречу XXV съезда КПСС, принимают на себя повышенные социалистические обязательства. Танкисты и артиллеристы, летчики и ракетчики, мотострелки и инженерные войска стремятся повышать свою боевую и политическую подготовку, быть преданными социалистической Родине и советскому народу. Но, к сожалению, в некоторых подразделениях нашего славного округа еще имеются отдельные случаи несерьезного отношения к такому важнейшему мероприятию, как достойная встреча партийного съезда. Так в 8 отделе технической службы в качестве повышенных социалистических обязательств решили разработать программу выработки простых чисел. В то время, как все бойцы и командиры стараются освоить новую, сложную технику, техническое подразделение ищет легких путей и простых чисел. В 8 отделе длительное время наблюдается снижение воинской дисциплины, многие офицеры этого отдела получили замечания на прошедшем строевом смотре и не сделали из них для себя должных выводов. ПРИКАЗЫВАЮ: 1) 8 отделу технической службы в недельный срок завершить разработку простых чисел и перейти к выработке программы для сложных чисел. 2) Все выработанные к настоящему моменту простые числа считать сложными. 3) Разработчикам простых чисел указать на необходимость повышения воинской дисциплины и выучки в их дальнейшей работе. 4) Приказ объявить во всех подразделениях Дальнего военного округа. Командир ДВО генерал-майор Безверхов.
