ЗМІСТ
TOC \o "2-2" \h \z \t "Заголовок 1;1;Заголовок 3;3"
HYPERLINK \l "_Toc279443283" АНОТАЦІЯ PAGEREF _Toc279443283 \h 6
HYPERLINK \l "_Toc279443284" ANNOTATION PAGEREF _Toc279443284 \h 7
HYPERLINK \l "_Toc279443285" ВСТУП PAGEREF _Toc279443285 \h 8
HYPERLINK \l "_Toc279443286" 1. КОДУВАННЯ ДАНИХ PAGEREF _Toc279443286 \h 10
HYPERLINK \l "_Toc279443287" 1.1 Кількість інформації PAGEREF _Toc279443287 \h 10
HYPERLINK \l "_Toc279443288" 1.2 Ентропія дискретного джерела інформації PAGEREF _Toc279443288 \h 11
HYPERLINK \l "_Toc279443289" 1.3 Застосування бінарних дерев до побудови двійкових префіксних кодів PAGEREF _Toc279443289 \h 16
HYPERLINK \l "_Toc279443290" 1.4 Ефективне кодування та стиснення даних PAGEREF _Toc279443290 \h 19
HYPERLINK \l "_Toc279443291" 2. ОСНОВИ КРИПТОЛОГІЇ PAGEREF _Toc279443291 \h 28
HYPERLINK \l "_Toc279443292" 2.1 Методи захисту інформації. Криптографія та криптоаналіз. PAGEREF _Toc279443292 \h 28
HYPERLINK \l "_Toc279443293" 3.2 Симетричні криптографічні системи PAGEREF _Toc279443293 \h 31
HYPERLINK \l "_Toc279443294" 2.3 Стійкість шифрів PAGEREF _Toc279443294 \h 36
HYPERLINK \l "_Toc279443295" 2.4 Тестування якості генераторів ключів PAGEREF _Toc279443295 \h 40
HYPERLINK \l "_Toc279443296" 2.5 Криптосистеми з відкритим ключем. Стандарти шифрування. PAGEREF _Toc279443296 \h 43
HYPERLINK \l "_Toc279443297" 3. КРИПТТОГРАФІЧНЕ ПЕРЕТВОРЕННЯ ЗА ДОПОМОГОЮ ДЕРЕВА ШТЕРНА-БРОКО PAGEREF _Toc279443297 \h 46
HYPERLINK \l "_Toc279443298" 3.1. Двійкове дерево Штерна-Броко PAGEREF _Toc279443298 \h 46
HYPERLINK \l "_Toc279443299" 3.2. Алгоритм криптографічного перетворення PAGEREF _Toc279443299 \h 50
HYPERLINK \l "_Toc279443300" 3.3 Стійкість шифру PAGEREF _Toc279443300 \h 53
HYPERLINK \l "_Toc279443301" 3.4 Опис програми шифрування-дешифрування PAGEREF _Toc279443301 \h 57
HYPERLINK \l "_Toc279443302" ВИСНОВОК PAGEREF _Toc279443302 \h 60
HYPERLINK \l "_Toc279443303" ЛІТЕРАТУРА PAGEREF _Toc279443303 \h 61
HYPERLINK \l "_Toc279443304" ДОДАТОК А Основні блоки програми у середовищі Delphi PAGEREF _Toc279443304 \h 64
ДОДАТОК B Презентація ……………………………………………………….


АНОТАЦІЯ
Головним завданням кваліфікаційної дипломної роботи є аналіз алгоритму симетричного криптування на основі двійкового дерева Штерна-Броко та його програмна реалізація. У роботі запропоновано варіант алгоритму криптування за допомогою дерева Штерна-Броко та здійснена програмна реалізація шифратора та дешифратора на мові Object Pascal в середовищі Delphi. Проведено попередній аналіз стійкості цього алгоритму криптування для типових умов криптоаналізу.





ANNOTATION
The main task of qualifying diploma work is development and software implementation of symmetric cryptography algorithm based on the Stern-Brocot benary tree. In the work a variant of algorithm based on the Stern-Brocot tree is proposed, encoder and decoder are released in Object Pascal language. Preliminary analysis of cryptographic stability of the algorithm is made for typical conditions of cryptanalysis.


ВСТУП
Захист інформації від несанкціонованого доступу, спотворення та знищення є серйозного економічною, соціальною та технічною проблемою [22]. Одним з ефективних методів захисту даних в електронній формі є шифрування – спеціальне перетворення (кодування) даних з метою їх захисту від несанкціонованого доступу.
Не зважаючи на стрімкий розвиток асиметричних криптосистем, на сьогодні широко використовують блокові та потокові симетричні шифри, завдяки їх простоті, високій швидкодії та надійності. Блокові шифри покладені в основу американських стандартів DES, AES, міжнародного стандарту IDES, радянського стандарту ГОСТ 28147-89, а потокове шифрування використовують стандарти A3, A5, A8, RC4, PIKE, SEAL та інші.
Проблема розробки стандарту шифрування є актуальною для України [15,16,18.20].
У дипломній роботі досліджується метод криптографічного перетворення за допомогою дерева Штерна-Броко, запропонований у роботах[8,9]. Здійснено модифікацію цього методу та виконана програмна реалізація шифратора та дешифратора на мові Object Pascal в середовищі Delphi. Також проведено попередній аналіз криптостійкості алгоритму криптування для типових умов криптоаналізу.
Робота складається зі вступу, трьох розділів, висновків та двох додатків.
У вступі зазначена актуальність роботи та дана її загальна характеристика.
У першому розділі викладено фундаментальні поняття теорії інформації важливі для розуміння подальшого матеріалу (кількість інформації, ентропія джерела інформації та ентропія повідомлення, побудова роздільних кодів за допомогою бінарних дерев). Також, в загальному, розглянуто методи ефективного кодування та стиснення даних, які можуть бути комбіновані з методами криптування.
У другому розділі розглянуто основи криптології. Основний акцент зроблено на блокових симетричних шифрах та потокових шифрах, понятті стійкості криптосистем.
У третьому розділі з використанням фундаментальних понять викладених у попередніх розділах розглянуто метод криптографічного перетворення з використанням дерев Штерна-Броко.
Насамперед описано властивості та метод побудови дерева Штерна-Броко. Далі запропоновано алгоритм криптування з використанням цього дерева. Також проведено попередній аналіз крипостійкості алгоритму криптування для типових умов криптоаналізу. Розглянуто програмну реалізацію алгоритму на мові Object Pascal в середовищі Delphi.
У висновках підсумовано результати проведених досліджень.
У додатках подано текст програми криптування та декриптування на мові та презентацію дипломної роботи.

1. КОДУВАННЯ ДАНИХ
1.1 Кількість інформації
Кількість інформації є фундаментальним поняттям для криптування та ефективного кодування даних. До оцінки кількості інформації найбільшого поширення отримав підхід на основі статистичного опису джерела інформації.
Вперше міру кількості інформації ввів американський математик Р. Хартлі у 1928 році. Пізніше у 1948 році К. Шеннон ввів поняття ентропії джерела інформації [23], повне обґрунтування якого дав радянський математик О. Я. Хінчін на основі теорії стаціонарних випадкових процесів.
Виходячи з емпіричних уявлень щодо природи інформації можна стверджувати, що:
коли деякий об’єкт може перебувати в одному із EMBED Equation.DSMT4 можливих станів, то за відсутності інформації про те, в якому саме стані він перебуває, існує невизначеність (незнання) щодо істинного стану об’єкта, а отримання повідомлення щодо актуального його стану цю невизначеність усуває;
якщо кількість можливих станів об’єкта EMBED Equation.DSMT4 , то повідомлення про те, що об’єкт перебуває у своєму єдино можливому стані не несе жодної інформації;
повідомлення про актуальний стан об’єкта з двома можливими станами ( EMBED Equation.DSMT4 ) несе мінімальну кількість інформації (її прийнято називати 1 біт);
що більше число EMBED Equation.DSMT4 можливих станів об’єкта, то більша кількість інформації несе повідомлення про його істинний стан;
якщо перехід об’єкта в будь-який його допустимий стан є подія випадкова, то кількість інформації, яку несе повідомлення про те, що об’єкт перейшов у EMBED Equation.DSMT4 -тий стан ( EMBED Equation.DSMT4 ) визначається ймовірністю EMBED Equation.DSMT4 цього стану, при цьому менш ймовірні події несуть більшу інформацію;
кількість інформації є адитивною величиною, тобто якщо подія EMBED Equation.DSMT4 є об’єднанням подій EMBED Equation.DSMT4 і EMBED Equation.DSMT4 , то кількість інформації, породженої подією EMBED Equation.DSMT4 , дорівнює сумі кількостей інформації подій EMBED Equation.DSMT4 та EMBED Equation.DSMT4 .
3.4 Опис програми шифрування-дешифрування
1. Загальні відомості
Програма CriptoBS написана на мові Object Pascal у середовищі Delphi 6 для ОС Windows.
2. Функціональне призначення
Призначена для тестування методу криптування з використанням дерева Штерна-Броко. Дозволяє здійснювати криптування та декриптування текстових блоків довільної довжини з однобайтовим кодом (ASCII, Win 1251 та ін.)
Програма функціонує у середовищі Windows .
3. Опис логічної структури
Програма має один модуль та використовує одну форму з двома сторінками. Детальний опис алгоритму дано у п.2.2., повний текст модуля подано у додатку А.
Використовує підпрограму BitValue, процедуру SBTREE та чотири підпрограми для обробки повідомлень від кнопок.
Підпрограма-функція function BitValue(var Ind:byte; var A:Byte):byte; встановлює величину біта на позиції Ind у байті A.
Підпрограма procedure SBTREE(var NSymb,f1,f2:byte) знаходить чисельник f1 та знаменник f2 нескоротного дробу з кодом NSymb у дереві Штерна-Броко.
Вікно після запуску програми має вигляд.
4. Вхідні та вихідні дані
Вікно після запуску програми має вигляд. Після натиснення на клавішу "Ввести повідомлення" відкривається діалогове вікно вибору текстового файлу, який завантажується у вікно Memo1.

Рис. 3.2. Сторінка криптування

Рис. 3.3. Сторінка декриптування
Далі у вікнах "Довжина блоку" та "Глибина " вводять відповідні параметри. У вікно Memo2 виводяться проміжкові результати.
Після натиснення на кнопку "Зберегти" результат криптування та ключ виводяться у вікна та у вибрані текстові файли.

4. Результати тестування
Результати тестування показані на рис. 3.2 та рис. 3.3. З введеного тексту виділено блок довжиною 512 символів (байт), здійснено криптографічне перетворення цього тексту за алгоритмом Штерна-Броко глибиною 2.
У результаті отримано файл криптотексту розміром 640 байт і файл ключа розміром 128 байт.

ВИСНОВОК
У дипломній роботі досліджується можливості криптографічного перетворення за допомогою бінарного дерева Штерна-Броко.
Розглянуто такі фундаментальні поняття теорії інформації які важливі для криптології, як кількість інформації, побудова префіксних кодів за допомогою бінарних дерев, тестування випадковості.
Запропоновано варіант алгоритму криптування за допомогою бінарного дерева Штерна-Броко та здійснена його програмна реалізація на мові Object Pascal в середовищі Delphi. Проведено тестування програми для верифікації алгоритму.
Проведено попередній аналіз стійкості алгоритму криптування для типових умов криптоаналізу, який показав його високу надійність.

ЛІТЕРАТУРА
Агpановcкий А. В. Практическая криптография: Алгоритмы и их программирование / А. В. Агpановcкий, Р. А. Хади. – М.: СОЛОН-Р, 2002. – 423 с.
Архангельский А.Я. Программирование в Delphi 6. – М.: Бином, 2003. – 1120 с.
Анохин М.И. Криптография в банковском деле [Електронний ресурс]/ М. И. Анохин, Н. П. Варновский, В. М. Сидельников , В. В. Ященко. – Режим доступу: http://www.geo.web.ru.htm.
Барычев С.Г., Серов Р.Е. Основы современной криптографии / С. Г. Барычев, Р. Е. Серов . – М.: Горячая линия-Телеком, 2002. – 175 с.
Брассар Ж. Современная криптология / Ж. Брассар. – М.:Полимед, 1999. – 178 с.
Вербіцький О.В. Вступ до криптології / О. В. Вербіцький. – Львів: ВНТЛ, 1998. – 247 с.
Гихман И.И., Скороход А.В., Ядренко М.И. Теория вероятностей и математическая статистика. – К.: Вища шк., 1988. – 439 с.
Глинчук Л.Я. Алгоритм криптографічного стиснення інформації за допомогою дерева Штерна-Броко / Л. Я. Глинчук // Проблеми програмування, 2008. – №2-3. – С.575-578.
Глинчук Л.Я. Дослідження стійкості алгоритму криптографічного стиснення, побудованого на основі дерева Штерна-Броко / Л. Я. Глинчук // Вісник Донецького університету, Сер. А: Природничі науки. – 2008, вип. 2. – С. 551-555.
Грэхем Р. Конкретная математика. Основание информатики / Р. Грэхем, Д. Кнут, О. Паташник О. – М.: Мир, 1998. –703 с.
Дмитриев В. И. Прикладная теория информации / В. И. Дмитриев – М.: Высш. шк., 1989.– 320 с.
Ємець В. Сучасна криптографія. Основні поняття / В. Ємець, А. Мельник, Р. Попович. – Львів: БАК, 2003. – 144 с.
Игоничкина Е.В. Статистический анализ потоковіх шифров. – Доклады ТУСУРа, 2008. – № 2 (18), Ч.1. – С.56-57.
Кнут Д. Искусство программирования, Т. 2. Получисленные алгоритмы, 3-е изд. – М.: Вильямс, 2001. – 882 с.
Лепеха О.М. Методи побудови схем розгортання ключів в сучасних блокових симетричних шифрах: дис. на здобуття наук. ступеня канд. техн. наук : спец. 05.13.21 "Системи захисту інформації" / О. М. Лепеха. – Харків, 2005. – 23 с. ( ДСК)
Михайленко М.С. Методи та засоби блокового симетричного шифрування з підвищеною стійкістю. автореф. дис. на здобуття наук. ступеня канд. техн. наук : спец. 05.13.21 "Системи захисту інформації" / М.С. Михайленко. – Харків, 2008. – 20 с. ( ДСК)
Новиков Ф.А. Дискретная математика для программистов / Ф. А. Новиков. – СПб.: Питер, 2001. – 304 с.
Олексійчук А. М. Теоретичні основи синтезу та обґрунтування стійкості рандомізованих симетричних систем шифрування і протоколів передачі та розподілу ключів: автореф. дис. на здобуття наук. ступеня докт. техн. наук : спец. 05.13.21 "Системи захисту інформації" / А. М. Олексійчук. – Київ, 2009. – 36 с. ( ДСК)
Потапов В.Н. Теория информации. Кодирование дискретних вероятностных источников / В. Н. Потапов. – Новосибирск, 1999. – 71 с.
Торба Г. О. Методи формування випадкових послідовностей з підвищеною швидкодією для систем захисту інформації: автореф. дис. на здобуття наук. ступеня докт. техн. наук : спец. 05.13.21 "Системи захисту інформації" / Г. О. Торба. – Харків, 2009. – 23 с. ( ДСК)
Фергюсон Н. Практическая криптографія / Н. Фергюсон, Б. Шнайер. – М.: Вильямс, 2005. – 424 с.
Хорошко В.А. Методы и средства защиты информации / В. А. Хорошко, А. А. Чекатков, под ред. Ю.С. Ковтанюка. – К.: Юниор, 2003. – 504 с.
Шеннон К. Работы по теории информации и кибернетике / К. Шеннон. – М.: Издательство иностранной литературы. – 829 с.
Шнайер Б. Прикладная криптография. Протоколы, алгоритмы и исходные тексты на языке Си / Б. Шнайер. – М.: Триумф, 2003. – 816 с.
ДОДАТОК А Основні блоки програми у середовищі Delphi
unit BinaryTree;
interface
uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, ExtCtrls, ComCtrls, Math;
type
TForm1 = class(TForm)
PageControl1: TPageControl;
TabSheet1: TTabSheet;
TabSheet2: TTabSheet;
LE_L: TLabeledEdit;
LE_m: TLabeledEdit;
Memo1: TMemo;
Button1: TButton;
Button2: TButton;
Memo2: TMemo;
OpenDialog1: TOpenDialog;
SaveDialog1: TSaveDialog;
Memo3: TMemo;
Memo4: TMemo;
Button3: TButton;
Memo5: TMemo;
Button5: TButton;
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure Button3Click(Sender: TObject);
procedure Button5Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
implementation
{$R *.dfm}
var Fname,Fname2, sProt, IniStr0, ResStr,SSR,SS0:String;
L0,M0:integer;
function BitValue(var Ind:byte; var A:Byte):byte;
//
// Величина біта на позиції Ind у байті A
//
var
Shablon: array[0..7] of byte;
i:byte;
begin
BitValue:=0; Shablon[0]:=1;
for i:=1 to 7 do Shablon[I]:=Shablon[I-1]*2;
If (A and Shablon[ind])=Shablon[ind] then BitValue:=1;
end;
procedure SBTREE(var NSymb,f1,f2:byte);
//
// Нескоротний дріб з номером NSymb у дереві Штерна-Броко,
// f1 - чисельник, f2 - знаменник
//
var
j,i,a11,a12,a21,a22:byte;
begin
a11:=1; a12:=0; a21:=0; a22:=1;
for j:=0 to 7 do
begin
i:=7-j;
if BitValue(i, Nsymb)=0
then begin a11:=a11+a12; a21:=a21+a22; end
else begin a12:=a11+a12; a22:=a21+a22; end;
end;
f1:=a21+a22; f2:=a11+a12;
end;
procedure TForm1.Button1Click(Sender: TObject);
//
// Завантаження початкового тексту
//
begin
Randomize;
if OpenDialog1.Execute
then begin
FName:= OpenDialog1.FileName;
Memo1.Lines.LoadFromFile(FName);
sProt:='Inputed file'+Fname;
Memo3.Lines.Clear;
Memo3.Lines.Add(sProt);
end
end;
procedure TForm1.Button2Click(Sender: TObject);
//
// Криптування
//
var
L1,iStr,NumStr,NumLet,i,il,im,k,if1,if2:integer;
IniStr,WorkStr,RobStr,SS,SSZ:string;
nwk,f1,f2,akb,bkb,xk,yk:byte;
wk,wf1,wf2:char;
begin
//
// Вхідні дані
//
L0:=StrToInt(LE_L.Text);
M0:=StrToInt(LE_m.Text);
NumStr:=Memo1.Lines.Count;
//
// Перетворення тексту у стрічку
//
IniStr0:='';il:=0;
for iStr:=0 to NumStr do
begin
WorkStr:=Memo1.Lines[iStr];
NumLet:=Length(WorkStr);
for i:=1 to NumLet do
begin
il:=il+1;
if il<=L0 then IniStr0:=IniStr0+WorkStr[i];
end;
end;
IniStr:=IniStr0;
Memo3.Lines.Add('Читання тексту');
Memo3.Lines.Add(IniStr);
ResStr:='';
L1:=L0;
//
// Очищення
//
Memo2.Lines.Clear;
Memo3.Lines.Clear;
Memo4.Lines.Clear;
Memo5.Lines.Clear;
//
for im:=1 to m0 do {Цикл по глибині перетворення}
begin
L1:=L1 div 2;
SSZ:='';SS:='';
//
for k:=1 to L1 do {Цикл по парах символів}
begin
nwk:=RandomRange(0,255);
wk:=Chr(nwk);
Memo3.Lines.Add(wk);
SS:=SS+wk;
SBTREE(nwk, f1,f2);
wf1:= Chr(f1); wf2:= Chr(f2);
if1:=f1; if2:=f2;
Memo3.Lines.Add(IntToStr(if1)+' '+IntToStr(if2));
akb:=ord(IniStr[2*k-1]); bkb:=ord(IniStr[2*k]);
xk:=f1 XOR akb; yk:=f2 XOR bkb;
SSZ:=SSZ+Chr(xk)+Chr(yk);
end; {Цикл по парах символів}
RobStr:=ResStr;
ResStr:=Concat(RobStr,SSZ);
Memo3.Lines.Add('Текст');
Memo3.Lines.Add(ResStr);
IniStr:=SS;
end; { Цикл по глибині}
SSR:=SS;
// Очищення
Memo2.Lines.Clear;
Memo4.Lines.Clear;
//
// Вивід результату криптування
//
Memo2.Lines.Add(ResStr);
Memo4.Lines.Add(SSR);
end;
procedure TForm1.Button3Click(Sender: TObject);
//
// Декриптування
//
var
L1,iz,i,im,k,if1,if2:integer;
SS,SS1:string;
nwk,f1,f2,akb,bkb,xk,yk:byte;
wk,wf1,wf2:char;
miz: array [1..100] of integer;
begin
//
L1:=L0;
SS:=SSR;
iz:=0;
miz[1]:=0;
for i:=1 to m0 do
begin
iz:=iz+L1;
miz[i+1]:=iz;
L1:=L1 div 2;
end;
//
for i:=1 to m0 do {Цикл по глибині}
begin
im:=m0-i+1;
SS1:='';
iz:=miz[im];
//
for k:=1 to L1 do {Цикл по парах символів}
begin
wk:=SS[k];
nwk:=ord(wk);
Memo3.Lines.Add(wk);
SBTREE(nwk, f1,f2);
wf1:= Chr(f1); wf2:= Chr(f2);
if1:=f1; if2:=f2;
Memo3.Lines.Add(IntToStr(if1)+' '+IntToStr(if2));
xk:=Ord(ResStr[iz+2*k-1]); yk:=Ord(ResStr[iz+2*k]);
akb:=f1 XOR xk; bkb:=f2 XOR yk;
SS1:=SS1+Chr(akb)+Chr(bkb);
end; {Цикл по парах символів}
SS:=SS1;
L1:=L1*2;
end; { Цикл по глибині}
//
// Вивід результату декриптування
//
SS0:=SS;
Memo5.Lines.Clear;
Memo5.Lines.Add(SS0);
//
end;