Криптография и свобода - Масленников Михаил

содержатся все ненулевые элементы из Z/2ⁿ, а какой-то один элемент встретился ровно 2 раза.

Просуммируем соотношение (7) по всем k от 0 до 2ⁿ-1. Поскольку П – подстановка, то в правой части суммы получается 0, следовательно, сумма всех значений j_k также должна быть нулевой.

Но среди j,j₁,…,j₂ⁿ_-1 содержатся все ненулевые элементы из Z/2ⁿ, а какой-то один элемент встретился ровно 2 раза. Поскольку сумма (по модулю 2ⁿ) всех ненулевых элементов кольца Z/2ⁿ равна 2^n-1(2ⁿ-1) = 2^n-1, то элементом, встретившимся два раза, должно быть 2^n-1.

Тогда, в силу свойства p_ij = p₍₂ⁿ_-i)(2ⁿ_-j) для любого значения i должно выполняться

p_i2^n-1 = p₍₂ⁿ_-i)2^n-1 = 2

и при i<>2^n-1 получается, что в 2^n-1 столбце как минимум 2 элемента равны 2. Следовательно, если некоторая i-я строка при i<>2^n-1 целиком ненулевая, то 2^n-1 столбец заведомо содержит хотя бы один нулевой элемент, т.е. множество (GП)² не является 2-транзитивным ни при какой подстановке П.

И еще отсюда сразу же вытекает, что общее число нулей в матрице P(П) не может быть меньше, чем 2ⁿ-3. В этом случае в матрице ровно две ненулевых строки, расположенных симметрично друг от друга, а в средней строке с номером 2^n-1 ровно одно нулевое значение посередине: p₍₂^n-1₎₍₂^n-1₎ = 0.

Подобными же методами легко показать, что в общем случае множество (GП)^k является 2-транзитивным при k>2 в том и только том случае, когда матрица P(П)^k-1 не содержит нулей. В частности, множество (GП)³ является 2-транзитивным тогда и только тогда, когда матрица P(П)² не содержит нулей.

Стало ясно, в каком направлении вести математические раскопки теории шифров на новой элементной базе: изучать матрицы P(П) для различных подстановок П. Здесь сразу же выделялись плохие подстановки – это линейные преобразования вида

П(x) = ax+b

В этом случае при любом фиксированном i<>0 система (2) имеет решение только при одном значении j<>0, такая матрица заведомо не будет положительной ни в какой степени и свойство 2-транзитивности недостижимо. Число нулей у такой матрицы будет максимальным.

А можно ли построить подстановки с минимально возможным числом нулей в матрице P(П)? Этот вопрос уже гораздо интереснее, простого и тривиального ответа на него нет. Пока. Но в следующих главах этой книги ситуация проясниться и в конечном итоге получится очень красивый результат.

Но это больше теоретические дебри. С точки зрения практического применения гораздо важнее знать, чего можно ожидать от матрицы P(П) при случайном и равновероятном выборе П. И здесь были доказаны очень важные теоремы о том, что в среднем ненулевых элементов в этой матрице будет примерно 2/3, что с вероятностью, близкой к 1, при случайном и равновероятном выборе П матрица P(П)² не будет содержать нулевых элементов, а группа будет совпадать с симметрической. В общем, все то, что требуется для использования подстановки П в качестве случайного разового ключа.

Вот такая была предыстория работ по шифрам на новой элементной базе. А ребята из НИИ Автоматики, по мотивам всех этих результатов, придумали следующую схему блочного шифра, работающего на основе байтового регистра сдвига и использующего только самые типовые операции с байтами, которые заложены в архитектуру появлявшихся тогда микропроцессоров. Эту схему назвали «Ангстрем-3».

В ней два регистра сдвига, работающих с байтами. В первый регистр сдвига длиной 8 байт записывается 8-байтовый блок открытого текста, во второй – ключ, или как его еще можно здесь назвать входное слово, длины Т для первого регистра. Схема крутится Т тактов, после чего заполнение первого регистра выдается в качестве 8 байтового блока шифртекста. Типичный блочный шифр, все операции сложения – в кольце Z/256, реализация – изумительно простая, если писать программу, то это буквально две-три строки.

Но программы будут позже, а пока, в 1980 году, эту схему предполагалось реализовывать аппаратно, с помощью типовых микропроцессоров, работающих с байтами. Идеи подстановки-ключа тоже появятся позже, первоначально предполагалось П выбрать и зафиксировать. А главный вопрос, который интересовал НИИ Автоматики – до какого предела можно уменьшать значение Т, количество тактов, которые должна отработать схема для зашифрования одного блока. Чем меньше Т, тем выше скорость шифрования, а это было для них определяющим фактором.

– Нельзя ли выбрать Т=16?

– Нужно подумать.

Так начиналась моя осмысленная работа в Теоретическом отделе. Перед глазами – чистая тетрадь, отчеты 4 факультета и НИИ Автоматики, сиди и думай, нельзя ли выбрать Т=16.

Глава 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