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

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

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 и известна подстановка π:

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

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

Давайте сначала выпишем уравнения зашифрования, реализуемые этой схемой. Если (y1,y2,…,y8) – блок, записанный в первом регистре сдвига «Ангстрем-3», то за один такт работы схемы он перейдет в блок (y2,y3,…,y9), где y9 = π(y1+y2+y8+x1), х1 – первый байт неизвестного ключа. В общем случае, если последовательность всех заполнений первого регистра сдвига обозначить как у1,у2,….,у23,у24, где (y1,y2,…,y8) – блок открытого текста, (y17,y18,…,y24) – блок шифртекста, то для любого i≥9 будет справедливо:

yi = π(yi-8+yi-7+yi-1+xi-8)

Преобразование блока (yi, yi+1,…yi+7) в блок (yi+1,yi+2,…,yi+8) за один такт обозначим как δxi. Очевидно, что это взаимно-однозначное преобразование, поскольку π - подстановка:

δxi (yi, yi+1,…yi+7) = (yi+1,yi+2,…, π(yi+yi+1+yi+7+xi))

δxi - это подстановка на множестве Z/264. Тогда все преобразование, осуществляемое схемой «Ангстрем-3», будет выглядеть как произведение подстановок:

δх1,х2,…,х16 = δx1δx2…δx16

Рассмотрим преобразование θ(у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, т.е.