Одноразова система шифрування

 

Майже всі шифри, що застосовуються на практиці, характеризуються як умовно надійні, оскільки вони можуть бути в принципі розкриті при наявності необмежених обчислювальних можливостей. Абсолютно надійні шифри не можна розкрити навіть маючи необмежені обчислювальні можливості. Існує єдиний абсолютно надійний шифр – одноразова система шифрування. Характерною рисою одноразової системи шифрування є одноразове використання ключової послідовності. Одноразова система винайдена в 1917 р. американцями Дж. Моборном і Г. Вернамом [9,11]. Для реалізації цієї системи підстановки іноді використовують одноразовий блокнот. Цей блокнот складений з відривних сторінок, на кожній з яких надрукована таблиця з випадковими числами (ключами)|. Блокнот виготовляється в двох екземплярах: один використовується відправником, а інший – одержувачем. Для кожного символу повідомлення використовується свій ключ з таблиці тільки один раз. Після того як таблиця використана, вона повинна бути вилучена з блокнота і знищена. Шифрування нового повідомлення починається з нової сторінки. Цей шифр абсолютно надійний, якщо набір ключів дійсно випадковий і непередбачений. Якщо криптоаналітик спробує використовувати для заданого шифртекста всі можливі набори ключів і відновити всі можливі варіанти вихідного тексту, то вони всі будуть рівноймовірними. Теоретично доведено, що одноразові системи не розкриваються, оскільки їхній шифртекст не містить достатньої інформації для відновлення відкритого тексту. Здавалося б, що одноразову систему варто було б застосовувати у всіх випадках, що вимагають абсолютної інформаційної безпеки. Однак можливості застосування одноразової системи обмежені практичними аспектами. Істотним моментом є вимога одноразового використання випадкової ключової послідовності. Ключова послідовність з довжиною, не меншою довжини повідомлення, повинна передаватися одержувачу повідомлення по деякому секретному каналі. Це вимога не буде занадто обтяжливою для передачі дійсно важливих одноразових повідомлень. Однак така вимога практично нездійсненна для сучасних систем обробки інформації, де потрібно шифрувати багато мільйонів символів.

2 СУЧАСНІ СИМЕТРИЧНІ АЛГОРИТМИ ШИФРУВАННЯ

 

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

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

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

	=
	=
	=
	=
	=

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

	=
	=
	=
	=
	=

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

Å		текст
	гама шифра
		шифр-текст

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

					=
					=
					=
					=
					=

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

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

Å		шифр-текст
	гама шифра
		текст

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

 

					=		S
					=		P
					=		A
					=		C
					=		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].

 

2.2 Блочні алгоритми

 

Для побудови сучасних блочних алгоритмів шифрування використовуються два загальних принципи: розсіювання і перемішування. Розсіювання являє собою поширення впливу одного знака відкритого тексту на багато знаків шифр-текста, що дозволяє приховати статистичні властивості відкритого тексту. Перемішування полягає в використанні таких перетворень шифрування, які ускладнюють відновлення взаємозв'язку статистичних властивостей відкритого і шифрованого текстів. Сучасний шифр повинен також забезпечувати легкість шифрування і розшифрування [1,2,3,4,5,8,9].

Розповсюдженим способом досягнення ефектів розсіювання і перемішування є використання складного шифру, тобто такого шифру, який може бути реалізований у вигляді деякої послідовності простих шифрів, кожен з яких вносить свій внесок у значне сумарне розсіювання і перемішування. У складних шифрах найчастіше використовуються прості шифри перестановки і підстановки. При перестановці просто перемішують символи відкритого тексту, причому конкретний вид перемішування визначається секретним ключем. При підстановці кожен символ відкритого тексту замінюють іншим символом з того ж алфавіту, а конкретний вид підстановки також визначається секретним ключем. Перед шифруванням сучасний складним шифром, текст спочатку розбивається на блоки однакової довжини. Потім кожен блок шифрується окремо. Тому такі шифри називаються блочними. У блочному шифрі блоки відкритого тексту і шифртекста являють собою двійкові послідовності довжиною 64 біта. Таким чином кожен блок може приймати 2⁶⁴ значень. Тому підстановки виконуються в дуже великому алфавіті, що містить до 2⁶⁴ ≈ 10¹⁹ "символів".

При багаторазовому чергуванні простих перестановок і підстановок, керованих досить довгим секретним ключем, можна одержати дуже стійкий шифр із гарним розсіюванням і перемішуванням. Розглянуті нижче криптоалгоритми DES, IDEA, CAST, Blowfish, AES, RC2 побудовані в повній відповідності з зазначеною методологією.