5.2. Основи сучасної криптографії

5.2.1. Традиційні симетричні криптосистеми

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

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

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

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

• достатня криптостійкість (надійність закриття даних);

• простота процедур шифрування та розшифровування;

• незначна надлишковість інформації за рахунок шифрування:

• нечутливість до незначних помилок шифрування та ін.

В тій чи іншій мірі цим вимогам відповідають:

• шифри перестановок;

• шифри заміни;

• шифри гамування;

• шифри, що базуються на аналітичних перетвореннях даних, що шифруються.

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

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

Шифрування гамуванням полягає в тому, що символи шифрованого тексту поєднуються з символами деякої випадкової послідовності, яка називається гамою шифру. Стійкість шифрування визначається в основному довжиною (періодом) гами шрифту. Оскільки за допомогою ЕОМ можна генерувати практично безмежну гаму шифру, то даний спосіб є одним із головних для шифрування інформації в інформаційних системах [Error: Reference source not found].

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

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

Як відкритий текст, так і шифротекст утворюються із букв, що входять до скінченної множини символів, яка називається алфавітом. При виконанні криптографічних перетворень корисно замінити букви алфавіту цілими числами, що дозволяє спростити виконання необхідних алгебраїчних маніпуляцій. Заміна букв традиційного алфавіту числами дозволяє більш чітко cформулювати основні концепції та прийоми криптографічних перетворень. Хоча в багатьох шифрах, зокрема класичних, напряму використовується звичайний алфавіт.

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

Шифри перестановки. При шифруванні перестановкою символи шифрованого тексту переставляються за певним правилом в межах блоку цього тексту. Шифри перестановки є найпростішими і ймовірно найдавнішими шифрами.

Таблиці шифрування. В шифрах перестановки епохи Відродження застосовувалися таблиці шифрування, які, по суті, задають правила перестановки букв у повідомленнях. В якості ключа в таблицях шифрування використовується:

• розмір таблиці;

• слово чи фраза, що задають перестановку;

• особливості структури таблиці.

Одним з найпримітивніших табличних шифрів перестановки є проста перестановка, ключем для якої служить розмір таблиці. Наприклад повідомлення „президент прибуває четвертого опівночі“ записується в таблицю почергово по стовпцях. Результат заповнення таблиці із 5 рядків та 7 стовпців представлено на рис. 5.5.

Після заповнення таблиці текстом повідомлення по стовпцях для формування шифротексту зчитують вміст таблиці по рядках. Якщо шифротекст записувати групами по п’ять букв, отримується таке шифроване повідомлення: „пдрав гвреи єеоне нбчро озтуе тпчип втоіі“. Зрозуміло, що відправник та отримувач повинні заздалегідь домовитися про спільний ключ у вигляді розміру таблиці. Слід зазначити, що об’єднання букв шифротексту в 5-буквені групи не входить до ключа шифру і використовується виключно для зручності записування тексту, що не має змісту. При розшифровуванні дії виконуються в оберненому порядку.

п	д	р	а	в	г	в
р	е	и	є	е	о	н
е	н	б	ч	р	о	о
з	т	у	е	т	п	ч
и	п	в	т	о	і	і

Рис. 5.5. Найпростіший приклад шифрування з використанням таблиці перестановки

Дещо більшою стійкістю до розкриття характеризується метод шифрування, який називається одиночною перестановкою по ключу. Цей метод відрізняється від попереднього тим, що стовпці таблиці переставляються по ключовому слову, фразі чи набору чисел, довжиною в рядок таблиці. Застосуємо в якості ключа, наприклад, слово „пелікан“, а текст повідомлення візьмемо з попереднього прикладу. На рис. 5.6 показано дві таблиці, заповнені текстом повідомлення та ключовим словом, причому ліва таблиця відповідає заповненню до перестановки, а права – після перестановки.

п

е

л

і

к

а

н

а

е

і

к

л

н

п

7

2

5

3

4

1

6

1

2

3

4

5

6

7

п

д

р

а

в

г

в

г

д

а

в

р

в

п

р

е

и

є

е

о

н

о

е

є

е

и

н

р

е

н

б

ч

р

о

о

о

н

ч

р

б

о

е

з

т

у

е

т

п

ч

п

т

е

т

у

ч

з

и

п

в

т

о

і

і

і

п

т

о

в

і

и

До перестановки

Після перестановки

Рис. 5.6. Таблиці, заповнені ключовим словом та текстом повідомлення

У верхньому рядку лівої таблиці записано ключ, а номери під буквами ключа визначені у відповідності до природного порядку відповідних букв в алфавіті. Якщо б у ключі зустрілися однакові букви, вони були б пронумеровані зліва направо. В правій таблиці стовпці переставлено відповідно до впорядкованих номерів букв ключа. При зчитуванні вмісту правої таблиці по рядках і записуванні шифротексту групами по п’ять букв отримаємо шифроване повідомлення „гавр впоеє еинро нчрбо ептет учзіп товіи“.

Для забезпечення додаткової секретності можна повторно зашифрувати повідомлення, яке уже пройшло шифрування. Такий метод шифрування називається подвійною перестановкою . У випадку подвійної перестановки стовпців та рядків таблиці перестановки визначаються окремо для стовпців та окремо для рядків. Спочатку в таблицю записується текст повідомлення, а потім почергово переставляються стовпці, після чого – рядки. При розшифровуванні застосовується обернений порядок.

Приклад виконання шифрування тексту „прибуваю восьмого“ методом подвійної перестановки представлено на рис. 5.7.

4

1

3

2

1

2

3

4

1

2

3

4

3

п

р

и

б

3

р

б

и

п

1

в

ю

а

у

1

у

в

а

ю

1

в

ю

а

у

2

о

о

г

м

4

в

о

с

ь

4

о

ь

с

в

3

р

б

и

п

2

м

о

г

о

2

о

о

г

м

4

о

ь

с

в

Вихідна таблиця

Перестановка стовпців

Перестановка рядків

Рис. 5.7. Приклад виконання шифрування методом подвійної перестановки

Якщо зчитувати текст з правої таблиці порядково блоками по чотири букви, то отримується зашифрований текст „вюау оогм рбип оьсв“. Ключем до шифру подвійної перестановки служить послідовність номерів стовпців та номерів рядків вихідної таблиці (у наведеному прикладі послідовності 4132 та 3142, відповідно).

Кількість варіантів подвійної перестановки швидко зростає при збільшенні розміру таблиці:

• для таблиці 3×3 – 36 варіантів;

• для таблиці 4×4 – 576 варіантів;

• для таблиці 5×5 – 14400 варіантів.

Однак подвійна перестановка має погану крипостійкість і досить просто „зламується“ при довільному розмірі таблиці шифрування.

Застосування магічних квадратів. В середні віки для шифрування перестановкою застосовувалися також магічні квадрати. Магічними квадратами називають квадратні таблиці із вписаними в їх клітинки послідовними натуральними числами, починаючи від 1, які дають в сумі по кожному стовпцю, кожному рядку та кожній діагоналі одне і те ж число. Шифрований текст вписували в магічні квадрати відповідно до нумерації їх клітинок. Якщо потім виписати вміст таблиці по рядках, то отримується шифротекст, сформований завдяки перестановці букв вихідного повідомлення. В ті часи вважалося, що створені за допомогою магічних квадратів шифротексти охороняє не тільки ключ, а й магічна сила.

На рис 5.8 показано приклад магічного квадрату та його заповнення повідомленням „прибуваю восьмого“.

16	3	2	13		о	и	р	м
5	10	11	8		у	о	с	ю
9	6	7	12		в	в	а	ь
4	15	14	1		б	г	о	п

Рис. 5.8. Приклад використання магічного квадрату 4×4 для шифрування перестановкою

Шифротекст, отриманий при зчитуванні правої таблиці по рядках має загадковий вигляд: „оирм уосю вваь бгоп“.

Кількість магічних квадратів швидко зростає зі збільшенням розміру квадрату. Існує тільки один магічний квадрат розмірами 3×3 (якщо не враховувати його повороти). Кількість магічних квадратів 4×4 складає уже 880, а кількість магічних квадратів 5×5 – біля 250000. Магічні квадрати середніх і великих розмірів могли служити доброю базою для забезпечення потреб шифрування того часу, оскільки практично нереально виконати вручну перебір усіх варіантів для такого шифру.

Шифри простої заміни. При шифруванні заміною (підстановкою) символи шифруємого тексту заміняються символами того ж чи іншого алфавіту із заздалегідь встановленим правилом заміни. В шифрі простої заміни кожний символ вихідного тексту заміняється символами того ж алфавіту однаково на протязі всього тексту. Часто шифри простої заміни називають шифрами одноалфавітної підстановки.

Система шифрування Цезаря. Шифр Цезаря є частковим випадком шифру простої заміни (одноалфавітної підстановки). Свою назву цей шифр отримав по імені римського імператора Гая Юлія Цезаря, який використовував цей шифр для листування з Цицероном (біля 50 р. до н.е.) [¹³⁷].

При шифруванні вихідного тексту кожна буква замінялася на іншу букву того ж алфавіту за таким правилом: заміняюча буква визначалася шляхом зміщення по алфавіту від вихідної букви на К букв. При досягненні кінця алфавіту виконувався циклічний перехід до його початку. Цезар використовував шифр заміни при зміщенні К=3. Такий шифр заміни можна задати таблицею підстановок, що містить відповідні пари букв відкритого тексту та шифротексту. Сукупність можливих підстановок для К=3 представлено в табл. 5.1.

Таблиця 5.1

Таблиця підстановок для шифру Цезаря у випадку використання англійського алфавіту

A→D	J→M	S→V
B→E	K→N	T→W
C→F	L→O	U→X
D→G	M→P	V→Y
E→H	N→Q	W→Z
F→I	O→R	X→A
G→J	P→S	Y→B
H→K	Q→T	Z→C
I→L	R→U

Наприклад, відоме послання Цезаря “VENI VIDI VICI” (у перекладі на українську означає „прийшов, побачив, переміг“), у зашифрованому виді виглядало б так: “YHQL YLGL YLFL”.

На відміну від шифру Цезаря, система шифрування Цезаря утворює, по суті, сімейство одноалфавітних підстановок для множини значень ключа К, причому 0≤К≤m (m – кількість букв алфавіту). Перевагою системи шифрування Цезаря є простота шифрування та розшифровування. До недоліків системи Цезаря відносять наступне:

• підстановки, що виконуються відповідно до системи Цезаря, не маскують частот появи різних букв вихідного відкритого тексту;

• зберігається алфавітний порядок в послідовності заміняючих букв – при зміні значення К змінюються тільки початкові позиції такої послідовності;

• невелика кількість можливих ключів К;

• шифр Цезаря легко дешифрується на основі аналізу частот появи букв у шифротексті.

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

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

Крім того, за принципами шифрів простої заміни працюють класичні системи, найвідомішими з яких є:

• шифруючі таблиці Трисемуса;

• біграмний шифр Плейфейра;

• криптосистема Хілла.

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

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

Багатоалфавітні шифри заміни запропонував та ввів у практику криптографії Леон Батист Альберті [¹³⁸]. Його книга „Трактат про шифр“, написана в 1566 році, представляла собою першу в Європі наукову роботу по криптології. Крім шифру багатоалфавітної заміни, Альберті також детально описав механічний пристрій для його реалізації. Криптологи усього світу вважають Л. Альберті засновником криптології.

Відомими реалізаціями принципів шифру складної заміни є система шифрування Віжінера [¹³⁹] та шифр „подвійний квадрат“ Уітстона [¹⁴⁰], які використовують для шифрування спеціальні таблиці. Більш цікавими для сучасності є дві інші системи, які базуються на системі складної заміни: одноразова система шифрування та шифрування методом Вернама.

Одноразова система шифрування. Майже усі шифри, що застосовуються на практиці, характеризуються як умовно надійні, оскільки вони можуть бути в принципі розкриті за наявності необмежених обчислювальних можливостей. Абсолютно надійні шифри неможливо розшифрувати навіть при використанні необмежених обчислювальних можливостей. Існує єдиний такий шифр, що використовується на практиці – одноразова система шифрування. Характерною особливістю одноразової системи шифрування є одноразове використання ключової послідовності.

Одноразова система шифрує вихідний відкритий текст

у шифротекст

засобами підстановки Цезаря

де К_і – і-й елемент випадкової ключової послідовності; оператор mod вказує на циклічний перехід до початку алфавіту за досягнення його кінця.

Ключовий простір одноразової системи представляє собою набір дискретних випадкових величин та міститьmⁿ значень. Процедура розшифровування описується оберненим співвідношенням

де К_і – і-й елемент тієї ж самої випадкової ключової послідовності.

Одноразова система запропонована в 1917 році американцями Дж. Моборном та Г. Вернамом [¹⁴¹]. Для реалізації цієї системи підстановки іноді використовують одноразовий блокнот. Такий блокнот складається з відривних сторінок, на кожній з яких надрукована таблиця з випадковими числами (ключами) К_і. Блокнот створюється в двох екземплярах: один використовується відправником, а другий – отримувачем. Для кожного символу X_i використовується свій ключ К_і з таблиці тільки один раз. Після використання таблиці вона видаляється з блокноту та знищується. Шифрування нового повідомлення починається з нової сторінки.

Цей шифр абсолютно надійний, якщо набір ключів К_і дійсно випадковий і непередбачуваний. Якщо криптоаналітик спробує використати для заданого шифротексту усі можливі набори ключів і відновити усі можливі варіанти вихідного тексту, то вони усі виявляться рівноймовірними. Клодом Шенноном теоретично доведено, що одноразові системи є абсолютно криптостійкими системами, оскільки їх шифротекст не містить достатньої інформації для відновлення відкритого тексту.

На перший погляд здається, що завдяки даній особливості одноразові системи слід застосовувати в усіх випадках, що потребують абсолютної інформаційної безпеки. Проте усі можливості застосування одноразової системи обмежені чисто практичними аспектами. Суттєвим моментом є вимога одноразового використання випадкової ключової послідовності. Ключова послідовність з довжиною, не меншою довжини повідомлення, повинна передаватися отримувачу повідомлення заздалегідь чи окремо по деякому секретному каналу. Така вимога застосовна для передачі дійсно важливих одноразових повідомлень. Однак така вимога практично нездійсненна для сучасних систем обробки інформації, в яких потрібно шифрувати величезні об’єми символів.

В деяких варіантах одноразового блокноту вдаються до простішого управління ключовою послідовністю, що, однак, приводить до деякого зниження надійності шифру. Наприклад, ключ визначається вказуванням місця в книжці, відомої відправнику та отримувачу повідомлення. Проте такі ключі не будуть випадковими і у криптоаналітика з’являється можливість використовувати інформацію про частоту букв вихідної природної мови.

Шифрування методом Вернама. Ця система, запропонована Гільбертом Вернамом – співробітником фірми AT&T США, використовує двійкове представлення символів вихідного тексту [Error: Reference source not found]. Кожний символ вихідного відкритого тексту з англійського алфавіту, розширеного шістьма допоміжними символами (пропуск, переведення рядка і т.п.), спочатку кодувався в 5-бітовий блок телеграфного коду Бодо. Крім того на паперовій стрічці записувалася випадкова послідовність двійкових ключів. Шифрування вихідного тексту, попередньо перетвореного в послідовність двійкових символів х, здійснювалося шляхом сумування по модулю 2 символів х з послідовністю двійкових ключів k:

y=xk.

Розшифровування полягає в сумуванні по модулю 2 символів y шифротексту з тією ж послідовністю ключів k:

yk=xkk=x.

При цьому послідовності ключів, використані при шифруванні та розшифровуванні, компенсують один одного (при сумуванні по модулю 2), і в результаті відновлюються символи х вихідного тексту.

Тут слід зазначити, що сумування по модулю 2, яке іще іноді називають виключаючим „або“, є логічною операцією булевої алгебри, яка працює за наступним правилом: „результат рівний 0 якщо обидва операнди рівні, в усіх інших випадках результат рівний 1“. Для кращого розуміння в табл 5.2 наведено таблицю істинності цієї логічної операції.

Таблиця 5.2.

Таблиця істинності для логічної операції сумування по модулю 2

a	b	ab
0	0	0
0	1	1
1	0	1
1	1	0

При розробці своєї системи Вернам перевіряв її за допомогою закільцеваних стрічок, встановлених на передвачі та приймачі для того, щоб використовувалася одна і та ж послідовність ключів. Слід зазначити, що метод Вернама не залежить від довжини послідовності ключів і, крім того, він дозволяє використовувати випадкову послідовність ключів. Проте при реалізації метода Вернама виникають серйозні проблеми, пов’язані з необхідністю доставки отримувачу такої ж послідовності ключів, як у відправника, або з необхідністю безпечного зберігання ідентичних послідовностей ключів у відправника та отримувача. Ці недоліки системи шифрування Вернама подолані при шифруванні методом гамування.

Шифрування методом гамування. Під гамуванням розуміють процес накладання за певним законом гами щифру на відкриті дані [¹⁴²]. Гама шифру – це псевдовипадкова послідовність, вироблена за певним алгоритмом для зашифровування відкритих даних та розшифровування зашифрованих даних. Процес зашифровування полягає в генерації гами шифру і накладання отриманої гами на вихідний відкритий текст відтворюваним способом, наприклад з використанням операції сумування по модулю 2.

Слід зазначити, що перед зашифровуванням відкриті дані розбивають на блоки Т₀^(і) однакової довжини, зазвичай по 64 біти. Гама шифру виробляється у вигляді послідовності блоків Г_ш^(і) аналогічної довжини. Рівняння зашифровування можна записати у вигляді

Т_ш^(і)=Г_ш^(і)Т₀^(і), і=1...М,

де Т_ш^(і) – і-й блок шифротексту; Г_ш^(і) – і-й блок гами шифру; Т₀^(і) – і-й блок відкритого тексту; М – кількість блоків відкритого тексту.

Процес розшифровування зводиться до повторної генерації гами шифру і накладання цієї гами на зашифровані дані. Гама генерується з використанням генератора псевдовипадкового числа. Для того, щоб у відправника і отримувача генерувалася одна і та ж гама, їм потрібно використовувати ідентичні алгоритми генерації псевдовипадкових чисел. Крім того, генератор псевдовипадкових чисел потрібно ініціалізувати початковим 64-бітним значенням, в якості якого дуже часто використовується поточний час шифрування. Останнє приводить до цікавого ефекту, який полягає в тому, що одне і те ж саме повідомлення, зашифроване в різні моменти часу, буде давати зовсім різні шифротексти.

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

Рівняння розшифровування має вигляд:

Т₀^(і)=Г_ш^(і)Т_ш^(і).

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

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

Зазвичай для генерації послідовності псевдовипадкових чисел використовуються комп’ютерні програми, які, хоча і називаються генераторами випадкових чисел, в дійсності видають детерміновані числові послідовності, які за своїми властивостями дуже подібні на випадкові. До криптографічно стійкого генератора псевдовипадкової послідовності чисел (гами шифру) ставляться три основні вимоги [Error: Reference source not found]:

• період гами повинен бути досить великим для шифрування повідомлень різної довжини;

• гама повинна бути практично непередбачуваною, що означає неможливість передбачити наступний біт гами, навіть якщо відомі тип генератора та попередня частина гами;

• генерування гами не повинно викликати великих технічних проблем.

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

Друга вимога зв’язана з такою проблемою: як можна достовірно впевнитися, що псевдовипадкова гама конкретного генератора є дійсно непередбачуваною? На даний час не існує таких універсальних і перевірених на практиці критеріїв та методик. Щоб гама вважалася непередбачуваною (істинно випадковою), необхідно, щоб її період був дуже великим, а різні комбінації біт певної довжини були рівномірно розподілені по всій її довжині.

Третя вимога обумовлює можливість практичної реалізації генератора програмним чи апаратним шляхом із забезпеченням необхідної швидкодії.