VI Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Применение частотного криптоанализа в написании программы дешифратора
Автор работы награжден дипломом победителя III степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Введение
В настоящее время первостепенным фактором, влияющим на политическую и экономическую составляющие национальной безопасности, является степень защищенности информации и информационной среды. Вследствие чего большое значение приобретают вопросы обеспечения безопасности информационных и телекоммуникационных технологий и гарантированной защиты данных в компьютерных сетях экономически значимых структур. О необходимости надежной защиты свидетельствуют многочисленные компьютерные преступления, совершаемые как в кредитно-финансовой сфере, так и в государственных органах.
Защита информации в компьютерных системах обладает рядом специфических особенностей, связанных с тем, что информация не является жестко связанной с носителем, может легко и быстро копироваться и передаваться по каналам связи. Известно очень большое число угроз информации, которые могут быть реализованы как со стороны внешних нарушителей, так и со стороны внутренних нарушителей.
В данной работе рассматривается решение проблем защиты электронной информации на базе использования криптографических методов, которые позволяют решать важнейшие проблемы защищенной автоматизированной обработки и передачи данных
Цель работы: Изучить методы частотного криптоанализа для написания программы дешифратора.
Цель достигается посредством решения следующих задач:
ознакомиться с простейшими методами шифрования информации;
изучить метод частотного криптоанализа;
выбрать язык, текст на котором будет дешифроваться;
реализовать алгоритмы на алгоритмическом языке;
проанализировать работу.
Простейшие методы шифрования информации
Шифр Цезаря, также известный как шифр сдвига, код Цезаря или сдвиг Цезаря — один из самых простых и наиболее широко известных методов шифрования.
Шифр Цезаря — это вид шифра подстановки, в котором каждый символ в открытом тексте заменяется символом, находящимся на некотором постоянном числе позиций левее или правее него в алфавите. Например, в шифре со сдвигом вправо на 3, А была бы заменена на Г, Б станет Д, и так далее.
Шифр назван в честь римского императора Гая Юлия Цезаря, использовавшего его для секретной переписки со своими генералами.
Шаг шифрования, выполняемый шифром Цезаря, часто включается как часть более сложных схем, таких как шифр Виженера, и все ещё имеет современное приложение в системе ROT13. Как и всемоноалфавитные шифры, шифр Цезаря легко взламывается и не имеет практически никакого применения на практике.
Криптоанализ
Криптоанализ (от др.-греч κρυπτός — скрытый и анализ) — наука о методах расшифровки зашифрованной информации без предназначенного для такой расшифровки ключа.
Термин был введён американским криптографом Уильямом Ф. Фридманом в 1920 году. Неформально криптоанализ называют также взломом шифра.
В большинстве случаев под криптоанализом понимается выяснение ключа; криптоанализ включает также методы выявления уязвимости криптографических алгоритмов или протоколов.
Первоначально методы криптоанализа основывались на лингвистических закономерностях естественного текста и реализовывались с использованием только карандаша и бумаги. Со временем в криптоанализе нарастает роль чисто математических методов, для реализации которых используются специализированные криптоаналитические компьютеры.
Попытку раскрытия конкретного шифра с применением методов криптоанализа называют криптографической атакой на этот шифр. Криптографическую атаку, в ходе которой раскрыть шифр удалось, называют взломом или вскрытием.
История криптоанализа
Криптоанализ эволюционировал вместе с развитием криптографии: новые, более совершенные шифрыприходили на смену уже взломанным системам кодирования только для того, чтобы криптоаналитикиизобрели более изощренные методы взлома систем шифрования. Понятия криптографии и криптоанализанеразрывно связаны друг с другом: для того, чтобы создать устойчивую ко взлому систему, необходимоучесть все возможные способы атак на неё.
Частотный криптоанализ
Частотный анализ, частотный криптоанализ — один из методов криптоанализа, основывающийся на предположении о существовании нетривиального статистического распределения отдельных символов и их последовательностей как в открытом тексте, так и в шифротексте, которое, с точностью до замены символов, будет сохраняться в процессе шифрования и дешифрования.
Упрощённо, частотный анализ предполагает, что частота появления заданной буквы алфавита в достаточно длинных текстах одна и та же для разных текстов одного языка. При этом в случае моноалфавитного шифрования если в шифротексте будет символ с аналогичной вероятностью появления, то можно предположить, что он и является указанной зашифрованной буквой. Аналогичные рассуждения применяются к биграммам (двубуквенным последовательностям), триграммам и т.д. в случае полиалфавитных шифров.
Метод частотного криптоанализа известен с 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.
Но существует некоторая разница значений частот, которая объясняется тем, что частоты существенно зависят не только от длины текста, но и от характера текста. Например, текст может быть технического содержания, где редкая буква Ф может стать довольно частой. Поэтому для надежного определения средней частоты букв желательно иметь набор различных текстов.
Практическая часть
Практическая часть работы заключается в написании программы дешифратора и она состоит из 5 этапов:
выбор языка программирования, на котором будут реализовываться алгоритмы;
выбор языка, текст на котором будет шифроваться и дешифроваться;
реализация зашифровки текста алгоритмом шифра Цезаря на алгоритмическом языке PascalABC;
подсчет частот появления каждой буквы в идеальном и зашифрованном текстах и реализация подсчета частот на алгоритмическом языке PascalABC;
расшифровка закодированного текста на основе идеального путем использования частотного криптоанализа.
1 Этап
Итак , первым этапом моей практической части был выбор языка программирования для реализации нашей идеи. Я решил выбрать среду программирования PascalABC.net, так как он является наиболее лучше изученным в отличие от других языков программирования, а так же потому, что наша цель не заключается в изучении нового языка программирования. Она заключается в использовании уже изученного языка программирования для реализации задуманной идеи.
2 Этап
Следующим этапом практической части данной работы был выбор языка, тексты на котором будут шифроваться и дешифроваться. Выбирая между русским и английским языком, я решил выбрать русский для более наглядного представления зашифрованного текста. Также русский язык наиболее легок для понимания.
3 Этап
Следующим этапом моей практической части заключался в реализации алгоритма шифра Цезаря на алгоритмическом языке PascalABC. Как уже известно, шифр Цезаря – это алгоритм шифра замены, который сдвигает каждую букву исходного текста на определенное количество букв вперед. Этим числом K было выбрано число 5. Кодирование текста идет по таблице ASCII. Но так как наш зашифрованный и исходный текст только на русском языке, нам нужно было избавиться от всех остальных знаков и английских букв в таблице ASCII и оставить только русские буквы и пробел. Программа была реализована на алгоритмическом языке PascalABC. Исходный код программы представлен в приложении А.
4 Этап. Следующий шаг моей практической работы заключался в подсчете частот появления букв в зашифрованном и исходном тексте. Именно с помощью частот появления букв мы сможем дешифровать текст. Частоту мы считаем следующим образом:
Считаем общее количество букв в тексте;
Считаем сколько раз каждая буква встречается в тексте;
Делим подсчитанное количество каждой буквы на общее количество букв в тексте и, таким образом, получаем частоту появления каждой буквы в тексте.
Программа была реализована и представлена в приложении Б и В.
5 Этап. Завершающим этапом моей работы было расшифровка текста частотным криптоанализом. Для этого была написана программа дешифратор. Для этого
был создан двумерный массив, состоящий из 4 столбцов. В первый столбец были записаны коды русских букв из таблицы ASCII, во второй столбец записаны частоты появления букв исходного текста в соответствии с их кодами из первого столбца. В третий столбец были записаны коды букв из таблицы ASCII зашифрованного текста, а в 4 столбец были записаны частоты появления букв в соответствии с 3 столбцом. Далее, мы сортируем частоты исходного текста и зашифрованного по убыванию, ставим коды букв в соответствии с частотами. И получим, что у нас в каждой строке массива получились одинаковые частоты, но разные коды букв из таблицы ASCII.
Это и есть наши зашифрованные буквы. То есть в 1 столбце массива у нас остались коды букв из таблицы ASCII исходного текста, а в 3 столбце получились коды букв из таблицы ASCII зашифрованного текста. Коды 3 столбца соответствуют кодам букв с 1 столбца. То есть мы расшифровали закодированный текст. Далее мы расшифруем закодированный текст путем замены закодированных букв на соответствующие буквы из 1 столбца. И таким образом, путем применения классического частотного криптоанализа мы расшифровали наш текст.
Заключение
В ходе проделанной работы были выполнены все поставленные задачи. А именно:
Был изучен алгоритм шифрования текста шифром Цезаря;
Был изучен криптографический метод шифрования информации. А именно частотный криптоанализ;
Был выбран язык программирования, на котором будет реализованы алгоритмы;
Также была реализована практическая часть данной работы. Были написаны алгоритмы программ, необходимых для программы дешифратора;
Была выполнена главная часть работы. Была написана программа дешифратор.
Использованная литература
1) Симонович С.В. Информатика. «Базовый курс».- М.: Дрофа 2000 .– 235с
2) Савельев А. Я. «Основы информатики: Учебник для вузов». – М.: Оникс 2001.-370с
3) Баричев С. «Введение в криптографию. Электронный сборник».- М.: Вече1998. -244c
4) Ведеев Д. «Защита данных в компьютерных сетях. Открытые системы».- М.: Дрофа 1995, №3.-180с
5) Левин В.К. «Защита информации в информационно-вычислительных системах и сетях // Программирование».- СПБ.: Питер 1994. - N5.-160с
Приложение А
var
k,m,c:integer; f,f2:text; ch,ch2:char;
begin
assign(f, '2.txt');
reset(f);
assign(f2, '4.txt');
rewrite(f2);
k:=5;//Ключшифрования
while not eof(f) do
begin
read(f, ch);
if (ch>='А') and (ch<='я') then
begin
c := ord(ch);
c:=(c-192+k) mod 64;
c:=c+192;
ch2:=chr(c);
writeln(f2,ord(ch2));
end
else writeln(f2,ord(ch));
end;
close (f);
close (f2);
end.
ПриложениеБ
var
f,f2: text;
mas: array [1..255] of real;
c:char;
k:longint;
i:integer;
begin
k:=0;
assign (f, '2.txt');
reset (f);
assign (f2,'3.txt');
rewrite(f2,'3.txt');
while not eof(f) do begin
read(f,c);
if (c>='А') and (c<='я') then
mas[ord(c)]:=mas[ord(c)]+1;
k:=k+1;
end;
for i:=192 to 255 do begin
writeln (chr(i),' ',mas[i]/k);
writeln(f2,mas[i]/k);
end;
close(f);
end.
ПриложениеВ
begin
assign(f, '2.txt');
assign(f1,'3.txt');
assign(f2,'4.txt');
assign(f3,'5.txt');
rewrite(f);
writeln(f,ord(ch));
reset(f);
for i:=1 to 63 do begin//Коды букв таблицы ASCII исходного текста
read(f,a[i,1]);
end;
reset(f1);
readln(f1,a[i,1]);
for i:=1 to 63 do begin//Частоты букв исходного текста
read(f1,a[i,2]);
end;
writeln;
reset(f2);
for i:=1 to 63 do begin//Кодыбубквтаблицы ASCII зашифрованноготекста
read(f2,a[i,3]);
end;
reset(f3);
for i:=1 to 63 do begin//Частотыбуквзашифрованноготекста
read(f3,a[i,4]);
end;
close(f1);
close(f3);
for i:=1 to 63 do begin
for j:=1 to 4 do
write(a[i,j],'|');
writeln;
end;
end.