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

В сучасній криптографії використовують ті ж основні ідеї, що й в традиційній криптографії, тобто перестановка та підстановка. В традиційній криптографії використовуються прості алгоритми. На сьогодні вірне інше: ціллю є створення настільки складного та заплутаного алгоритму шифрування, що навіть якщо криптоаналітику дати зашифрований текст, щоб він не зміг взяти з цього тексту ніякої користі.
Першим класом алгоритмів шифрування, який ми вивчимо, буде клас алгоритмів з симетричним ключем. Він отримав таку назву тому, що для цифрації та дешифрації повідомлення використовувався один і той самий ключ. На мал. 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в, тобто обчислює DB(EB(P))= Р. Більше ніхто не може прочитати це зашифроване повідомлення ЕВ(Р), оскільки передбачається, що система шифрування достатньо надійна, а одержати ключ Dв на підставі відомого ключа Ев дуже важко. Посилаючи відповідь, Боб передає ЕA(R). Таким чином, Аліса і Боб одержують надійний секретний канал зв'язку.
Зверніть увагу на використовувану тут термінологію. Шифрування з відкритим ключем припускає у кожного користувача наявність двох ключів —відкритого ключа, і закритого ключа, потрібного користувачу для дешифрації повідомлень, що приходять до нього. Ми будемо і далі називати ці ключі відкритим і закритим, щоб відрізняти їх від секретних ключів, використовуваних для шифрування і дешифрації в звичайній криптографії з симетричним ключем.
Питання 7
Алгоритм RSA
Єдина заковика полягає в тому, щоб знайти алгоритми, що задовольняють всім трьом вимогам. Оскільки переваги шифрування з відкритим ключем очевидні, багато дослідників невпинно працювали над створенням подібних алгоритмів, і деякі з них вже опубліковані. Один хороший метод був розроблений групою дослідників Массачусетського технологічного інституту (Rivest і ін., 1978). Він названий по початкових буквах прізвищ трьох розробників: RSA (Rivest, Shamir, Adleman). Цей метод ось вже чверть століття витримує спроби злому і вважається дуже міцним. На його основі побудовані багато практичних систем безпеки. Головний недолік RSA полягає в тому, що для забезпечення достатнього рівня захищеності потрібен ключ завдовжки, принаймні, 1024 біта (проти 128 біт в алгоритмах з симетричними ключами). Через це алгоритм працює досить поволі.
У основі методу RSA лежать деякі принципи теорії чисел. Опишемо у загальних рисах, як користуватися цим методом. Подробиці див. у відповідних джерелах.
Виберемо два великі прості числа р і q (звичайно завдовжки 1024 біта).
Злічимо n=pq і z = (р - 1)(q - 1).
Виберемо число d, що є взаємно простим з числом z.
Знайдемо таке число е, що залишок від ділення твору ed на число z рівний 1.
Обчисливши наперед ці параметри, можна починати шифрування. Спочатку розіб'ємо весь відкритий текст (що розглядається як бітовий рядок) на блоки так, щоб кожне повідомлення Р потрапляло в інтервал 0 < Р < n. Це нескладно зробити, якщо розбити відкритий текст на блоки по до біт, де до — максимальне ціле число, для якого 2k < n.
Щоб зашифрувати повідомлення Р, обчислимо З = Pe (mod n). Щоб розшифрувати З, злічимо Р= Сd (mod n). Можна довести, що для всіх значень Р у вказаному діапазоні функції шифрування і дешифрації є взаємно зворотними. Щоб виконати шифрування, потрібні е і n. Для дешифрації потрібно d і n. Таким чином, відкритий ключ складається з пари (е, n), а закритий ключ — з пари (d, n).
Надійність методу забезпечується складністю знаходження множників великих чисел. Якби криптоаналітик міг розкласти на множники (відкрите) число n, він міг би тоді знайти значення р і q, а отже, і число z. Після цього числа e і d можна знайти за допомогою алгоритму Евкліда. На щастя, математики намагалися вирішити проблему розкладання на множники великих чисел щонайменше 300 років, і накопичений досвід дозволяє припустити, що ця проблема надзвичайно важка.
Рівест (Rivest) з колегами стверджує, що для розкладання на множники числа з 500 цифр необхідне 1025лет, якщо застосовувати грубу силу. Передбачається, що задіяні кращий відомий алгоритм і комп'ютер, що виконує одну інструкцію за 1 мкс. Навіть при збереженні експоненціального зростання швидкостей комп'ютерів буде потрібно століття, щоб знайти множники числа з 500 цифр, а до цього часу наші нащадки можуть просто вибрати ще більші р і q.
Тривіальний учбовий приклад роботи алгоритму RSA приведений на мал. 8.14. Для цього прикладу ми вибрали р = 3, а q = 11, що дає значення n = 33, а z = 20. Число d можна вибрати рівним 7, оскільки числа 20 і 7 не мають загальних дільників. При такому виборі значення е можна знайти, вирішивши рівняння 7е = 1 (mod 20), звідки витікає, що е = 3. Зашифрований текст З виходить з відкритого повідомлення Р по формулі З = Р3 (mod 33). Одержувач розшифровує повідомлення по формулі Р= С7 (mod 33). Як приклад на малюнку показано шифрування слова «SUZANNE».
Оскільки вибрані для даного прикладу прості числа такі малі, Р повинне бути менше 33, тому кожен блок відкритого тексту може містити лише одну букву. В результаті виходить моно алфавітний підстановлювальний шифр, що не дуже вражає. Якби ми натомість вибрали числа р і q близько 2512, тоді число n було б близько 21024. В цьому випадку кожен блок міг би містити до 1024 біт, або 128 восьми розрядних символів, проти 8 символів шифру DES або 16 AES.
Слід зазначити, що використання алгоритму RSA в описаному раніше вигляді аналогічно використанню симетричного алгоритму в режимі ЕСВ (Electronic Code Book — електронний шифроблокнот), в якому однакові блоки на вході перетворяться в однакові блоки на виході. Таким чином, для шифрування даних потрібне зчеплення блоків в якому-небудь вигляді. Проте на практиці алгоритм RSA з відкритим ключем використовується тільки для передачі одноразового секретного ключа, після чого застосовується який-небудь алгоритм з симетричним ключем типу AES або потрійного DES. Система RSA дуже повільна, щоб шифрувати великі об'єми даних, проте вона широко застосовується для розповсюдження ключів.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать