Лабораторная работа №2. Методы анализа шифрованных текстов, поиск ключа шифрования.

Цель работы:

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

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

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

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

Идея состоит в подсчёте чисел вхождений каждой n^m возможных m-грамм в достаточно длинных открытых текстах T=t₁t₂…t_l, составленных из букв алфавита {a₁, a₂, …, a_n}. При этом просматриваются подряд идущие m-граммы текста:

t₁t₂…t_m, t₂t₃… t_m+1, …, t_i-m+1t_l-m+2…t_l.

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

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

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

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

Общая постановка задачи

Ход работы:

· Получить два шифрованных текста (результат выполнения лабораторной работы №1 другой парой студентов).

· Разработать алгоритм выявления включений, основываясь на полученном шифр тексте.

· Собрать статистические данные по шифр тексту №1

· Собрать статистические данные по шифр тексту №2

· Сопоставить полученные статистические данные

· Попытаться выявить часть ключа шифрования или алгоритма шифрования(таблицы замен)

· Попытаться расшифровать полученное сообщение

· Сделать выводы.

Список индивидуальных данных

Индивидуальность заданий связана с индивидуальностью текстов полученных в ходе выполнения Лабораторной работы №1.

Пример выполнения работы

 

 

Необходимо дать краткие теоретические сведения по алгоритму, используемому по заданию, например:

Для выполнения данной работы потребуется знание относительных частот появления русских букв (Буква/Частота): о/0,09; в/0,038; з/0,016; ж/0,007; е, ё/0,072; л/0,035; ы/0,016; ш/0,006; а/0,062; к/0,028; б/0,014; ю/0,006; и/0,062; м/0,026; ь, ъ/0,014; ц/0,004; н/0,053; д/0,025; г/0,013; щ/0,003; т/0,053; п/0,023; ч/0,012; э/0,003; с/0,045; у/0,021; й/0,01; ф/0,002; р/0,04; я/0,018; х/0,009.

В качестве примера приведен листинг программного обеспечения для подсчета частотных характеристик бит входного файла.

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls;

type

TForm1 = class(TForm)

Memo1: TMemo;

Button1: TButton;

Edit1: TEdit;

procedure Button1Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);

var

f:file;

x:byte;

count:array[0..255] of integer;

size:integer;

i:byte;

begin

ZeroMemory(@count,SizeOf(count));

AssignFile(f,Edit1.Text);

Reset(f,1);

size:=FileSize(f);

While not EoF(f) do

begin

BlockRead(f,x,1);

inc(count[x]);

end;

CloseFile(f);

Memo1.Clear;

for i:=0 to 255 do

Memo1.Lines.Add(FloatToStr((count[i]/size)*100));

end;

end.

Далее полученные данные следует сопоставить с известными частотными характеристиками и произвести обратные замены для получения открытого текста.

После выполнения работы необходимо сделать выводы.

 

Контрольные вопросы к защите

Изложите полученные знания по разделу:

1. История криптоанализа.

2. Классический криптоанализ.

3. Современный криптоанализ.

4.  Методы криптоанализа.

5.  Атака на основе открытых текстов и соответствующих шифротекстов.

6. Дополнительные методы криптоанализа.