ОГЛАВЛЕНИЕ

КРИПТОАНАЛИЗ — НАУКА РЕШЕНИЯ ГОЛОВОЛОМОК
Ведущий X-Puzzle делится советами


Задания на криптоанализ присутствуют практически в каждом выпуске X-
Puzzle. Одна из причин этому – многочисленные просьбы, которые сыплются ко
мне в ящик. Однако я не совсем удовлетворен числом присылаемых ответов –
оно значительно меньше общего числа читателей нашего журнала. Это
свидетельствует о том, что многие просто не знают с какой стороны подойти к
этим головоломкам. А ведь зная простейшие методы криптоанализа, на решение
требуется всего несколько минут! Сейчас я покажу, как это делается на примере
реальных задач из рубрики X-Puzzle.

ЧАСТОТНЫЙ АНАЛИЗ

Метод частотного анализа известен уже больше тысячи лет! Изобретателем его
является знаменитый ученый арабского мира IX века (приготовься это прочитать):
Абу Юсуф Якуб ибн-Исхак ибн-Ас-Сабах ибн-Умран ибн-Исмалил аль-Кинди. На
самом деле, если знать, что приставка «абу» означает отец, «ибн» - сын, а «аль» -
уроженец, то имя легко можно перечитать по-русски, а сокращенно ученого у нас
принято называть Аль Кинди. Для рассказа о методе, сразу же возьмем в качестве
примера головоломку из X-Puzzle за номером ][ #58 «Глупенькая секретарша»,
условие которой звучит так:

Глупенькая, но хорошенькая секретарша устраивалась на работу к одному

эксцентричному директору. Директор решил над ней подшутить. На рабочем
компьютере он поменял местами некоторые клавиши и попросил ее напечатать
«на время» одно предложение. Т. к. секретарша не умела печатать вслепую, то
напечатала предложение, не отрывая глаз от клавиатуры, и вот что у нее
получилось:

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

Какое предложение продиктовал эксцентричный директор?

Подсказка: директор поменял местами всего десять пар клавиш.

Понятно, что буквы в шифротексте просто заменяются другими буквами. Если ты
читал рассказ Конан Дойля «Пляшущие человечки», то наверняка помнишь, что
каждый человечек в шифре соответствовал определенной букве алфавита – наша
задача зашифрована аналогично, просто буква прячется не за изображением
человечка, а за другой буквой. Именно для разгадывания таких шифров и
предназначен частотный анализ! Вот суть метода непосредственно из «уст» самого
Аль Кинди:
«Есть способ прочесть зашифрованное послание, написанное на известном тебе
языке. Нужно найти нешифрованный текст на этом языке, размером на страницу или
около того, пересчитать все буквы в нем и увидеть, сколько раз встречается каждая из
букв. Букву, что встречается чаще всех, назови «первая», ту, что на втором месте по
частоте, - «вторая» и так далее, пока не назовешь все буквы алфавита. Затем возьми
шифрованный текст и посчитай все его знаки. Так же выбери тот, что встречается
чаще других, «второй», «третий» и так далее. «Первый» знак служит для замены
«первой» буквы, «второй» - для «второй» буквы и т.д.» Приблизительные частоты
распределения букв уже давно составлены практически для всех языков мира (см.
таблицы распределения букв).




Таким образом, нам нужно только подсчитать частоты букв в нашем зашифрованном
предложении и заменить эти буквы буквами с аналогичными или близкими частотами из
таблицы, и все! Все, да не совсем, т. к. частоты точно можно определить только в больших
шифротекстах, а у нас всего одно маленькое предложение. Но рискнуть, думаю, стоит :).

• Как определяется частота буквы?

Частота буквы определяется следующим образом: подсчитывается сколько раз
она встречается в шифротексте, затем полученное число делится на общее
число символов шифротекста; для выражения в процентном выражении, еще
умножается на 100

Хотя и не сложно произвести расчет для одного предложения вручную, я все равно
попробовал поискать для этого в интернете специализированную программу, и, как и
ожидалось, нашел, причем на русском языке – программа с говорящим названием
Freq 2.0. Программу можно взять на сайте http://corvus.h12.ru/. Несмотря на
небольшую глючность Freq 2.0, работу частотного анализа далее мы рассмотрим в
нем. Запустим Freq и откроем в нем наше зашифрованное предложение (шифротекст
должен быть предварительно сохранен в текстовый файл), см. рисунок 1.




Рис.1. Открыт файл с шифротекстом
Далее перейдем на вкладку «Подсчет» и рассчитаем сначала все частоты появления
букв (не по эталону), см. рисунок 2.




Рис.2. Частоты букв содержащиеся в шифротексте

Как видишь, определилось всего несколько разных частот, что не есть хорошо. Если
бы у нас был большой текст, частоты распределились бы более точно для каждой
буквы шифротекста. Но попробуем провести анализ с тем, что есть. Для этого во
вкладке «Эталон» откроем так называемый эталон для русского теста (RusEtln.txt),
см. рисунок 3.




Рис.3. Открыт эталон для текста на русском

В папке с программой присутствуют два текстовых файла RusEtln.txt и LatEtln.txt, в
них хранятся последовательности букв в убывающем порядке согласно
распределениям эталонных частот (см. таблицы распределения букв). Снова перейдем
на вкладку «Подсчет» и произведем уже подсчет по эталону. Теперь каждая буква из
нашего шифротекста, соответствует определенной эталонной букве, см. рисунок 4.
Рис.4. Буквы шифротекста распределены по эталону

Откроем вкладку «Новый файл» и нажмем кнопку «В окно», чтобы предложение
отобразилось в нижнем окне с подставленными эталонными буквами, см. рисунок 5.




Рис.5. В нижнем окне предложение с подставленными эталонными буквами

Правда, понять что-либо все равно невозможно, но это, как я уже говорил, из-за того,
что у нас очень маленькое предложение, если бы это был большой текст, то наверняка
уже можно было бы прочитать ответ. Но не будем отчаиваться. Если ты внимательно
посмотришь на таблицы распределения букв, то заметишь, что многие буквы имеют
одинаковую частоту. Следовательно, в эталоне нашей программы мы можем смело
поменять их местами. Так, перейдем на вкладку «Эталон» и поменяем местами буквы
«а» и «и» - у них одинаковая частота 0,062. Далее нужно снова вернуться на вкладку
«Подсчет» и сделать подсчет по эталону. Теперь, если перейти на вкладку «Новый
файл» и нажать «В окно» мы получим следующее предложение:

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

Смотри, последнее слово в предложении приобрело осмысленные очертания. Это
может быть случайностью, а может быть и нет. Попробуем сделать еще какие-нибудь
изменения в эталоне. Поменяем теперь буквы не с одинаковыми частотами, а с
близкими, т. е. рядом стоящие в эталоне. Нам никто этого не запрещает делать, т. к.
эталонные частоты, это лишь приблизительные частоты и для разных типов текста
они могут различаться (проза, сленг, технический язык). Поменяем местами, к
примеру, первые буквы в эталоне: «о» и «е». Повторим операции, которые мы делали
выше и получим следующее предложение:

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

Да, не сильно помогло, однако второе слово, очевидно, должно быть словом «ещё». И
того, вместе с «чаю» мы имеем предположительно два расшифрованных слова, а это
значит 5 пар клавиш, которые поменял местами эксцентричный директор:



ч–б

у–а

ю–ж

е–э

щ-з

Попробуем произвести замену этих пар в первоначальном зашифрованном
предложении:

Мъешл ещё этиг сяхкиг рфанцузскиг буьок ва дыпей же чаю.

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

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

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

XOR

Но частотный анализ бессилен перед другими типами шифровок, когда одна буква
может иметь разные значения в одном и том же шифротексте. Так, к примеру,
шифрует знаменитый XOR при условии, что ключ, которым кодируют, больше
одного знака. C начала вспомним, что такое вообще XOR. XOR – это операция
логического исключающего ИЛИ, которая имеет следующую семантику:



0 xor 1 = 1

1 xor 0 = 1

0 xor 0 = 0

1 xor 1 = 0
Например, буква «А» (латинская) в кодировке ASCII имеет код 41h или 1000001 в
двоичном виде, а цифра «1» 31h=110001. Проксорим эти буквы (точнее их коды):



A = 1000001

XOR

1 = 0110001

-----------

p = 1110000

Получился ответ 1110000, а это есть двоичный ASCII-код буквы «p». На этом
принципе и основа шифровка XOR! Ну а что если дан ключ «1984». Закодируем с
помощью него фразу «Hacker Hacker Hacker». Это может сделать, например,
следующая программа на Си (протестировано в среде Visual C++ 6.0):



#include <stdio.h>



int main() {



char str[]="Hacker Hacker Hacker";

char key[]="1984";

int i=0, j=0;



printf("%s\n", str);

while (str[i] != '\0') {

if (j>3) j=0;

printf("%c", str[i++]^=key[j++]);

}

printf("\n");



return 0;

}

Посмотрим на схеме, что происходит в действительности, см. рисунок 6.
Рис.6. К предложению str применяем оператор xor с ключом «1984»

Как видишь, одна и та же буква может быть закодирована по-разному, например
буква «H» в шифротексте принимает следующие значения: «y» «|» и «p» (см. рисунок
6). XOR представляет собой, по сути, шифр Вижнера. Такой шифр частотным
анализом вскрыть невозможно!

АТАКА ПО ОТКРЫТОМУ ТЕКСТУ

У XOR есть еще одно важное свойство, которое нужно всегда держать в голове:



X xor Key = Y

Y xor Key = X

X xor Y = Key

То есть, зная хотя бы часть открытого текста - можно получить ключ! Посмотрим это
еще на одном примере из рубрики X-Puzzle (][ #55):

M.J.Ash скачал третью версию уже всем знакомой программы CryptFuck! Уверенной
рукой Эш набрал в поле ввода слово «Ivan» (без кавычек) и нажал кнопку Crypt,
программа выдала следующий шифр:

{@Q^

Затем он набрал «Sklyarov» и получил следующее:

a]\ISD_F

И что-то опять не понравилось ведущему самой варезной рубрики. Набрав последнее
слово «Ash» и посмотрев на полученный шифр, M.J.Ash окончательно разгадал
алгоритм шифрования, после чего ему ничего не оставалось, как удалить программу
со своего винчестера (он совершенно не хотел рекомендовать читателям программу
со столь нестойким алгоритмом шифрования).

Как «CryptFuck v3.1» зашифровал слово «Ash»?

Руководствуясь вышеназванным свойством XOR, попробуем сделать следующее:

Sklyarov

XOR

a]\ISD_F
--------

26002600

Ясно, что ключ, которым было зашифровано слово «Sklyarov» есть «2600»!
Применим его к слову «Ash» и получим ответ «sEX». Вот и все! Решение заняло не
больше минуты! И я, честно говоря, был удивлен, что тогда пришло так мало ответов.

Ну а представим, что нам первоначально неизвестно вообще ни одного участка
открытого текста (что чаще всего и бывает в реальности). Например, нужно
расшифровать следующий текст:




Т. к. частотный анализ в данном случае не поможет, то попробуем произвести атаку
по открытому тексту. Что это значит? Просто попробуем на удачу поискать слова,
которые предположительно могут оказаться в зашифрованном тексте. Например, для
английского языка с большой долей вероятности это могут быть: and, are, with, than и
т. д. Но мы пойдем нестандартным путем и попробуем поискать слово fuck :). Для
этого проксорим шифротекст этим словом и вот, что получим в итоге:




Здесь должен сказать, что вместо непечатных символов, типа разных стрелок и т. п., в
программе на Си нужно указывать их коды, например, так «\x13». Если в
шифротексте попадается обратный слэш, то его нужно удвоить «\\», чтобы
компилятор не выдавал ошибку.
Но посмотрим внимательно на полученный результат. Заметно, что присутствуют
похожие последовательности: «231» и «1231», это может быть, опять же, простым
совпадением, а может быть и нет. Попробуем взять в качестве ключа «123» и
проксорить им первоначальный шифротекст. Вот, что мы получим:

Fuck your mother all to fuck hell!

Нам повезло, что ключ оказался таким маленьким! Если бы он был большим
(длинным), то пришлось бы угадывать различные слова в шифротексте, выискивать
одинаковые последовательности и делать попытки составить из них полноценное
ключевое слово.

Конечно, я рассказал далеко не обо всех методах криптоанализа, но того, что ты уже
знаешь, достаточно, чтобы вскрыть большинство защит :). Узнать о других методах и
углубить свои знания ты сможешь благодаря умным книгам по криптоанализу и
криптографии (Рекомендую книгу Брюса Шнайера «Прикладная криптография»).

Удачи в рубрике X-Puzzle! ;)

Что такое Криптология?

Криптология (с греческого kryptos - тайный, logos - наука) — наука,
занимающаяся изучением защиты информации путем ее преобразования.
Криптология включает в себя два направления - криптографию и криптоанализ.
Криптография изучает способы преобразования информации с целью ее
защиты, а криптоанализ исследует способы расшифровки информации без
знания ключей.

http://www.sklyaroff.ru/x6.htm



ОГЛАВЛЕНИЕ