Як працює шифрування
Щоразу, коли ви входите в систему, купуєте щось онлайн або надсилаєте повідомлення, шифрування зберігає це приватним. Від простого зсуву літер Юлія Цезаря до алгоритму RSA, що захищає сучасний інтернет, — це історія про те, як математика творить таємниці.
Шифр Цезаря
За переказами, Юлій Цезар надсилав повідомлення своїм полководцям, зсуваючи кожну літеру алфавіту на три позиції вперед. A стає D, B стає E, і так далі. Одержувач знав, що треба зсунути назад на три.
Шифр (зсув +3) D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
Повідомлення ATTACK AT DAWN
Зашифровано DWWDFN DW GDZQ
Це просте шифрування заміною: кожен символ відкритого тексту замінюється іншим символом. Ключ — це просто число 3.
Зламати його можна щонайбільше за 25 спроб (існує лише 25 нетривіальних зсувів). Проти сучасних комп'ютерів — або навіть олівця й паперу — шифр Цезаря розпадається миттєво. Корінна проблема в тому, що він має надзвичайно малий простір ключів.
Симетричне шифрування з ключем
Суттєвим удосконаленням є використання довгого випадкового ключа, де кожна позиція у відкритому тексті зсувається власним символом ключа. Це шифр Віженера. Застосований ідеально — ключ завдовжки з повідомлення, використаний лише раз, по-справжньому випадковий — він стає незламним одноразовим блокнотом (математично доведено безпечним Клодом Шенноном 1949 року).
Сучасні симетричні шифри на кшталт AES-256 використовують 256-бітні ключі. Існує 2²⁵⁶ ≈ 10⁷⁷ можливих ключів — більше, ніж кількість атомів у видимому Всесвіті. Підбір AES-256 повним перебором обчислювально неможливий навіть якщо всі комп'ютери світу працюватимуть до теплової смерті Всесвіту.
| Шифр | Біти ключа | Простір ключів | Статус |
|---|---|---|---|
| Цезаря | ~5 | 25 ключів | Зламано тривіально |
| DES | 56 | 7.2 × 10¹⁶ | Зламано (1999, 22 год) |
| 3DES | 112 | 5.2 × 10³³ | Виведено з ужитку (2024) |
| AES-128 | 128 | 3.4 × 10³⁸ | Безпечний |
| AES-256 | 256 | 1.2 × 10⁷⁷ | Постквантово безпечний |
AES шифрує дані фіксованими 128-бітними блоками за 10–14 раундів математичних операцій: заміна (S-блок), зсув рядків, перемішування стовпців і додавання ключа. Результат — повністю переплутаний блок без статистичного сліду оригіналу.
Проблема розподілу ключів
Симетричне шифрування має одну фатальну слабкість: і відправник, і одержувач мусять уже мати той самий секретний ключ. Але як? Якщо Аліса хоче надіслати Бобу зашифроване повідомлення, вона спершу має передати йому ключ — але сам ключ мусить подорожувати безпечно. Це замкнене коло.
Століттями це вирішували фізичним розподілом ключів — кур'єрами, кодовими книгами та шифрувальними машинами (як «Енігма»). Для цифрових комунікацій у масштабі інтернету цей підхід неможливий. 1976 року Вітфілд Діффі та Мартін Геллман опублікували революційне рішення.
Обмін ключами Діффі–Геллмана
Діффі–Геллман дозволяє двом сторонам узгодити спільний секрет через повністю публічний канал, який прослуховують. Прийом — математична одностороння функція на основі модульного піднесення до степеня:
Обчислити g^x mod p (піднести g до степеня x, а потім знайти остачу від ділення на p) — швидко. Але маючи результат, працювати у зворотному напрямку, щоб знайти x — задача дискретного логарифма — обчислювально важко для великих p.
Аліса обирає секрет a = 4 Надсилає: A = 5⁴ mod 23 = 4
Боб обирає секрет b = 3 Надсилає: B = 5³ mod 23 = 10
Спільний секрет Аліса: 10⁴ mod 23 = 18
Боб: 4³ mod 23 = 18 ✓
Підслуховувач бачить g, p, A=4 та B=10 у відкритому вигляді. Щоб знайти спільний секрет 18, він мусить розв'язати задачу дискретного логарифма — що для 2048-бітних чисел тривало б довше за вік Всесвіту.
RSA: замок, який може закрити будь-хто
Винайдена Рівестом, Шаміром і Адлеманом (RSA) 1977 року криптографія з відкритим ключем розв'язує іншу проблему: не лише обмін ключами, а й автентифіковане шифрування. Кожен може шифрувати повідомлення для вас, але розшифрувати їх можете лише ви.
RSA ґрунтується на складності факторизації цілих чисел: перемножити два великі прості числа p і q тривіально, але маючи добуток n = p × q, відновити p і q обчислювально важко, щойно n стає достатньо великим (2048+ бітів).
Як RSA працює концептуально:
- Генерація ключів: оберіть великі прості числа p, q. Обчисліть n = p·q та φ(n) = (p−1)(q−1). Оберіть відкритий показник e й обчисліть закритий показник d такий, що e·d ≡ 1 (mod φ(n)).
- Відкритий ключ: (n, e) — поширте його світом.
- Закритий ключ: (n, d) — тримайте його в таємниці.
- Шифрування: C = M^e mod n
- Розшифрування: M = C^d mod n
Для 2048-бітного ключа RSA факторизація n потребувала б приблизно 10¹⁵ років за найкращим відомим класичним алгоритмом (загальне решето числового поля) на всьому наявному обчислювальному обладнанні разом узятому.
Односторонні функції та лазівки
І Діффі–Геллман, і RSA спираються на односторонні функції з лазівкою: операції, що швидкі в одному напрямку, але обчислювально неможливі у зворотному, якщо тільки ви не маєте особливої інформації (лазівки — вашого закритого ключа).
| Алгоритм | Одностороння функція | Лазівка | Важка задача |
|---|---|---|---|
| Діффі–Геллман | g^x mod p | Закритий показник x | Дискретний логарифм |
| RSA | M^e mod n | Факторизація n | Факторизація цілих чисел |
| ECDSA (криві) | k·G на еліптичній кривій | Скаляр k | Дискретний логарифм на еліптичній кривій |
Криптографія на еліптичних кривих (ECC) використовує коротші ключі за тієї ж безпеки: 256-бітний ключ ECC забезпечує безпеку, подібну до 3072-бітного ключа RSA. ECDH та ECDSA нині є кращим вибором для TLS і цифрових підписів.
Гібридне шифрування на практиці
Криптографія з відкритим ключем (RSA/ECC) математично елегантна, але повільна — приблизно у 1000 разів повільніша за AES для великих обсягів даних. На практиці системи завжди використовують гібридне шифрування:
- Використати (повільний) алгоритм із відкритим ключем, щоб безпечно обмінятися випадковим сеансовим ключем.
- Використати (швидкий) симетричний алгоритм (AES) з цим сеансовим ключем, щоб зашифрувати всі реальні дані.
Ви отримуєте безпеку криптографії з відкритим ключем для обміну ключами та швидкість симетричної криптографії для основного обсягу даних — найкраще з обох світів.
Як насправді працює HTTPS
Коли ваш браузер з'єднується із сайтом через HTTPS, рукостискання TLS (Transport Layer Security) виконує цю гібридну схему за частку секунди. Ось що відбувається, спрощено:
-
ClientHello: ваш браузер оголошує версію TLS та набори шифрів, які він підтримує (наприклад, TLS 1.3 + AES-256-GCM + обмін ключами X25519).
-
ServerHello + сертифікат: сервер обирає набір шифрів і надсилає свій сертифікат X.509, що містить відкритий ключ сервера, підписаний довіреним центром сертифікації (CA).
-
Перевірка сертифіката: ваш браузер перевіряє ланцюжок сертифікатів проти вбудованого списку довірених CA. Це запобігає атакам «людина посередині».
-
Обмін ключами: обидві сторони виконують Діффі–Геллман (або його варіант на еліптичних кривих ECDH), щоб вивести спільний сеансовий ключ. Жоден закритий ключ не передається лінією зв'язку.
-
Симетричне шифрування: усі подальші дані шифруються AES-256-GCM із використанням сеансового ключа. Сеансовий ключ згодом відкидається (пряма секретність).
Квантова загроза
Алгоритм Пітера Шора 1994 року показав, що достатньо потужний квантовий комп'ютер може розв'язати і задачу дискретного логарифма, і задачу факторизації цілих чисел за поліноміальний час — зламавши RSA та Діффі–Геллман.
Такого квантового комп'ютера ще не існує. Сучасні шумні квантові процесори сягають щонайбільше кількох сотень логічних кубітів із виправленням помилок; для злому RSA-2048 знадобилося б близько 4 000 логічних кубітів.
Національний інститут стандартів і технологій США (NIST) стандартизував перші постквантові алгоритми 2024 року: ML-KEM (інкапсуляція ключів на основі ґраткових задач) та ML-DSA (цифрові підписи). Їх уже додають до бібліотек TLS 1.3.
Спробуйте самі
Дослідіть, як випадковість і ймовірність лежать в основі всього — від перетасовування до симуляцій — ті самі математичні засади, що змушують шифрування працювати:
Симуляція нейронної мережі показує, як ітеративні математичні операції (подібні до раундів блокового шифру) перетворюють дані на щось невпізнаване — і назад: