Взлом шифра - частотный криптоанализ. Часть первая - теория.
https://t.me/ENcoding
Добрый день.
В предыдущих постах мы научились производить шифрование на более - менее примитивном уровне. Но что делать, когда ваши недруги тоже обладают кое - какими знаниями и важную информацию прячут от посторонних глаз, а ключа к зашифрованному тексту у вас как назло нет? Правильно, ломать всё к чертям, а если быть точнее, взламывать :D. Для таких случаев и был создан криптоанализ - наука о методах расшифровки без ключа. Этим же термином обозначают и сам процесс такой расшифровки. К слову, методов взлома существует несколько :
- Атака на основе шифротекста - тот случай, когда кроме зашифрованных сообщений в вашем распоряжении больше ничего нет. Целью такой атаки является получение как можно большего количества открытых текстов, соответствующих имеющимся шифротекстам, а ещё лучше - ключа, которым производилось шифрование. Самый слабый и неудобный вид атаки, если шифр довольно сложен, вероятность взлома стремится к нулю. Впрочем, всё зависит от вашей логики, удачи и дедукции.
- Атака на основе открытых текстов - тот случай, когда смысл отдельных отрывков шифротекста вам известен. На его основе можно произвести дешифровку всего сообщения, а уже после найти ключ и алгоритм шифрования. Известен случай, когда англичанам, безуспешно пытавшимся расшифровать тексты, переданные с помощью немецкой шифровальной машины " Энигма ", произвести взлом помогла фраза " Heil Hitler! ", находящаяся абсолютно в каждом передаваемом сообщении. При таком раскладе вероятность взлома существенно возрастает.
- Атака на основе подобранного открытого текста - тот случай, когда вы имеете несколько открытых текстов и соответствующих им шифротекстов, кроме того, имеется возможность зашифровать несколько предварительно выбранных исходных текстов. Один из основных способов криптоаналитического вскрытия. При таком раскладе целью взломщика становится нахождение ключа либо же создание алгоритма, позволяющего взломать сообщения, зашифрованные с помощью этого ключа. Пример из истории : в 1942 году криптоаналитики ВМС США перехватили японские сообщения, в которых говорилось о готовящейся атаке на загадочный " AF ". Предполагая, что целью является остров Мидуэй, американцы посылают по открытому каналу сообщение, будто бы на острове нехватка пресной воды. После было перехвачено послание противника, в котором докладывалось, что на " AF " не хватает воды. Таким образом, командование было заранее уведомлено о готовящемся захвате. Силы японцев всего за 4 дня были разгромлены. Вероятность взлома ещё выше, чем при двух предыдущих методах.
- Атака на основе адаптивно подобранного открытого текста. Тот случай, когда вы можете прямо во время атаки подбирать открытые тексты и получать их зашифрованные варианты. Цели - получить возможность извлекать информацию из перехваченных шифротекстов либо ключ, сопоставляя открытый и зашифрованный тексты. С помощью данного метода англичане тоже пытались произвести дешифрацию немецких донесений. Например, если противник освобождал какой - либо участок прибрежных вод от мин, британцы посылали сообщение, что тот участок снова был заминирован. Дальнейшие немецкие сообщения сопровождались словом " мины " и названием того самого места, благодаря чему производился довольно эффективный анализ сообщений и получение полностью открытых текстов. Наиболее удачный метод, практически гарантирующий успешный исход атаки.
То были основные виды, однако существуют ещё некоторые :
- Атака на основе подобранного шифротекста - случай, когда вы имеете несколько зашифрованных сообщений и устройство, которое может их расшифровывать. Произведя многократные расшифровки, взломщик на основе открытых текстов может попытаться получить информацию о ключе. Имеет два вида - неадаптивная атака, при которой результаты предыдущих расшифровок не используются, т.е. тексты подбираются заранее, и адаптивная атака, обратная ей.
- Атака на основе подобранного ключа - случай, когда имея лишь информацию о некотором математическом соотношении между ключами, взломщик ведёт наблюдение за работой алгоритма шифрования, использующего несколько ключей.
- Терморектальная атака - случай, когда предыдущие методы не сработали. Производится при помощи нагретого паяльника, введённого в задний проход хранителя нужной вам информации. Грубо, негуманно, но эффективно. Правда, не очень законно, поэтому не рекомендуем.
В этот раз мы разберём с вами частотный криптоанализ, который тоже является одним из методов вскрытия алгоритмов и ключей шифрования.
Частотный криптоанализ
Частотный криптоанализ есть один из его методов, основывающийся на предположении об определённой частоте использования букв алфавита в тексте, которая будет сохранена и при шифровании данного текста. Метод эффективен лишь при наличии довольно больших текстов ( от 1000 символов ) и несёт в себе риск определённой погрешности, достигающих порой колоссальных значений. Для того, чтобы подсчитать частоту использования того или иного символа, необходимо подсчитать его количество в шифротексте, после поделить на длину сообщения и умножить на 100 для выражения в процентах.
Ниже представлено соотношение букв русского алфавита и частоты их использования в сообщениях в порядке убывания:
О - 10,98 %
Е - 8,48 %
А - 8 %
И - 7,37 %
Н - 6,7 %
Т - 6,32 %
С - 5,47 %
Р - 4,75 %
В - 4,53 %
Л - 4,34 %
К - 3,49 %
М - 3,2 %
Д - 2,96 %
П - 2,8 %
У - 2,62 %
Я - 2 %
Ы - 1,9 %
Ь - 1,74 %
Г - 1,69 %
З - 1,64 %
Б - 1,59 %
Ч - 1,45 %
Й - 1,21 %
Х - 0,97 %
Ж - 0,94 %
Ш - 0,72 %
Ю - 0,64 %
Ц - 0,49 %
Щ - 0,36 %
Э - 0,33 %
Ф - 0,27 %
Ъ - 0,04 %
Ё - 0,01 %
Данные весьма усредненные и от текста к тексту выглядеть будут иначе. Наибольших значений погрешность будет достигать при сравнении обычного и, например, технического текстов, в котором частота использования " непопулярных " букв значительно увеличивается.
Несмотря на то, что метод несовершенен и для многих типов шифров попросту не годится, его изучение обязательно для тех, что хочет иметь дело с криптографией, поскольку является базовым алгоритмом взлома, без понимания принципов работ которого невозможно дальнейшее постижение науки. А как взламывать с помощью него шифротексты, мы рассмотрим на конкретном примере в следующих статьях.
============
============