Квантовий комп’ютер зламав 22-бітове шифрування RSA

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

«Використовуючи [пристрій] D-Wave Advantage, ми успішно розклали на множники 22-бітове число RSA, продемонструвавши потенціал квантових машин у криптографії», — зазначають автори.

До цього алгоритм вважався непридатним до зламу на аналогічному обладнанні.

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

Сьогодні більшість систем захищені 2048-бітовим RSA, а найбільший ключ, зламаний класичними методами, — RSA-250 (829 біт). Його вдалося зламати за кілька тижнів роботи суперкомп’ютера.

Для факторизації 22-бітового модуля вчені застосували ту саму методику, що й під час успішної атаки на алгоритми Present, Gift-64 та Rectangle у жовтні 2024 року. Тоді дослідники назвали це «першим випадком, коли реальний квантовий комп’ютер становить серйозну загрозу для повноцінних криптосистем».

Методологія

22-бітовий ключ — надзвичайно малий порівняно з промисловими RSA-системами. Цей експеримент виходить за межі попередніх досліджень, обмежених 19 бітами та більшим навантаженням на кожну змінну.

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

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

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

Загроза вже поруч

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

Більшість компаній, зокрема банки та установи, що залежать від криптографії, ще не адаптували свої системи до квантової епохи.

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

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

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

Нагадаємо, CEO Tether передбачив можливий злам і повернення пов’язаних із Сатоші Накамото біткоїнів.