Симетричне шифрування

1.3.4 Симетричне шифрування

Симетричні алгоритми шифрування — алгоритми, які застосовуються при шифруванні інформації. Особливість симетричних алгоритмів шифрування полягає у тому, що ключ шифрування та розшифрування однаковий, тобто з його допомогою можна як зашифрувати, так і розшифрувати (відновити) повідомлення. Симетричні алгоритми шифрування можна розділити на потокові та блочні алгоритми шифрування. Потокові алгоритми шифрування послідовно обробляють текст повідомлення. Блочні алгоритми працюють з блоками фіксованого розміру. Як правило, довжина блоку дорівнює 64 бітам, але, в алгоритмі AES використовуються блоки довжиною 128 біт. [21]

Симетричні алгоритми шифрування не завжди використовуються самостійно. В сучасних криптоситемах, використовуються комбінації симетричних та асиметричних алгоритмів, для того, аби отримати переваги обох схем. До таких систем належить SSL, PGP та GPG. Асиметричні алгоритми використовуються для розповсюдження ключів швидших симетричних алгоритмів. До деяких відомих, поширених алгоритмів з гарною репутацією належать: Twofish, Serpent, AES (або Рейндайль), Blowfish, CAST5, RC4, TDES (3DES), та IDEA. [12]

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

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

Мережа Фейстеля (конструкція Фейстеля) - один з методів побудови блокових шифрів. Мережа являє собою певну багаторазову структуру що повторюється (ітерована) і називається осередком Фейстеля. При переході від однієї комірки до іншої змінюється ключ, причому вибір ключа залежить від конкретного алгоритму. Операції шифрування та розшифрування на кожному етапі дуже прості, і при певній доробці збігаються, вимагаючи тільки зворотного порядку використовуваних ключів. Шифрування за допомогою даної конструкції легко реалізується як на програмному рівні, так і на апаратному, що забезпечує широкі можливості застосування. Більшість сучасних блокових шифрів використовують мережу Фейстеля в якості основи. Альтернативою мережі Фейстеля є узагальнення-перестановочне мережу. [18]

У 1971 Хорст Фейстель (Horst Feistel) запатентував два пристрої, які реалізували різні алгоритми шифрування, названі потім загальною назвою «Люцифер» (Lucifer). Одне з пристроїв використовувало конструкцію, згодом названу «мережею Фейстеля» («Feistel cipher», «Feistel network»). Робота над створенням нових криптосистем велася ним у стінах IBM разом з Доном Копперсмітом (Don Coppersmith). Проект «Люцифер» був скоріше експериментальним, але став базисом для алгоритму Data Encryption Standard (DES). У 1973 Хорст Фейстель в журналі Scientific American опублікував статтю «Криптографія і Комп'ютерна безпека» ^[1][2] («Cryptography and Computer Privacy»), в якій розкрив ряд важливих аспектів шифрування і привів опис першої версії проекту «Люцифер» , не використала мережу Фейстеля. У 1977 DES став стандартом у США на шифрування даних, і до останнього часу широко використовувався в криптографічних системах. Ітеративний структура алгоритму дозволяла спростити його реалізацію у програмних і апаратних середовищах. Згідно з деякими даними вже в 1970-і роки в КДБ (СРСР) розроблявся блоковий шифр, що використав мережу Фейстеля і, ймовірно, саме він пізніше був прийнятий як ГОСТ 28147-89 в 1990 році. [14]

У 1987 були розроблені алгоритми FEAL і RC2 . Широке поширення мережі Фейстеля отримали в 1990-і роки, коли з'явилися такі алгоритми, як: Blowfish, CAST-128, TEA, XTEA, XXTEA, RC5, RC6 та ін.

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

·  Вся інформація розбивається на блоки фіксованої довжини. У разі, якщо довжина вхідного блоку менше, ніж розмір, який шифрується заданим алгоритмом, то блок подовжується будь-яким способом. Як правило довжина блоку є ступенем двійки, наприклад: 64 біта, 128 біт. Далі будемо розглядати операції відбуваються тільки з одним блоком, тому що з іншими в процесі шифрування виконуються ті ж самі операції.

·  Обраний блок ділиться на два рівних подблока - «лівий» (L₀) і «правий» (R₀)_.

·  «Лівий подблок» L₀ видозмінюється функцією f (L_0, K₀₎ залежно від раундового ключа K_0, після чого він складається за модулем 2 з «правим подблоком» R_0.

·  Результат складання присвоюється новому лівому подблоку L_1, який буде половиною вхідних даних для наступного раунду, а «лівий подблок» L ₀ присвоюється без змін новому правому подблоку R ₁ (див. схему), який буде іншою половиною.

·  Після чого операція повторюється N-1 раз, при цьому при переході від одного етапу до іншого змінюються раундовий ключі (K₀ на K₁ і т. д.) за будь-яким математичному правилом, де N - кількість раундів в заданому алгоритмі.

·  Розшифровка інформації відбувається так само, як і шифрування, з тим лише виключенням, що ключі ідуть у зворотному порядку, тобто не від першого до N-го, а від N-го до першого (рис. 1.4).

Рис. 1.3 Шифрування

Рис. 1.4 Розшифрування

Конструкцію Фейстеля можна описати так:

·  блок відкритого тексту ділиться на 2 рівні частини

·  в кожному раунді обчислюється ( — номер раунду)

,

де f - деяка функція, а K _{i - 1} ключ i-го раунду.

Результатом виконання n раундів є . Але зазвичай в n-му раунді перестановка L _n і R _n не проводиться, що дозволяє використовувати ту ж процедуру і для розшифрування, просто інвертувати порядок використання раундової ключової інформації:

,

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

Математичний опис опис полягає в наступному. Інволюція - взаємно-однозначне перетворення, яке є зворотним самому собі. Розглянемо на прикладі: Нехай X - вхідний блок, а A - деякий інволютивно перетворення, Y - результат. При одноразовому застосуванні перетворення до вхідного блоку вийде: Y = A X, при застосуванні перетворення до результату попереднього перетворення вийде: .

Нехай вхідний блок X = (L, R) складається з двох підблоків (L і R) однакової довжини. Визначимо два перетворення

 

(шифрування ключем K) і T (L, R) = (R, L) (перестановкапідблоків). Введемо позначення:

Доведемо їх інволютивно:

1.  Нескладно помітити, що перетворення G міняє лише лівий підблок L, залишаючи правий R незмінним. Тому далі будемо розглядати тільки підблок L. Після того як перетворення G буде двічі застосовано до L отримаємо:

2. 

Таким чином G² X = X, отже G - інволюція.

3.  T² X = T ² (L,R) = T (R,L) = (L,R ) = X.

Розглянемо сам процес шифрування. Визначимо X як вхідний значення. Нехай G_i - перетворення з ключем K_i, а Y_i - вихідне значення після i-го раунду. Тоді перетворення на i +1- му раунді можна записати у вигляді

Y_i+1 = T G_i Y_i,

крім першого, де

Y₁ = T G₁ X

Отже, вихідне значення після m раундів шифрування буде

.

Можна помітити, що на останньому етапі не обов'язково виконувати перестановку T.

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

 [16]

У своїй роботі «Криптографія і Комп'ютерна безпека» Хорст Фейстель описує два різних блоку перетворень (функцій ) — блок підстановок (S-блок) та блок перестановок (P-блок). Можна показати, що будь-яке бінарне перетворення над двійковим блоком фіксованої довжини, зводяться до S-блоку, але на практиці в силу складності будови n-розрядного S-блоку при великих n, застосовують більш прості конструкції. Термін «блок» в оригінальній статті використовується замість функції внаслідок того, що мова йде про блокове шифрі і передбачалося, що S-і P-блоки будуть цифровими мікросхемами (цифровими блоками).

Блок підстановок (S-блок) складається з дешифратора, що перетворює n-розрядний двійковий сигнал у однорозрядної сигнал по підставі 2ⁿ, системи комутаторів внутрішніх з'єднань (усього з'єднань 2ⁿ!) і шифратора , переводить сигнал з однорозрядною 2ⁿ-річно в n- розрядний двійковий. Аналіз n-розрядного S-блоку при великому n вкрай складний, проте реалізувати такий блок на практиці дуже складно, так як число можливих з'єднань вкрай велике (2ⁿ!). На практиці блок підстановок використовується як частина більш складних систем (Рис. 1.5).

У загальному випадку S-блок може мати неспівпадаючі число входів/виходів, в цьому випадку в системі комутації від кожного виходу дешифратора може йти не строго одне з'єднання, а 2 або більше чи не йти зовсім. Те ж саме справедливо і для входів шифратора. [14]

Рис. 1.5 Принципова схема 3-розрядного S-блоку

В електроніці можна безпосередньо застосовувати наведену схему, в програмуванні ж генерують таблиці заміни. Обидва цих підходу є еквівалентними, тобто файл, зашифрований на комп'ютері, можна розшифрувати на електронному пристрої і навпаки. [21]

Таблиця 1.2

Заміни для наведеного 3-розрядного S-блоку

Блок перестановок всього лише змінює положення цифр і є лінійним пристроєм. Цей блок може мати дуже велику кількість входів-виходів, проте в силу лінійності систему не можна вважати криптостійкою. Криптоаналіз ключа для n-розрядного P-блоку проводиться шляхом подачі на вхід n-1 різних повідомлень, кожне з яких складається з n-1 нуля («0») та 1 одиниці («1») (Рис. 1.6).

Рис. 1.6 Принципова схема 8-розрядного P-блоку

Можна показати, що циклічний зсув є окремим випадком P-блоку. У найпростішому випадку (зсув на 1 біт), крайній біт відщеплюється і переміщується на інший кінець регістру або шини. Залежно від того який біт береться, правий чи лівий, зсув називається вправо або вліво. Зрушення на більше число біт можна розглядати, як багаторазове застосування зсуву на 1.

Таблиця1.3

Циклічний зсув на m біт для n-розрядного входу (m <n)

Рис. 1.7 Циклічний зсув вліво на 3 розряди 8-ми бітної шини

Позначення операції - (A + B) mod n - це залишок від ділення суми A + B на n, де A і B - складати числа. Можна показати, що складання двох чисел за модулем n представляється в двійковій системі числення, як S-блок, у якого на вхід подається число A, а в якості системи комутації S-блоку використовується циклічний зсув вліво на B розрядів. У комп'ютерній техніці та електроніці операція додавання, як правило, реалізована як складання по модулю n = 2 ^m, де m - ціле (зазвичай m одно розрядності машини). Для отримання в двійковій системі A + B mod 2 ^m досить скласти числа, після чого відкинути розряди починаючи з m-того і старше.

Позначення операції - (A * B) mod n - це залишок від ділення твори A * B на n, де A і B - перемножується числа. У персональних комп'ютерах на платформі x86 при перемножування двох m-розрядних чисел виходить число розрядністю 2 * m. Щоб отримати залишок від ділення на 2 ^m потрібно відкинути m старших біт. [16][19]

Переваги:

·  Простота апаратної реалізації на сучасній електронній базі

·  Простота програмної реалізації в силу того, що значна частина функцій підтримується на апаратному рівні у сучасних комп'ютерах (наприклад, складання за модулем 2 , додавання за модулем 2 ^n, множення за модулем 2 ^n, і т. д.)

·  Гарна вивченість алгоритмів на основі мереж Фейстеля.

Недоліки:

·  За один раунд шифрується тільки половина вхідного блоку. [12]

Мережі Фейстеля були широко вивчені криптографами в силу їх великого розповсюдження. У 1988 Майкл Люби (Michael Luby) і Чарльз Ракофф (Charles Rackoff) провели дослідження мережі Фейстеля і довели, що якщо раундовий функція є криптостійкого псевдовипадковою, і використовувані ключі незалежні у кожному раунді, то 3-х раундів буде достатньо для того, щоб блочний шифр був псевдовипадковою перестановкою, тоді як чотирьох раундів буде достатньо для того, щоб зробити сильну псевдовипадкову перестановку.

Псевдовипадковою перестановкою Люби і Ракофф назвали таку, яка стійка до атаки з адаптивним вибором відкритого тексту, а сильною псевдовипадковою перестановкою - псевдовипадкових перест ановку стійку до атаки з використанням обраного шифрованого тексту. [14]

При великому розмірі блоків шифрування (128 біт і більше) реалізація такої мережі Фейстеля на 32-розрядних архітектурах може викликати труднощі, тому застосовуються модифіковані варіанти цієї конструкції (Рис. 1.7). Зазвичай використовуються мережі з 4 гілками. На малюнку показані найбільш поширені модифікації. Також існують схеми, в яких довжини половинок L₀ і R₀ не співпадають. Вони називаються незбалансованими. [21]