Основи класичної криптографії та криптоаналізу та їх історичний

Розвиток

 

Подивимося, як розвивалася криптографія та які методи покладені в основу класичної криптографії.

Надамо визначення криптографії [4]. Криптографія – дисципліна, що включає принципи, засоби та математичні методи перетворення інформації з метою приховування змісту та структури даних, а також для їх захисту від несанкціонованого використання або підробки. Додамо, що крім криптографії використовуються кодування та стеганографія, які ми розглянемо нижче.

Основним методом криптографії є шифрування. Шифруванням зветься взаємно-однозначне перетворення відкритого повідомлення у закрите шляхом перетворення літер відкритої абетки у літери таємної абетки. Мета шифрування - приховування змісту відкритого повідомлення від сторонніх осіб.

Отже, сенс шифрування лежить у заміні однієї, відомої всім відкритої абетки, що використовується для написання відкритого повідомлення, на іншу, відому лише відправнику та адресату.

Історично так і склалося, що одним з найперших шифрів був шифр заміни. Це так званий шифр Цезара відомості про який дійшли до нас від “батька історії” – Геродоту [21]. Принцип простого шифру заміни наведено на рис. 5.1.

Відкрита абетка: А, Б, В, Г, Д, Е, Є, Ж, З, И, К, Л, М, Н,.., Ш, Щ, Ю, Я

Таємна абетка: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12,13, 14,.., 29, 30, 31, 32

Рис. 5.1. Принцип побудови простого шифру заміни

 

 

На рис. 5.2 надано реальний шифр Цезара, у вигляді, наданим Геродотом

Відкрита абетка: A, B, C, D, E, F,………………….., W, X, Y, Z

Таємна абетка: D, E, F, G, H, I,…………………..., Z, A, B, C

 

Рис. 5.2. Шифр Цезара

 

З рис. 5.2 видно, що таємна абетка утворена шляхом зсуву літер таємної абетки на три позиції лівіше відносно відкритої абетки. Таким чином літера А відкритої абетки шифрується літерою D таємної абетки і так далі. Зрозуміло, що замість літер у таємній абетці можуть бути використані, наприклад, символи або цифри.

Це так звані одноабеткові (прості) шифри заміни. Особливістю простих шифрів заміни є їх низька стійкість, оскільки такий шифр легко піддається криптоаналізу з використанням таблиці частотності.

Це, до речі, чудово проілюстровано у оповіданні Едгара По “Золотий жук”.

Криптоаналіз з використанням таблиці частотності був винайдений арабами приблизно у 750 – 850 р.р. н.е. Саме в той час відбувався розквіт арабської культури у халіфаті під час панування династії Аббасидів. І саме в той час було відкрито спосіб частотного аналізу зашифрованих текстів.

Цей спосіб засновано на тому, що у будь-якій мові існує залежність між літерами, що відповідають певним звукам, та частотою їх використання у мові й, відповідно, у письмових текстах [21].

Існує припущення, що після хрестових походів цій спосіб розшифрування перехоплених шифрованих повідомлень потрапив у Європу, де з часом дістав широкого використання.

Таблиця частотності для, наприклад, англійської мови, надається у табл. 5.1.

Таблиця 5.1.

Літе-ра	Частота появлення, %	Літе-ра	Частота появлення, %
a	8,2	n	6,7
b	1,5	o	7,5
c	2,8	p	1,9
d	4,3	q	0,1
e	12,7	r	6,0
f	2,2	s	6,3
g	2,0	t	9,1
h	6,1	u	2,8
i	7,0	v	1,0
j	0,2	w	2,4
k	0,8	x	0,2
l	4,0	y	2,0
m	2,4	z	0,1

 

Класичним прикладом компрометації одноабеткового шифру заміни є історичний факт розшифрування шифру Марії Стюарт, що закінчилося для неї смертним вироком.

Подивимося як розвивалася класична криптографія у напрямку створення загальної теорії абсолютно стійкого шифрування, яка, нарешті, була надана Клодом Шенноном.

Питаннями розвитку криптографічного захисту (як і криптоаналізу) завжди займалися видатні математики, наприклад, Франсуа Вієт, Джероламо Кордано, Джон Валліс. Використання математики для криптографії та

криптоаналітики сприяло появленню нових методів як закриття інформації, так і дешифрування перехоплених шифрограм.

У таку ж сиву давнину з’явилося шифрування методом перестановки, яке стало іншим етапом розвитку криптографії.

Перші повідомлення про його застосування спартанцями дійшли до нас від Геродоту та відносяться до V віку до н.е. Спартанці для шифрування методом перестановки винайшли перший військовий шифрувальний апарат – так звану скиталу. Це циліндр визначеного діаметру, на який намотувалася по спіралі смужка шкіри. На шкірі горизонтально вздовж утворених таким чином рядків записувалося відкрите повідомлення. При розмотуванні стрічки на ній утворювалося зашифроване повідомлення. Щоб його розшифрувати потрібно було стрічку з шифровкою намотати на скиталу того ж діаметру.

Для того, щоб зрозуміти принцип дії цього методу розглянемо наступний приклад.