Частотный анализ во взломе шифров — это одна из методик криптографического анализа, которая основана на предположении о наличии нетривиального статистического распределения отдельных символов и их последовательностей.
Введение
Криптографическим анализом (криптоанализом) является наука о том, как можно расшифровать зашифрованную информацию, без наличия ключа для расшифровки. Криптоанализом так же может называться сам процесс дешифрования. Но наиболее часто под криптоанализом понимают определение ключа шифрования, так как при помощи ключа криптоаналитики могут осуществить расшифровку любого сообщения. Тем не менее, криптоанализ может состоять и в анализе криптосистемы, а не только зашифрованного с ее помощью открытого сообщения, и может включать также методики выявления уязвимостей шифровальных алгоритмов.
Статистическим криптоанализом является один из методов криптоанализа. Как и в каждой задаче, сопряженной с математической статистикой, вводится понятие статистики, то есть, определенной величины, вычисляемой на базе выборки или, в случае с криптоанализом, на базе криптограммы. В идеальном варианте статистика должна быть простой в вычислении и применении, а так же не сильно изменяться от сообщения к сообщению, когда такие сообщения зашифрованы при помощи одного и того же ключа. Целью статистического криптоанализа является расшифровка конечного сообщения при помощи вычисленной статистики.
Частотный анализ во взломе шифров
Частотный анализ основан на гипотезе о том, что символы или последовательности символов в тексте обладают некоторым вероятностным распределением, которое сохраняется при шифровке и дешифровке. Данный метод является одним из самых простых и предоставляет возможность атаки шифров простой замены, в которых символы в сообщении заменены на другие, по определенному не сложному правилу соответствия.
Но подобный метод совершенно непригоден, к примеру, для шифров перестановки. В этих шифрах символы или их последовательности в сообщении просто меняются местами, однако их число всегда постоянно, как в анаграммах. По этой причине опадают все методики, которые основаны на вычислении частот появления символов.
Для полиалфавитных шифров, то есть, шифров, где циклически используются простые шифры замены, подсчет символов так же не даст эффекта, так как для кодирования всех символов используются разные алфавиты. Количество алфавитов и их распределение так же является неизвестным. Одним из самых известных примеров полиалфавитных шифров является шифр Виженера. Он является достаточно простым для понимания и построения, тем не менее после его создания еще в течение трехсот лет не находился способ, позволяющий взломать этот шифр.
Рассмотрим конкретный пример. Предположим, что исходным текстом является: МИНДАЛЬВАНГОГ. Шифрование выполняется следующим образом:
- Необходимо составить таблицу шифров Цезаря по количеству символов в применяемом алфавите. Для нашего случая, в русском алфавите тридцать три буквы. Это означает, что таблица Виженера (квадрат Виженера) должен иметь размер 33х33, и каждая i-ая строчка в этой таблице представляет собой алфавит, который смещен на i символов.
- Далее следует выбрать ключевое слово, пусть это будет, к примеру, МАСЛО. Символы в ключевом слове должны повторяться до тех пор, пока размер не станет равным длине шифруемого текста, то есть, МАСЛОМАСЛОМАС.
- Буквы зашифрованного текста должны определяться по квадрату Виженера, а именно, столбец должен соответствовать символу в исходном тексте, а строчка должна соответствовать символу в ключе. Зашифрованное сообщение будет иметь следующий вид: ЩЙЯРПШЭФМЬРПХ.
На рисунке ниже изображена таблица Виженера.
Рисунок 1. Таблица Виженера. Автор24 — интернет-биржа студенческих работ
Такой шифр в самом деле достаточно трудно взломать, тем не менее выделяющиеся особенности он все-таки имеет. На выходе все же не получится создать равномерное распределение символов (что является идеалом), и это означает, что потенциальные злоумышленники могут определить взаимные связи между зашифрованным сообщением и ключом. Главной проблемой в шифре Виженера является повторение ключа.
Взлом данного шифра может состоять из следующих этапов:
- Определение длины ключа. Для этого следует постепенно брать разные образцы из текста, то есть, вначале сам текст, затем текст из каждой второй буквы, дальше из каждой третьей буквы и так далее. В определенный момент можно отказаться от гипотезы о равномерном распределении символов в данном тексте, то есть, тогда длина ключа считается найденной.
- Выполнение взлома нескольких шифров Цезаря, которые тогда будут легко взламываться.
Определение длины ключа является самой нетривиальной здесь частью. Введем индекс совпадений сообщения m:
Рисунок 2.
где:
- n является количеством символов в алфавите.
- Pi является частотой появления i-го символа в сообщении.
Эмпирически были определены индексы совпадений для текстов на разных языках. Оказалось, что индекс совпадений для совершенно случайных текстов гораздо ниже, чем для осмысленных текстов. При помощи данной эвристики и может быть найдена длина ключа.
Другим вариантом является использование критерия хи-квадрат, для того чтобы проверить гипотезу о распределении символов в сообщении. Тексты, которые получаются выбрасыванием некоторых символов, все равно будут оставаться выборкой из соответствующего распределения. Тогда в критерии хи-квадрат вероятности появления символов могут быть выбраны при помощи частотных таблиц языка.
Не только самые простые шифры подвержены статистическим методам криптоанализа. К примеру, статистические атаки насыщения могут направляться на блочные шифры, которые сегодня повсеместно используются в криптографических протоколах. Еще одним методом взлома блочных шифров является линейный криптоанализ. Он считается одним из самых распространенных подходов. Анализ базируется на построении соотношений между открытым текстом P, ключом K и зашифрованным сообщением C, а далее их применении для определения ключа.
