Китайські вчені заявляють про злам RSA? Трохи перебільшення, як завжди

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

Як Працює RSA Шифрування та Його Квантова Вразливість

RSA, назване на честь його винахідників — Рівеста, Шаміра та Адлемана, є криптосистемою з публічним ключем, яка базується на складності факторизації великих чисел на їхні прості компоненти. Її безпека залежить від того, що класичним комп’ютерам знадобиться неймовірно багато часу для факторизації цих великих чисел — тисячі або навіть мільйони років для типових розмірів ключів: RSA Paper.

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

Китайські Дослідження та Останні Досягнення у Квантових Обчисленнях

Останні досягнення, зокрема в галузі квантового відпалу (quantum annealing), досягли значного прогресу в покращенні методів факторизації цілих чисел. Китайські вчені заявили про використання системи D-Wave для оптимізації процесу факторизації, здійснивши кілька методологічних удосконалень. Ці удосконалення містять оптимізаційні моделі для таблиць множення, зменшення розмірності для економії кубітів та перероблені моделі Ізінга й QUBO, що підвищують ефективність квантового відпалу.

Хоча ці внески викликають значний інтерес, їхні гучні заяви про можливість зламати RSA в реальних умовах поки не підтверджені. Квантові відпалювачі, як-от D-Wave, не здатні виконувати класичні квантові алгоритми, які необхідні для ефективної факторизації великих чисел (Preskill, 2018). Робота з D-Wave та подібними платформами більше нагадує академічний доказ концепції, ніж реальну загрозу кібербезпеці.

Масштабованість і Обмеження Квантового Відпалу

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

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

Підготовка до Пост-Квантового Майбутнього

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

У відповідь на цю майбутню квантову загрозу дослідники звернули свою увагу на постквантову криптографію (PQC). Наприклад, NIST обрав кілька кандидатів на алгоритми, які обіцяють бути квантово-стійкими, включаючи CRYSTALS-Kyber для публічного шифрування та встановлення ключів, а також CRYSTALS-Dilithium для цифрових підписів. Ці алгоритми використовують математичні проблеми, які вважаються складними для розв’язання як класичними, так і квантовими комп’ютерами. Наприклад, криптографія на базі граток. Більше інформації про криптографічні рішення на базі граток можна знайти в роботі про CRYSTALS-Kyber (preprint).

Чому Важлива Квантово-Стійка Криптографія

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

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

Висновок

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

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

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті

👍ПодобаєтьсяСподобалось5
До обраногоВ обраному2
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

А хіба є аналог алгоритма Шора для еліптичних кривих? Ну або чому ECDSA квантово вразливий?

arxiv.org/abs/1706.06752
Quantum resource estimates for computing elliptic curve discrete logarithms

arxiv.org/pdf/quant-ph/0301141
Shor’s discrete logarithm quantum algorithm for elliptic curves

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

A 160 bit elliptic curve cryptographic key could be broken
on a quantum computer using around 1000 qubits while factoring the
security-wise equivalent 1024 bit RSA modulus would require about 2000
qubits

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

Зараз багато зусиль спрямовано саме на корекцію помилок і спроби зробити ‘справжні’ кубіти з того, що є :))

arxiv.org/abs/2406.01743v3
Порівняння annealing vs gate-model

Вибачаюсь, не втримався :)

У цій статті показано, як квантові комп’ютери gate-model, зокрема IBM quantum комп’ютер на 127 кубітів, можуть реально outperform квантові annealers у binary optimization задачах. Це важливий момент, оскільки раніше вважалося, що annealers мають переваги в певних типах optimization задач завдяки їхній простішій архітектурі та меншій кількості шляхів для помилок. Але команда показала, що завдяки кастомним алгоритмам, таким як Quantum Approximate Optimization Algorithm (QAOA), gate-model quantum комп’ютери можуть не тільки наздогнати, а й перевершити annealers у деяких сценаріях.

Annealers, як D-Wave, добре підходять для Quadratic Unconstrained Binary Optimization (QUBO) проблем, тому що вони мають просту архітектуру, яка дозволяє масштабувати задачі до сотень вузлів. Але вони стикаються з серйозними обмеженнями в точності на великих масштабах і для складніших моделей. У той же час gate-model quantum комп’ютери, такі як IBM, можуть обробляти більш складні задачі, включаючи higher-order interactions (наприклад, кубічні взаємодії), що робить їх більш універсальними.

Ключовим моментом є те, що QAOA на gate-model quantum hardware використовує гібридний класично-квантовий підхід для оптимізації параметрів алгоритму, що дозволяє отримувати правильні результати навіть у великих системах (до 127 кубітів). У порівнянні з D-Wave, gate-model машини показали до 1500x більшу ймовірність знаходження мінімальної енергії в деяких тестах спін-скла. Це показує, що з правильними error suppression техніками та постпроцесінгом gate-model комп’ютери стають більш ефективними для деяких класів задач, ніж annealers.

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

arxiv.org/pdf/2003.00133
Про фізичну топологію annealers

Але це «ідеальні кубіти», для корекції помилок та для передачі квантових станів між несусідніми кубітами треба ще в декілька разів більше реальних кубітів.

Реально існуючі девайси від IBM, Google та інших реально мають близько 100 «noisy qubits» і вже багато років обіцяють тисячі кубітів, але через 10 років :))

У D-Wave понад 5000 «кубітів», але це зовсім інша технологія і зовсім інші підходи. Це фактично клітинки, які перерозподіляють енергію між собою за певними правилами, специфічними для конкретної задачі, і намагаються досягти оптимального для цієї задачі розподілу. Наприклад, розрахувати рівень чи швидкість потоку води на складному рельєфі, або опір матеріалів та подібні речі. З певної точки зору вони навіть більш корисні для реальних інженерних задач, але для криптографії їх використати дуже важко.

Згадалася ще одна технологія, яка «буде через 10 років» вже більш ніж півстоліття :) Енергетичні установки на ядерному синтезі :)

Ну один тип «енергетичних» установок на ядерному синтезі існує ще з 1952 року.
Правда це далеко не «мирний атом»
Так само і тут — була б мотивація. Для усіляких деструктивних речей у людства завжди було більше мотивації

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

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

Ну та залізяка, на якій китайці ‘зламали’, по суті не дуже може зламувати, це такий собі акселератор для розв’язання перевизначених систем лінійних рівнянь.
Вони зламували гібридом зі звичайного комп’ютера та D-Wave. І D-Wave виконував одну, але дуже специфічну частину роботи.

dou.ua/forums/topic/50789 тут трішки детальніше :)

Підписатись на коментарі