Расшифровка шифротекста не зная ключ по XOR

Доброго времени суток. Я новичок в криптографии. Хотелось бы рассказать свой ход мыслей по поводу расшифровки текста по алгоритму 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 01100001 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 111120 0010 0000 - пробел может быть50 0101 0000 - не может быть, тогда бы у нас был не 6F, а 7F. Значит число не 5.60 0110 0000 - не может быть, так как бы сработал XOR, и результат будет 0F70 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 5A7E 62 0d 0a 33 1E 04 07 0716 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 5A7E 62 0d 0a 33 1E 04 07 0716 48 63 68 06 11 0A 46 001B 0D 20 50 11 1D 0B 03 1707 48 47 75 17 17 0F 04 1101 0F 20 77 06 10 41 16 1514 0D 73 20 05 1D 13 46 1706 1A 72 65 0D 06 41 02 1B1D 09 74 69 0C 1C 6C 6C 1916 1C 68 6F 07 01 41 07 1A17 48 61 64 07 00 04 15 0716 1B 2E 20 27 1D 0F 07 001A 07 6E 73 43 13 13 03 5412 0B 63 65 13 06 04 02 541A 06 20 61 43 1C 14 0B 1616 1A 20 6F 05 52 0E 12 1C16 1A 0D 0A 14 13 18 15 541A 06 63 6C 16 16 08 08 1353 0B 68 65 00 19 12 4A 541C 06 6C 69 0D 17 41 16 150A 05 65 6E 17 01 41 07 1A17 48 63 72 06 16 08 12 5410 09 72 64 43 16 0E 08 1507 01 6F 6E 10 5C 41 32 1B7E 62 64 6F 0D 13 15 03 5853 18 6C 65 02 01 04 46 021A 1B 69 74 59 52 16 11 035D 0F 75 74 06 1C 03 03 0614 46 6F 72

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

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

[octopus@octopus crypto]$ ./show-by-key session.0 dict.txt book.txt 9 ahoecaafa~l strff;....P.eafw chepk aze Pr|jevf Gutvnbp`g weq ptues f|r vgrreng dz|atio}..xwthod` a{v addaesfws. D|naa{ons rre5sccepged5{n a }umwwr of3ot}wr..wrys5{ncluwinr2checxs,5}nlinv ptkment` a{v crewit5qard wontfions= Tz..donrte92plea`e c{sit:3wwb<gute}begu.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;....Pleafw check aze Projevf Gutenbp`g web ptues for vgrrent dz|ation..xwthods a{v addresfws. Donaa{ons are5sccepted5{n a numwwr of ot}wr..ways5{ncludinr2checks,5}nline ptkments a{v credit5qard dontfions. Tz..donate92please c{sit: wwb<gutenbegu.or

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

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

[octopus@octopus crypto]$ ./show-by-key session.0 dict.txt book.txt 9 shoecraft 1ll 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 операции над числами, то может и стоит.

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