2. Сучасні симетричні алгоритми шифрування

Сучасні симетричні криптоистеми утворюють дві групи: потокові алгоритми шифрування та блочні алгоритми шифрування.

1. Потокові алгоритми

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

Стандартним методом генерування псевдовипадкових послідовностей для потокового шифрування є режим OFB стандарту шифрування DES (див. наступний розділ).

Іншими словами, потокові алгоритми шифрування будуються на основі процесу гамування. Під гамуванням розуміють процес накладення по визначеному закону гами шифру на відкриті дані. Гама шифру – це псевдовипадкова послідовність, вироблена по заданому алгоритмі для шифрування відкритих даних і розшифрування шифрованих даних. Процес шифрування полягає в генерації гами шифру і накладенні отриманої гами на вихідний відкритий текст, наприклад з використанням операції двійкового підсумовування. Вихідний відкритий текст переводиться у двійковий вигляд, тобто кожен символ тексту замінюється на своє двійкове зображення, наприклад, А = 00000, У = 00001, З = 00010 і т.д. Потім біти ключа (гами шифру) і вихідного тексту підсумовуються по модулю 2. В результаті маємо шифрований текст.

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

C_i =P_i  G_i , i=1, … , m,

де C_i – i-й блок шифр-текста; G_i – i-й блок гами шифру; P_i – i-й блок відкритого тексту; m – кількість блоків відкритого тексту.

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

P_i = C_i  G_i, i=1, … , m.

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

Генерування непередбачених двійкових послідовностей великої довжини є однієї з важливих проблем класичної криптографії. Для вирішення цієї проблеми широко використовуються генератори двійкових псевдовипадкових послідовностей. Звичайно для генерації послідовності псевдовипадкових чисел застосовують комп'ютерні програми. Вони хоча і називаються генераторами випадкових чисел, насправді видають детерміновані числові послідовності, Але за своїми властивостями ці послідовності дуже схожі на випадкові [2,6,8,9,10,11,12].

До криптографічно стійкого генератора псевдовипадкової послідовності чисел (гами шифру) висуваються три основні вимоги:

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

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

• Генерування гами не повинне викликати великих технічних складностей, щоб можна було практично реалізувати генератор програмним чи апаратним шляхом із забезпеченням необхідної швидкодії.

З відомих процедур генерації послідовності псевдовипадкових цілих чисел найбільш часто застосовується лінійний конгруентний генератор. Цей генератор виробляє послідовність псевдовипадкових чисел y₀,y₁,…y_i,… використовуючи рекурентну формулу

y_i=(a* y_i-1+b) mod m,

де y_i – i-те (поточне) число послідовності; y_i-1 – попереднє число послідовності; a, b і m – константи; m – модуль; a – множник (коефіцієнт); b – приріст;, y₀ – число, що породжує гамму. Ця формула генерує псевдовипадкові числа з періодом повторення, який залежить від обраних значень параметрів a, b і m і може досягати значення m. Значення модуля m береться рівним 2ⁿ або рівним простому числу, наприклад m=2³¹-1. Приріст b повинен бути взаємно простим з m, коефіцієнт a повинен бути непарним числом.

Конгруентні генератори, що працюють по алгоритму, запропонованому Національним бюро стандартів США, використовуються, зокрема, у системах програмування. Ці генератори мають довжину періоду 2²⁴ і мають гарні статистичні властивості. Однак така довжина періоду мала для криптографічних застосувань. Крім того, доведено, що послідовності, що генеруються конгруентними генераторами, не є криптографічно стійкими [2,9,12].

Розглянемо приклад генерації послідовності псевдовипадкових цілих чисел лінійним конгруентним генератором. Нехай необхідні константи вибрані так: a=3, m=29, b=5, y₀=2. Тоді послідовність пседовипадкових чисел матиме вигляд:

y₁=(3* 2+5) mod 29 =11,

y₂=(3* 11+5) mod 29 =9,

y₃=(3* 9+5) mod 29 =3,

y₄=(3* 3+5) mod 29 =14,

y₅=(3* 14+5) mod 29 =18,

. . .

Використаємо цю послідовність псевдовипадкових чисел для шифрування методом гамування такого тексту:

SPACE

Спочатку закодуємо кожну літеру тесту 5-значним двійковим числом. Для цього кожній літері поставимо у відповідність її номер у аглійському алфавіті:

S	P	A	C	E
19	16	1	3	5

Потім номер літери запишемо двійковим 5-значним числом:

		16	8	4	2	1
19	=	1	0	0	1	1
16	=	1	0	0	0	0
1	=	0	0	0	0	1
3	=	0	0	0	1	1
5	=	0	0	1	0	1

Зобразимо побудовану нами послідовність псевдовипадкових чисел у вигляді послідовності двійкових 5-значних чисел:

		16	8	4	2	1
11	=	0	1	0	1	1
9	=	0	1	0	0	1
3	=	0	0	0	1	1
14	=	0	1	1	1	0
18	=	1	0	0	1	0

Накладемо тепер вихідний текст на гаму шифра, використовуючи сумування за модулем 2:

	1001110000000010001100101	текст
	0101101001000110111010010	гама шифра
	1100011001000100110110111	шифр-текст

Шифр-текст переведемо з послідовності 5-значних двійкових чисел до послідовності десяткових чисел:

16	8	4	2	1
1	1	0	0	0	=	24
1	1	0	0	1	=	25
0	0	0	1	0	=	2
0	1	1	0	1	=	13
1	0	1	1	1	=	23

Таким чином, шифруючи текст SPACE методом гамування за допомогою вказаної гами шифра маємо шифр-текст: 24, 25, 2, 13, 23.

Щоб розшифрувати цей шифр-текст, треба знати гаму шифра. Гаму шифра можна побудувати, якщо відомі константи a, m, b, y₀. Ці константи утворюють секретний ключ потокового алгоритму шифрування. Побудувавши гаму шифра, накладемо її на шифр-текст, використовуючи сумування за модулем 2:

	1100011001000100110110111	шифр-текст
	0101101001000110111010010	гама шифра
	1001110000000010001100101	текст

Зосталось перевести текст з послідовності 5-значних двійкових чисел до послідовності цілих чисел. Згадаємо, що ці числа є номерами літер у англійському алфавіті. В результаті цих перетворень маємо:

16	8	4	2	1
1	0	0	1	1	=	19	S
1	0	0	0	0	=	16	P
0	0	0	0	1	=	1	A
0	0	0	1	1	=	3	C
0	0	1	0	1	=	5	E

Прикладом потокового шифру є алгоритм RC4, розроблений у 1987 році Роном Райвестом для RSA DSI [11]. Алгоритм працює в режимі OFB (див. наступний розділ), тобто гама шифру не залежить від шифрованого тексту. Використовується S-блок, елементи S₀,S₁,…,S₂₅₅ якого являють собою перестановки чисел від 0 до 255.

Ініціалізація S-блоку полягає в наступному:

1. Спочатку S₀=0,S₁=1,…,S₂₅₅=255.

2. Потім ключем алгоритму заповнюється інший 256-байтовий блок K. Якщо необхідно, ключ повторюється, щоб заповнити весь масив K₀,K₁,…,K₂₅₅ .

3. j=0;

Для i від 0 до 255

j=(j+S_i+K_j) mod 256;

поміняти місцями S_i і S_j;

кінець для;

В алгоритмі застосовуються 2 лічильники i і j з нульовими початковими значеннями. Щоб згенерувати випадковий байт R, виконується наступне:

1. i=(i+j) mod 256,

2. j=(j+S_i) mod 256,

3. елементи S_i і S_j міняються місцями,

4. t=( S_j + S_i) mod 256,

5. R= S_t.

Байт R використовується в операції XOR c відкритим текстом для одержання шифртекста чи в операції XOR із шифртекстом для одержання відкритого тексту. Шифрування виконується приблизно в 10 разів швидше, ніж в алгоритмі DES (см. наступний розділ).

RC4 використовується в десятках комерційних програмних продуктах. Наприклад, у Oracle Secure SQL, у багатьох програмах Microsoft.

Потоковий шифр A5 використовується для шифрування зв'язку GSM. Це європейський стандарт для мобільних цифрових стільникових телефонів. Він використовується для шифрування каналу «телефон – базова станція». Частина каналу, що залишилася, не шифрується. На сьогоднішній день алгоритм A5 цілком розкритий. Атака вимагає 2⁴⁸ попередніх обчислень, а потім займає кілька секунд на персональному комп'ютері [11].