Лабораторная работа №1.  Тайнопись

Практикум (лабораторный)

Практикум состоит из 5 лабораторных работ.

Для успешного выполнения лабораторных работ необходимо изучение соответствующих модулей теоретического блока (лекций).

Общие требования к содержанию, оформлению и порядку выполнения

Перед выполнением лабораторной работы необходимо создать папку «Ваша фамилия_Lab №_variant№_» (Использовать только буквы латинского алфавита. Например: «Ivanov I.P. Lab №1_variant№5»). В эту папку в ходе выполнения работы необходимо сохранять требуемые материалы.

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

Задания лабораторной работы необходимо выполнять последовательно, при необходимости результат выполнения сохранять в свою папку. Папку с результатами необходимо заархивировать, создав один файл архива в формате ZIP. Файлу архива необходимо дать имя в формате: «Ваша фамилия_Lab №_variant№_.zip» (Использовать только буквы латинского алфавита. Например: «Ivanov I.P. Lab №1_variant№5.zip»). Полученный файл архива необходимо загрузить на страницу задания «Лабораторная работа №__».

Для оценки результатов лабораторной работы используются следующие критерии:

· отметка «отлично» выставляется студенту, глубоко и прочно усвоившему материал темы, получившему практические навыки свободной работы с соответствующим программным продуктом и продемонстрировавшим их, выполнив все задания и дав ответы на поставленные вопросы;

· отметка «хорошо» выставляется студенту, твердо знающему материал темы, который правильно применяет теоретические положения при работе с соответствующим программным продуктом и частично выполнившему индивидуальные задания по варианту;

· отметка «удовлетворительно» выставляется студенту, который знает в основном материал темы, методику работы с программным продуктом;

· отметка «неудовлетворительно» выставляется студенту, который не знает значительной части программного материала, допускает существенные ошибки и не смог выполнить задания лабораторной работы.

 

 

Лабораторная работа №1.  Тайнопись

Цель работы:

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

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

Имеются свидетельства, что криптография как техника защиты текста возникла вместе с письменностью, и способы тайного письма были известны уже древним цивилизациям Индии, Египта и Месопотамии. В древнеиндийских текстах среди 64-х искусств названы способы изменения текста, некоторые из них можно отнести к криптографическим. Автор таблички с рецептом для изготовления глазури для гончарных изделий из Месопотамии использовал редкие обозначения, пропускал буквы, а имена заменял на цифры, чтобы скрыть написанное. В дальнейшем встречаются различные упоминания об использовании криптографии, большая часть относится к использованию в военном деле.

Древний Египет

Первым известным применением криптографии принято считать использование специальных иероглифов около 4000 лет назад в Древнем Египте. Элементы криптографии обнаружены уже в надписях Старого и Среднего царств, полностью криптографические тексты известны с периода XVIII династии. Иероглифическое письмо, произошедшее от пиктографии, изобиловало идеограммами и, в результате отсутствия огласовки, дало возможность создавать фонограммы по принципу ребусов. Криптография египтян использовалась не с целью затруднить чтение, а вероятнее, со стремлением писцов превзойти друг друга в остроумии и изобретательности, а также, с помощью необычности и загадочности, привлечь внимание к своим текстам. Одним из показательных примеров являются тексты прославления вельможи Хнумхотепа II (XIX в. до н. э.) найденные в хорошо сохранившейся гробнице № BH 3 в местности Бени-Хасан.

Атбаш

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

 

Скитала.

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

Бесспорно известно, что скитала использовалась в войне Спарты против Афин в конце V века до н. э. Возможно также, что её упоминают поэты Архилох(VII век до н. э.) и Пиндар, хотя вероятнее, что в их стихах слово «скитала» использовано в своём первичном значении «посох».

Принцип её действия изложили Аполлоний Родосский(середина III века до н. э.) и Плутарх (около 45—125 н. э.), но сохранилось лишь описание последнего.

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

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

 

Диск Энея, Линейка Энея, Книжный шифр Энея

С именем Энея Тактика, полководца IV века до н. э., связывают несколько техник шифрования и тайнописи.

Диск Энея представлял собой диск диаметром 10—15 см с отверстиями по числу букв алфавита. Для записи сообщения нитка протягивалась через отверстия в диске, соответствующие буквам сообщения. При чтении получатель вытягивал нитку, и получал буквы, правда, в обратном порядке. Хотя недоброжелатель мог прочитать сообщение, если перехватит диск, Эней предусмотрел способ быстрого уничтожения сообщения — для этого было достаточно выдернуть нить, закреплённую на катушке в центре диска.

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

В своём сочинении «О перенесении осады» Эней описывает ещё одну технику тайнописи, позже названную «книжным шифром». Он предложил делать малозаметные дырки рядом с буквами в книге или другом документе. Много позже аналогичный шифр использовали немецкие шпионы во время Первой мировой войны.

 

Квадрат Полибия

     1  2  3  4  5

1  Α  Β  Γ  Δ  Ε

2  Ζ  Η  Θ  Ι   Κ

3  Λ  Μ Ν  Ξ  Ο

4  Π  Ρ  Σ  Τ  Υ

5  Φ  Χ  Ψ  Ω

 

Квадрат Полибия с греческим алфавитом. Для передачи, например, буквы «Θ» сначала показывали два факела, потом три.

 

Во II веке до н. э. в Древней Греции был изобретён квадрат Полибия. В нём буквы алфавита записывались в квадрат 5 на 5 (при использовании греческого алфавита одна ячейка оставалась пустой), после чего с помощью оптического телеграфа передавались номер строки и столбца, соответствующие символу исходного текста (на каждую букву приходилось два сигнала: число факелов обозначало разряд буквы по горизонтали и вертикали).

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

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

Ход работы:

· Объединиться по парам.

· Получить открытый текст у преподавателя(каждый студент получает текст получает самостоятельно, то есть на пару 2 текста).

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

· Зашифровать текст(текст №1) – передать шифрованный напарнику.

· Получить шифрованный текст от напарника, расшифровать(текст №2).

· Сделать контрольную шифрацию (Текст №2) – передать напарнику.

· Получить контрольный текст от напарника – расшифровать.

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

 

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

Задание

Зашифровать фразу КОРАБЛИ ОТХОДЯТ ВЕЧЕРОМ

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

Одним из открытых сообщений является фраза:

КОРАБЛИ ОТХОДЯТ ВЕЧЕРОМ

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

ЮПЯТБНЩМСДТЛЖГПСГХСЦЦ

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

При выборе правила шифрования надо стремиться к тому, чтобы посторонние лица, не знающие правила расшифрования, не смогли восстановить по криптограмме открытое сообщение. В этом случае вы скроете смысл сообщения и обеспечите ``тайнопись''.

В криптографии конкретное значение такого параметра обычно называют ключом. По сути дела, ключ выбирает конкретное правило зашифрования из данного класса правил.

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

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

 

Скриншот программы:

Рис. 1. Снимок экранной формы

 

Код программы

 

unit Unit1;

interface

uses

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

Dialogs, StdCtrls,Unit2;

type

TForm1 = class(TForm)

Button1: TButton;

OpenDialog1: TOpenDialog;

SaveDialog1: TSaveDialog;

Button2: TButton;

Button3: TButton;

procedure Button1Click(Sender: TObject);

procedure Button2Click(Sender: TObject);

procedure Button3Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

 

var

Form1: TForm1;

f1, f2: TextFile;

 

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);

var

SrcStr,ResStr: string;

begin

AssignFile(f1, OpenDialog1.FileName);

AssignFile(f2, SaveDialog1.FileName);

reset(f1);

rewrite(f2);

 

create_alphavit;

while not Eof(f1) do begin

Readln(f1,SrcStr);

ResStr:=code_string(SrcStr);

writeln(f2,ResStr);

end;

 

closefile(f1);

closefile(f2);

end;

 

procedure TForm1.Button2Click(Sender: TObject);

begin

OpenDialog1.Execute;

end;

 

procedure TForm1.Button3Click(Sender: TObject);

begin

SaveDialog1.Execute;

end;

 

end.

 

unit Unit2;

 

interface

 

type

code_rec = record

Letter_1:char;

Letter_2:char;

end;

 

var

code_list: array of code_rec;

code_size: integer;

 

function code_string(str:string):string;

procedure create_alphavit;

 

implementation

 

//*****************************************

 

procedure add_char(a,b:char);

begin

inc(code_size);

setlength(code_list,code_size);

code_list[code_size-1].Letter_1:= a;

code_list[code_size-1].Letter_2:= b;

end;

 

procedure clear_swap;

begin

code_size:= 0;

setlength(code_list,code_size);

end;

 

//*****************************************

 

function GetCodeChar(a:char):char;

var rez:char;

t:integer;

begin

rez:='1';

 

t:=0;

while t <= code_size do begin

if code_list[t].Letter_1 = a then rez:= code_list[t].Letter_2;

if code_list[t].Letter_2 = a then rez:= code_list[t].Letter_1;

inc(t);

end;

 

GetCodeChar:= rez;

end;

 

//*****************************************

 

function code_string(str:string):string;

var rez:string;

t:integer;

char_kun:char;

begin

rez:='';

for t:=1 to length(str) do begin

char_kun:= GetCodeChar(str[t]);

if char_kun <> '1' then

rez:=rez + GetCodeChar(str[t])

else rez:=rez + str[t];

end;

code_string:= rez;

end;

 

//*****************************************

 

procedure create_alphavit;

begin

clear_swap;

add_char('а','к');

add_char('б','т');

add_char('в','х');

add_char('г','о');

add_char('д','ц');

add_char('е','ш');

add_char('ж','с');

add_char('з','у');

add_char('й',' ');

add_char('и','н');

add_char('л','ч');

add_char('м','ы');

add_char('п',',');

add_char('р','щ');

add_char('ф','я');

add_char('х','в');

add_char('ц','д');

add_char('ъ','ь');

add_char('э','ю');

end;

 

end.

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

 

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

1. Какие цели  преследует тайнопись?

2. Что такое системы замены букв?

3. Условные алфавиты.

 

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

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

Как упоминалось выше, важными характеристиками текста являются повторяемость букв (количество различных букв в каждом языке ограничено), пар букв, то есть 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

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

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

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

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

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

 

 

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

Для выполнения данной работы потребуется знание относительных частот появления русских букв (Буква/Частота): о/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. Дополнительные методы криптоанализа.

 

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

Шифр Цезаря.

Одним из самых древних и простых в реализации является шифр Цезаря, который использовал его для тайной переписки. Суть его в том, что каждая буква исходного шифруемого сообщения сдвигается в алфавите на заданное количество символов. Так, например, если сдвиг равен 3, то буква А превратится в Г, буква Б - в Д и так далее:

Рис. 2. Визуализация алгоритма Цезаря

Символы в конце алфавита (Э, Ю, Я), соответственно, будут превращаться его начало (А, Б, В).

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

Шифр Виженера. В 15 веке был впервые придуман, а потом в 16 веке французским дипломатом Блезом Виженером официально представлен более совершенный метод на основе шифра Цезаря, получивший впоследствии название "шифр Виженера". Его принцип в том, что каждая буква в исходном шифруемом тексте сдвигается по алфавиту не на фиксированное, а переменное количество символов. Величина сдвига каждой буквы задается ключом (паролем) - секретным словом или фразой, которая используется для шифрования и расшифровки.

Допустим, мы хотим зашифровать фразу "КЛАД ЗАРЫТ В САДУ" используя слово ЗИМА в качестве ключа. Запишем это слово подряд несколько раз под исходной фразой:

Рис. 3. Подготовка ключа для шифрования алгоритмом Виженера

 

Для удобства шифрования используем так называемый "квадрат Виженера" - таблицу, где в каждой строке алфавит сдвигается на одну позицию вправо:

Рис. 4. Визуализация процесса шифрования методом Виженера

Если взять строку с первой буквой ключа (З) и столбец с первой буквой исходного текста (К), то на их пересечении увидим букву "Т" - это и будет первая буква нашего зашифрованного сообщения. Затем процедура повторяется для всех остальных пар букв ключа и исходного сообщения по очереди и в результате мы получаем зашифрованный вариант нашей исходной фразы:

Рис. 5. Результат шифрования методом Виженера

Заметьте, что одна и та же буква (например А) в исходном сообщений превратилась в разные буквы на выходе (Н, Й и Б), т.к. сдвиг при шифровании для них был разный. Именно поэтому вскрыть шифр Виженера простыми способами невозможно - вплоть до 19 века он считался невзламываемым и успешно использовался военными, дипломатами и шпионами многих стран, частности - конфедератами во время Гражданской войны в США.

 

 

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

Ход работы:

· Выбрать алфавит, подходящий для шифрования сообщения полученного в ходе выполнения Лабораторной работы №1

· Реализовать программное обеспечение для шифрования/дешифрования при помощи выбранного алфавита и алгоритма

· Зашифровать сообщение – сохранить результат в файл

· Закрыть программное обеспечение

· Открыть программное обеспечение – дешифровать файл.

· Сравнить полученный файл с исходным

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

 

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

Необходимо изложить задание, например:

Написать и отладить программу для шифровки/дешифровки сообщений шифром Виженера.

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

 

Шифр Виженера является достаточно стойким для взлома. Это один из старейших многоалфавитных шифров, то есть таких шифров, где одному символу шифруемого сообщения соответствует более одного символа. Для использовании этого шифра строится квадрат с построчным сдвигом символов в каждом ряду.

Далее выбираем ключ, например, «граф Дракула» и циклически записываем его под шифруемым текстом, предварительно исключив из последнего пробелы. Пусть в нашем случае шифруемый тест имеет вид «Отряд ждет указаний». Тогда, описанный выше процесс будет выглядеть так:

ОТРЯДЖЕТУКАЗАНИЙ

ГРАФДРАКУЛАГРАФДР

 

Шифровка сообщения производится так: буква шифруемого текста находится в построенном квадрате на пересечении буквы исходного текста (строка) и буквы ключа (столбец). По этому принципу наше сообщение примет вид «СВРУИЦДПЕЮКГЧАБМЩ».

Дешифровку можно проводить так: найти индекс столбца, где расположен символ ключа. Найти индекс строки, в которой стоит буква зашифрованного сообщения, расположенная в столбце с найденным индексом. Буква исходного сообщения будет находиться в элементе квадрата по адресу: [индекс_строки_с_шифрованным_символом; первый_столбец]

 

Скриншот программы

Рис. 6. Снимок экранной формы

 

 

Код программы

 

unit VijenerCodeU;

 

interface

 

uses

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

Dialogs, StdCtrls, ExtCtrls;

 

const

AlphabetSize = {57}32;

Alphabet: array[1..AlphabetSize] of char =('а','б', 'в', 'г', 'д', 'е','ж', 'з', 'и', 'й', 'к', 'л', 'м', 'н', 'о', 'п', 'р', 'с', 'т', 'у', 'ф',

   'х', 'ц', 'ч', 'ш', 'щ', 'ъ', 'ы', 'ь', 'э', 'ю', 'я'{,

   'a','b','c','d','e','f','g','h','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'});

 

type

T_array= array[1..AlphabetSize] of char;

T_matr = array[1..AlphabetSize] of T_array;

 

TfrmVijenerCode = class(TForm)

lbedSourceMessage: TLabeledEdit;

lbedKey: TLabeledEdit;

lbedEncryptMessage: TLabeledEdit;

bbEncrypt: TButton;

mmResults: TMemo;

bbDecrypt: TButton;

gbCodeTableOptions: TGroupBox;

lbedSharpInSrcAlphabet: TLabeledEdit;

sttxtHelp: TStaticText;

gbCodeTable: TGroupBox;

cbShowCodeTable: TCheckBox;

bbClear: TButton;

lbedSharpInCodeTable: TLabeledEdit;

procedure bbEncryptClick(Sender: TObject);

procedure bbDecryptClick(Sender: TObject);

procedure FormCreate(Sender: TObject);

procedure cbShowCodeTableClick(Sender: TObject);

procedure bbClearClick(Sender: TObject);

private

//удаление пробелов из строки

function deleteSpaces(str:string):string;

 

//формирование кодовой таблицы

procedure createCodeTable(var codeTable:T_matr; sharpInSourceAlphabet,

         sharpFromStartStr:byte);

 

//кодирование сообщения шифром Виженера

function EncodeMessageByVijener(srcMessage, key:string; sharpInAlphabet, sharpInCodeTable:byte):string;

 

//кодирование сообщения шифром Виженера

function DecodeMessageByVijener(codeMessage, key:string; sharpInAlphabet, sharpInCodeTable:byte):string;

   

//нахождение индекса символа в строке с номером indRow

function FindIndexInRow(ch:char; indRow: byte; codeTable:T_matr):byte;

 

//нахождение индекса символа в столбце с номером indCol

function FindIndexInColumn(ch:char; indCol: byte; codeTable:T_matr):byte;

 

public

{ Public declarations }

end;

 

var

frmVijenerCode: TfrmVijenerCode;

 

implementation

 

{$R *.dfm}

 

{ TfrmVijenerCode }

 

procedure TfrmVijenerCode.createCodeTable(var codeTable: T_matr;

sharpInSourceAlphabet,sharpFromStartStr: byte);

 

var

i, j, c:byte;

sharpedAlphabet:T_array;

 

begin

//инициализируем кодовую таблицу

for i:=1 to alphabetSize do

for j:=1 to alphabetSize do

  codeTable[i,j]:='0';

 

//формируем алфавит, сдвинутый на заданное значение

for i:=1 to alphabetSize do

if (i= AlphabetSize) and (sharpInSourceAlphabet =0) then

  sharpedAlphabet[i]:= alphabet[i]

else

begin

  j:= (i mod alphabetSize) + sharpInSourceAlphabet;

  if j> AlphabetSize then

    j:= j mod AlphabetSize;

  sharpedAlphabet[i]:= alphabet[j];

end;

 

//заполняем первую строку таблицы исходным алфавитом

for i:=1 to alphabetSize do

codeTable[1,i]:= sharpedAlphabet[i];

 

//заполнение остальных строк таблицы символами исходного алфавита,

//сдвинутыми на заданное значение

for i:=2 to alphabetSize do

for j:=1 to alphabetSize do

begin

c:= (j mod alphabetSize)+ sharpFromStartStr;

if c> AlphabetSize then

   c:= c mod AlphabetSize;

codeTable[i,j]:= codeTable[i-1,c];

end;

 

mmResults.Lines.Clear;

for i:=1 to alphabetSize do

mmResults.Lines.Add(codeTable[i]);

end;

 

function TfrmVijenerCode.deleteSpaces(str: string): string;

var

i:byte;

begin

i:= Pos(' ', str);

while i<>0 do

begin

Delete(str,i,1);

i:= Pos(' ', str);

end;

 

deleteSpaces:= str;

end;

 

procedure TfrmVijenerCode.bbEncryptClick(Sender: TObject);

var

codeTable:T_matr;

begin

lbedEncryptMessage.Text:= EncodeMessageByVijener(lbedSourceMessage.Text, lbedKey.Text,

         StrToInt(lbedSharpInSrcAlphabet.Text), StrToInt(lbedSharpInCodeTable.Text));

end;

 

function TfrmVijenerCode.EncodeMessageByVijener(srcMessage,

key: string; sharpInAlphabet, sharpInCodeTable:byte): string;

 

var

codeTable:T_matr;

newKey, resultMessage:string;

i,

fullKeyInMes, //сколько раз ключ полностью входит в кодируемое сообщение

partiallyKeyInMes //сколько символов ключа частично входит в кодируемое сообщение

              :byte;

tmp:string;                 

 

keyCharIndex, srcMessageCharIndex:byte;

begin

//создание кодовой таблицы

createCodeTable(codeTable, sharpInAlphabet,sharpInCodeTable);

 

//удалениие пробелов из ключа и кодируемого сообщения

srcMessage:= deleteSpaces(srcMessage);

key:= deleteSpaces(key);

 

//формирование циклического ключа

newKey:='';

 

//длина циклического ключа = длине кодируемого сообщения

SetLength(newKey, length(srcMessage));

newKey:='';

 

//вычисляем количество полных вхождений ключа в кодируемое сообщение

fullKeyInMes:= length(srcMessage) div length(key);

 

//располагаем полные ключи в результирующем друг за другом

for i:=1 to fullKeyInMes do

newKey:= newKey + key;

 

//вычисляем количество свободных символов в циклическом ключе

//после добавления к нему полных

partiallyKeyInMes:= length(srcMessage) mod length(key);

 

//копируем получившееся число символов из начала строки исходного ключа

tmp:= Copy(key,1, partiallyKeyInMes);

 

//добавляем скопированное в циклический ключ

newKey:= newKey + tmp;

 

//=============шифруем исходное сообщен======

//символ исходного текста - строка

//символ ключа - столбец

//=====================================

resultMessage:='';

 

for i:=1 to Length(srcMessage) do

begin

//узнаем индекс символа исходного текста в кодовой таблице

srcMessageCharIndex:= FindIndexInRow(srcMessage[i],1,codeTable);

 

//узнаем индекс символа ключа в кодовой таблице

keyCharIndex:= FindIndexInColumn(newKey[i],1, codeTable);

 

//добавляем символ, лежащий на пересечении символов исходного текста и

//ключа к строке результата

resultMessage:= resultMessage + codeTable[srcMessageCharIndex, keyCharIndex];

end;

 

EncodeMessageByVijener:= resultMessage;

end;

 

function TfrmVijenerCode.FindIndexInColumn(ch: char; indCol: byte; codeTable:T_matr): byte;

var

i:byte;

f:boolean;

begin

f:=false;

i:=1;

 

while (i<= AlphabetSize) and (not f) do

begin

f:= (ch = codeTable[i,indCol]);

inc(i);

end;

 

if f then

begin

Dec(i);

FindIndexInColumn:= i;

end

 

else

FindIndexInColumn:= 0;

end;

 

function TfrmVijenerCode.FindIndexInRow(ch: char; indRow: byte; codeTable:T_matr): byte;

var

i:byte;

f:boolean;

begin

f:=false;

i:=1;

 

while (i<= AlphabetSize) and (not f) do

begin

f:= (ch = codeTable[indRow,i]);

inc(i);

  end;

 

if f then

begin

Dec(i);

FindIndexInRow:= i;

end

 

else

FindIndexInRow:= 0;

end;

 

function TfrmVijenerCode.DecodeMessageByVijener(codeMessage, key: string;

sharpInAlphabet, sharpInCodeTable: byte): string;

 

var

codeTable:T_matr;

i,j:byte;

tmp,

resstr,

newKey:string;

fullKeyInMes,

partiallyKeyInMes: integer;

indRow, indCol:byte;

begin

resstr:='';

 

//создание кодовой таблицы

createCodeTable(codeTable,sharpInAlphabet,sharpInCodeTable);

 

//==============СОЗДАНИЕ ЦИКЛИЧЕСКОГО КЛЮЧА===============

//формирование циклического ключа

newKey:='';

 

//удаление пробелов из исходного ключа и из кодированного сообщения

key:= deleteSpaces(key);

codeMessage:= deleteSpaces(codeMessage);

 

//длина циклического ключа = длине кодируемого сообщения

SetLength(newKey, length(codeMessage));

newKey:='';

 

//вычисляем количество полных вхождений ключа в кодируемое сообщение

fullKeyInMes:= length(codeMessage) div length(key);

 

//располагаем полные ключи в результирующем друг за другом

for i:=1 to fullKeyInMes do

newKey:= newKey + key;

 

//вычисляем количество свободных символов в циклическом ключе

//после добавления к нему полных

partiallyKeyInMes:= length(codeMessage) mod length(key);

 

//копируем получившееся число символов из начала строки исходного ключа

tmp:= Copy(key,1, partiallyKeyInMes);

 

//добавляем скопированное в циклический ключ

newKey:= newKey + tmp;

 

//===============ДЕКОДИРОВАНИЕ СООБЩЕНИЯ=========================

for i:=1 to Length(codeMessage) do

begin

//узнаем индекс столбца, в котором расположен символ ключа

indCol:= FindIndexInRow(newKey[i],1,codeTable);

 

//ищем индекс строки в этом столбце, в которой стоит

//буква кодированного текста

indRow:= FindIndexInColumn(codeMessage[i],indCol,codeTable);

 

//символ, стоящий в начале этой строки- символ исходного сообщения

//добавляем его в строку результата

resstr:= resstr + codeTable[indRow,1];

end;

 

DecodeMessageByVijener:= resstr;

end;

 

procedure TfrmVijenerCode.bbDecryptClick(Sender: TObject);

begin

lbedSourceMessage.Text:= DecodeMessageByVijener(lbedEncryptMessage.Text, lbedKey.Text,

  StrToInt(lbedSharpInSrcAlphabet.Text), StrToInt(lbedSharpInCodeTable.Text));

 

//lbedSourceMessage.Text:= EncodeMessageByVijener(lbedEncryptMessage.Text, lbedKey.Text,

// StrToInt(lbedSharpInSrcAlphabet.Text), StrToInt(lbedSharpInCodeTable.Text));

end;

 

procedure TfrmVijenerCode.FormCreate(Sender: TObject);

begin

sttxtHelp.Caption:= sttxtHelp.Caption + IntToStr(AlphabetSize);

end;

 

procedure TfrmVijenerCode.cbShowCodeTableClick(Sender: TObject);

begin

if cbShowCodeTable.Checked then

 gbCodeTable.Show

else

gbCodeTable.Hide; 

end;

 

procedure TfrmVijenerCode.bbClearClick(Sender: TObject);

begin

lbedSourceMessage.Text:='';

lbedKey.Text:='';

lbedEncryptMessage.Text:='';

mmResults.Lines.Clear;

end;

 

end.

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

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

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

1. Основные сведения о криптографии, отличие от тайнописи.

2. Общая схема алгоритма Виженера.

3. Параметры алгоритмов Цезаря и Виженера.

4. Простая перестановка. Одиночная перестановка по ключу. Двойная перестановка.

5. Виды симметричных шифров. Достоинства. Недостатки.

 

 

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

Алгоритм RSA стоит у истоков асимметричной криптографии. Он был предложен тремя исседователями-математиками Рональдом Ривестом (R.Rivest), Ади Шамиром (A.Shamir) и Леонардом Адльманом (L.Adleman) в 1977-78 годах.

Первым этапом любого асимметричного алгоритма является создание пары ключей: открытого и закрытого и распространение открытого ключа "по всему миру". Для алгоритма RSA этап создания ключей состоит из следующих операций:

1. Выбираются два простых (!) числа p и q

2. Вычисляется их произведение n(=p*q)

3. Выбирается произвольное число e (e<n), такое, что НОД(e,(p-1)(q-1))=1, то есть e должно быть взаимно простым с числом (p-1)(q-1).

4. Методом Евклида решается в целых числах (!) уравнение e*d+(p-1)(q-1)*y=1. Здесь неизвестными являются переменные d и y – метод Евклида как раз и находит множество пар (d,y), каждая из которых является решением уравнения в целых числах.

5. Два числа (e,n) – публикуются как открытый ключ.

6. Число d хранится в строжайшем секрете – это и есть закрытый ключ, который позволит читать все послания, зашифрованные с помощью пары чисел (e,n).

Как же производится собственно шифрование с помощью этих чисел:

1. Отправитель разбивает свое сообщение на блоки, равные k=[log₂(n)] бит, где квадратные скобки обозначают взятие целой части от дробного числа.

2. Подобный блок, как Вы знаете, может быть интерпретирован как число из диапазона (0;2^k-1). Для каждого такого числа (назовем его m_i) вычисляется выражение c_i=((m_i)^e)mod n. Блоки c_i и есть зашифрованное сообщение Их можно спокойно передавать по открытому каналу, поскольку.операция возведения в степень по модулю простого числа, является необратимой математической задачей. Обратная ей задача носит название "логарифмирование в конечном поле" и является на несколько порядков более сложной задачей. То есть даже если злоумышленник знает числа e и n, то по c_i прочесть исходные сообщения m_i он не может никак, кроме как полным перебором m_i.

А вот на приемной стороне процесс дешифрования все же возможен, и поможет нам в этом хранимое в секрете число d. Достаточно давно была доказана теорема Эйлера, частный случай которой утвержает, что если число n представимо в виде двух простых чисел p и q, то для любого x имеет место равенство (x^(p-1)(q-1))mod n = 1. Для дешифрования RSA-сообщений воспользуемся этой формулой. Возведем обе ее части в степень (-y): (x^{(-y)(p-1)(q-1)})mod n = 1^(-y) = 1. Теперь умножим обе ее части на x: (x^{(-y)(p-1)(q-1)+1})mod n = 1*x = x.

А теперь вспомним как мы создавали открытый и закрытый ключи. Мы подбирали с помощью алгоритма Евклида d такое, что e*d+(p-1)(q-1)*y=1, то есть e*d=(-y)(p-1)(q-1)+1. А следовательно в последнем выражении предыдущего абзаца мы можем заменить показатель степени на число (e*d). Получаем (x^e*d)mod n = x. То есть для того чтобы прочесть сообщение c_i=((m_i)^e)mod n достаточно возвести его в степень d по модулю m: ((c_i)^d)mod n = ((m_i)^e*d)mod n = m_i.

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

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

Ход работы:

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

· Реализовать программно алгоритм шифрования/дешифрования RSA

· Реализовать программно алгоритм генерации ключей RSA

· Зашифровать сообщение – сохранить результат в файл

· Закрыть программное обеспечение

· Открыть программное обеспечение – дешифровать файл.

· Сравнить полученный файл с исходным

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

 

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

Необходимо изложить задание, например: Реализовать алгоритм RSA.

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

В качестве примера приведен листинг программы реализующий алгоритм шифровании RSA.

unit RSAU;

interface

uses

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