Алгоритми шифрування, пояснені на прикладах

Криптографія, в основному, є наукою про використання кодів і шифрів для захисту повідомлень.

Шифрування - це кодування повідомлень з наміром лише дозволити одержувачу зрозуміти значення повідомлення. Це двостороння функція (вам потрібно мати можливість скасувати будь-яке скремблювання, яке ви зробили з повідомленням). Це призначено для захисту даних під час передачі.

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

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

І якщо третя сторона отримала ключ, їм було дуже легко розірвати шифрування, перемігши цілі безпечного зв'язку.

Діффі-Хеллман вирішив цю проблему, дозволивши незнайомцям обмінюватися інформацією через загальнодоступні канали, які можна використовувати для формування спільного ключа. Спільний ключ важко зламати, навіть якщо відстежується весь зв’язок.

Як діє Діффі-Хеллман?

Діффі-Хеллман - це так званий протокол обміну ключами. Це основне використання Діффі-Хеллмана, хоча його можна використовувати також для шифрування (як правило, це не так, оскільки ефективніше використовувати DH для обміну ключами, а потім перейти на (значно швидше) симетричне шифрування для передачі даних ).

Це працює наступним чином:

В основному, є дві сторони, Аліса та Боб, які домовляються про початковий колір (довільний, але кожен раз повинен бути іншим). Вони також мають таємний колір, який тримають у собі. Потім вони змішують цей колір із загальним кольором, отримуючи два різних кольори. Потім вони передають цей колір іншій стороні, яка змішує його з їхнім секретним кольором, отримуючи той самий кінцевий секретний колір.

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

Наприклад:

  1. Боб та Аліса домовляються про два числа, велике просте число, p = 29, і основа g = 5
  2. Тепер Боб вибирає секретне число x (x = 4) і робить наступне: X = g ^ x% p (у цьому випадку% вказує залишок. Наприклад, 3% 2 дорівнює 3/2, де залишок дорівнює 1) . X = 5 ^ 4% 29 = 625% 29 = 16
  3. Аліса також вибирає секретний номер y (y = 8) і робить наступне: Y = g ^ y% p. Y = 5 ^ 8% 29 = 390,625% 29 = 24
  4. Боб посилає X Алісі, а Аліса Y - Бобу.
  5. Тоді Боб робить наступне: K = Y ^ x% p, K = 24 ^ 4% 29 = 331776% 29 = 16
  6. Потім Аліса робить наступне: K = X ^ y% p, K = 16 ^ 8% 29 = 4 294 967 296% 29 = 16

Чудова (* можливо, магічна *) річ у цьому полягає в тому, що і Боб, і Аліса мають однакове число K, і тепер вони можуть використовувати це для таємної розмови, бо ніхто інший не знає K.

Безпека цього протоколу визначається кількома речами:

  1. (Факт) Порівняно легко генерувати прості числа, навіть великі прості числа (наприклад, p).
  2. (Факт) Модульне піднесення ступеня дуже просто. Іншими словами, відносно легко обчислити X = g ^ x% p.
  3. (Припущення, засноване на поточній обчислювальній потужності та математиці) Модульне вилучення коренів без основних факторів дуже важко. По суті, дуже важко знайти K, не знаючи x та y, навіть якщо ви підглянули рух і бачите p, g, X та Y.

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

Навіть якщо зловмисник міг скомпрометувати цей ключ, Діффі-Хеллман забезпечує ідеальну вперед секретність.

Що є досконалою таємницею вперед?

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

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

Це можливо, якщо кожен сеанс має різний ефемерний ключ для кожного сеансу. Оскільки Діффі-Хеллман завжди використовує нові випадкові значення для кожного сеансу, (отже, генеруючи нові ключі для кожного сеансу), він називається ефемерним Діффі Хеллман (EDH або DHE). Багато наборів шифрів використовують це для досягнення ідеальної прямої таємниці.

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

Пряма секретність увімкнена при будь-якому обміні ключами Діффі-Хеллмана, але лише ефемерний обмін ключами (інший ключ для кожного сеансу) забезпечує ідеальну пряму секретність.

Ось допис від Скотта Хельме, який розповідає про це більш детально та пояснює, як увімкнути це на своїх серверах.

Які обмеження Діффі-Хеллмана?

Найбільшим обмеженням DH є те, що не підтверджує особу. Іншими словами, кожен може претендувати на те, що він Аліса чи Боб, і немає вбудованого механізму для перевірки того, що їх твердження відповідає дійсності.

Крім того, якщо впровадження не здійснюється в безпечному порядку, алгоритм може бути зламаний із достатньою кількістю виділених ресурсів (малоймовірно, але можливо для академічних команд або акторів національних держав).

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

Крім того, в 2015 році була продемонстрована атака, яка показала, що коли одні й ті самі прості числа використовувалися багатьма серверами як початок обміну ключами, загальна безпека Діффі-Хеллмана була нижчою, ніж очікувалося.

По суті, зловмисник міг просто попередньо обчислити атаку проти цього простого номера, полегшуючи компрометацію сеансів для будь-якого сервера, який використовував це просте число.

Це сталося тому, що мільйони серверів використовували однакові прості числа для обміну ключами. Для попереднього обчислення цього типу атак все ще потрібні ресурси академічного або національного рівня, і навряд чи це вплине на переважну більшість людей.

Однак, на щастя для тих, кому доводиться турбуватися про зловмисників національних держав, існує інший спосіб досягти обміну ключами DH за допомогою криптографії еліптичної кривої (ECDHE). Це виходить за рамки цієї статті, але якщо ви хочете дізнатись більше про математику, що лежить в основі цього обміну, перегляньте цю статтю.

Для більш детального вивчення слабких сторін ЦТ перегляньте цей довідковий документ та веб-сайт.

RSA

RSA названо на честь творців - Рівеста, Шаміра, Адлемана - і це спосіб генерування відкритих та приватних ключів.

Технічно існує два алгоритми RSA (один використовується для цифрових підписів, а другий - для асиметричного шифрування.) - у цій статті розглядається алгоритм асиметричного шифрування.

Це дозволяє обмінюватися ключами - спочатку ви призначаєте кожну сторону транзакційним відкритим / приватним ключам, потім генеруєте симетричний ключ і, нарешті, використовуєте пари відкритого / приватного ключів для надійної передачі спільного симетричного ключа.

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

Отже, як це працює?

  1. Виберіть 2 дуже великі прості числа (принаймні 512 біт або 155 десяткових цифр кожна), x та y (ці числа повинні бути секретними та випадковими)
  2. Знайдіть добуток, тобто z = x * y
  3. Виберіть непарне загальнодоступне ціле число e від 3 до n - 1 і не має спільних факторів (крім 1) з (x-1) (y-1) (тому воно відносно просто до x - 1 та y - 1 ).
  4. Знайдіть найменший спільний кратний x - 1 та y - 1 і назвіть його L.
  5. Обчисліть приватний показник ступеня, d, з x, y та e. de = 1% L. d - обернена до e% L (ви знаєте, що існує обернена, оскільки e відносно проста до z - 1 та y - 1). Ця система працює, оскільки p = (p ^ e) ^ d% z.
  6. Вихідні дані (z, e) як відкритий ключ і (z, d) як приватний ключ.

Тепер, якщо Боб хоче надіслати повідомлення Алісі, він генерує зашифрований текст (C) із простого тексту (P), використовуючи цю формулу:

C = P ^ e% z

Для того, щоб розшифрувати це повідомлення, Аліса обчислює наступне:

P = C ^ d% z

Зв'язок між d та e гарантує, що функції шифрування та дешифрування є зворотними. Це означає, що функція дешифрування може успішно відновити вихідне повідомлення, і що відновити оригінальне повідомлення досить важко без приватного ключа (z, d) (або простих факторів x та y).

Це також означає, що ви можете зробити z та e загальнодоступними, не порушуючи безпеку системи, полегшуючи спілкування з іншими, з якими у вас ще немає спільного секретного ключа.

Ви також можете використовувати операції в зворотному напрямку, щоб отримати цифровий підпис повідомлення. По-перше, ви використовуєте операцію дешифрування у відкритому тексті. Наприклад, s = ПІДПИС (p) = p ^ d% z.

Потім одержувач може перевірити цифровий підпис, застосувавши функцію шифрування та порівнявши результат із повідомленням. Наприклад, m = ПЕРЕВІРИТИ (и) = S ^ e% z.

Часто, коли це робиться, відкритий текст є хешем повідомлення, тобто ви можете підписати повідомлення (незалежно від довжини) лише одним піднесенням ступеня.

Безпека системи базується на кількох речах:

  1. (Факт) Порівняно легко генерувати прості числа, навіть великі прості числа (наприклад, x та y).
  2. (Факт) Множення легко. Знайти z дуже просто.
  3. (Припущення, засноване на поточній математиці) Факторинг важкий. Враховуючи z, відновити x та y відносно важко. Це можливо, але це займає деякий час, і це дорого.

    За однією з оцінок, відновлення основних множників 1024-бітового числа зайняло б рік на машині, яка коштувала 10 мільйонів доларів. Подвоєння розміру в геометричній прогресії збільшило б обсяг необхідної роботи (у кілька мільярдів разів більше роботи).

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

    Як правило, єдиними хакерами, які мають такий тип грошей і відданість одній цілі, є національні держави. Крім того, якщо існує простіший спосіб скомпрометувати систему (див. Нижче), це, мабуть, кращий варіант.

4. (Факт) Модульне піднесення ступеня дуже просто. Іншими словами, відносно легко обчислити c = p ^ e% z.

5. (Факт) Модульне вилучення кореня - змінити процес вище - легко, якщо у вас є прості множники (якщо у вас є z, c, e та прості множники x і y, легко знайти p таких, що c = p ^ e% z).

6. (Припущення, засноване на поточній обчислювальній потужності та математиці) Модульне вилучення кореня без простих множників дуже важко (якщо у вас z, c, e, але не x і y, порівняно важко знайти p таких, що c = p ^ e% z, особливо якщо a достатньо великий).

Хочете дізнатися більше про математику набагато розумніших людей? Перегляньте цю статтю.

Чудово, що краще?

Це залежить від вашого випадку використання. Між двома алгоритмами є кілька відмінностей - по-перше, ідеальна пряма секретність (PFS), про яку ми говорили раніше в контексті Діффі-Хеллмана. Хоча технічно ви можете створити ефемерні пари ключів RSA і забезпечити ідеальну пряму секретність з RSA, обчислювальні витрати набагато вищі, ніж для Діффі-Хеллмана - це означає, що Діффі-Хеллман є кращим вибором для реалізацій SSL / TLS, де ви хочете досконалу пряму секретність .  

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

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

Наприклад, в той час, як Діффі-Хеллман був затверджений урядом США та підтриманий інституційним органом, стандарт не був випущений - тоді як РДА (стандартизований приватною організацією) забезпечував безкоштовний стандарт, що означає, що РДА став дуже популярним серед приватних організацій.

Якщо вам цікаво читати більше, тут є чудова нитка щодо відмінностей.

Хочете дізнатись, як хакери використовують криптографічні атаки? Спробуйте цей набір завдань від Cryptopals.

Чим більше я дізнаюся про криптографію, тим більше я думаю, що Аліса та Боб, мабуть, повинні просто поговорити особисто.

- Пол Рейнхаймер (@preinheimer) 13 березня 2017 р