Алгоритми з симетричним криптографічним ключем

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

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

Криптографічні алгоритми можуть реалізовуватись як апаратно (що підвищує швидкість їх роботи), так і програмно (для збільшення гнучкості). Розглянемо принцип побудови шифрувальної апаратури. Підстановки та перестановки можуть бути реалізовані при допомозі простих електричних ланцюгів. На мал. 8.5 зображено пристрій, який називають Р-блоком (літера Р означає permutation - перестановка) та використовується для перестановки восьми вхідних розрядів. Якщо пронумерувати вхідні біти зверху вниз (01234567), вихід цього Р-блоку буде виглядати (36071245). При допомозі відповідного внутрішнього пристрою Р-блоку (розпайки дротів) можна заставити його виконувати будь-яку операцію перестановки практично зі швидкістю світла, так як ніякі обрахунки в ньому не використовуються, а просто передається сигнал з входу на вихід. Таке рішення відповідає принципу Кергофа: порушник знає, що використовується метод перестановки бітів. Але він не знає порядок перестановки.

Мал. 8.5. Основні елементи продукційних шифрів: Р-блоків (а); S-блоків (б); продукційних шифрів (в)

Підстановки виконуються S-блоками, як показано на мал..8.5,б. На вхід подається 3-бітовий вхідний текст, а на виході появляється 3-бітний зашифрований текст. Для кожного вхідного сигналу вибирається одна із 8 ліній декодера шляхом встановлення її в 1. Всі остальні лінії = 0. Потім ці лінії проходять через Р-блок, що являє собою 2-гу степінь S-блока. Третя степінь робить обернене кодування 1 із 8 ліній в 3-бітове двійкове число. Такий пристрій заміняє вісімкові числа 01234567 на 24506713 відповідно. 0 заміняється числом 2, 1-4… Сила цих елементів є очевидною, якщо сформувати каскад із пристроїв як показано на малюнку 8.5,в. Отриманий пристрій називається продукційних шифром. В даному прикладі на першому етапі (Р1) 12 вхідних ліній міняються місцями. Теоретично друга ступінь могла би бути S-блоком, що відображає одне 12-розрядне число в інше 12-розрядне число. Такий пристрій повинен мати в середній стадії 212=4096 перехресних проводів. Вхід розбивається на 4 групи по 3 розряди , з кожною з яких операція заміни виконується незалежно. Продукційні шифри, що працюють з к_бітними входами широко розповсюджені. Звичайне значення к знаходиться між 64 і 256.

Питання 9

Алгоритми з відкритим ключем

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

У 1976 році два дослідники із Стэнфордского університету, Діффі (Diffie) і Хеллман (Hellman), запропонували радикально нову криптосистему, в якій ключ шифрування і ключ дешифрації були різними, крім того, ключ дешифрації не можна було одержати з ключа шифрування. Запропоновані ними алгоритм шифрування Е і алгоритм дешифрації D (обидва що параметризуються ключем) повинні були задовольняти наступним трьом вимогам:

1.d(e(p))=p.

2. Украй складно вивести D з Е.

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

Цей метод працює таким чином. Хтось, наприклад Аліса, бажаючи одержувати секретні повідомлення, спочатку формує два алгоритми, що задовольняють перерахованим вище вимогам. Потім алгоритм шифрування і його ключ відкрито оголошуються, звідси назва — шифрування з відкритим ключем. Це можна зробити, розмістивши відкритий ключ, наприклад, на домашній сторіночці. Для позначення алгоритму шифрування, що параметризується відкритим ключем Аліси, ми використовуватимемо запис ЕА. Аналогічно (секретний) алгоритм дешифрації, що параметризується персональним ключем Аліси, ми позначатимемо Dа. Боб робить те ж саме, відкрито оголошуючи Ев, але зберігаючи в таємниці DB.

Тепер подивимося, чи зможемо ми вирішити проблему установки надійного каналу між Алісою і Бобом, які раніше ніколи не зустрічалися. Обидва ключі шифрування Аліси і Боба, ЕА і Ев, є відкритими. (Взагалі, всі користувачі мережі можуть, стаючи користувачами, опублікувати свої ключі шифрування.) Тепер Аліса бере своє перше повідомлення Р, обчислює Ев(Р) і посилає його Бобу. Боб розшифровує його за допомогою свого секретного ключа Dв, тобто