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

Глава 5. Взломаем?

Глава 5. Взломаем?

Итак, читатель, давай себе представим, что мы – высококвалифицированные криптоаналитики из американского АНБ. Собственный загородный трехэтажный особняк, жена-красавица, три машины, одна из которых джип для воскресных поездок к морю, ежемесячный оклад тысяч так 5 – 6 USD.

На этом месте мое воображение представлять что-нибудь еще просто отказывается. Так и хочется воскликнуть, немного перефразируя крылатые слова Жеглова – Высоцкого:

– Ну посмотри, какой из тебя американский криптоаналитик? У тебя же зарплата 250 рублей на лбу написана!

Так что лучше представить себе что-нибудь другое, ближе к нашей Российской действительности. Например, вот такую вот сценку, свидетелем которой мне довелось быть уже намного позже, в 1993 году в период активной работы с Центральным Банком России.

Это было вскоре после успешного внедрения системы защиты телеграфных авизо. Руководство ЦБ решило устроить селекторное совещание со всеми крупнейшими расчетно-кассовыми центрами (РКЦ) и пригласить на него разработчиков системы защиты с тем, чтобы все смогли напрямую высказать свое мнение о системе и предложения по ее совершенствованию. Но помимо системы защиты телеграфных авизо все старались воспользоваться благоприятным моментом и донести до центробанковского начальства свои заботы и печали. Так мне невольно пришлось стать свидетелем реальных будней из жизни Российской глубинки. Один момент из жизни инкассаторов (они должны были развозить секретные ключи для системы защиты авизо) запомнился особо.

– Недавно в нашем РКЦ произошло ЧП. Один из инкассаторов, будучи в нетрезвом состоянии, на спор пробил ломом бронированное лобовое стекло инкассаторской машины.

Вот это уже родное, а то какие-то американские криптографы с их роскошной жизнью! Так что давайте представим, что один советский криптограф на спор взялся взломать «Ангстрем-3» при Т=16. А другой (начальник) пообещал, что если взломает, то ему прибавят к ежемесячному окладу в 250 руб. еще 20 руб.

Здесь я еще раз хочу извиниться перед читателями за ту криптографическую рутину, которая сейчас последует. Что поделаешь: сказывается многолетняя привычка никогда и ничему не верить на слово, требовать ясных и четких доказательств. Заявлено: шифры на новой элементной базе, новое перспективное направление, математические результаты… Хватит общих слов! Нужны конкретные результаты! Что там было нового и как анализировались эти шифры? И здесь, признаюсь, началось с того, что первый пример шифра на новой элементной базе был самым тривиальным образом взломан. Так, как в этом примере.

Вот шифровка, которую надо прочитать.

D8 C7 83 EF F9 CA 71 FA 07 55 16 9B 3A 1A 99 53 87 CC 83 9D FA 1D D6 D8 35 98 FA 84 A2 57 EE 67 F2 F1 B7 63 2D AC 6C EB 76 08 38 99 B3 D5 83 A9 31 CB 5C 03 9A 2A 3C 23 8A 8F DC 62 CD 72 C5 DE 5C E2 0C 7B A8 1E B4 96 D9 77 28 30 EA CD F9 38 89 BB 30 71 08 EC 01 50 2C E0 E2 C4 2B 03 8B 30 35 C3 10 A5 86 92 B8 06 F7 F2 00 21 BF 28 4E 0A 04 67 11 07 B6 7E 7C 5D AA 25 7F 68 1B 09 F2 81 FF E4 31 A5 41 4D CA BE D1 58 85 1F 76 F3 DE 89 03 40 9D B4 00 50 29 99 EC C9 DF BB 66 86 6D CC CA 2F 0E 93 E7 2D AB 38 F3 1B AD EE 55 09 44 B3 D6 D3 CC 4F 0A 01 0D 63 78 FA 9D D4 A1 C9 84 85 CC B5 4C D4 99 5C 4D CB 2E 92 F0 29 19 7B 85 7F 7C 9E FD 63 7F 9B 95 5A 4D D7 AF A5 CD 6E 80 5F A5 B8 9E E5 C9 AB 6F 0F CD 33 46 98 6A D5 66 21 D4 E9 19 20 3E AD 03 6E F6 6D 8A 73 F6 B2 CE 60 F1 AE 87 A7 11 18 36 46 E8 C5 3A 30 9A 24 F2 65 55 8D 49 90 BD 0D F5 FD 29 D2 56 D9 D0 A9 92 22 16 76 D9 69 67 C2 B7 6A 42 CB E2 82 36 94 ED C0 91 2E A0 9D CD B0 9B FC 5C 77 15 5A C4 ED 17 54 22 22 F2 E3 26 39 A5 4A E6 91 63 7F 60 A0 F2 EA 5C 6A FF 9F D3 0F E0 63 0E 69 97 A8 05 5A 91 07 65 52 65 E0 6C DF EA EB 28 4E B4 34 FF AC B1 36 35 C8 19 DE 44 02 8B F1 50 6F CE 1C 6C 99 55 0E 2E 92 F0 29 19 7B 85 7F E8 D3 CB 3B 84 79 D7 8E 62 88 D6 2F D1 D9 2E 9F EE B1 D6 54 85 D2 65 ED 3A 73 F8 C5 90 E5 ED DB 6F B8 A2 0F 01 D6 CA B6 B7 9C B1 31 12 EA 45 48 F6 D0 D4 A2 F0 45 3B E9 AE D1 14 04 22 2C 15 FB CA 3E 58 99 14 3F 51 29 49 43 4D 95 48 FD 6C 2F ED 48 0C C9 6B F6 BC F9 5A EE 79 E9 0C 35 A2 F4 A6 C7 4E 1E B1 2B CB F9 A3 4B 30 9F 57 51 6A 90 97 72 45 90 72 95 BE 19 7B F3 D2 41 34 18 9D E1 BA 7C EF 07 35 B3 A1 D9 CF 2D 6B 80 5C F4 73 93 A8 3B 78 B5 3D 09 00 BE 85 09 B7 98 B6 74 BE 45 40 29 43 0E 92 92 C2 AA B1 50 94 AB FD CE 2D B5 8D 4E CD 35 DD 05 EA C2 6E C0 CE 45 3F 29 4D E8 49 8C D9 7B A7 D9 2A 59 C8 50 25 F3 29 29 F0 D2 27 3B BB E7 1D 7C 58 8C 7C D4 0E E2 7F 55 16 A1 89 2D A0 8D EC 82 2B C5 6B 88 2C 45 10 D9 46 55 4B 26 CC 25 21 8E 7D D7 4C CD 7C DE A5 A1 25 15 C4 52 5D 81 66 B6 6B 48 97 F2 A7 A1 8C E4 ED 39 82 E9 7C 6A AE 4A 8A 7F B0 32 43 57 F2 E4 EB 2A 13 14 51 5E CF 03 F7 02 F2 C2 38 5A 00 79 7C 04 6D 4E 50 46 E1 8D 55 9F 98 E5 04 F4 03 8F DF 28 DC 09 AB 9C C2 9C 36 24 A9 93 43 F2 C7 2C 01 EE F6 3D 63 74 EC 04 4F 2A 64 11 69 E2 F2 BE 50 F4 46 D3 6E AA CD EE F2 87 9E 6B 46 8F 27 7D B2 9A 73 4E DB 02 64 29 90 C7 00 28 A6 3F 0A 3E 06 62 C3 76 D9 BA 75 CD AC 05 3C 51 DF 7D 29 16 44 80 0C 8B DF 53 EB C0 1E 48 04 B6 40 4F 77 75 88 D0 28 76 EE 70 B6 D5 3C 44 77 AD 6C 13 55 AC 8D 15 18 C4 6B DD FF 0C 32 60 7B 52 2F B8 0E 57 E2 01 0F A5 85 C9 69 DD DC 5D D0 60 27 64 28 43 AD 11 19 B1 25 6D AF 36 F5 80 F3 CB 54 91 F0 B6 08 B8 11 FD 5C A3 C9 41 BD 70 86 27 AB 26 AB 31 BA FE F7 36 0B 06 69 8B 65 24 B0 54 6A A0 CD F9 19 CC E3 E2 77 5F F3 D5 1B 39 99 64 0A 69 F0 B4 BF E4 6D 9B B4 63 28 B1 1C DD E5 A1 B1 87 E8 83 3D 99 C2 E0 09 3C 70 96 61 7E 9E FE FA 47 CE 91 16 FF AA 11 EA 20 A1 7E 5A BB 43 47 33 0E C4 B8 34 78 EE AF 74 EF 23 81 B3 EE 47 44 05 18 2A CB 6D 4E A4 0C 2B 2F 8D 2D 93 03 3C 91 F4 48 08 50 FB DC 91 BC 5F 7B B4 C1 2F BC 81 9E FA 57 2E 20 AB 38 0D 8D 92 A0 87 6D 58 8A B6 86 DE 31 60 94 2C D7 41 8C E8 99 CA 2E 63 D8 0E 0A A4 7C 6A FB A8 76 E1 B8 A9 4F 75 41 08 CA 74 24 9C 6F D2 86 49 E4 DF D8 88 CD BC 79 AE DE 5C 1D D1 6E 23 61 FE 38 08 C1 6E 0B 4A F5 F3 75 61 95 04 D2 8A 4F 35 4F 96 D1 9F CC F7 63 33 AB D0 75 29 74 82 68 84 5A 3A 50 1A 55 D4 37 6A 9B 12 49 C9 6F 9C 2A 83 D7 12 5C 87 0D F3 AB 67 32 BF 0A 9B 9D 9E 50 74 BD BC 75 87 E9 19 21 92 C5 C6 A8 0A 0C 6F 9E D9 09 C8 1A F4 11 81 E8 A3 52 6D 06 48 FE 04 AF 31 1C 3D 51 2B 33 B5 2F 21 85 08 F4 13 C2 8D C2 C8 7B D9 0E EC D8 F5 30 C0 0E AB D8 AB ED F5 38 3D 4A E6 06 C6 84 89 4B 29 A4 B2 56 E7 FE D3 6C 82 62 3A 1F F8 93 5A 41 EC F6 4C 1C 7E 72 91 E0 67 FD 92 9A 94 B3 45 63 FC BC 6E 3B BD 41 F7 A4 DA 0E 6B 48 E1 61 5A 7A 7F 4A 50 1E 85 99 CA 8C 47 64 5A A6 1F 5C EC BF 5D 5B 12 A3 13 D6 4A 4D CC E0 AC C7 52 CA 2B E4 1F E5 76 22 9C 91 7F AF 94 21 D6 BC F1 6E CC AA AD E7 15 77 09 10 36 8A 8D F5 35 95 41 30 43 62 C8 09 46 D3 6E AA CD EE F2 87 F0 4B E2 7C DE 71 96 58 CF 24 AF 9F 57 0E 7E 97 FC 73 06 4B 91 3C 5B 12 5E D6 E7 94 E3 4B 91 C9 2E 55 FF 64 00 7F 08 36 05 0F 1C 33 BB A6 3A C2 02 FC 5F B8 B9 4B 92 ED 8A 69 CF 37 F8 2A EA E1 6A AB A4 6F AF 6E C3 D0 B8 92 39 56 C0 38 FA 07 AD 8F 21 79 4E 95 EF B5 13 A1 59 64 70 64 D1 8A 35 1D 25 F6 C6 D5 0D 01 4E FF 62 D4 D5 50 8E A4 C3 EC C1 C0 A0 0C F8 AE 11 60 DE 21 11 8C CB A1 04 F6 04 05 6F 72 4A 27 F2 3E C0 0C 39 11 61 4B F3 CA F0 E6 0A 8C 52 A3 C3 F3 F8 21 18 0B 28 AF 47 55 03 88 A4 03 D5 B6 F0 75 EB BD E2 7C 49 56 22 76 F8 1D EA B8 5B 1A 7F CE 84 00 D5 97 84 B9 74 B3 AD 3D 13 EE F2 60

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

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

Давайте сначала выпишем уравнения зашифрования, реализуемые этой схемой. Если (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 знака известного нам открытого текста, соответствующие им знаки шифртекста и составляем две пары переходов из открытого текста в шифрованный.

Первая пара

Вторая пара

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

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

Первая пара

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

Шифртекст

Сначала с помощью уравнений (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

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

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

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

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

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

Шифртекст

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

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

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

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

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

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

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

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

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

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

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

?(у₉)- ?(у₉-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) Приказ объявить во всех подразделениях Дальнего военного округа. Командир ДВО генерал-майор Безверхов.

Была ли такая телеграмма на самом деле – ничего определенного сказать не могу, дальних военных округов в России много, за всеми не уследишь. Но легенда про армейский приказ считать все группы абелевыми очень долго ходила по 4 факультету ВКШ КГБ.

А вообще-то «Ангстрем – 3» при Т=16 вполне можно поставлять развивающимся странам в качестве братской бескорыстной помощи.

Назад, к балалайкам?

Оглавление книги