Доброго времени суток. Я новичок в криптографии. Хотелось бы рассказать свой ход мыслей по поводу расшифровки текста по алгоритму XOR, когда не знаешь ключ.

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

С XOR другая ситуация. Алгоритм простой, но сложность есть. Я скачал книгу с gutenberg project в текстовом формате и также взял словарик в линуксе. Сделал получение случайным образом позицию в книге и случайный ключ из словаря.

Программа, которая отображает дамп шифра, сохраняет в файле session позиции для проверки ответа.

Теперь я хочу показать сам дамп памяти, который подлежит расшифровке.

****| 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F
-----------------------------------------------------
0000| 1F 04 4F 16 17 13 07 00 5A 7E 62 62 6F 33 1E 04 
0010| 07 07 16 48 0C 0D 06 11 0A 46 00 1B 0D 4F 35 11 
0020| 1D 0B 03 17 07 48 28 10 17 17 0F 04 11 01 0F 4F 
0030| 12 06 10 41 16 15 14 0D 1C 45 05 1D 13 46 17 06 
0040| 1A 1D 00 0D 06 41 02 1B 1D 09 1B 0C 0C 1C 6C 6C 
0050| 19 16 1C 07 0A 07 01 41 07 1A 17 48 0E 01 07 00 
0060| 04 15 07 16 1B 41 45 27 1D 0F 07 00 1A 07 01 16 
0070| 43 13 13 03 54 12 0B 0C 00 13 06 04 02 54 1A 06 
0080| 4F 04 43 1C 14 0B 16 16 1A 4F 0A 05 52 0E 12 1C 
0090| 16 1A 62 6F 14 13 18 15 54 1A 06 0C 09 16 16 08 
00a0| 08 13 53 0B 07 00 00 19 12 4A 54 1C 06 03 0C 0D 
00b0| 17 41 16 15 0A 05 0A 0B 17 01 41 07 1A 17 48 0C 
00c0| 17 06 16 08 12 54 10 09 1D 01 43 16 0E 08 15 07 
00d0| 01 00 0B 10 5C 41 32 1B 7E 62 0B 0A 0D 13 15 03 
00e0| 58 53 18 03 00 02 01 04 46 02 1A 1B 06 11 59 52 
00f0| 16 11 03 5D 0F 1A 11 06 1C 03 03 06 14 46 00 17

В первую очередь я стал думать, как можно вообще это анализировать? Взяв таблицу ascii на вооружение, я обнаружил, что байт по смещению 0x02 содержит символ 4F.

Я предположил, что здесь может быть пробел, так как XOR операция на затронула этот байт. Дело в том, что XOR работает так.

0010 0110
0001 0100
_________
0011 0010

А у нас 4F. 4F, это

0100 1111

Я стал думать. Старший полубайт я решил называть группой, чтобы было удобно описывать это. Младший полубайт подгруппой.

Текст у нас на английском языке. А это значит, что меньше 0x20 буква не может быть. Да, есть ещё перенос строки, но я пока об этом не думаю. Предположим пока, что мы рассматриваем цифры старше 0x20. Тогда, числа от 0x30-0x39 это символьное представление чисел '0' - '9'.

Остается группа c 4, 5, 6, 7. Но группа 4,5,6,7 не может быть у ключа, если результат не 0x20 у текста. Получается, что в действительности там скорее всего пробел под номером 0x20.

Пока это только предположения, так как в тексте может быть число, например 0x30, а у ключа может быть группа 0x7F, тогда с помощью XOR будет получаться 0x4F.

Теорию надо проверить и возьмём 0x20 в тексте, так как они должны встречаться, пробелы, и тогда получается, что наш ключ в позиции 0x2 может быть 0x6F, если это пробел. Вообще я выделил такие вот варианты.

В 4F может быть пробел, или " или ’ или , или . или ! Тогда

  • 20 пробел, тогда 6F ‘o’

  • 21 !, тогда 6E ‘n’

  • 22 ", тогда 6C ‘l’

  • 27 ', тогда 68 ‘h’

  • 2C , тогда 62 ‘b’

  • 2E ., тогда 61 ‘a’

Что ж. Дальше всё равно сложно анализировать, так как мы не знаем размер ключа. Тогда я додумался сделать блочный сортировщик шифротекста. Например для 5 символов получилось так.

1F 04 4F 16 17 
13 07 00 5A 7E 
62 62 6F 33 1E 
04 07 07 16 48 
0C 0D 06 11 0A 
46 00 1B 0D 4F 
35 11 1D 0B 03 
17 07 48 28 10 
17 17 0F 04 11 
01 0F 4F 12 06 
10 41 16 15 14 
0D 1C 45 05 1D 
13 46 17 06 1A 
1D 00 0D 06 41 
02 1B 1D 09 1B

Что мы должны увидеть здесь? Я думаю, что если у нас ключ должен иметь группу 0x6X, то значит, что в этой колонке не могут быть числа, которые будут равны 6.

В данном случае, я думаю, что ключ из пяти букв не подходит, так как в 3 строке мы имеем 0x6F, что не может соответствовать нашей группе, потому что бы в таком случае, XOR бы сделал своё дело и здесь оказался бы ноль в группе 0x0X.

Тогда я стал увеличивать размер блока и смотреть на результаты.

Вообще, в третьей колонке никогда не должно оказаться 6, хотя нет, может оказаться, если в этой колонке будет 0xa, то есть символ переноса строки. В таком случае, этот символ должен быть редким. Я додумался, что если у нас символ 0x6F, то вероятность такая.

6F 0110 1111
20 0010 0000 - пробел может быть
50 0101 0000 - не может быть, тогда бы у нас был не 6F, а 7F. Значит число не 5.
60 0110 0000 - не может быть, так как бы сработал XOR, и результат будет 0F
70 0111 0000 - не может быть, так как 7 не может произвестись из 6, было бы 3.

Значит, получается, что во 2 позиции могут быть группы 4, 0, 1. Если другие группы, то значит, что длина ключа неправильная.

Ищем с такими значениями теперь длину ключа.

Я уж было думал, что нашел длину ключа, но вот что оказалось странным.

1F 04 4F 16 17 13 07 00 5A 
7E 62 62 6F 33 1E 04 07 07 
16 48 0C 0D 06 11 0A 46 00 
1B 0D 4F 35 11 1D 0B 03 17 
07 48 28 10 17 17 0F 04 11 
01 0F 4F 12 06 10 41 16 15 
14 0D 1C 45 05 1D 13 46 17 
06 1A 1D 00 0D 06 41 02 1B 
1D 09 1B 0C 0C 1C 6C 6C 19 
16 1C 07 0A 07 01 41 07 1A 
17 48 0E 01 07 00 04 15 07 
16 1B 41 45 27 1D 0F 07 00 
1A 07 01 16 43 13 13 03 54 
12 0B 0C 00 13 06 04 02 54 
1A 06 4F 04 43 1C 14 0B 16 
16 1A 4F 0A 05 52 0E 12 1C 
16 1A 62 6F 14 13 18 15 54 
1A 06 0C 09 16 16 08 08 13 
53 0B 07 00 00 19 12 4A 54 
1C 06 03 0C 0D 17 41 16 15 
0A 05 0A 0B 17 01 41 07 1A 
17 48 0C 17 06 16 08 12 54 
10 09 1D 01 43 16 0E 08 15 
07 01 00 0B 10 5C 41 32 1B 
7E 62 0B 0A 0D 13 15 03 58 
53 18 03 00 02 01 04 46 02 
1A 1B 06 11 59 52 16 11 03 
5D 0F 1A 11 06 1C 03 03 06 
14 46 00 17

Как можно видеть, в пятой строке в позиции 0x2, если считать от нуля, будет число 0x28. Но 0x28 никак получиться из 0x6F, хотя, нет, стоп, может. Если у нас будет в этом месте число 0x4X, то XOR 4 и 6 будет в результате давать 2. Хорошо. Значит мы можем видеть в группе 0, 1, 2, 4.

Кажется я нашел длину ключа. Значит наш ключ равен длине 9. Довольно большое слово.

Что делать дальше?

Кстати, там где 00 встречается, это значит, что байт по XOR имеет полное совпадение. Тут тоже можно попробовать анализировать, но сначала нам надо выяснить, что если у нас пробел всё таки там на второй позиции, то значит, что мы имеем число 0x6F, а это значит, что там у нас 'o' буква.

Тогда можно восстановить каждую букву в этом столбце. Сделаем это.

У меня получилось вот что.

9 символов.

      6F  
       o   
__________________________
1F 04 20 16 17 13 07 00 5A  
7E 62 0d 6F 33 1E 04 07 07  
16 48 63 0D 06 11 0A 46 00  
1B 0D 20 35 11 1D 0B 03 17  
07 48 47 10 17 17 0F 04 11  
01 0F 20 12 06 10 41 16 15  
14 0D 73 45 05 1D 13 46 17  
06 1A 72 00 0D 06 41 02 1B  
1D 09 74 0C 0C 1C 6C 6C 19  
16 1C 68 0A 07 01 41 07 1A  
17 48 61 01 07 00 04 15 07  
16 1B 2E 45 27 1D 0F 07 00  
1A 07 6E 16 43 13 13 03 54  
12 0B 63 00 13 06 04 02 54  
1A 06 20 04 43 1C 14 0B 16  
16 1A 20 0A 05 52 0E 12 1C  
16 1A 0D 6F 14 13 18 15 54  
1A 06 63 09 16 16 08 08 13  
53 0B 68 00 00 19 12 4A 54  
1C 06 6C 0C 0D 17 41 16 15  
0A 05 65 0B 17 01 41 07 1A  
17 48 63 17 06 16 08 12 54  
10 09 72 01 43 16 0E 08 15  
07 01 6F 0B 10 5C 41 32 1B  
7E 62 64 0A 0D 13 15 03 58  
53 18 6C 00 02 01 04 46 02  
1A 1B 69 11 59 52 16 11 03  
5D 0F 75 11 06 1C 03 03 06  
14 46 6F 17

Я поменял все символы с помощью обратного XOR с 6F. Также я обнаружил, что есть символ 0x0d. Я решил убедиться и посмотреть в книге через дамп, если ли такой символ, ведь если так, то это бы означало, что книга была создана в Windows редакторе, так как только там, насколько я знаю, строки заканчиваются \r\n, то есть 0x0d 0x0a. Я убедился, что это действительно как в windows. Эта шифрограмма взята из какой-то середины книги, так что я никак не нарушил кайф разгадать шифр и пока не знаю, что за текст там прячется. Но так как я всё ещё обучаюсь этому делу, то думаю, что мне нужно было точно убедиться, для опыта, что я действительно на правильном пути. Что ж, значит скорее всего я угадал с длинной ключа и третий символ, это 'o'. А так как мы обнаружили, что это в windows сделано и у нас есть символ 0x0d, то это значит, что следующий символ должен быть 0x0a. Тогда мы сможем обнаружить следующий символ в ключе. Посмотрим, что получится.

9 символов.

      6F 65
       o  e
__________________________
1F 04 20 73 17 13 07 00 5A
7E 62 0d 0a 33 1E 04 07 07
16 48 63 68 06 11 0A 46 00  
1B 0D 20 50 11 1D 0B 03 17  
07 48 47 75 17 17 0F 04 11  
01 0F 20 77 06 10 41 16 15  
14 0D 73 20 05 1D 13 46 17  
06 1A 72 65 0D 06 41 02 1B  
1D 09 74 69 0C 1C 6C 6C 19  
16 1C 68 6F 07 01 41 07 1A  
17 48 61 64 07 00 04 15 07  
16 1B 2E 20 27 1D 0F 07 00  
1A 07 6E 73 43 13 13 03 54  
12 0B 63 65 13 06 04 02 54  
1A 06 20 61 43 1C 14 0B 16  
16 1A 20 6F 05 52 0E 12 1C  
16 1A 0D 0A 14 13 18 15 54  
1A 06 63 6C 16 16 08 08 13  
53 0B 68 65 00 19 12 4A 54  
1C 06 6C 69 0D 17 41 16 15  
0A 05 65 6E 17 01 41 07 1A  
17 48 63 72 06 16 08 12 54  
10 09 72 64 43 16 0E 08 15  
07 01 6F 6E 10 5C 41 32 1B  
7E 62 64 6F 0D 13 15 03 58  
53 18 6C 65 02 01 04 46 02  
1A 1B 69 74 59 52 16 11 03  
5D 0F 75 74 06 1C 03 03 06  
14 46 6F 72

Итак, я восстановил два символа ключа. Дальше я думаю, что можно сделать сложный анализ, так как я другого выхода не вижу, это определить что скрывается за байтами 00. У нас же есть столбец с байтами и в некоторых мы видим, что там 0x00. Можно ли вообще из этого что-то вывести? Я думаю, что мне пора сходить на прогулку и обдумать это.

Прогуливаясь по улице, я пытался осознать, можно ли вообще найти символ, если есть нулевой байт и не находил ответа. Зато я подумал, что можно ведь просто находить пробел. В большинстве своём пробелы имеют яркую черту в таком шифротексте. Попробуем тогда взять и идентифицировать следующую букву в ключе после 'e'.

Несколько раз в четвёртом столбце встречается символ 43, Кажется это похоже на пробел. Что ж, то это символ 0x63.

Проверим гипотезу. Прошу обратить внимание, чтобы эффект быть действенным, посмотрим на 17 строку, на второй символ от нуля. Там 0x2E, это уже расшифрованный символ и он обозначает точку, а по правилам письма, после точки мы ставим пробел, а потом начинается слово с большой буквы. Проверим и это. Возьмём наш 63 ^ 27 = 44, а 0x44 это у нас 'D'. Большая буква, ага. Значит по пробелам мы легко может восстановить весь ключ. Что ж, будем постепенно проверять, пока не додумаемся какой там ключ. Как можно понять, я сейчас все пробелы превращу в ключ и посмотрю, правильный ли будет ответ.

Я восстановил часть ключа, но так и не понял, что это за слово. Да и я пока полагаюсь на то, что пробелы действительно открывают возможность узнать ключ. Вот как сейчас выглядит. Я не стал переписывать байты в шифротексте.

9 символов.

   68 6F 65 63    61 66
    h  o  e  c     a  f
__________________________
1F 04 20 73 17 13 07 00 5A
7E 62 0d 0a 33 1E 04 07 07
16 48 63 68 06 11 0A 46 00
1B 0D 20 50 11 1D 0B 03 17
07 48 47 75 17 17 0F 04 11
01 0F 20 77 06 10 41 16 15
14 0D 73 20 05 1D 13 46 17
06 1A 72 65 0D 06 41 02 1B
1D 09 74 69 0C 1C 6C 6C 19
16 1C 68 6F 07 01 41 07 1A
17 48 61 64 07 00 04 15 07
16 1B 2E 20 27 1D 0F 07 00
1A 07 6E 73 43 13 13 03 54
12 0B 63 65 13 06 04 02 54
1A 06 20 61 43 1C 14 0B 16
16 1A 20 6F 05 52 0E 12 1C
16 1A 0D 0A 14 13 18 15 54
1A 06 63 6C 16 16 08 08 13
53 0B 68 65 00 19 12 4A 54
1C 06 6C 69 0D 17 41 16 15
0A 05 65 6E 17 01 41 07 1A
17 48 63 72 06 16 08 12 54
10 09 72 64 43 16 0E 08 15
07 01 6F 6E 10 5C 41 32 1B
7E 62 64 6F 0D 13 15 03 58
53 18 6C 65 02 01 04 46 02
1A 1B 69 74 59 52 16 11 03
5D 0F 75 74 06 1C 03 03 06
14 46 6F 72

Дальше я подумал, что стоит написать программу, которая будет расшифровывать этот текст, чтобы додумать, где в предложении могут быть знакомые части слов. Я стал писать утилиту.

Получилось вот что.

[octopus@octopus crypto]$ ./show-by-key session.0 dict.txt book.txt 9 ahoecaafa
~l strff;
....P.eaf
w chepk a
ze Pr|jev
f Gutvnbp
`g weq pt
ues f|r v
grreng dz
|atio}..x
wthod` a{
v addaesf
ws. D|naa
{ons rre5
sccepged5
{n a }umw
wr of3ot}
wr..wrys5
{ncluwinr
2checxs,5
}nlinv pt
kment` a{
v crewit5
qard wont
fions= Tz
..donrte9
2plea`e c
{sit:3wwb
<gute}beg
u.or

Я вижу, что в 4 строке например может быть слово check. Там символ как раз неразгадан. Попробуем найти символ, который бы соответсовал ему.

   68 6F 65 63    61 66
    h  o  e  c     a  f
__________________________
1F 04 20 73 17 13 07 00 5A  
7E 62 0d 0a 33 1E 04 07 07  
16 48 63 68 06 11 0A 46 00 <- в 6 строке после 06 байта

После 06 байта стоит 0x11. Смотрим. Должен быть 'c', а это у нас символ 0x63. 63 ^ 11 = 72. 72 это r.

Получилось.

~l staff;
....Pleaf
w check a
ze Projev
f Gutenbp
`g web pt
ues for v
grrent dz
|ation..x
wthods a{
v addresf
ws. Donaa
{ons are5
sccepted5
{n a numw
wr of ot}
wr..ways5
{ncludinr
2checks,5
}nline pt
kments a{
v credit5
qard dont
fions. Tz
..donate9
2please c
{sit: wwb
<gutenbeg
u.or

Вижу слово Pleafw, который должен быть Please. Я и не думал, что шифр будет где-то в конце книги, блин. Ну ладно, восстановим.

Таким образом я восстановил ключ. и он получился shoecraft. А текст вот как перевёлся.

[octopus@octopus crypto]$ ./show-by-key session.0 dict.txt book.txt 9 shoecraft 1
ll staff.....Please check the Project Gutenberg web pages for current donation..methods and addresses. Donations are accepted in a number of other..ways including checks, online payments and credit card donations. To..donate, please visit: www.gutenberg.or

Ух какое классное приключение. Даже и не знаю, стоит ли попробовать ещё подобные шифры по разбирать, если в низ узкое место, это пробелы. Хотя, если взять с собой блокнотик и тренировать в уме XOR операции над числами, то может и стоит.

Спасибо за внимание.