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

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

До кінця уроку ми охопимо:

Що таке асиметрична криптографія з відкритим ключем
Використання асиметричної криптографії, зокрема обмін ключами та цифрові підписи
Безпека асиметричної криптографії загалом
Детальний розгляд алгоритмів RSA, DSA та еліптичних кривих і їхня безпека
Приклади коду на Python, які показують, як алгоритми працюють на практиці
Загрози цим алгоритмам з боку як класичних, так і квантових комп'ютерів

Вступ до асиметричної криптографії з відкритим ключем

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

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

Розв'язання обох цих проблем забезпечує асиметрична криптографія з відкритим ключем (АКК), також відома як криптографія з відкритим ключем (PKC), яка є наріжним каменем сучасної цифрової безпеки.

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

Рисунок 1. Асиметричне шифрування

Рисунок 1. Асиметричне шифрування

АКК пропонує кілька корисних функцій, зокрема:

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

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

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

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

Інтерактивний обмін ключами

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

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

Сучасні криптосистеми на основі криптографії на еліптичних кривих (ECC) розширюють цю концепцію за допомогою обміну ключами Діффі-Геллмана на еліптичних кривих (ECDH). ECDH працює аналогічно до DH, але використовує властивості еліптичних кривих, що забезпечує більш безпечну та ефективну систему.

Рисунок 2. Протокол обміну ключами

Рисунок 2. Протокол обміну ключами

Неінтерактивний обмін ключами

На відміну від протоколів обміну ключами, таких як DH та ECDH, які є інтерактивними й вимагають двостороннього спілкування для погодження симетричного ключа, АКК також забезпечує неінтерактивні способи встановлення спільного секретного ключа. У таких схемах одна сторона генерує пару ключів (відкритий і закритий) та ділиться відкритим ключем з іншою стороною. Ця друга сторона потім генерує випадковий симетричний ключ, шифрує його отриманим відкритим ключем і надсилає назад першій стороні. Перша сторона використовує свій закритий ключ для розшифрування отриманого повідомлення, тим самим отримуючи спільний симетричний ключ. Ця схема є неінтерактивною в тому сенсі, що симетричний ключ визначається однією стороною і просто безпечно передається іншій стороні у зашифрованому вигляді.

Важливим аспектом неінтерактивного обміну ключами є різниця в бітах між симетричним ключем, яким сторони хочуть обмінятися, та рекомендованими розмірами повідомлень в АКК. Зазвичай сучасні симетричні ключі мають довжину в діапазоні 128–256 біт, тоді як асиметричні криптосистеми, такі як RSA, працюють з розмірами повідомлень близько 1024–4096 біт. Тому при використанні АКК для передачі симетричного ключа, з міркувань безпеки, його все одно необхідно закодувати у довше повідомлення розміром 1024–4096 біт. Це можна досягти двома підходами:

Обмін ключами на основі доповнення (padding): У цьому підході спочатку генерується коротший (128–256 біт) симетричний ключ, а потім узгоджена зворотна схема доповнення, наприклад OAEP, використовується для вбудовування його у довше (1024–4096 біт) повідомлення. Це довше повідомлення шифрується за допомогою АКК та транслюється як шифртекст. Одержувач спочатку розшифровує шифртекст, а потім видаляє доповнення, щоб отримати коротший симетричний ключ.
Механізми інкапсуляції ключів (KEM): При обміні ключами на основі KEM спочатку генерується випадковий довгий (1024–4096 біт) відкритий текст, з якого можна отримати коротший (128–256 біт) симетричний ключ за допомогою узгодженої функції виведення ключа (KDF). Довший відкритий текст шифрується за допомогою АКК і транслюється одержувачу як шифртекст. Одержувач декодує шифртекст за допомогою свого закритого ключа, а потім використовує KDF для отримання коротшого (128–256 біт) симетричного ключа. Популярні криптосистеми, такі як RSA, завдяки здатності безпосередньо шифрувати дані, можуть використовуватися для реалізації KEM.

Рисунок 3. Механізм інкапсуляції ключів

Рисунок 3. Механізм інкапсуляції ключів

Цифрові підписи з асиметричною криптографією

Цифрові підписи — ще одне потужне застосування асиметричної криптографії. Вони забезпечують автентифікацію, цілісність та невідмовність завдяки тому, що в АКК кожен суб'єкт має унікальний закритий ключ. Основна ідея протоколів підпису полягає в тому, що відправники захищених повідомлень додатково цифрово підписують повідомлення за допомогою свого унікального закритого ключа. Одержувач потім перевіряє цифровий підпис за допомогою відкритого ключа відправника. В АКК цифрові підписи можуть бути реалізовані за допомогою алгоритмів, спеціально розроблених для цієї мети, або за допомогою загальних криптосистем.

Рисунок 4. Цифрові підписи з асиметричною криптографією

Рисунок 4. Цифрові підписи з асиметричною криптографією

Спеціалізовані алгоритми цифрового підпису

На сьогодні американський Федеральний стандарт обробки інформації (FIPS) для цифрових підписів — це спеціалізована схема, яка просто називається Алгоритмом цифрового підпису (DSA). Дещо подібно до протоколу Діффі-Геллмана, DSA використовує алгебраїчні властивості модульного піднесення до степеня та мультиплікативних обернених для генерації та перевірки підпису.

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

Як DSA, так і ECDSA будуть розглянуті детальніше пізніше.

Схеми цифрового підпису з використанням загальних криптосистем

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

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

Застосування асиметричної криптографії

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

Інтернет-комунікації: Безпечна комунікація через інтернет, наприклад HTTPS, значною мірою спирається на асиметричну криптографію. Протоколи Transport Layer Security (TLS) та його попередник Secure Sockets Layer (SSL) використовують асиметричну криптографію під час початкового рукостискання (handshake) для встановлення симетричного ключа, який потім використовується протягом усього сеансу зв'язку.
Автентифікація: Асиметрична криптографія використовується для створення цифрових підписів, що дозволяє суб'єкту підтвердити автентичність цифрового документа або повідомлення як надісланого конкретним відправником. Це використовується в багатьох сценаріях: від перевірки оновлень програмного забезпечення до юридично обов'язкових цифрових контрактів.
Шифрування електронної пошти: Протоколи шифрування електронної пошти, такі як PGP (Pretty Good Privacy) та його відкритокодова альтернатива GPG (GNU Privacy Guard), використовують асиметричну криптографію, щоб гарантувати, що лише призначений одержувач може прочитати вміст електронного листа.
Захищена оболонка (SSH): SSH — це протокол для безпечного віддаленого входу та інших безпечних мережевих служб через небезпечну мережу. Він використовує асиметричну криптографію для автентифікації сервера клієнтом і, за бажанням, клієнта сервером.
VPN (віртуальна приватна мережа): Асиметричне шифрування використовується для встановлення безпечних з'єднань у VPN, забезпечуючи захищений зв'язок через публічні мережі.
Блокчейн та криптовалюти: Технології блокчейну, зокрема Bitcoin та Ethereum, використовують асиметричну криптографію. Наприклад, право власності на Bitcoin підтверджується за допомогою цифрових підписів з використанням асиметричної криптографії.
Центри сертифікації: Асиметрична криптографія використовується центрами сертифікації (CA) для видачі та підписання цифрових сертифікатів, що застосовуються в TLS-комунікаціях, підписуванні коду, шифруванні електронної пошти тощо. Цифровий сертифікат прив'язує відкритий ключ до конкретного суб'єкта (наприклад, людини або сервера).

Рисунок 5. Видача та підписання цифрових сертифікатів з використанням асиметричної криптографії

Рисунок 5. Видача та підписання цифрових сертифікатів з використанням асиметричної криптографії

Безпека асиметричної криптографії

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

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

Функціональність "пастки" (Trapdoor): В АКК операції шифрування та дешифрування включають різні взаємодоповнювальні ключі з єдиної пари ключів. Шифртекст, згенерований шифруванням за допомогою одного з ключів (наприклад, відкритого), повинен бути незрозумілим для третіх сторін, але легко розшифровуватися власником взаємодоповнювального ключа (у цьому випадку закритого). Іншими словами, шифрування повинно нагадувати одностороннє функцію з пасткою таку, що треті сторони не можуть інвертувати операцію та відновити відкритий текст, але закритий ключ надає секретну пастку, що дозволяє легке інвертування. Популярні алгоритми АКК використовують модульне піднесення до степеня для створення поведінки односторонньої функції з пасткою.

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

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

Протокол	Типові розміри ключів (у бітах)	Застосування
RSA	1024 (застарілий), 2048, 3072, 4096	Шифрування, цифрові підписи
DSA	1024 (застарілий), 2048, 3072	Цифрові підписи
DH	2048, 3072, 4096	Обмін ключами
ECDH	224, 256, 384, 521	Обмін ключами
ECDSA	224, 256, 384, 521	Цифрові підписи

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

Ризики безпеки для асиметричної криптографії

Як зазначено в наведеній вище таблиці, сучасні асиметричні алгоритми, такі як RSA, зазвичай використовують значно більші розміри ключів, ніж загальновживані симетричні аналоги, такі як AES-128. Навіть протоколи на основі ECC (ECDH та ECDSA), що мають менші розміри ключів, використовують мінімум 224 біти для ключів. Це означає, що атака грубої сили, що включає вичерпний пошук простору закритих ключів для ідентифікації правильного ключа, є обчислювально нездійсненною у передбачуваному майбутньому. Це залишається вірним навіть у разі використання квантових комп'ютерів для цього завдання. Тому атаки проти АКК зазвичай зосереджуються на використанні інших потенційних слабкостей конкретних криптосистем. Деякі добре задокументовані режими атак спрямовані на:

Алгоритмічну слабкість — шляхом використання складних математичних та обчислювальних засобів для підриву припущень про складність, що лежать в основі асиметричних алгоритмів. Наприклад, безпека RSA ґрунтується на складності факторизації великих простих чисел, і нещодавні обчислювальні досягнення дозволили успішно факторизувати 829-бітні ключі RSA. Тому 1024-бітний RSA наразі є застарілим. Як буде обговорено далі, основний ризик, який квантові комп'ютери становлять для АКК, також підпадає під цю категорію.
Недосконалу випадковість, яка може призвести до слабкості в процесі генерації ключів. Наприклад, якщо генератор випадкових чисел, що використовується для створення ключів, є дефектним та генерує ключі, які не є по-справжньому випадковими, зловмисник може виявитися здатним передбачити ключі.
Вади реалізації — такі як помилки в реалізації криптографічних алгоритмів, які ненавмисно розкривають інформацію про ключі. Наприклад, неправильне доповнення (padding) потенційно може розкрити деталі про ключі.
Бічні канали — вони стосуються витоку інформації з фізичної системи, що виконує криптографію. Такі витоки можуть бути у формі інформації про час, споживання енергії або навіть звуку, що може бути використано в так званій атаці по бічному каналу. Наприклад, аналіз часу виконання криптографічних операцій може виявити кількість одиниць '1' у двійковому ключі. Цей, здавалося б, нешкідливий витік значно звужує простір пошуку, розкриваючи потенційні розв'язання задач, які спочатку здавалися непереборними.
Обмін ключами — шляхом перехоплення ключів під час їх обміну, наприклад у атаці «людина посередині» (MITM). Протокол DH вразливий до атак MITM, якщо не вжито додаткових кроків автентифікації.
Зберігання ключів — шляхом спроби викрасти ключі з погано захищених сховищ. Це включає фізичні атаки, такі як маніпуляції або крадіжка пристроїв зберігання.

Захист асиметричних криптосистем від різноманітних можливих атак є тому значним завданням, що включає математичні, апаратні, програмні, логістичні та правові міркування.

RSA

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

У цьому розділі ми проілюструємо асиметричну криптографію (АКК) на прикладі RSA через прості приклади.

Ми використаємо стандартний сценарій двох сторін — Аліси та Боба — які хочуть безпечно спілкуватися за допомогою АКК.

Алгоритм RSA

Базовий алгоритм RSA включає чотири операції: генерацію ключів, розподіл ключів, шифрування та дешифрування:

Генерація ключів:

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

Ми будемо називати їх:
- Відкритий ключ: $(e, n)$
- Закритий ключ: $(d, n)$
Зверни увагу, що $n$ є спільним для відкритого та закритого ключів і називається модулем. Він знадобиться нам пізніше.

Математична деталь

Вибери два різних простих числа $p$ $p$ та $q$ $q$ .
- Вибираються випадково (з міркувань безпеки).
- Вони повинні бути схожої величини, але відрізнятися за довжиною на кілька цифр, щоб ускладнити факторизацію.
- Прості числа можна ефективно вибрати за допомогою тесту на простоту.
Обчисли $n = p*q$ $n = p * q$ .
- $n$ є модулем як для відкритого, так і для закритого ключів.
Обчисли тотієнт $φ$ $(n) = (p-1)*(q-1)$ $(n) = (p - 1) * (q - 1)$ .
- Тотієнт зберігається в таємниці і зазвичай відкидається після генерації ключів.
Вибери ціле число $e$ $e$ таке, що $1 < e <$ $1 < e <$ $φ$ $(n)$ $(n)$ та $gcd$ $(e,$ $(e,$ $φ$ $(n)) = 1$ $(n)) = 1$ .
- Тобто $e$ та $φ$ $(n)$ повинні бути взаємно простими.
- Це число $e$ утворює показник відкритого ключа і зазвичай вибирається як мале число для обчислювальної ефективності.
- Просте число $65537 = 2^{16} + 1$ часто використовується.
- Обчисли $d$ $d$ , щоб задовольнити відношення конгруентності $d*e ≡ 1 ($ $d * e \equiv 1 ($ $mod$ $φ$ $(n))$ $(n))$ .
  - Тобто $d$ є мультиплікативним оберненим числа $e$ за модулем $φ$ $(n)$ .
  - Це ефективніше обчислюється за допомогою розширеного алгоритму Евкліда.
  - Це число $d$ є показником закритого ключа.
Відкритий ключ складається з $(e, n)$ , а закритий ключ — це $(d, n)$ .

Розподіл ключів:
- Відкритий ключ $(e, n)$ оприлюднюється для тих, хто може бажати надіслати повідомлення.
- Закритий ключ $(d, n)$ зберігається в таємниці.
Шифрування:
- Аліса хоче надіслати повідомлення $M$ Бобу. У цьому випадку — просте ціле число.
- Аліса використовує відкритий ключ Боба $(e, n)$ для шифрування повідомлення в шифртекст $C$ .
Математична деталь
- $M$ — це ціле число $0 ≤ M < n$ .
- $C ≡ M^e (mod n)$ , де $C$ — шифртекст.
Дешифрування:
- Боб отримує шифртекст $C$ .
- Боб використовує свій закритий ключ $(d, n)$ для розшифрування повідомлення назад у повідомлення $M$ .
Математична деталь
- $M ≡ C^d (mod n)$ .

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

Ілюстрація RSA на Python

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

примітка

Примітка: У цьому розділі ми покажемо математичні обчислення детально як частину коду на Python.

Генерація ключів RSA

Пройдемося по простому прикладу алгоритму RSA з малими простими числами.

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

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

# Added by doQumentation — required packages for this notebook
!pip install -q cryptography

import math

# Example function to compute the gcd (greatest common divisor)
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

# let's calculate some examples using algorithm
n1 = gcd(50, 10)
n2 = gcd(99, 33)
n3 = gcd(59, 9)

# do the same with the python library call

m1 = math.gcd(50, 10)
m2 = math.gcd(99, 33)
m3 = math.gcd(59, 9)

# Confirm they are the same
assert n1 == m1
assert n2 == m2
assert n3 == m3

# They are - print out the values for explanation
print("gcd(50,10) =", m1)
print("gcd(99,33) =", m2)
print("gcd(59,9) =", m3)

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

# Choosing two prime numbers and keep them secret
p = 13
q = 19
print("The secret prime numbers p and q are:", p, q)

Далі обчислюється модуль $n$ , який є просто добутком двох обраних простих чисел. Цей модуль буде опублікований як частина відкритого ключа.

# Calculate n which is the modulus for both the public and private keys
n = p * q
print("modulus n (p*q)=", n)

Далі обчислюється функція тотієнта Ейлера $\varphi(n)$ , оскільки вона необхідна для операції модульного мультиплікативного оберненого, що використовується для визначення ключів в RSA. $phi$ також зберігається в таємниці і зазвичай відкидається після генерації ключів.

# Compute Euler's totient function, φ(n) and keep it secret
phi = (p - 1) * (q - 1)
print("The secret Euler's function (totient) [phi(n)]:", phi)

Тепер ми готові обчислити відкритий та закритий ключі. В RSA кожен з них задається кортежем із двох цілих чисел. Перший елемент кожного кортежу є окремим цілим числом, а другий елемент — модуль $n$ , спільний для обох ключів.

Перший елемент відкритого ключа може бути будь-яким цілим числом, більшим за 1, яке є взаємно простим з $phi$ . Два цілих числа є взаємно простими, якщо їх найбільший спільний дільник дорівнює 1. Тому ми використовуємо функцію math.gcd, щоб знайти ціле число $e$ , взаємно просте з $phi$ .

# Choose an integer e such that e and φ(n) are coprime
e = 2
while e < phi:
    if math.gcd(e, phi) == 1:
        break
    else:
        e += 1
print("Public Key (e):", e)

Для закритого ключа потрібне ціле число $d$ , яке є мультиплікативним оберненим числа $e$ за модулем $phi$ ; тобто воно задовольняє відношення конгруентності $d*e\equiv 1 \pmod{\varphi(n)}$ . Для цього простого прикладу, де ми маємо справу з малими цілими числами, ми можемо просто перебрати натуральні числа, щоб знайти підходяще $d$ . У реалістичних умовах для цієї мети використовується обчислювально ефективний розширений алгоритм Евкліда.

# Compute a value for d such that (d * e) % φ(n) = 1
d = 1
while True:
    if (d * e) % phi == 1:
        break
    else:
        d += 1
print("Private Key (d):", d)

Тепер ми формуємо кортежі $(e, n), (d, n)$ , які утворюють відкритий та закритий ключі відповідно. Відкритий ключ потім публікується, тоді як закритий ключ зберігається в таємниці.

# Public and Private Key pair
public = (e, n)
private = (d, n)

print(f"The Public key is {public} and Private Key is {private}")

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

Тут ми ілюструємо випадок, коли відкритий ключ $(e,n)$ використовується для шифрування, а закритий ключ $(d, n)$ — для дешифрування, визначаючи функцію Python для кожної операції.

Потім ми шифруємо та розшифровуємо ціле повідомлення $msg$ .

# Encryption function
def encrypt(plain_text):
    return (plain_text**e) % n

# Decryption function
def decrypt(cipher_text):
    return (cipher_text**d) % n

# Simple message to encode
msg = 9

# encrypt then decrypt
enc_msg = encrypt(msg)
dec_msg = decrypt(enc_msg)

print("Original Message:", msg)
print("Encrypted Message:", enc_msg)
print("Decrypted Message:", dec_msg)

Хоча малі цілі числа, використані вище, корисні для легкого ознайомлення з основними ідеями алгоритму RSA, у реальних застосуваннях RSA вимагає використання дуже великих цілих чисел. Наприклад, 2048-бітний RSA передбачає використання модуля $n$ довжиною 2048 біт, десяткові цілочисельні еквіваленти якого становлять близько 10 $^{616}$ . Ці справді величезні числа необхідні для практичної безпеки RSA.

Обмін симетричними ключами з RSA

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

Розглянемо такий сценарій. Аліса та Боб хочуть використовувати SKC для шифрування та дешифрування повідомлень. Однак перш ніж цей процес можна ініціалізувати, їм потрібно погодити спільний секретний ключ. Один варіант — одна зі сторін, скажімо Аліса, генерує секретний ключ, а потім безпечно передає його Бобу. Щоб здійснити цю безпечну передачу, Аліса вирішує використати RSA як механізм інкапсуляції ключів (KEM).

Це включає такі кроки:

Спочатку Аліса генерує випадковий симетричний ключ, яким вона має намір поділитися з Бобом.
Потім Боб генерує асиметричну пару ключів та публікує свій відкритий ключ на відповідному каналі.
Далі Аліса використовує відкритий ключ Боба для шифрування симетричного ключа, таким чином інкапсулюючи його в шифртекст.
Потім Аліса транслює шифртекст через надійний, але не обов'язково безпечний канал.
Нарешті, Боб отримує шифртекст і розшифровує його за допомогою свого закритого ключа. Тепер він має доступ до симетричного ключа, згенерованого Алісою.

Рисунок 1. Обмін симетричними ключами з RSA

Рисунок 1. Обмін симетричними ключами з RSA

Приклад обміну ключами на основі доповнення (padding) на Python

Практичний робочий процес із використанням RSA для неінтерактивного обміну ключами на основі доповнення тепер проілюстровано за допомогою бібліотеки cryptography для Python.

Імпортуємо необхідні модулі з бібліотеки cryptography для Python. За потреби цю бібліотеку можна встановити за допомогою команди pip install cryptography.

Потім Аліса генерує випадковий секретний ключ, яким вона має намір передати Бобу.

# pip install cryptography
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.fernet import Fernet
from cryptography.hazmat.primitives import hashes

symmetric_key = Fernet.generate_key()
print(f"\nSymmetric key generated by Alice: {symmetric_key}")

За допомогою модуля rsa з бібліотеки cryptography Боб генерує пару ключів, а потім транслює свій відкритий ключ. Будь-хто може перехопити відкритий ключ і зчитати відкриті числа $(e,n)$ , що утворюють ключ.

# Bob generates a 2048-bit RSA key pair
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()
print(f"Public key broadcast by Bob: {bob_public_key}")
print(f"\nPublic numbers in Bobs' public key: {bob_public_key.public_numbers()}")

На цьому етапі ми припускаємо, що Аліса отримала відкритий ключ, транслювований Бобом. symmetric_key Аліси тепер може бути зашифрований відкритим ключем Боба для отримання шифртексту. У реалістичних умовах Аліса також використовуватиме додаткові методи доповнення (padding), такі як OAEP, щоб забезпечити семантичну безпеку своїх комунікацій з Бобом.

# Encryption
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Ciphertext:", ciphertext)

Потім Аліса транслює шифртекст через відкритий канал, впевнена, що лише Боб із відповідним закритим ключем зможе його розшифрувати. Ми припускаємо, що Боб отримав шифртекст і тепер може розшифрувати його за допомогою свого конфіденційного закритого ключа.

# Bob decrypts ciphertext to access the symmetric key
decrypted_symmetric_key = bob_private_key.decrypt(
    ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted key:", decrypted_symmetric_key)
assert decrypted_symmetric_key == symmetric_key

На цьому етапі і Аліса, і Боб мають доступ до секретного симетричного ключа, який вони можуть використовувати для застосувань SKC.

Симуляція механізму інкапсуляції ключів за допомогою RSA на Python

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

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

Починаємо з імпорту необхідних бібліотек Python.

Боб генерує свою пару ключів RSA та публікує відкритий ключ.

from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes
from os import urandom

# Bob's RSA key pair
private_key_Bob = rsa.generate_private_key(public_exponent=65537, key_size=2048)
public_key_Bob = private_key_Bob.public_key()

print("Bob's private and public keys created")

Аліса спочатку генерує довгий випадковий секрет, з якого буде виведений спільний секрет. У чистому KEM цей довгий секрет є випадковим елементом алгебраїчної структури, що лежить в основі криптосистеми. У випадку 2048-бітного RSA це було б випадкове ціле число за модулем 2048-бітного RSA-модуля. Таким чином, чистий KEM не потребує додаткового заповнення, але в цьому прикладі ми лише симулюємо KEM за допомогою RSA, і бібліотека cryptography вимагає використання заповнення під час шифрування RSA. Тому ми використаємо дещо коротший довгий секрет, який, проте, значно довший за стандартний 256-бітний ключ AES.

Alice_long_secret = urandom(160)  # A 160 byte or 1280 bit random message
print("Alice's secret created")

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

Alice_encrypted_secret = public_key_Bob.encrypt(
    Alice_long_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)
print("Alice's secret encrypted")

Боб розшифровує зашифрований секрет, отриманий від Аліси, за допомогою свого приватного ключа.

Bob_decrypted_secret = private_key_Bob.decrypt(
    Alice_encrypted_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

assert Alice_long_secret == Bob_decrypted_secret, "Secrets do not match!"

# if we get here they match
print("Secrets match")

Нарешті, і Аліса, і Боб окремо застосовують узгоджену функцію виведення ключів (KDF) до довгого секрету для отримання симетричного ключа.

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

Тому припустимо, що і Аліса, і Боб мають доступ до однієї й тієї ж випадкової солі.

def key_derivation_function(secret, salt):
    hkdf = HKDF(
        algorithm=hashes.SHA256(),
        length=32,  # Desired key length
        salt=salt,
        info=None,
        backend=None,
    )
    return hkdf.derive(secret)

common_salt = urandom(16)  # Random salt accessible to both Alice and Bob

symmetric_key_Alice = key_derivation_function(Alice_long_secret, common_salt)
symmetric_key_Bob = key_derivation_function(Bob_decrypted_secret, common_salt)

assert symmetric_key_Alice == symmetric_key_Bob, "Derived keys do not match!"
print(
    f"A symmetric key of length {len(symmetric_key_Alice)*8} bits was successfully derived by both Alice and Bob!"
)

Цифрові підписи з RSA

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

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

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

Розглянемо цей загальний сценарій, який передбачає такі кроки:

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

Рисунок 2. Цифрові підписи з RSA

Рисунок 2. Цифрові підписи з RSA

Цей процес цифрового підпису проілюстровано нижче.

Знову імпортуємо корисні модулі з бібліотеки cryptography. Як і раніше, Аліса має намір безпечно надіслати симетричний ключ Бобу, але вона також хоче поставити цифровий підпис. У цьому випадку нам потрібні відкриті ключі як Аліси, так і Боба. Тому першим кроком є генерація кожним із них власної пари ключів за допомогою RSA та публікація свого відкритого ключа.

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import padding, rsa
from cryptography.hazmat.primitives.asymmetric.utils import Prehashed

# Generate keys for Bob
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()

# Generate keys for Alice
alice_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
alice_public_key = alice_private_key.public_key()

print("Private and Public keys generated for Bob and Alice.")

На наступному кроці Аліса, як і раніше, використовує відкритий ключ Боба для шифрування симетричного ключа та готує шифротекст.

# Alice encrypts the message using Bob's public key
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("ciphertext of symmetric key: ", ciphertext)

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

Створення хешу шифротексту за допомогою алгоритму хешування.
Шифрування хешу приватним ключем Аліси, що і є підписом.

# Alice signs the ciphertext using her private key
digest = hashes.Hash(hashes.SHA256())
digest.update(ciphertext)
hash_to_sign = digest.finalize()

signature = alice_private_key.sign(
    hash_to_sign,
    padding.PSS(mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH),
    Prehashed(hashes.SHA256()),
)

print("signature: ", signature)

Потім Аліса передає шифротекст і підпис по мережі, щоб Боб міг отримати обидва.

# Bob receives the ciphertext and signature
received_ciphertext = ciphertext
received_signature = signature

# Send signature and ciphertext here
print("Sending ciphertext and signature.....")

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

# Bob creates a hash of the ciphertext using the same algorithm used by Alice
digest = hashes.Hash(hashes.SHA256())
digest.update(received_ciphertext)
hash_to_verify = digest.finalize()

print("hash to verify: ", hash_to_verify)

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

У коді Python нижче ці операції об'єднані в корисну утилітну функцію verify, яку надає об'єкт, пов'язаний з відкритим ключем Аліси.

from cryptography.exceptions import InvalidSignature

def is_signature_valid(public_key, signature, data_hash):
    try:
        public_key.verify(
            signature,
            data_hash,
            padding.PSS(
                mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH
            ),
            Prehashed(hashes.SHA256()),
        )
        return True
    except InvalidSignature:
        return False

if is_signature_valid(alice_public_key, received_signature, hash_to_verify):
    print("The signature is valid.")
else:
    print("The signature is not valid.")

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

# Bob decrypts the message using his private key
decrypted_message = bob_private_key.decrypt(
    received_ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted message:", decrypted_message.decode())

У наведеному вище сценарії з цифровим підписом будь-яка сторона — не лише Боб — може перевірити, що Аліса є відправником шифротексту, оскільки кожен має доступ до відкритого ключа Аліси, шифротексту та цифрового підпису. Крім того, після надсилання шифротексту та підпису Аліса не зможе згодом заперечити, що робила це, адже підпис можна розшифрувати до осмисленого хешу лише за допомогою її відкритого ключа. Це встановлює невідмовність.

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

Злом RSA

Корисність та безпека алгоритму RSA, описаного вище, ґрунтується на двох математичних припущеннях:

Знаходження мультиплікативного оберненого за модулем $d$ за умови доступу лише до $(e, n)$ є обчислювально нездійсненним.
У контексті RSA операція модульного піднесення до степеня поводиться як одностороння функція з люком. При використанні для шифрування вона дає шифротекст, непридатний для читання, і без доступу до приватного ключа інвертування операції для відновлення відкритого тексту з шифротексту є нездійсненним. Однак з доступом до приватного ключа, який діє як люк, шифротекст можна легко розшифрувати.

Найбільш відома атака на алгоритм RSA спрямована на підрив припущення 1 шляхом ефективного відновлення числа приватного ключа $d$ через факторизацію модуля $n$ . Як буде показано нижче, відновити $d$ легко, якщо є доступ до простих множників $p$ та $q$ числа $n$ , або до тотієнта $φ$ $(n)$ . Нагадаємо, що $p$ , $q$ та $φ$ $(n)$ зберігаються в таємниці під час генерації ключа і знищуються після. Третя сторона, яка відновить цю інформацію за допомогою класичного або квантового комп'ютера, фактично розкриє приватний ключ, зламавши RSA. Таким чином, факторизація простих чисел є ключовим обчислювальним примітивом, необхідним для злому RSA.

Класичні обчислення та RSA

Відомо, що факторизація великих цілих чисел демонструє надполіноміальне або субекспоненціальне масштабування на класичних комп'ютерах. Найкращий відомий класичний алгоритм для факторизації цілих чисел, більших за $10^{100}$ , — це загальне решето числових полів (GNFS)

Математична деталь

$L_n[\frac{1}{3}, (\frac{64}{9})^{(\frac{1}{3})}] = e^{[((\frac{64}{9})^{(\frac{1}{3})} + o(1)) (log(n))^{\frac{1}{3}}(log(log(n))^{\frac{2}{3}})]}$

як функція цілого числа $n$ , що підлягає факторизації.

Це масштабування є надполіноміальним відносно кількості бітів, потрібних для представлення $n$ .

Тому факторизація простих чисел вважається неефективною на класичних комп'ютерах.

На сьогодні найбільші цілі числа, факторизовані на класичному обладнанні, мають порядок 829 бітів або 250 десяткових цифр. Враховуючи експоненціальне зростання потужності класичних обчислень, що спостерігалося протягом останніх кількох десятиліть, 1024-бітний RSA більше не вважається безпечним у найближчій перспективі та є застарілим. Тим не менш, у найближчому майбутньому факторизація 2048-бітних цілих чисел порядку $10^{617}$ вважається нездійсненною на класичних системах, що свідчить про збереження життєздатності. Однак поява квантових комп'ютерів ставить цю оцінку під сумнів.

Квантовий алгоритм Шора та RSA

Мабуть, найвідоміший сьогодні квантовий алгоритм — це алгоритм Шора для знаходження простих множників цілих чисел. Коли він був представлений Пітером Шором у 1994 році, він був визнаний першим квантовим алгоритмом, що пропонує надполіноміальне прискорення порівняно з класичними алгоритмами для задачі великої практичної важливості — а саме факторизації простих чисел.

Алгоритм Шора може розкладати числа на множники за $O(n^2)$ , де $n$ — кількість бітів.

Математичне пояснення алгоритму Шора

У контексті RSA, алгоритм Шора працює, використовуючи періодичність модульної показникової функції $f(x) = a^x (mod~n)$ та надає квантовий примітив пошуку période, що дозволяє ефективно факторизувати модуль $n$ .

Спрощений загальний нарис схеми Шора для злому RSA виглядає так:

Маючи модуль $n$ , опублікований як частина відкритого ключа, обери число $a$ , взаємно просте з $n$ , тобто $gcd(a,n) = 1$ . Оскільки ми знаємо, що $n = p*q$ має рівно два простих множники $(p, q)$ , майже будь-яке випадково вибране число, менше за $n$ , швидше за все буде взаємно простим з $n$ .
Обравши $a$ , знайди показник $r$ такий, що $a^r \equiv 1 (mod~n)$ . Це означає $a^r - 1 \equiv 0 (mod~n)$ . Існування показника $r$ , за якого виконується зазначена конгруенція, гарантується властивістю періодичності модульного піднесення до степеня.
Якщо $r$ парне, $a^r - 1 \equiv 0 (mod~n) \implies (a^{r/2} - 1) (a^{r/2} + 1) = \gamma*n$ для деякого цілого числа $\gamma$ . Ліва частина цієї останньої рівності повинна містити $p$ та $q$ як два зі своїх простих множників, оскільки права частина їх містить. Якщо $r$ непарне, повернися до кроку 1 та спробуй інший вибір $a$ .
Використай розширений алгоритм Евкліда для знаходження $gcd((a^{r/2} - 1), n)$ або $gcd((a^{r/2} + 1), n)$ . Обчислений НСД, швидше за все, ідентифікує один із простих множників $p$ або $q$ . Розділи $n$ на цей простий множник, щоб отримати другий.
Знаючи $p, q$ , використай кроки оригінального алгоритму RSA для відновлення тотієнта $\phi(n)$ та генерації числа приватного ключа $d$ як мультиплікативного оберненого за модулем відомого числа відкритого ключа $e$ .

У серпні 2023 року Одед Регев опублікував покращення оригінального алгоритму Шора, використовуючи багатовимірний підхід і отримавши $O(n^{1.5})$ . Подальші дослідження в цій галузі, зокрема роботи Рагавана та Вайкунтанатана, продовжуються і можуть зменшити вимоги до часу, вартості або кількості кубітів. Хоча ми не можемо сказати, коли саме застосування таких алгоритмів проти реального RSA-шифрування стане дійсно можливим, це стає ближчим з кожним днем.

Приклад на Python, що демонструє злом RSA-шифрування

У наступних комірках коду ми ілюструємо приклад знаходження приватного ключа, маючи лише відкритий ключ. Тут буде використано метод грубої сили на класичному комп'ютері, але це демонструє, як можна було б застосувати алгоритм Шора — зокрема для великих ключів.

примітка

У цьому розділі ми детально покажемо математичні обчислення як частину коду Python

У прикладі маємо відкритий ключ $(5, 247)$ і відновимо приватний ключ.

Крок 1: Перший крок — вибрати число, взаємно просте з 247. Майже будь-яке число підійде. Візьмемо 6.

n = 247  # the modulus
e = 5  # public key number
a = 6  # an integer coprime to n
assert gcd(a, n) == 1
print(f"Checked {n} and {a} are coprime")

Крок 2: Далі потрібно знайти період $r$ такий, що $6^r \equiv 1 (mod~247)$ . У цьому прикладі ми обчислюємо $r$ класично методом грубої сили, але можна також використати алгоритм Шора на квантовому комп'ютері за допомогою Qiskit.

r = 0
rem = 100
while rem != 1:
    r += 1
    rem = (a**r) % n

print(f"period r is: {r}")
assert a**r % n == 1

print(f"Checked {a}^{r} mod {n} is 1")

Крок 3: Оскільки період $r = 36$ парний, ми можемо обчислити $f1 = (a^{r/2}-1), f2=(a^{r/2}+1)$ .

# explicitly use as integer
f1 = int(a ** (r / 2) - 1)
f2 = int(a ** (r / 2) + 1)

print(f"f1 = {f1}")
print(f"f2 = {f2}")

Крок 4: Знайди НСД одного з цих множників та $n$ . Просто розділи $n$ на вже знайдений простий множник, щоб отримати другий простий множник.

q_found = gcd(f1, n)
print(f"One possible prime factor of n ({n}) is: {q_found}")

# explicit int (to avoid floating point)
p_found = int(n / q_found)
print(f"The second prime factor of n ({n}) is: {p_found}")

assert n == p_found * q_found

Крок 5: Відновивши прості множники $n = 247$ як $p_{found}=13$ та $q_{found}=19$ , обчислимо тотієнт $\phi_{found} = (p_{found}-1)*(q_{found}-1)$ .

Приватний ключ — це мультиплікативний обернений за модулем числа відкритого ключа $e=5$ .

# Compute the totient
phi_found = (p_found - 1) * (q_found - 1)
print(f"The totient is: {phi_found}")

# Recover the private key number d_found by satisfying (d_found * e) % phi_found = 1
d_found = 1
while True:
    if (d_found * e) % phi_found == 1:
        break
    else:
        d_found += 1
print("Private Key number:", d_found)

У наведеній схемі крок 2 є ключовою операцією пошуку período, для якої алгоритм Шора використовує два фундаментальні квантові примітиви: квантове перетворення Фур'є та квантову оцінку фази. Детальне пояснення квантових аспектів алгоритму Шора дивись у уроці про оцінку фази та факторизацію в курсі Основи квантових алгоритмів. Кроки 1 та 3–5 передбачають відносно нескладні операції, які можна легко виконати на класичних комп'ютерах.

За бажанням, ось детальний візуальний покроковий огляд реалізації алгоритму Шора.

На квантових комп'ютерах алгоритм Шора може демонструвати полілогарифмічне масштабування, настільки сприятливе, як $O((log~n)^2 (log~log~n))$ відносно модуля $n$ , або поліноміальне масштабування відносно кількості бітів, потрібних для представлення $n$ . Це є надполіноміальним прискоренням порівняно з класичним алгоритмом GNFS.

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

Обмін ключами Діффі–Хеллмана та алгоритм цифрового підпису

У попередньому розділі ми обговорювали криптосистему RSA, безпека якої ґрунтується на обчислювальній складності факторизації простих чисел. Тут ми розглянемо два популярних протоколи асиметричної криптографії: обмін ключами Діффі–Хеллмана (DH) та алгоритм цифрового підпису (DSA), обидва з яких базуються на іншій математичній задачі — задачі дискретного логарифма (DLP).

Задача дискретного логарифма

У наступному рівнянні потрібно знайти $a$ , маючи лише $e$ , $M$ , $c$

$a^e$ $mod$ $M = c$

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

Це відоме як задача дискретного логарифма (DLP).

Математичні деталі задачі дискретного логарифма

DLP зазвичай формулюється в контексті циклічних груп і формулюється таким чином.

Розглянемо циклічну групу $G$ , породжену елементом групи $g \in G$ , і для довільного елемента $h \in G$ знайдемо ціле число $k$ таке, що $h = g^{k}$ .

Тут ціле число $k \equiv log_{g}h$ є дискретним логарифмом. Циклічна властивість $G$ гарантує, що для кожного $h$ існує дійсне ціле число $k$ .

Для криптографії корисною виявляється DLP на мультиплікативній групі цілих чисел за модулем простого числа $p$ , що позначається $(\mathbb{Z}_p)^{\times}$ . Елементами $(\mathbb{Z}_p)^{\times}$ є класи конгруентності, позначені цілими числами за модулем $p$ , що є взаємно простими з $p$ .

Наприклад:

$(\mathbb{Z}_5)^{\times} = \{[1],[2],[3],[4]\}~\mathrm{and}~(\mathbb{Z}_7)^{\times} = \{[1],[2],[3],[4],[5],[6]\}$

Операція множення $(\times)$ на цих групах є просто звичайним цілочисельним множенням з наступним зведенням за модулем $p$ , а піднесення до цілого степеня $k$ — це лише повторне множення $k$ разів і зведення за модулем $p$ .

Розглянемо приклад DLP на $(\mathbb{Z}_7)^{\times}$ .

Ця мультиплікативна група має два генератори ${[3],[5]}$ , також відомих як примітивні корені. Використаємо $[5]$ як генератор, тобто породимо кожен елемент $(\mathbb{Z}_7)^{\times}$ за допомогою послідовних цілих степенів 5.

#Generate elements of (Z_7)^{x} using generator [5].
g = 5
p = 7
print(f"Using generator {g}")
for k in range(3*p):
    print(f"{g}**{k} mod {p} ≡ {(g**k)%7}")

Ми бачимо, що в арифметиці за модулем 7 піднесення 5 до послідовних цілих степенів дає кожен елемент $(\mathbb{Z}_7)^{\times}$ рівно один раз, після чого цикл повторюється нескінченно з періодом $p-1 =6$ .

Отже, DLP на $(\mathbb{Z}_7)^{\times}$ з генератором [5] формулюється так:

$\mathrm{Given}~h \in (\mathbb{Z}_7)^{\times} \mathrm{, find~} k \mathrm{~such~that~} 5^{k} \equiv h~(mod~7)$ .

З виводу наведеної вище комірки Python бачимо, що:

$h = 2 \implies k=4 \mathrm{~or~} 4 = log_5(2) (mod~7)$

$h = 6 \implies k=3 \mathrm{~or~} 3 = log_5(6) (mod~7)$

У звичайній арифметиці дійсних чисел піднесення до степеня є монотонною функцією, і знаходження логарифма будь-якого числа до будь-якої основи є обчислювально простим. На відміну від цього, як очевидно з простого прикладу $(\mathbb{Z}_7)^{\times}$ вище, модульне піднесення до степеня є немонотонним, і хоча воно є periodичним з period $p-1$ , в іншому воно є дуже нетривіальним. Тому обчислення оберненої до нього функції — дискретного логарифма — виявляється неефективним для великих $p$ на класичних комп'ютерах.

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

DLP можна розширити на циклічні підгрупи таким чином:

Розглянемо $(\mathbb{Z}_p)^{\times}$ , визначену вище, та елемент $g \in (\mathbb{Z}_p)^{\times}$ простого порядку $r$ , тобто $g^r \equiv 1 (~mod~p)$ .
Множина цілочисельних степенів $g$ : $\{g^k~(mod~p) | 1 \le k \le r\} = \langle g \rangle$ є циклічною підгрупою $(\mathbb{Z}_p)^{\times}$ з порядком групи $r$ .
DLP можна задати на $\langle g \rangle$ , обравши $h \in \\langle g \rangle$ і поставивши задачу знайти $1 \le a \le r$ таке, що $g^a~(mod~p) = h$

Обмін ключами Діффі-Геллмана

У 1976 році Вітфілд Діффі та Мартін Геллман запропонували протокол обміну ключами для створення спільного секретного ключа через незахищені канали зв'язку. Цей секретний ключ сторони, що його спільно використовують, могли б застосовувати для симетричного шифрування. Алгоритм спирається на DLP.

Рисунок 1. Обмін ключами Діффі-Геллмана

Рисунок 1. Обмін ключами Діффі-Геллмана

Математичні деталі обміну ключами Діффі-Геллмана

Якщо двома сторонами є Аліса і Боб, протокол працює так:

Спершу Аліса і Боб домовляються про велике просте число $p$ і примітивний корінь або генератор $a$ .
Потім Аліса випадково обирає секретний показник $k_A$ з $1 \le k_A \le p-2$ і обчислює $h_A = a^{k_A}~(mod~p)$ . $k_A, h_A$ — це відповідно приватний і публічний ключі Аліси.
Далі Боб випадково обирає секретний показник $k_B$ з $1 \le k_B \le p-2$ і обчислює $h_B = a^{k_B}~(mod~p)$ . $k_B, h_B$ — це відповідно приватний і публічний ключі Боба.
Потім Аліса надсилає Бобу $h_A$ , а Боб надсилає Алісі $h_B$ через надійний, але не обов'язково захищений канал.
Після цього Аліса використовує отриманий $h_B$ , щоб обчислити спільний секретний ключ $\kappa = h_B^{k_A}~(mod~p)$ .
Нарешті, Боб тим часом використовує отриманий $h_A$ , щоб обчислити спільний секретний ключ $\kappa = h_A^{k_B}~(mod~p)$ .

Завдяки цьому протоколу:

Аліса і Боб гарантовано отримають однаковий секретний ключ $\kappa$ , оскільки $h_B^{k_A}~(mod~p) = (a^{k_B})^{k_A}~(mod~p) = a^{k_A k_B}~(mod~p) = (a^{k_A})^{k_B}~(mod~p) = h_A^{k_B}~(mod~p)$ .
Третя сторона, що перехопить $h_A$ або $h_B$ , не зможе побудувати секретний ключ $\kappa$ , оскільки не має доступу до $k_B$ або $k_A$ відповідно.
Витягти $k_A$ або $k_B$ з публічної інформації $a$ , $p$ , $h_A$ та $h_B$ обчислювально складно, оскільки це рівносильно розв'язанню DLP на $(\mathbb{Z}_p)^{\times}$ .

Ілюстрація протоколу Діффі-Геллмана на Python

Розглянемо простий приклад протоколу DH на Python із використанням малих простих чисел:

примітка

У цьому розділі математичні обчислення показані детально як частина коду Python

Крок 1: Аліса і Боб домовляються про просте число $p$ і примітивний корінь $a$ . Оберімо $p=11, a=7$ .

# Step 1: Choose a prime `p` and a primitive root `a`
p = 11
a = 7

print(f"prime: {p}")
print(f"primitive root: {a}")

Кроки 2, 3: Аліса обирає секретний показник $k_A$ і обчислює $h_A = a^{k_A}~(mod~p)$ . Аналогічно Боб обирає секретний показник $k_B$ і обчислює $h_B = a^{k_B}~(mod~p)$ .

k_A = 4  # Alice's private key
h_A = (a ** (k_A)) % p  # Alice's public key

print(f"Alice's private key is {k_A} and public key is {h_A}")

k_B = 8  # Bob's private key
h_B = (a ** (k_B)) % p  # Bob's public key

print(f"Bob's private key is {k_B} and public key is {h_B}")

Крок 4: Обидві сторони оголошують свої публічні ключі $h_A$ та $h_B$ .

Кроки 5, 6: Кожна сторона комбінує свій приватний ключ із публічним ключем іншої сторони, щоб отримати спільний секретний ключ.

secret_key_alice = h_B**k_A % p
secret_key_bob = h_A**k_B % p
assert secret_key_alice == secret_key_bob
print(f"The shared secret key is: {secret_key_bob}")

Тепер Аліса і Боб можуть використовувати спільний секретний ключ для симетричного шифрування.

Безпека обміну ключами Діффі-Геллмана

Як зазначалось вище, безпека DH залежить від обчислювальної складності розв'язання DLP із великими простими числами $p$ . У типових застосуваннях NIST рекомендує 2048- або 3072-бітні прості числа для обміну ключами DH, що вважається достатньо безпечним проти спроб розв'язати DLP за допомогою класичних комп'ютерів.

Атаки «людина посередині» (MITM): Те, що DH є інтерактивною схемою, де спільний секрет залежить від поєднання приватного ключа однієї сторони з публічним ключем іншої, робить його вразливим до так званої атаки «людина посередині» (MITM).

Математичні деталі безпеки DH та атак MITM

У цьому сценарії третя сторона — скажімо, Єва — перехоплює публічні ключі $h_A, h_B$ під час передачі і підміняє кожен із них на свій власний публічний ключ $h_E$ , перш ніж передати їх далі — Бобу та Алісі відповідно.

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

Оскільки $h_E$ використовувався для створення спільного секрету Аліси (Боба), відкритий текст, зашифрований Алісою (Бобом), може бути розшифрований Євою.

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

Алгоритм цифрового підпису (DSA)

Хоча загальні криптосистеми, як-от RSA, забезпечують функціональність цифрового підпису, у 1994 році NIST прийняв спеціалізовану схему підпису на основі модульного піднесення до степеня та задачі дискретного логарифму як федеральний стандарт цифрових підписів. Ця схема, відома просто як Алгоритм цифрового підпису (DSA), передбачає чотири окремі фази:

Генерація ключів:

Ключі DSA генеруються з:
- 2 простих чисел, що відповідають певним правилам
  - $p$ — зазвичай 256 біт (позначимо цю довжину $N$ )
  - $q$ — зазвичай 3072 біти (позначимо цю довжину $L$ )
- Криптографічної хеш-функції, яка перетворює рядки довжини $L$ на рядки довжини $N$
- Додаткового параметра $g$ (дивись деталі нижче)
З цього ми обираємо випадкове число $x$ як приватний ключ і можемо обчислити публічний ключ $y$
Математичні деталі генерації ключів
- Генерація параметрів: Математично DSA залучає циклічну підгрупу $(\mathbb{Z}_p)^{\times}$ , породжену елементом $g$ простого порядку q < p. Тому перший крок DSA — вибір двох простих чисел p, q для побудови необхідних математичних структур.
  
  Обери $N$ -бітне просте число $q$ .
  
  Обери $L$ -бітне просте число $p$ таке, що $p-1$ кратне $q$ . Вибір $p$ визначає групу $(\mathbb{Z}_p)^{\times}$
  
  Вибери випадкове ціле число $1 < h < p-1$ і обчисли $g = h^{(p-1)/q}~mod~p$ . Якщо $g=1$ (що трапляється рідко), спробуй інше h.
  
  Перевір, що $g^q~mod~p = 1$ . Таким чином g є генератором циклічної підгрупи $\langle g \rangle$ групи $(\mathbb{Z}_p)^{\times}$ простого порядку q.
  
  Параметри $(q, p, g)$ визначають екземпляр алгоритму і є публічною інформацією. Зазвичай у реальних застосуваннях $N \sim 256$ та $L \sim 3072$ .
  
  Протокол також потребує криптографічної хеш-функції $H : \{0,1\}^L \rightarrow \{0, 1\}^N$ , яка відображає бінарні $L$ -бітні рядки на $N$ -бітні рядки, наприклад SHA-256.
- Генерація пари ключів: Підписувач має згенерувати пару ключів зі свого боку.
  
  Обери випадкове секретне ціле число $x \in \{1,2...q-1\}$ . $x$ — це приватний ключ.
  
  Обчисли $y = g^{x}~mod~p$ . $y$ — публічний ключ підписувача.
Розповсюдження ключів:

Наступна інформація передається всім, хто бажає перевірити підпис:
- Використані параметри $(p,q,g)$ , які описують алгоритм
- Хеш-функція $H$
- Публічний ключ $y$
Підписання:
- Підписувач тепер може підписати повідомлення $m$ . Результуючий підпис — це $(r,s)$
- Повідомлення та підпис обидва передаються отримувачу
Математичні деталі підписання повідомлення
Підписувач підписує повідомлення $m$ так:
- Обери випадкове секретне ціле число k з $\{1,2...q-1\}$
- Обчисли $r = (g^k~mod~p)~mod~q$ . У рідкісному випадку, коли $r=0$ , спробуй інше випадкове k.
- Обчисли $s = (k^{-1} (H(m) + xr))~mod~q$ . У рідкісному випадку, якщо $s=0$ , спробуй інше випадкове k.
- Підпис — це кортеж $(r, s)$ .
- Підписувач передає повідомлення $m$ разом із підписом $(r,s)$ верифікатору.
Оскільки і $r$ , і $s$ є цілими числами за модулем $q$ , розмір підпису має порядок $N$ біт, а не довших $L$ біт.
Верифікація:

Отримувач тепер хоче перевірити автентичність відправника. Він має доступ до публічної інформації $(q, p, g, H, y, (r,s), m)$ Він може виконати обчислення, яке доводить, що відправник мав доступ до приватного ключа $x$

і прагне встановити, що підписувач — це хтось із доступом до приватного ключа $x$ .
Математичні деталі схеми верифікації DSA
- Перевір, що $0 \lt r \lt q$ і $0 \lt s \lt q$ , тобто $r, s$ є дійсними цілими числами за модулем~q.
- Обчисли $w = s^{-1}~mod~q$ .
- Обчисли $u_1 = H(m)w~mod~q$ .
- Обчисли $u_2 = rw~mod~q$ .
- Обчисли $v = (g^{u_1}y^{u_2}~mod~p)~mod~q$ .
- Підпис є вірним, якщо $v = r$ .
Коректність алгоритму DSA для легітимних підписів легко демонструється так:
- На стороні підписувача: $s = (k^{-1} (H(m) + xr))~mod~q \implies k = ((H(m) + xr)s^{-1})~mod~q$
- Розглядаючи праву частину останньої рівності, верифікатор може обчислити $s^{-1}, H(m)$ , оскільки $s, q, m, H$ є публічною інформацією.
- Таким чином, верифікатор обчислює $w = s^{-1}~mod~q$ і $u_1 = H(m)w~mod~q = H(m)s^{-1}~mod~q$ .
- Верифікатор також обчислює $u_2 = rw~mod~q = rs^{-1}~mod~q$ , оскільки $r$ теж є публічним.
- Зауваж, що $k = (u_1 + xu_2)~mod~q$ .
- Проте верифікатор не має доступу до $x$ , оскільки це приватний ключ підписувача, тож $k$ не можна обчислити безпосередньо. - Схема натомість спирається на те, що навіть якщо верифікатор не може обчислити $k$ , при легітимному підписувачеві верифікатор має змогу повторно обчислити $(g^k~mod~p)~mod~q = r$ за допомогою публічного ключа підписувача $y = g^{x}~mod~p$ .
- Отже, верифікатор обчислює $v = (g^{u_1}y^{u_2}~mod~p)~mod~q = (g^{u_1}g^{xu_2}~mod~p)mod~q = (g^{u_1+xu_2}~mod~p)mod~q = (g^k~mod~p)mod~q$ .
- Остання рівність випливає з того, що $g$ має порядок $q$ , і доводить $v = r$ для дійсних підписів.

Ілюстрація DSA на Python

У цьому прикладі ми використаємо малі прості числа, щоб проілюструвати процес DSA в сценарії, де Аліса надсилає підписане повідомлення Бобу. У цьому прикладі ми будемо використовувати малі цілі числа. У реальному сценарії застосовувалися б значно більші прості числа порядку 2048–3072 біт.

примітка

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

Починаємо з імпортування необхідних бібліотек і вибору параметрів. Цілочисельні параметри $p$ , $q$ , $g$ є публічною інформацією і задовольняють такі правила:

$p$ , $q$ — обидва прості
$(p-1) \mod\ q = 0$
$g \ge 2$
$g \le (p-2)$
$g^{(p-1)/q} \mod\ p \neq 1$

from random import randint

# parameter generation: select the primes q, p and generator g:
# EXPERIMENT with the values, they must meet certain rules
# this example code does not verify p,q are prime

q = 11
p = 23
g = 4

assert (p - 1) % q == 0
assert g >= 2
assert g <= (p - 2)
assert (pow(g, (p - 1) / q) % p) != 1

print(f"Public information is good: q={p}, p={q}, g={g}")

Далі підписувач, Аліса, генерує свій приватний ключ.

Приватний ключ, k (alice-private-key у коді Python) має задовольняти:

$k \ge 2$
$k \le (q-1)$

# Alice chooses an integer randomly from {2..q-1}
# EXPERIMENT with the values

alice_private_key = randint(2, q - 1)
# alice_private_key =

assert alice_private_key >= 2
assert alice_private_key <= (q - 1)

print(f"Alice's private key is {alice_private_key}")

Аліса зберігає свій приватний ключ у таємниці.

Далі Аліса обчислює свій публічний ключ за допомогою модульного піднесення до степеня. Інвертування цього кроку для відновлення приватного ключа є прикладом DLP, тому його важко обчислити на класичних комп'ютерах при використанні великих простих чисел.

З математичного пояснення вище ми знаємо, що це можна обчислити за формулою:

$y = g^{x} \mod\ p$

alice_public_key = pow(g, alice_private_key, p)
# Alternatively can use (g ** alice_private_key) % p

print(f"Alice's public key is {alice_public_key}")

Як завжди, Аліса робить свій публічний ключ доступним через не обов'язково секретний канал.

Тепер Аліса може підписати повідомлення.

Для схеми цифрового підпису нам потрібно згенерувати хеш $H(m)$ повідомлення $m$ , яке підписується.

Припустімо, що Аліса і Боб домовились використовувати певний алгоритм хешування з довжиною хешу $N$ , рівною кількості бітів у $q$ . У цьому простому прикладі ми обмежимо виходи нашої тестової хеш-функції числом $q$ . Тут хеш-функція є тривіальною — вона просто генерує випадкове ціле число.

hash_dict = {}

def mock_hash_func(input_message):
    print(input_message)
    if input_message not in hash_dict:
        hash_dict[input_message] = randint(1, q)
    return hash_dict[input_message]

alice_message = "Inspection tomorrow!"
alice_hash = mock_hash_func(alice_message)  # In reality, you'd use a hash function
print(f"Alice's message hash is: {alice_hash}")

Далі Алісі потрібно згенерувати випадкове секретне число $k$ для кожного повідомлення, а також його мультиплікативне обернене за модулем $q$ для обчислення підпису.

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

# brute-force implementation to find modular inverse
def modular_inverse(k, q):
    for i in range(0, q):
        if (k * i) % q == 1:
            return i
    print(f"error! no inverse found! for {k},{q}")
    return 0

# Let's compare this algorithm with the standard python 'pow' function

n1 = modular_inverse(3, 7)
n2 = modular_inverse(4, 11)
n3 = modular_inverse(7, 5)
m1 = pow(3, -1, 7)
m2 = pow(4, -1, 11)
m3 = pow(7, -1, 5)

assert n1 == m1
assert n2 == m2
# assert(n3==m3)

print(f"modular_inverse(3,7) = {m1}")
print(f"modular_inverse(4,11) = {m2}")
print(f"modular_inverse(7,5) = {m3}")

# Some numbers don't have modular inverses - our function throws an error
n4 = modular_inverse(2, 6)

# The python library will throw an exception, which must be caught
if math.gcd(2, 6) == 1:
    m4 = pow(2, -1, 6)
else:
    print("Exception from pow() - no modular inverse found!")

Тепер Аліса може обчислити підпис.

$r = (g^{k} \mod p) \mod\ q$
$s = (k^{-1} (H(m) + xr)) \mod q$

Зауваж, що існують певні умови, за яких нам потрібно обрати інше значення $k$ у випадку, коли або $r$ , або $s$ обчислюються рівними $0$ . У такому разі ми генеруємо нове значення і повторюємо.

# Start an infinite loop; we will 'break' out of it once a valid signature is found.
while True:
    k = randint(1, q - 1)  # Should be different for every message
    print("Using random k =", k)

    r = pow(g, k, p) % q
    # If r is 0, the value is invalid. Try again with a new k.
    if r == 0:
        print(f"{k} is not a good random value to use to calculate r. Trying another k")
        continue

    s = (pow(k, -1, q) * (alice_hash + alice_private_key * r)) % q
    # If s is 0, the value is also invalid. Try again with a new k.
    if s == 0:
        print(f"{k} is not a good random value to use to calculate s. Trying another k")
        continue

    # If we've reached this point, both r and s are valid. Break the loop.
    signature = (r, s)
    print(f"Alice's signature is : {(r,s)}")
    break

# After the loop, the valid r and s values can be used here.
# print(f"Generated Signature -> r: {r}, s: {s}")

Аліса оголошує повідомлення та свій підпис отримувачу або верифікатору — Бобу.

Боб раніше отримав публічний ключ Аліси і тепер може перевірити підпис, щоб автентифікувати її повідомлення.

Для цього він виконує кілька перевірок, а потім повторно генерує хеш оголошеного Алісою повідомлення та обчислює допоміжні величини $w, u_1, u_2$ і $v$ .

$0 < r < q$
$0 < s < q$
$w = s^{-1} \mod\ q$
$u_{1} = H(m) . w \mod\ q$
$u_{2} = r . w \mod\ q$
$v = (g^{u1}y^{u2} \mod\ p) \mod\ q$

Нарешті, Боб перевіряє, чи рівне $v$ значенню $r$ . Якщо вони рівні, підпис вважається підтвердженим.

# Bob re-generates message hash using Alice's broadcast message
bob_hash = mock_hash_func(alice_message)

# Bob computes auxiliary quantities w (using modular inverse), u1, u2 and v
w = (pow(s, -1, q)) % q
u1 = (bob_hash * w) % q
u2 = (r * w) % q
v = ((g**u1 * alice_public_key**u2) % p) % q

if v == r:
    print("Signature is valid!")
else:
    print("Signature is invalid!")

Безпека DSA

На класичних комп'ютерах безпека DSA може визначатися кількома факторами:

Розмір ключа: Як завжди, розмір ключа забезпечує базовий захист від атак перебором. Сучасні застосування, що використовують DSA, використовують ключі розміром щонайменше 2048 біт.
Якість $k$ : У DSA кожен підпис потребує унікального, випадкового та секретного значення $k$ (дивись вище). Унікальність, ентропія та секретність $k$ є критично важливими, і слабкість будь-якого з цих аспектів може призвести до компрометації приватного ключа $x$ . Генератори випадкових чисел, що використовуються для генерації $k$ , самі по собі мають бути захищеними.
Стійкість хеш-функції: Оскільки DSA використовує хеш-функцію як частину процесу генерації та верифікації підпису, слабка хеш-функція може поставити під загрозу безпеку цифрового підпису. Наприклад, використання SHA-1 з DSA є застарілим, і рекомендується SHA-2 або вища версія.

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

Автентифікований обмін ключами з Діффі-Геллманом і DSA

Сучасні протоколи мережевої безпеки, такі як Transport Layer Security (TLS) та багато інших, передбачають поєднання функціональності обміну ключами та автентифікації. У контексті Діффі-Геллмана автентифікація необхідна для захисту від атак MITM. У наступних клітинках коду ми ілюструємо приклад, де Аліса і Боб виконують автентифікований обмін ключами, поєднуючи протоколи Діффі-Геллмана і DSA. Для цього ми будемо використовувати бібліотеку Python cryptography.

Рисунок 2. Автентифікований обмін ключами з Діффі-Геллманом і DSA

Рисунок 2. Автентифікований обмін ключами з Діффі-Геллманом і DSA Спершу Аліса і Боб домовляються про набір параметрів DH і генерують набір пар публічно-приватних ключів DH.

# import necessary library modules
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import dh, dsa

# Generate DH parameters
parameters = dh.generate_parameters(generator=2, key_size=2048)

# Generate Alice's DH private key and public key
alice_dh_private_key = parameters.generate_private_key()
alice_dh_public_key = alice_dh_private_key.public_key()

# Generate Bob's DH private key and public key
bob_dh_private_key = parameters.generate_private_key()
bob_dh_public_key = bob_dh_private_key.public_key()

print("Public and private keys generated for Bob and Alice")

Публічні ключі DH оголошуються. Далі і Аліса, і Боб кожен окремо генерують пару ключів для використання з DSA. Ці ключі, своєю чергою, будуть використовуватися для підписання публічних ключів DH, якими обмінюватимуться сторони.

# Generate DSA keys for Alice and Bob
alice_dsa_private_key = dsa.generate_private_key(key_size=2048)
alice_dsa_public_key = alice_dsa_private_key.public_key()
bob_dsa_private_key = dsa.generate_private_key(key_size=2048)
bob_dsa_public_key = bob_dsa_private_key.public_key()

print("Additional key pair generated for signing")

Аліса підписує свій публічний ключ DH за допомогою свого приватного ключа DSA.

# Alice signs
alice_public_bytes = alice_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
alice_signature = alice_dsa_private_key.sign(alice_public_bytes, hashes.SHA256())

print("Alice signed public key")

Аналогічно, Боб підписує свій публічний ключ DH за допомогою свого приватного ключа DSA.

bob_public_bytes = bob_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
bob_signature = bob_dsa_private_key.sign(bob_public_bytes, hashes.SHA256())

print("Bob signed public key")

Публічні ключі DH та відповідні підписи тепер оголошуються обома — Алісою і Бобом. Отримавши публічний ключ і підпис контрагента, кожна сторона перевіряє дійсність підпису. Таким чином можна запобігти атаці MITM, адже Аліса, наприклад, знає, що публічний ключ DH Боба дійсно підписаний Бобом, і навпаки.

# Alice and Bob verify each other's DH public keys using DSA public keys
# An InvalidSignature exception will occur if they are not valid
alice_dsa_public_key.verify(alice_signature, alice_public_bytes, hashes.SHA256())
bob_dsa_public_key.verify(bob_signature, bob_public_bytes, hashes.SHA256())

print("Signatures are valid")

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

# Perform key exchange
alice_shared_key = alice_dh_private_key.exchange(bob_dh_public_key)
bob_shared_key = bob_dh_private_key.exchange(alice_dh_public_key)

print("Shared secrets generated")

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

# Derive a shared symmetric key using key-stretching
def derive_key(shared_key):
    return HKDF(
        algorithm=hashes.SHA256(),
        length=32,
        salt=None,
        info=None,
    ).derive(shared_key)

alice_symmetric_key = derive_key(alice_shared_key)
bob_symmetric_key = derive_key(bob_shared_key)

assert alice_symmetric_key == bob_symmetric_key
print("Keys checked to be the same")

Злом Діффі-Геллмана та DSA

Протоколи Діффі-Геллмана (DH) та DSA передбачають генерацію відкритих ключів виду $y = g^{x}~mod~p$ , де закритий ключ $x$ є дискретним логарифмом.

Зловмисник, який зможе розв'язати задачу DLP, може розкрити закритий ключ однієї зі сторін і, поєднавши його з відкритим ключем другої сторони, отримати доступ до спільного секрету. У випадку DSA зловмисник, який розв'яже DLP, може відновити закритий ключ підписувача, що підважує саму основу цифрового підпису.

На класичних обчислювальних системах вважається, що DLP не має поліноміального розв'язку за часом. Проте, як показав Пітер Шор у своїй оригінальній статті 1994 року, алгоритм Шора також розв'язує DLP за поліноміальний час на квантових комп'ютерах.

Алгоритм Шора та задача дискретного логарифму

Алгоритм Шора здатний розв'язати задачу дискретного логарифму за поліноміальний час. Його ефективність досягається насамперед завдяки використанню квантових алгоритмів, які вміють знаходити період функції, що залежить від вхідних даних задачі, — а потім цей результат поєднується зі звичайнішими операціями.

Математичні деталі алгоритму Шора

Алгоритм Шора забезпечує ефективний розв'язок DLP, відображаючи її на загальнішу задачу теорії груп, відому як задача прихованої підгрупи (HSP).

У HSP задається алгебраїчна група $G$ і функція $f: G \rightarrow X$ з $G$ у деяку множину $X$ така, що $f$ є сталою на кожному суміжному класі деякої підгрупи $H$ групи $G$ (і різною на різних суміжних класах). Тоді задача полягає у визначенні $H$ . Відомо, що квантові комп'ютери можуть розв'язати HSP на скінченних абелевих групах за час, поліноміальний відносно $log~|G|$ , де $|G|$ — порядок групи.

У випадку цілочисельного DLP, розглянутого в цьому уроці, відображення на HSP виглядає так:

Нехай $p$ — просте число і розглянемо DLP виду $y = g^r~mod~p$ , де $g$ — генератор $(\mathbb{Z}_p)^{\times}$ . Оскільки $g^{p-1} \equiv 1~mod~p$ , $g$ має порядок $p-1$ .
Оберемо $G = \mathbb{Z}_{p-1} \times \mathbb{Z}_{p-1}$ , де $\mathbb{Z}_{p-1}$ — група цілих чисел за модулем $(p-1)$ .
Оберемо $f : G \rightarrow (\mathbb{Z}_p)^{\times}$ вигляду $f(a, b) = g^a y^{-b}~mod~p \equiv g^{a-rb}~mod~p$ .
Ядро $f$ — це підгрупа $H_0 = \langle (r, 1) \rangle = \{(a,b) \in G | f(a,b) \equiv 1~mod~p\} = \{ (a, b) \in G | a - rb \equiv 0~mod~(p-1)\}$ .
$f$ є сталою на суміжних класах $(\delta, 0) + H_0$ і «приховує» підгрупу $H_0$ , формулюючи HSP.

З огляду на вищесказане, квантовий алгоритм Шора для цілочисельного DLP використовує квантовий оракул для обчислення функції $f$ на стані, що представляє рівномірну суперпозицію над $G$ , а потім застосовує квантове перетворення Фур'є та вимірювання з оцінкою фази для отримання квантових станів, що дають змогу ідентифікувати генератор $(r, 1)$ підгрупи $H_0$ . Із цього можна витягти $r$ — шуканий дискретний логарифм.

Оригінальна стаття Шора містить докладний опис алгоритму.

Криптографія на еліптичних кривих

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

Базові принципи криптографії на еліптичних кривих

Еліптична крива зазвичай має вигляд $y^2 = x^3 + ax + b$ і має кілька цікавих властивостей.

Вона симетрична відносно горизонтальної осі. Тобто для будь-якої точки $(x,y)$ на кривій її відображення $(x,-y)$ також лежить на кривій.
Будь-яка невертикальна пряма може перетнути криву не більше ніж у трьох точках.

Figure 1. Operations of addition and point doubling on an elliptic curve. Facet 1 defines P + Q = -R. Facet 2 illustrates point doubling 2Q = -P. Facet 3 defines the additive inverse of a point as its reflection about the x-axis i.e, P = -Q

Рисунок 1. Операції додавання та подвоєння точки на еліптичній кривій. Грань 1 визначає P + Q = -R. Грань 2 ілюструє подвоєння точки 2Q = -P. Грань 3 визначає адитивний обернений елемент точки як її відображення відносно осі x, тобто P = -Q

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

Математичні принципи криптографії на еліптичних кривих

Еліптична крива над алгебраїчним полем $K$ визначається математичним рівнянням, як правило, у формі $y^2 = x^3 + ax + b$ з коефіцієнтами $a, b \in K$ і описує точки $(x, y) \in K \otimes K$ з додатковою умовою, що крива не має кутів і самоперетинів.

Властивості еліптичних кривих дозволяють визначити операції «додавання» та «скалярного множення» над точками кривої.

Додавання: якщо $P$ і $Q$ — дві точки на еліптичній кривій, то $P + Q$ визначає унікальну третю точку, яка знаходиться так: проведемо пряму через $P$ і $Q$ і знайдемо третю точку $R$ , в якій пряма знову перетинає криву. Тоді визначаємо $P + Q = −R$ — точку, протилежну $R$ , відображену через вісь $x$ (див. рисунок нижче). Коли пряма через $P, Q$ не перетинає криву в жодній скінченній точці $(x, y)$ , кажуть, що вона перетинає криву в точці на нескінченності $\mathbf{O}$ .

Додавання на еліптичній кривій задовольняє алгебраїчні властивості групи, де точка на нескінченності є адитивним нейтральним елементом.

Подвоєння та скалярне множення: операція подвоєння точки, що відповідає скалярному множенню на $2$ , отримується підстановкою $P = Q$ в операції додавання і графічно відповідає дотичній прямій у точці $P$ . Загальне скалярне множення на ціле число $n$ , визначене як $nP = P + P + ...~n$ разів, отримується повторним подвоєнням та додаванням.

Задача дискретного логарифму на еліптичних кривих

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

Операція скалярного множення на еліптичних кривих дозволяє сформулювати задачу дискретного логарифму на еліптичних кривих:

Задано точки $P, Q$ на еліптичній кривій такі, що $Q = nP$ . Визначити $n$ .

Ця задача вважається нерозв'язною на класичних комп'ютерах для великих $n$ і є основою криптографічної стійкості.

Математичний опис ECDLP

Криптографія на еліптичних кривих переважно ґрунтується на ECDLP, сформульованій на певних алгебраїчних скінченних полях. У 1999 році NIST рекомендував десять скінченних полів для використання в ECC, а саме:

П'ять простих полів $\mathbb {F} _{p}$ для простих $p$ розміром $\{192, 224, 256, 384, 521\}$ біт.
П'ять двійкових полів $\mathbb {F} _{2^{n}}$ для $n \in \{163, 233, 283, 409, 571\}$ .

З урахуванням вищесказаного, асиметрична криптосистема на основі ECC для випадку простих полів може бути задана так:

Обрати $p$ зі списку рекомендованих NIST значень, щоб задати $\mathbb {F} _{p}$ .
Вибрати параметри $a, b$ еліптичної кривої.
Обрати базову точку $G$ , яка «породжує» циклічну підгрупу на кривій порядку $n$ , тобто найменше ціле число таке, що $nG = \mathbf{O}$ .
Обчислити кофактор $h = |E(\mathbb {F} _{p})|/n$ , де $|E(\mathbb {F} _{p})|$ — кількість точок на кривій. $h$ зазвичай є малим цілим числом.
Параметри домену $(p, a, b, G, n, h)$ дозволяють задати асиметричні ключі таким чином:
- Закритий ключ — це випадково обране ціле число $d$ з тією ж кількістю біт, що й просте $p$ . Його потрібно зберігати в таємниці.
- Відкритий ключ — результат «множення» базової точки $G$ на закритий ключ $d$ . Зазвичай позначається як $Q = dG$ .

Відновлення $d$ рівнозначне розв'язанню ECDLP, що вважається нерозв'язним для великих $d$ . Тому ECDLP є основою схем обміну ключами та цифрових підписів у прямій аналогії зі схемами Діффі-Геллмана та DSA, визначеними над $(\mathbb{Z}_p)^{\times}$ , які розглядалися раніше.

Обмін ключами з використанням ECC

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

Хоча виконати додавання точок на еліптичній кривій і отримати відкритий ключ із закритого відносно нескладно, зворотний процес — отримання закритого ключа з відкритого — є обчислювально неможливим. Саме ця «одностороння» поведінка забезпечує безпеку обміну ключами ECDH.

Нижче наведено приклад того, як можна виконати обмін ключами ECDH за допомогою Python та бібліотеки cryptography.

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import hashes

# Each party generates a private key
private_key1 = ec.generate_private_key(ec.SECP384R1())
private_key2 = ec.generate_private_key(ec.SECP384R1())

# They exchange public keys
public_key1 = private_key1.public_key()
public_key2 = private_key2.public_key()

# Each party uses their own private key and the other party's public key
# to derive the shared secret
shared_key1 = private_key1.exchange(ec.ECDH(), public_key2)
shared_key2 = private_key2.exchange(ec.ECDH(), public_key1)

# The shared secrets are the same
assert shared_key1 == shared_key2
print("Keys checked to be the same")

Цифрові підписи з використанням ECC

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

Нижче наведено приклад простої транзакції підписання та перевірки з використанням ECDSA у Python і cryptography.

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import ec

# Generate a private key for use in the signature
private_key = ec.generate_private_key(ec.SECP384R1())

message = b"A message to be signed"

# Sign the message
signature = private_key.sign(message, ec.ECDSA(hashes.SHA256()))

# Anyone can verify the signature with the public key
public_key = private_key.public_key()

def check_ecdsa_signature(public_key, signature, message):
    try:
        public_key.verify(signature, message, ec.ECDSA(hashes.SHA256()))
        return True
    except InvalidSignature:
        return False

if check_ecdsa_signature(public_key, signature, message):
    print("The signature is valid.")
else:
    print("The signature is invalid.")

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

Злом ECDH та ECDSA

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

Підсумок

У цьому уроці ми почали з розгляду основних характеристик асиметричної ключової криптографії (AKC) та обговорили базові міркування безпеки, що лежать в основі асиметричних криптосистем. Зокрема, ми представили два головних застосування AKC — обмін ключами та цифрові підписи, — які є невід'ємними складовими сучасних інтернет-комунікацій.

Потім ми розглянули криптосистему RSA, яка з 1970-х років виявилася надзвичайно цінною для захисту сучасних цифрових комунікацій, забезпечуючи обмін ключами та цифрові підписи в простій і універсальній системі. Криптографічна стійкість RSA щодо класичних обчислень ґрунтується на складності розкладання великих цілих чисел на множники та потребує розмірів ключів від 2048 біт, щоб цілі числа, які використовуються в практичних застосуваннях, були достатньо великими для опору факторизації.

Далі ми розглянули обмін ключами Діффі-Геллмана (DH) та алгоритм цифрового підпису (DSA). Безпека цих схем ґрунтується на задачі цілочисельного дискретного логарифму (DLP): закритий ключ обчислювально важко витягти з відкритого, і на класичних комп'ютерах поліноміального алгоритму для цього немає. Використання випадкових і унікальних ключів забезпечує додатковий захист від атак. Як цілочисельний варіант на скінченних полях, так і варіант на еліптичних кривих протоколів DH та DSA наразі широко використовуються в багатьох сучасних протоколах цифрових комунікацій, таких як TLS, SSH тощо.

Наостанок ми розглянули криптографію на еліптичних кривих. Завдяки ефективному розміру ключів та міцним властивостям безпеки вона на сьогодні є чудовим вибором для багатьох криптографічних застосувань — від обміну ключами до цифрових підписів.

Усі ці алгоритми є вразливими до атак квантових алгоритмів, оскільки можна розробити методи розв'язання математичних задач, що були покладені в їх основу. Одним із таких прикладів є алгоритм Шора. Тому їх необхідно замінити квантово-безпечними асиметричними криптосистемами, більш стійкими до атак із застосуванням квантових комп'ютерів, а також такими, що залишаються надійними проти класичних алгоритмів. Математичні задачі, на яких вони базуються, можуть бути ефективно розв'язані квантовими комп'ютерами — що зумовлює необхідність розробки квантово-безпечних асиметричних криптосистем, здатних протистояти квантовим атакам, зберігаючи при цьому класичну безпеку.

Вступ до асиметричної криптографії з відкритим ключем​

Обмін ключами з асиметричною криптографією​

Інтерактивний обмін ключами​

Неінтерактивний обмін ключами​

Цифрові підписи з асиметричною криптографією​

Спеціалізовані алгоритми цифрового підпису​

Схеми цифрового підпису з використанням загальних криптосистем​

Застосування асиметричної криптографії​

Безпека асиметричної криптографії​

Ризики безпеки для асиметричної криптографії​

RSA​

Алгоритм RSA​

Ілюстрація RSA на Python​

Генерація ключів RSA​

Обмін симетричними ключами з RSA​

Приклад обміну ключами на основі доповнення (padding) на Python​

Симуляція механізму інкапсуляції ключів за допомогою RSA на Python​

Цифрові підписи з RSA​

Злом RSA​

Класичні обчислення та RSA​

Квантовий алгоритм Шора та RSA​

Приклад на Python, що демонструє злом RSA-шифрування​

Обмін ключами Діффі–Хеллмана та алгоритм цифрового підпису​

Задача дискретного логарифма​

Математичні деталі задачі дискретного логарифма​

Обмін ключами Діффі-Геллмана​

Ілюстрація протоколу Діффі-Геллмана на Python​

Безпека обміну ключами Діффі-Геллмана​

Алгоритм цифрового підпису (DSA)​

Ілюстрація DSA на Python​

Безпека DSA​

Автентифікований обмін ключами з Діффі-Геллманом і DSA​

Злом Діффі-Геллмана та DSA​

Алгоритм Шора та задача дискретного логарифму​

Криптографія на еліптичних кривих​

Базові принципи криптографії на еліптичних кривих​

Задача дискретного логарифму на еліптичних кривих​

Обмін ключами з використанням ECC​

Цифрові підписи з використанням ECC​

Злом ECDH та ECDSA​

Підсумок​

Вступ до асиметричної криптографії з відкритим ключем

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

Інтерактивний обмін ключами

Неінтерактивний обмін ключами

Цифрові підписи з асиметричною криптографією

Спеціалізовані алгоритми цифрового підпису

Схеми цифрового підпису з використанням загальних криптосистем

Застосування асиметричної криптографії

Безпека асиметричної криптографії

Ризики безпеки для асиметричної криптографії

RSA

Алгоритм RSA

Ілюстрація RSA на Python

Генерація ключів RSA

Обмін симетричними ключами з RSA

Приклад обміну ключами на основі доповнення (padding) на Python

Симуляція механізму інкапсуляції ключів за допомогою RSA на Python

Цифрові підписи з RSA

Злом RSA

Класичні обчислення та RSA

Квантовий алгоритм Шора та RSA

Приклад на Python, що демонструє злом RSA-шифрування

Обмін ключами Діффі–Хеллмана та алгоритм цифрового підпису

Задача дискретного логарифма

Математичні деталі задачі дискретного логарифма

Обмін ключами Діффі-Геллмана

Ілюстрація протоколу Діффі-Геллмана на Python

Безпека обміну ключами Діффі-Геллмана

Алгоритм цифрового підпису (DSA)

Ілюстрація DSA на Python

Безпека DSA

Автентифікований обмін ключами з Діффі-Геллманом і DSA

Злом Діффі-Геллмана та DSA

Алгоритм Шора та задача дискретного логарифму

Криптографія на еліптичних кривих

Базові принципи криптографії на еліптичних кривих

Задача дискретного логарифму на еліптичних кривих

Обмін ключами з використанням ECC

Цифрові підписи з використанням ECC

Злом ECDH та ECDSA

Підсумок