Сучасна криптографія

ЗАВЕРШАЛЬНІ ЗАУВАЖЕННЯ

ДОДАТОК

 

 

 

 

В.Ємець, А.Мельник, Р.Попович

 

Сучасна криптографія. Основні  поняття. – Львів: БаК, 2003.

 

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

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

 

 

 

 

 

 

 

 

 

 

 

 

Рецензенти:  д.т.н., професор В.П.Тарасенко, НТУ “КПІ”

д.т.н., професор Р.П.Базилевич, НУ “ЛП”

 

 

 

 

 

 

 

ÓВ.Ємець, А.Мельник, Р.Попович, 2003

 

 

 

 

ЗМІСТ

 

 

 

ВСТУП

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

Методи криптографічного захисту інформації передбачають як програмне, так і апаратне використання. Програмна реалізація шифрування є  дешевшою та практичнішою. Водночас апаратна реалізація продуктивніша та простіша у використанні. Сучасні криптографічні системи повинні задовольняти такі загальноприйняті вимоги [4]:

 

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

 

Викладення теоретичних  основ сучасної криптографії, не пов’язаних з державною таємницею, – мета цієї книжки. Наведено основні термінологічні поняття та приклади використання шифрування на практиці. Наведено основні законодавчі акти України в області криптографії. Зроблено екскурс в історію криптографії та розглянуто класичні алгоритми шифрування: підстановки й перестановки. Поряд із загальними принципами утворення блокових симетричних шифрів, описано найбільш широко вживані на даний час алгоритми шифрування, включаючи стандарт AES. Розглянуто теоретичні основи асиметричних алгоритмів, висвітлено питання складності обчислень та описано алгоритми шифрування RSA, Рабіна, Ель-Гамаля, а також утворення криптосистем на основі еліптичних кривих та рюкзакові шифри. Висвітлено питання генерування псевдовипадкових послідовностей, утворення хешувальних функцій. У додатку наведено необхідні базові поняття абстрактної алгебри.

 

 

 

Розділ 1. ОСНОВНІ ПОНЯТТЯ

1.1. Термінологія

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

 

• алфавіт Z₃₃, що включає 33 літери української абетки без додаткових символів для апострофа, розділових знаків, цифр, великих літер;
• двійковий алфавіт Z₂ = {0, 1};
• алфавіт Z₂₅₆, що складається з символів ASCII та КОІ 8;
• алфавіт Z₂₆, що використовує 26 літер латинської абетки без додаткових символів, розділових знаків, цифр, великих літер.

 

Для шифрування й дешифрування потрібні додатково ключ або ключі (рис. 1.1).

 

 

 

Рис. 1.1. Загальна схема шифрування й дешифрування.

 

Алгоритм шифрування й дешифрування утворює криптосистему або шифр. Розглянемо два здавна відомі шифри.

 

 Шифр Цезаря (100-44 р. до н. е.). Його названо за іменем римського імператора Гая Юлія Цезаря, який доручав Цицерону складати шифровані повідомлення для керування військами. Літери абетки тут ототожнені з цифрами. В системі Цезаря використано 26 символів (26 літер латинської абетки), які пронумеровані числами від 0 до 25 (табл. 1.1). Шифр ґрунтується на підстановці:

 

00 (a) ® 03 (d); 01 (b) ® 04 (e); 02 (c) ® 05 (f); ...; 25 (z) ® 02 (c).

 

Це означає, що в шифрограмі кожну  літеру явного тексту замінюють на літеру, розташовану в абетці на три позиції далі. Висловлюючись сучасною мовою, римляни застосовували операцію додавання до номера літери числа 3 за модулем 26 : C ≡ P + 3 (mod 26), де С – номер літери в криптограмі, а P – номер відповідної літери в явному тексті. Наприклад, латинському слову imperium (імперія) відповідає криптограма lpshulxp, а латинському тексту Veni, vidi, vici (прийшов, побачив, переміг – крилата фраза Цезаря), коли з нього викинути коми й пропуски між словами, відповідає криптограма yhqlylglylfl.

 

Таблиця 1.1. Нумерація літер латинської абетки

a	00	h	07	o	14	v	21
b	01	i	08	p	15	w	22
c	02	j	09	q	16	x	23
d	03	k	10	r	17	y	24
e	04	l	11	s	18	z	25
f	05	m	12	t	19
g	06	n	13	u	20

 

Таблиця 1.2. Нумерація літер української  абетки

а	00	є	07	к	14	с	21	ш	28
б	01	ж	08	л	15	т	22	щ	29
в	02	з	09	м	16	у	23	ь	30
г	03	и	10	н	17	ф	24	ю	31
ґ	04	і	11	о	18	х	25	я	32
д	05	ї	12	п	19	ц	26
е	06	й	13	р	20	ч	27

 

 

Шифр Цезаря стосовно української  абетки (табл.1.2) означає, що літеру а замінюють на літеру г, літеру б – на літеру ґ, літеру в - на літеру д і т.д. Останні букви абетки ь, ю, я зміщуються циклічно, тобто переходять у а, б, в, відповідно. Наприклад, слову імперія відповідає криптограма кптзукв.

Шифр Цезаря є шифром зсуву на три позиції.

 

‚ Шифр частоколу. Цей шифр належить до шифрів перестановки. Наприклад, слово криптографія записуємо у вигляді і шляхом зчитування по рядках з верху до низу отримуємо криптограму рпорфякитгаі. У цьому випадку висота частоколу дорівнює 2. Для висоти частоколу, що дорівнює 3, маємо: й отримуємо криптограму иоаяртрікпгф.

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

Явний текст P, зашифрований за допомогою ключа K, будемо позначати через E_K(P) = C, а явний текст, отриманий з криптограми C за допомогою ключа K, - через D_K(C) = P. Такі позначення передбачають, що знаємо, який ключ шифрування або дешифрування використовують.

З огляду на використання ключів розрізняють  два методи шифрування: метод, що використовує симетричні алгоритми, та метод, що використовує асиметричні алгоритми.

Симетричні алгоритми – це алгоритми, де ключ для шифрування та ключ для дешифрування є одним і тим самим (рис. 1.2).

 

 

 

Рис. 1.2. Симетрична схема шифрування й дешифрування.

 

 

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

У рамках криптографії вивчають також методи розкриття шифрів, або методи криптоаналізу. На підставі криптограми необхідно знайти відповідний їй явний текст або ключ. Криптоаналіз також може виявити слабкі місця в криптосистемах, що зрештою призведе до попереднього результату. Отримання ключа не криптографічним способом називають компрометацією ключа. Найпростішою формою криптоаналізу є метод, який називають систематичним пошуком, або брутальною атакою (англ. термін brute-force). Цей метод полягає у випробуванні всіх можливих ключів. Наприклад, знаючи явний текст P i відповідну йому криптограму C, можемо шифрувати P по черзі всіма можливими ключами, доки не знайдемо такий ключ, який дає в результаті C. З огляду на стрімке зростання продуктивності ЕОМ можна припустити, що такий метод криптоаналізу може виявитися досить ефективним.

 

 

 

Рис. 1.3. Асиметрична схема шифрування й дешифрування.

 

 

Головне припущення криптоаналізу, вперше сформульоване в ХІХ ст. Дутчманом  А.Керкхофсом [6], полягає в тому, що безпека шифру повністю визначена ключем. Керкхофс припустив, що в криптоаналітика є повний опис алгоритму і його реалізації (звичайно ж, ЦРУ не має звички повідомляти Моссад про свої криптографічні алгоритми, але Моссад намагатиметься все одно їх роздобути). Хоча в реальному світі криптоаналітики не завжди мають відповідну детальну інформацію, таке припущення є доброю гіпотезою. Якщо супротивник не зможе зламати алгоритм, навіть знаючи те, як він працює, то тим більше цей зловмисник не зможе розкрити алгоритм без цієї інформації.

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

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

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

1. Атака, що оперує тільки відомими криптограмами (атака типу ciphertext only). Зловмисник має лише криптотекст E_K(P) або певну кількість криптотекстів E_K(P₁), …, E_K(P_l), зашифрованих тим самим ключем, але не має інформації про відповідні їм явні тексти.
2. Атака з відомим явним текстом (атака типу known plaintext). Крім E_K(P), певні пари E_K(P₁) i P₁, …, E_K(P_l) i P_l є відомими, та ці пари не можуть бути вибрані зловмисником.
3. Атака з вибраним явним текстом (атака типу chosen plaintext). Зловмисник має криптограму E_K(P) для довільно вибраного явного тексту P. Атака такого типу можлива, коли є змога шифрувати за допомогою криптографічного пристрою, проте ключ K невідомий.
4. Атака з вибраною криптограмою (атака типу chosen ciphertext). Зловмисник може отримати явні тексти D_K(C₁), …, D_K(C_l) для довільно вибраних криптограм C₁, …, C_l. Така ситуація виникає, коли зловмисник має змогу дешифрувати за допомогою криптографічного пристрою, проте не має ключа.

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

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