Тема: Частотный анализ текста.

 2020

Ведение.

С распространением письменности в человеческом обществе появилась потребность в обмене письмами и сообщениями, что вызвало необходимость сокрытия содержимого письменных сообщений от посторонних.

На начальном этапе (до начала XVI в.) для защиты информации использовались методы кодирования и стеганографии. Большинство из используемых шифров сводились к перестановке или моноалфавитной подстановке.

Этап формальной криптографии (конец XV – начало XX вв.) связан с появлением формализованных и относительно стойких к ручному криптоанализу шифров. Важная роль на этом этапе принадлежит Леону Батисте Альберти, итальянскому архитектору, который одним из первых предложил многоалфавитную подстановку. Данный шифр, состоял в последовательном "сложении" букв исходного текста с ключом (процедуру можно облегчить с помощью специальной таблицы). Его работа "Трактат о шифре" (1466 г.) считается первой научной работой по криптологии.

Научная криптография (1930 – 60-е гг.) обусловлена появлением криптосистем со строгим математическим обоснованием криптостойкости. К началу 30-х гг. окончательно сформировались разделы математики, являющиеся научной основой криптологии: теория вероятностей и математическая статистика, общая алгебра, теория чисел, начали активно развиваться теория алгоритмов, теория информации, кибернетика. Своеобразным водоразделом стала работа Клода Шеннона "Теория связи в секретных системах" (1949), которая подвела научную базу под криптографию и криптоанализ.

Компьютерная криптография (с 1970-х гг.) обязана своим появлением вычислительным средствам с производительностью, достаточной для реализации криптосистем, обеспечивающих при большой скорости шифрования на несколько порядков более высокую криптостойкость, чем "ручные" и "механические" шифры. Первым классом криптосистем стали блочные шифры. В 70-е гг. был разработан американский стандарт шифрования DES (принят в 1978 г.). Один из его авторов, Хорст Фейстель (сотрудник IBM), описал модель блочных шифро. В середине 70-х гг. ХХ столетия появились асимметричные криптосистемы, которые не требовали передачи секретного ключа между сторонами. Асимметричная криптография открыла сразу несколько новых прикладных направлений, в частности системы электронной цифровой подписи (ЭЦП) и электронных денег.

Актуальность работы заключается в том, что каждый метод криптоанализа добавляет новые требования к алгоритмам шифрования. Частотный метод, в котором по распределению символов в шифртексте выдвигаются гипотезы о ключе шифрования, породил требование равномерного распределения символов в шифртексте. Кроме того, принципы частотного анализа сегодня широко применяются в программах по поиску паролей, фильтрации текстов в поисковых системах, в алгоритмах сжатия информации Целью данной работы является вскрытие текста, зашифрованного шифром моноалфавитной подстановки, без знания ключа.

Для достижения цели необходимо решить следующие задачи:

• Сбор и анализ научной информации о применении частотного анализа для вскрытия шифров моноалфавитной  подстановки.

• Определение частотных характеристик криптограмм.

• Применение полученных данных для вскрытия криптограмм.

• Сделать вывод о возможностях применения частотного анализа при дешифровке текстов моноалфавитной подстановки и рассмотреть область применения данного метода в других областях.

При написании работы использовались следующие методы:

• Эмпирический –  наблюдение, сравнение.

• Теоретический – обобщение результатов, их анализ и выводы.

Теоретическая часть

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

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

Метод частотного криптоанализа известен с IX-го века (работы Ал-Кинди), хотя наиболее известным случаем его применения в реальной жизни, возможно, является дешифровка египетских иероглифов Ж.-Ф. Шампольоном в 1822 году. В художественной литературе наиболее известными упоминаниями являются рассказы «Золотой жук» Эдгара По, «Пляшущие человечки» Конан Дойля, а также роман «Дети капитана Гранта» Жюль Верна.

Начиная с середины XX века большинство используемых алгоритмов шифрования разрабатываются устойчивыми к частотному криптоанализу.

Описание частотного криптоанализа

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

Как упоминалось выше, важными характеристиками текста являются повторяемость букв (количество различных букв в каждом языке ограничено), пар букв, то есть m (m-грамм), сочетаемость букв друг с другом, чередование гласных и согласных и некоторые другие особенности. Примечательно, что эти характеристики являются достаточно устойчивыми.

Идея состоит в подсчете чисел вхождений каждой nm возможных m-грамм в достаточно длинных открытых текстах T=t1t2…tl, составленных из букв алфавита {a1, a2, …, an}. При этом просматриваются подряд идущие m-граммы текста:

t1t2…tm, t2t3… tm+1, …, ti-m+1tl-m+2…tl.

Если L (ai1ai2 … aim) — число появлений m-граммы ai1ai2…aim в тексте T, а L — общее число подсчитанных m-грамм, то при достаточно больших  L частоты L (ai1ai2… aim)/ L, для данной m-граммы мало отличаются друг от друга.

В силу этого, относительную частоту считают приближением вероятности P (ai1ai2…aim) появления данной m-граммы в случайно выбранном месте текста (такой подход принят при статистическом определении вероятности).

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

Но существует некоторая разница значений частот, которая объясняется тем, что частоты существенно зависят не только от длины текста, но и от характера текста. Например, текст может быть технического содержания, где редкая буква Ф может стать довольно частой. Поэтому для надежного определения средней частоты букв желательно иметь набор различных текстов.

В таблице 1 приведены относительные частоты появления русских букв. ^[1]

Кроме того, порядок букв в словах и фразах естественного языка подчиняется определенным статистическим закономерностям. Частотный анализ также учитывает частоту появления различных буквосочетаний: например, пара стоящих рядом букв «ся» в русском языке более вероятна, чем «цы», а «оь» не встречается никогда. Для большинства естественных языков такая статистика документирована. Эти принципы широко применяются в распространенных сегодня программах по подбору паролей. Возможные методы подбора пароля (могут применяться в совокупности)[2]

·                    неоптимизированный перебор;

·                    перебор, оптимизированный по словарям вероятных паролей;

·                    перебор, оптимизированный на основе встречаемости символов и биграмм;

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

·                    перебор с использованием знаний о пользователе. Как правило, опробуются пароли, использование которых представляется наиболее вероятным.

Если программа перебора вначале подбирает наиболее вероятные пароли, а менее вероятные оставляет на потом, то перебор сокращается в десятки и сотни раз. В таблице 2 приводится ряд результатов, полученных при подборе пароля.[3] Числа, указанные в первой колонке таблицы 2, соответствуют сложности полного перебора. Однако применялся оптимизированные перебор, а в первом случае пароль представлял собой два английских слова, записанных без пробела. Таким образом, время перебора сократилось во много раз. Во втором же случае пароль состоял из трех строчных английских букв, двух заглавных английских букв и одной цифры и был абсолютно бессмысленным.

Практическая часть

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

В ходе эксперимента учащимся 8 класса (15 человек) провели урок, посвященный частотному анализу текста. На данном уроке учащимся рассказали о истории развития криптографии и в частности о методе частотного анализа. Объяснили основные принципы и алгоритм использования данного метода дешифровки.

После этого предложили расшифровать текст, зашифрованный методом моноалфавитной подстановки. Данный текст был взят из художественной литературы и содержал около 3400 символов. Для облегчения подсчетов использовалось ПО Excel 2007.

Задание (приведен не полный текст задания):

Спустя 40 минут работы практически все учащиеся (кроме 1) справились с заданием. В результате получили следующий текст:

Выводы

•      Метод моноалфавитной подстановки не маскирует частотные характеристики открытого текста.

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

•      Для повышения стойкости шифра моноалфавитной подстановки при шифровании следует убирать из открытых текстов пробелы и шифровать сообщение без них.

Применение данного метода

Алгоритм Хаффмана 

Один из первых алгоритмов эффективного кодирования информации был предложен Хаффманом в 1952 г. Этот алгоритм стал базой для большого количества программ сжатия информации. Например, кодирование по Хаффману используется в программах сжатия ARJ, ZIP, RAR, в алгоритме сжатия графических изображений с потерями JPEG, а также встроено в современные факс-аппараты.

Эффективное кодирование по Хаффману состоит в представлении наиболее вероятных (часто встречающихся) букв двоичными кодами наименьшей длины, а менее вероятных - кодами большей длины (если все кодовые слова меньшей длины уже исчерпаны). Это делается таким образом, чтобы средняя длина кода на букву исходного сообщения была минимальной.[5]

Лучше всего проиллюстрировать этот алгоритм на простом примере. Имеется пять символов с вероятностями, заданными на рисунке

Рисунок Коды Хаффмана.

Символы объединяются в пары в следующем порядке:

1.    . объединяется с ., и оба заменяются комбинированным символом  . с вероятностью 0.2;

2.    Осталось четыре символа,  с вероятностью 0.4, а также    и  с вероятностями по 0.2.

3.    Произвольно выбираем  и , объединяем их и заменяем вспомогательным символом   с вероятностью 0.4;

4.    Теперь имеется три символа   и   с вероятностями 0.4, 0.2 и 0.4, соответственно. Выбираем и объединяем символы    и  во вспомогательный символ  с вероятностью 0.6;

5.    Наконец, объединяем два оставшихся символа     и   и заменяем на    с вероятностью 1.

Дерево построено. Оно изображено на рисунке слева, «лежа на боку», с корнем справа и пятью листьями слева. Для назначения кодов мы произвольно приписываем бит 1 верхней ветке и бит 0 нижней ветке дерева для каждой пары. В результате получаем следующие коды: 0, 10, 111, 1101 и 1100. Распределение битов по краям - произвольное.

Средняя длина этого кода равна  бит/символ. Очень важно то, что кодов Хаффмана бывает много. Некоторые шаги алгоритма выбирались произвольным образом, поскольку было больше символов с минимальной вероятностью. На рисунке справа показано, как можно объединить символы по-другому и получить иной код Хаффмана (11, 01, 00, 101 и 100). Средняя длина равна  бит/символ как и у предыдущего кода.

Если не использовать сжатие информации, то на один символ приходилось бы 3 бита информации.

Список литературы

1.     Алексеев А. Криптография и криптоанализ: вековая проблема человечества. // Опубликовано: http://infocity.kiev.ua/hack/content/hack008.phtml

2.     Дориченко С.А., Ященко В.В. 25 этюдов о шифрах – Москва «Теис», 2010

3.     Жельников В. Криптография от папируса до компьютера – Москва, ABF, 2015

4.     Загнетко А. Информация доступная и недоступная. // http://pda.cio-world.ru/?action=article&id=273907

5.     Зубов А.Ю. Криптографические методы защиты информации. Совершенные шифры: Учебное пособие. М.: Гелиос АРВ, 2005.

6.     Иванов М.А. криптографические методы защиты информации в компьютерных системах и сетях // М.: КУДИЦ-ОБРАЗ, 2001

7.     Николай Носов. Приключения Незнайки и его друзей //Опубликовано: http://lib.ru/NOSOW/nezn1.txt

8.     Ященко В.В. Введение в криптографию – Москва, МЦНМО, 2012