Криптографічний аналіз
Міністерство
культури і туризму України
Київський
національний університет культури і мистецтв
Факультет
економіки і менеджменту
Кафедра
комп’ютерних наук
КУРСОВА
РОБОТА
з
дисципліни «Технології створення програмних продуктів»
на
тему: «Криптографічний аналіз»
Роботу виконав
Студент ІV курсу
групи КН-29
Рудницький
Павло Олегович
Науковий керівник:
доц. Гузій М.М.
Київ
-2012р.
Реферат
Курсова робота складається з 31 сторінки включаючи додаток.
Пояснювальна записка містить у собі: одну таблицю, дев’ять
ілюстрацій, одну таблицю, чотири блок схеми, один додаток, чотири джерела.
Об’єкт дослідження:Частотний аналіз, частотний крипто аналіз,
статистичний аналіз - один з методів крипто аналізу.
Мета:Закріплення вивченого матеріалу з дисципліни «Розробка
програмних продуктів»
Технічні та програмні засоби:Програмний продукт виконувався
за допомогою мови програмування С#, у середовищі visual studio express 2010.
Висновки: Знайдено такий недолік статистичного методу
кріптоаналізу, як що вхідний текст недостатньо великий то не буде вистачати
унікальних значень для створення ключа.
Як що
в створені ключа використовується лише метод порівняння частоти входження
символу в тексті, то доцільно програми доповнювати алгоритмами пошуку ширини
слів. Оскільки в процесі порівняння отримується така велика кількість варіантів
дешифвації, то подальший його процес теж треба автоматизовувати.
Рекомендації щодо використання результатів роботи: Програмний
продукт рекомендується використовувати на великих обсягах тексту для отримання
ключів простих шифрів котрі працюють по принципам заміни символів.
Ключові слова: ООП, Криптографічний аналіз, Шифротекст,
Статистичний аналіз, Частотний аналіз, Криптографія, Криптограф.
Вступ
Актуальність
У міру розвитку нових методів шифрування математика ставала
все більш і більш значущою. Так, наприклад, при частотному аналізі
криптоаналітик повинен володіти знаннями і в лінгвістиці, і в статистиці. У той
час як теоретичні роботи з криптоаналізу Енігми виконувалися переважно
математиками, наприклад, Аланом Матісоном Тьюрінгом. Тим не менше завдяки все
тій же математиці криптографія досягла такого розвитку, що кількість необхідних
для злому елементарних математичних операцій стало досягати астрономічних
значень. Сучасна криптографія стала набагато більш стійкою до криптоаналізу,
ніж колись використовувані, застарілі методики, для злому яких було достатньо
ручки і аркуша паперу. Може здатися, що чистий теоретичний криптоаналіз не
здатний більш ефективно зламувати сучасні шифри. Тим не менш історик Девід Кан
у своїй замітці до 50-ої річниці Агентства національної безпеки пише:
"У наші дні сотні фірм пропонують безліч різних
криптосистем, які неможливо зламати жодним з відомих методів криптоаналізу.
Дійсно, такі системи стійкі навіть до атаки по підібраному відкритому тексту,
тобто порівняння відкритого тексту і відповідного йому шіфротекста не дозволяє
дізнатися ключ шифрування, який би дозволив дешифрувати інші повідомлення.
Таким чином, в деякому розумінні криптоаналіз мертвий. Але це ще не кінець.
Криптоаналіз може бути і мертвий, але, висловлюючись метафорично, з кішки можна
зняти шкірку декількома способами ».
Тим не менш, криптоаналіз поки ще рано списувати з рахунків.
По-перше, невідомо, наскільки ефективні вживані спецслужбами методи криптоаналізу,
а по друге-, за роки становлення та вдосконалення сучасної комп'ютерної
криптографії було висловлено безліч претензій як до теоретичних, так і до
практичних криптографічних примітивів.
У 1998 було виявлена уразливість до атак на основі
шіфротекста у блоковий шифр MADRYGA, запропонований ще в 1984 році, але не
отримав широкого розповсюдження.
Ціла серія атак з боку наукового співтовариства, багато з
яких були цілком практичними, буквально знищила блоковий шифр FEAL,
запропонований як заміна DES в якості стандартного алгоритму шифрування, але
також не отримав широкого розповсюдження
Також було встановлено, що за допомогою широко доступних
обчислювальних засобів потокові шифри A5 / 1, A5 / 2, блоковий шифр РЕВ, і
стандарт шифрування DECT, використовувані для захисту мобільного і бездротового
телефонного зв'язку, можуть бути зламані за лічені години чи хвилини, а порию і
в режимі реального часу.
Атака методом грубої сили допомогла зламати деякі з
прикладних систем захисту, наприклад, CSS-систему захисту цифрового
медіаконтенту на DVD-носіях.
Таким чином, хоча найбільш надійні з сучасних шифрів є
набагато стійкішими до криптоаналіз, ніж Енігма, тим не менш криптоаналіз як і
раніше відіграє важливу роль в обширній області захисту інформації.
Мета:
Дослідження методів криптографічного аналізу, програмна
реалізація одного з методів криптографічного аналізу, набуття навичок в ООП.
Об`єкт дослідження:
Частотний аналіз, частотний крипто аналіз, статистичний
аналіз - один з методів криптоаналізу, що грунтується на припущенні про
існування нетривіального статистичного розподілу окремих символів і їх
послідовностей як у відкритому тексті, так і в шіфротекста, яке, з точністю до
заміни символів, буде зберігатися в процесі шифрування і дешифрування
статичний кріптоаналіз алгоритм
Розділ
1. Теоретичні відомості
.1
Опис методу
У загальному випадку статистичний аналіз виконується
наступним чином:
За перехопленої криптограмі обчислюється деяка статистика. Ця
статистика така, що для всіх осмислених повідомлень вона приймає значення, що
мало відрізняються від, величини, залежної тільки від приватного
використовуваного ключа.
Отримана таким чином величина служить для виділення тих
можливих ключів, для яких значення лежить в близькому оточенні спостереженого
значення.
Статистика, яка не залежить від чи змінюється в залежності
від так само сильно, як і в залежності від, не може бути істотна для виділення
деякого підмножини ключів. Так, у шифрах транспозиції підрахунок частот букв не
дає ніякої інформації про - для будь-якого ця статистика залишається тією ж
самою. Тому не можна витягти ніякої користі з підрахунку частот для розкриття
шифрів транспозиції. Більш точно даній статистиці можна приписати деяку
«роздільну потужність». Для кожної величини є умовна ненадійність ключа (ненадійність
при фіксованому значенні) і це все, що відомо щодо ключа. Середнє арифметичне
зважене цих величин дає середню ненадійність ключа при відомому, де є апріорною
ймовірністю конкретного значення. Різниця обсягу ключа і цієї середньої
невизначеності вимірює «роздільну потужність» статистики. У строго ідеальному
шифрі всі статистики даної криптограми не залежать від приватного
використовуваного ключа. Це випливає з властивості збереження міри
перетворенням в просторі або в просторі.
Є хороші і погані статистики, точно так само, як є хороші і
погані методи випробувань та помилок. Фактично перевірка деякої гіпотези
методом випробувань і помилок являє собою деякий тип статистики, і те, що було
сказано вище щодо найкращих типів випробувань, вірно і взагалі.
.2
Властивості гарної статистики
Хороша статистика для вирішення системи повинна володіти
наступними властивостями:
1. Вона повинна просто обчислюватися;
2. Вона повинна залежати від ключа більше, ніж від
повідомлення, якщо з її допомогою потрібно знаходити ключ. Зміни по не повинні
маскувати змін по. Ті значення статистики, які можуть бути «відмінності»,
незважаючи на «розмитість», створювану зміною по, повинні поділяти простір
ключів на кілька підмножин, ймовірності яких порівняні по величині, причому
статистика буде характеризувати підмножина, в якому лежить правильний ключ;
. Статистика повинна давати інформацію про значні
обсяги ключа, а не про обсяги, складових малу частку загального числа біт;
. Інформація, що дається статистикою, повинна бути простою
і зручною для використання. Таким чином, підмножини, на які статистика поділяє
простір ключів, повинні мати просту структуру в просторі ключів.
Розділ
2. Модель статичного кріптоаналізу
Розглянемо безліч повідомлень довжини N символів для даної
мови. Коефіцієнт мови довжиною N визначається як
= Н (Х) / N
де H (Х) - кількість інформації при виборі повідомлення X.
Надмірність мови з коефіцієнтом r визначається за формулою:
= R-г
де R - абсолютний коефіцієнт мови;
= log2 L
де L - довжина алфавіту мови.
Для англійської мови R = log2 26 = 4,7 біт на букву.
Тоді
= H (Z) / D
де H (Z) - кількість інформації при виборі ключа Z.
Обчислимо кількість букв, необхідне для розкриття
повідомлення, зашифрованого методом підстановки, в алфавіті довжиною L. Якщо всі
ключі рівноймовірно, то число можливих ключів одно L!. Тоді
= H (Z) / D = log2 L! / D.
Для англійської мови No = log2 26! / 3,2 = 27,6.
Таким чином, 27-28 букв достатньо для розкриття розглянутого
шифру за допомогою частотного аналізу. Якщо обсяг перехопленого шифртексту
перевершує точку єдиності, криптограма в принципі може бути вирішена перебором
всіх можливих ключів, поки не вийде єдине рішення (повідомлення, що має сенс у
даному мовою).
Багато видів шифрів можуть бути розкриті за допомогою
статистичного аналізу, тому що всі природні мови мають характерне частотний
розподіл букв. Наприклад, для англійської мови частоти появи літер наведені в
таблиці1:
|
буква
|
частота,%
|
буква
|
частота,%
|
буква
|
частота,%
|
|
A
|
8.1
|
K
|
0.4
|
V
|
0.9
|
1.4
|
L
|
3.4
|
W
|
1.5
|
|
C
|
2.7
|
M
|
2.5
|
X
|
0.2
|
|
D
|
3.9
|
N
|
7.2
|
Y
|
1.9
|
|
E
|
13.0
|
O
|
7.9
|
Z
|
0.1
|
|
F
|
2.9
|
P
|
2.0
|
G
|
2.0
|
|
H
|
5.2
|
S
|
6.1
|
I
|
6.5
|
|
J
|
0.2
|
U
|
2.4
|
|
|
Таблиця1
З таблиці видно, що Е - найбільш часто зустрічається буква в
англійській мові, а Z - найбільш рідкісна.
Багато повідомлення, зашифровані методами перестановки чи
заміни, зберігають характерне частотний розподіл букв і тим самим надають
можливість розкриття шифру. Введемо міру точності:
= торб. (Pi-1 / L) ** 2 i = 0 .. (L-1)
де торб. Pi = 1; i = 0 .. (L-1)ймовірність (частота) появи
i-й букви;- кількість символів в алфавіті.
Для англійської мови
= сум. (Pi-1/26) ** 2 = сум. (Pi ** 2) -2/26 +1 / 26 = сум.
Pi ** 2 -0.038 = 0.03= 0 .. 25
Загальне число пар букв, які можуть бути обрані з тексту
довжиною N символів, є
n = N * (N-1) / 2
Нехай fi-частота i-й букви в тексті; сум. fi = N
Тоді визначимо індекс відповідності Ic наступним чином:
= (сум. fi * (fi-1)) / (N * (N-1)) i = 0 .. 25
Теоретичне значення для англійської мови Ic = 0,066. Якщо
шифр використовує m алфавітів, то можна записати:
= (1 / m) * ((Nm) / (N-1)) * 0,066 + ((m-1) / m) * (N /
(N-1)) * 0,038.
Таким чином, шифртексту, для яких Ic> 0,066, дають
криптоаналітика інформацію про те, що, ймовірно, використовувалася
моноалфавитной заміна. Якщо 0.052 <= Ic <= 0.066, то, ймовірно,
використовувався двухалфавітний підстановлювальний шифр. Значення індексів
відповідності для різного числа алфавітів наведені у таблиці 12.
Процес криптоаналізу можна представити таким чином.
Криптоаналітика бере найбільш часто зустрічається в шифртексту символ і
припускає, що це прогалина. Потім криптоаналітик бере наступний найбільш часто
зустрічається символ і припускає, що це Е (для англійської мови), і т.д.
Шляхом проб і помилок такий метод може призвести до вирішення
завдання. Крім того, при підставляння букв замість символів аналізованого
шифртексту криптоаналітик враховує частоти появи сполучень з двох літер
(діаграм), трьох букв (триграм) і т.д.
Розділ
3 Програмна реалізація
.1 C
#
# (вимовляється сі шарп) - об'єктно-орієнтована мова
програмування. Розроблено в 1998-2001 роках групою інженерів під керівництвом
Андерса Хейлсберга в компанії Microsoft як мова розробки додатків для платформи
Microsoft.Framework і згодом був стандартизований як ECMA-334 і ISO / IEC
23270.# відноситься до сім'ї мов з C-подібним синтаксисом, з них його синтаксис
найбільш близький до C + + і Java. Мова має статичну типізацію, підтримує
поліморфізм, перевантаження операторів (у тому числі операторів явного і
неявного приведення типу), делегати, атрибути, події, властивості, узагальнені типи
і методи, ітератори, анонімні функції з підтримкою замикань, LINQ, виключення,
коментарі у форматі XML.
Перейнявши багато що від своїх попередників - мов C + +,
Java, Delphi, Модула і Smalltalk - С #, спираючись на практику їх використання,
виключає деякі моделі, що зарекомендували себе як проблематичні при розробці
програмних систем, наприклад, C # на відміну від C + + не підтримує множинне
успадкування класів (між тим допускається множинне спадкування інтерфейсів).
Особливості
мови C #
C # розроблявся як мова програмування прикладного рівня для
CLR і, як такий, залежить, насамперед, від можливостей самої CLR. Це
стосується, перш за все, системи типів C #, яка відображає BCL. Присутність або
відсутність тих чи інших виразних особливостей мови диктується тим, чи може
конкретна мовна особливість бути транслювали у відповідні конструкції CLR. Так,
з розвитком CLR від версії 1.1 до 2.0 значно збагатився й сам C #; подібної
взаємодії слід чекати і надалі. (Проте ця закономірність була порушена з
виходом C # 3.0, що представляє собою розширення мови, не спираються на
розширення платформи. NET.) CLR надає C #, як і всім іншим. NET-орієнтованим
мовам, багато можливостей, яких позбавлені «класичні» мови програмування.
Наприклад, збірка сміття не реалізована в самому C #, а проводиться CLR для
програм, написаних на C # точно так само, як це робиться для програм на VB.NET,
J #.
3.2
Алгоритм програми криптографічного аналізу
Блок схема №1 «Робота кнопок 1-3»(основний сценарій).
Код
основного сценарію:
private void button1_Click(object sender, EventArgs e)
{.KriptoAnaliz Input = new Kript.KriptoAnaliz();.InputText =
this.textBox1.Text;s = this.textBox1.Text;.InputText = s;dt = new
DataTable();.Columns.Add("Символ");.Columns.Add("Статистика");(int i = 0; i < s.Length;
i++)
{cunter=0;(int j = 0; j < dt.Rows.Count;
j++)(Convert.ToString(dt.Rows[j]["Символ"])[0] == s[i])
{++;
}(cunter == 0)
{dr = dt.NewRow();["Символ"] = s[i];["Статистика"] = Input.Analiz(s, i);.Rows.Add(dr);
}.DataSource = dt;
}
}
Код підрахунку статистики:
public float Analiz(string Liter, int k)
{liter = Liter;= 0;(int i = 0; i < InputText.Length; i++)
{(liter[k] == InputText[i])++;
}Static = (Static / InputText.Length) * 100;
}
Блок схема №3
(порівняння статистик)
Код порівняння статистик:
private void button3_Click(object sender, EventArgs e)
{dt = new DataTable();.Columns.Add("Исходный символ");
dt.Columns.Add("закодированый символ");
for (int i = 0; i < dataGridView1.Rows.Count; i++)
{(int j = 0; j < dataGridView2.Rows.Count; j++)
{(Convert.ToString(dataGridView2.Rows[j].Cells["Статистика"].Value) ==
Convert.ToString(dataGridView1.Rows[i].Cells["Статистика"].Value))
{dr = dt.NewRow();["Исходный символ"]
=dataGridView1.Rows[i].Cells["Символ"].Value;["закодированый символ"] =
dataGridView2.Rows[j].Cells["Символ"].Value;.Rows.Add(dr);
}
}
}
.DataSource = dt;
}
Блок
схема №4 (Спроба дешифрації)
Код
Спроби дешифрації:
private void button4_Click(object sender, EventArgs e)
{sv1 = this.textBox1.Text;(int i = 0; i <
dataGridView3.Rows.Count; i++)
{(Convert.ToString(dataGridView3.Rows[i].Cells["закодированый символ"].Value) !=
Convert.ToString(dataGridView3.Rows[i].Cells["Исходный символ"].Value))=
sv1.Replace(Convert.ToString(dataGridView3.Rows[i].Cells["закодированый символ"].Value),
Convert.ToString(dataGridView3.Rows[i].Cells["Исходный символ"].Value));
}.Text = sv1;
}
3.3
Інтерфейс програми
Інтерфейс програми, складається з таких елементів рис1:
· textBox
· tabPage
· button
· dataGridView
Рис.1
Кожна вкладка відповідає за свій процес: аналіз вихідного
тексту, аналіз зашифрованого тексту, отримання ключа.
3.4
Приклад роботи програми
Приклад
1
Нехай вхідним словом S буде «аббввв».
Крок 1 задамо вхідний текст рис.2
Рис.2
Крок 2 задамо зашифрований текст рис.3
Нехай а = 1, б = 2, в = 3 то слово S = 122333
Рис.3
Крок 3 отримання ключа и спроба дешифрації рис.4
Рис.4
Після отримання ключа можна провести спробу дешифрації.
Приклад
2
Нехай S = «Криптоаналіз (від др.-греч. Κρυπτός
- прихований і
аналіз) - наука про методи розшифровки зашифрованою інформацією без
призначеного для такої розшифровки ключа Термін був введений американським
криптографом Вільямом Ф. Фрідманом в 1920 році. Неформально криптоаналіз
називають також зломом шифру» рис. 5
Рис. 5
Отримуємо таку статистику.
Шифруємо текст: S = «Кри35о1н1ліз (2ід др.-греч. Κρυπτός
- 3рихо21ний і 1н1ліз) -
н1ук1 3ро ме5оди роз4ифро2ки з14ифро21ною інформ1цією без 3ризн1ченого для
51кої роз4ифро2ки ключ1 5ермін бу2 22едений 1мерик1нським кри35огр1фом 2ільямом
Ф. Фрідм1ном 2 1920 році. Неформ1льно кри35о1н1ліз н1зи21ю5ь 51ко4 зломом
4ифру» рис.6
Рис.6
Спробуємо отримати ключ.рис.7
Рис.7
Як бачимо програма відображає усі можливі варіанти
співвідношення кодованого тексту и вхідного.
Приклад
3
Не хай S = «увесь
вступ»
Тоді отримуємо статистику рис. 8
Рис. 8
Нехай зашифрований текст дорівнює вхідному
Тоді коли ми порівнюємо їх статистики то отримуємо такий ключ
рис.9
Рис.9
Висновки
Знайдено
такий недолік статистичного методу кріптоаналізу, як що вхідний текст
недостатньо великий то не буде вистачати унікальних значень для створення
ключа.
Як що
в створені ключа використовується лише метод порівняння частоти входження
символу в тексті, то доцільно програми доповнювати алгоритмами пошуку ширини
слів. Оскільки в процесі порівняння отримується така велика кількість варіантів
дешифвації, то подальший його процес теж треба автоматизовувати.
Додаток
Повний
код програми
using System;
using System.Collections.Generic;System.ComponentModel;System.Data;System.Drawing;System.Linq;System.Text;System.Windows.Forms;
WindowsFormsApplication1
{partial class Form1 : Form
{Form1()
{();
}
{
}
void button1_Click(object sender, EventArgs e)
{.KriptoAnaliz Input = new Kript.KriptoAnaliz();.InputText =
this.textBox1.Text;s = this.textBox1.Text;.InputText = s;dt = new
DataTable();.Columns.Add("Символ");.Columns.Add("Статистика");(int i = 0; i < s.Length;
i++)
{cunter=0;(int j = 0; j < dt.Rows.Count;
j++)(Convert.ToString(dt.Rows[j]["Символ"])[0] == s[i])
{++;
}(cunter == 0)
{dr = dt.NewRow();["Символ"] = s[i];["Статистика"] = Input.Analiz(s, i);.Rows.Add(dr);
}.DataSource = dt;
}
}
void button2_Click(object sender, EventArgs e)
{.KriptoAnaliz Input = new Kript.KriptoAnaliz();.InputText =
this.textBox1.Text;s = this.textBox1.Text;.InputText = s;dt = new
DataTable();.Columns.Add("Символ");.Columns.Add("Статистика");(int i = 0; i < s.Length;
i++)
{cunter = 0;(int j = 0; j < dt.Rows.Count;
j++)(Convert.ToString(dt.Rows[j]["Символ"])[0] == s[i])
{++;
}(cunter == 0)
{dr = dt.NewRow();["Символ"] = s[i];["Статистика"] = Input.Analiz(s, i);.Rows.Add(dr);
}
.DataSource = dt;
}
}
void button3_Click(object sender, EventArgs e)
{dt = new DataTable();.Columns.Add("Исходный символ");
dt.Columns.Add("закодированый символ");
for (int i = 0; i < dataGridView1.Rows.Count; i++)
{(int j = 0; j < dataGridView2.Rows.Count; j++)
{(Convert.ToString(dataGridView2.Rows[j].Cells["Статистика"].Value) ==
Convert.ToString(dataGridView1.Rows[i].Cells["Статистика"].Value))
{dr = dt.NewRow();["Исходный символ"]
=dataGridView1.Rows[i].Cells["Символ"].Value;["закодированый символ"] = dataGridView2.Rows[j].Cells["Символ"].Value;.Rows.Add(dr);
}
}
}
.DataSource = dt;
}
void button4_Click(object sender, EventArgs e)
{sv1 = this.textBox1.Text;(int i = 0; i <
dataGridView3.Rows.Count; i++)
{(Convert.ToString(dataGridView3.Rows[i].Cells["закодированый символ"].Value) !=
Convert.ToString(dataGridView3.Rows[i].Cells["Исходный символ"].Value))=
sv1.Replace(Convert.ToString(dataGridView3.Rows[i].Cells["закодированый символ"].Value),
Convert.ToString(dataGridView3.Rows[i].Cells["Исходный символ"].Value));
}.Text = sv1;
}
}
}
Kript
{KriptoAnaliz
{string InputText;float Static;float Analiz(string Liter, int
k)
{liter = Liter;= 0;(int i = 0; i < InputText.Length; i++)
{(liter[k] == InputText[i])++;
}Static = (Static / InputText.Length) * 100;
}
}
}