[Ciko 0]

Два принципово різні типи шифрування

Перш ніж говорити про квантову загрозу, важливо розуміти, що AES і RSA вирішують різні завдання та побудовані на різній математиці.
AES – симетричний алгоритм. Один і той же ключ використовується і для шифрування, і розшифровки. Саме AES шифрує твій диск через LUKS, файли через VeraCrypt, сам трафік усередині VPN-тунелю.

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

---

Чому RSA вразливий для квантових комп'ютерів

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

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

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

---

Чому AES влаштований принципово інакше

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


Для симетричних алгоритмів єдиний відомий квантовий метод прискорення перебору — алгоритм Гровера, опублікований 1996 року. Але на відміну від алгоритму Шора, який дає експоненційне прискорення (злом стає якісно, значно швидше), алгоритм Гровера дає лише квадратичне прискорення.

---

Що означає "квадратичне прискорення" на практиці


Якщо AES-256 звичайному комп'ютеру потрібно перебрати в середньому половину від 2 до 256 комбінацій ключа, то алгоритм Гровера на квантовому комп'ютері скоротить цю роботу до приблизно 2 у ступені 128 операцій - що еквівалентно за складністю звичайному брутфорсу AES-1.


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


Тобто AES-256 після появи потужних квантових комп'ютерів не стане "зламаним" - він просто ефективно "просяде" до рівня надійності AES-128, який сам залишається досить сильним.

---

Підсумкова різниця простими словами

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

AES стійкий, тому що для симетричних шифрів існує лише алгоритм Гровера, який дає лише квадратичне, а не експоненційне прискорення — і навіть із цим прискоренням AES-256 зберігає практичний захист, еквівалентний нинішньому AES-128.

---

Дані, зашифровані через LUKS або VeraCrypt з AES-256, залишаються захищені навіть у гіпотетичному світі з працюючими великомасштабними квантовими комп'ютерами .

А ось все, що побудовано на RSA – обмін ключами у старих версіях TLS, частина PGP-інфраструктури, цифрові підписи багатьох сервісів – потенційно вразливе, коли (і якщо) з'явиться досить потужне квантове залізо.

---

Що вже роблять в індустрії на випередження

NIST в 2024 році фіналізував нові стандарти постквантової криптографії - алгоритми на кшталт CRYSTALS-Kyber для обміну ключами і CRYSTALS-Dilithium для цифрових підписів, побудовані на математичних задачах, для яких поки не існує відомого ефективного квантового алгоритму.

Signal вже додав постквантовий компонент у свій протокол обміну ключами. WireGuard-спільнота працює над інтеграцією постквантового захисту через проекти на кшталт Rosenpass.

---

Підсумок

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