Вони пропонують метод розшифровки ключів RSA-2048
Група дослідники з різних наукових центрів та університетів китайська Я запропонувавn новий спосіб оптимізаціїr процес факторизації ключового параметра RSA в квантових комп'ютерах.
За даними слідства, розроблений ними метод дозволяє використовувати квантовий комп’ютер з 372 кубітами для розшифровки ключів RSA-2048. Для порівняння, IBM Osprey, найпотужніший квантовий процесор на даний момент, містить 433 кубіти, а до 2026 року IBM планує створити систему Kookaburra з 4000 кубітів.
Варто зазначити це метод все ще лише теоретичний, він не перевірений на практиці і викликає скептицизм у деяких криптографів.
Шифрування RSA базується на операції піднесення до степеня за модулем великого числа. Відкритий ключ містить модуль і ступінь. Модуль формується на основі двох випадкових простих чисел, які знає лише власник закритого ключа. Квантові комп’ютери дозволяють ефективно вирішувати задачу розкладання числа на прості множники, за допомогою яких можна синтезувати закритий ключ із відкритого.
До цього часу вважалося, що з огляду на сучасний розвиток квантових комп'ютерів, Ключі RSA розміром 2048 біт довго не можуть бути зламані, оскільки за допомогою класичного алгоритму Шора квантовому комп’ютеру з мільйонами кубітів потрібно багато часу, щоб розкласти 2048-бітний ключ RSA.
Метод, запропонований китайськими дослідниками, ставить під сумнів це припущення. і, в разі підтвердження, дає можливість зламувати ключі RSA-2048 не в системах далекого майбутнього, а в уже існуючих квантових комп'ютерах.
В основі методу лежить алгоритм швидкої факторизації Шнорра. запропонований у 2021 році, який дозволяє різко скоротити кількість операцій при виборі на звичайних комп’ютерах. Однак на практиці алгоритм виявився малопридатним для злому реальних ключів, оскільки він працював тільки для ключів RSA з малими значеннями по модулю (ціле число, яке потрібно розкласти на прості числа). Алгоритм виявився непридатним для розкладання великих чисел. Китайські дослідники стверджують, що за допомогою квантових методів їм вдалося обійти обмеження алгоритму Шнорра.
Скептицизм від деяких криптографів пов'язано з тим що демонструє стаття китайських дослідників застосовуючи ваш метод лише до невеликих чисел, приблизно в тому самому порядку, для якого працює алгоритм Шнорра. Незважаючи на заяви про перевищення ліміту розміру, жодних доказів чи деталей поки не надано. На практиці показано, що метод розкладає на множники 48-бітні цілі числа за допомогою 10-кубітного квантового комп’ютера.
Алгоритм Шора серйозно поставив під загрозу безпеку інформації на основі криптосистем з відкритим ключем. Однак для зламу широко використовуваної схеми RSA-2048 потрібні мільйони фізичних кубітів, що значно перевищує поточні технічні можливості. Тут ми повідомляємо про універсальний квантовий алгоритм для цілочисельної факторизації шляхом поєднання класичної редукції решітки з квантовим алгоритмом нечіткої оптимізації (QAOA).
Потрібна кількість кубітів дорівнює O(logN/loglogN), яка сублінійна щодо довжини цілого біта N, що робить його алгоритмом факторизації з найбільшою економією кубітів на сьогоднішній день. Ми демонструємо алгоритм експериментально, розкладаючи цілі числа до 48 біт на 10 надпровідних кубітів, найбільше ціле число, розкладене на множники в квантовому пристрої. За нашими оцінками, щоб випробувати RSA-372 за допомогою нашого алгоритму, необхідна квантова схема з 2048 фізичними кубітами та глибиною тисяч. Наше дослідження дає великі надії на прискорення застосування сучасних шумних квантових комп’ютерів і прокладає шлях до розкладання великих цілих чисел реалістичного криптографічного значення.
Зазначається, що припущення про те, що 372 фізичних кубітів буде достатньо для розкладання ключа RSA-2048, є теоретичним, тому дуже ймовірно, що квантовий метод, заснований на алгоритмі Шнорра, має ті ж проблеми масштабування і не працює під час розкладання чисел. .
Якщо проблему з масштабуванням дійсно вирішити, то безпека криптоалгоритмів, заснованих на складності розкладання великих простих чисел, буде підірвана не в довгостроковій перспективі, як очікувалося, а вже сьогодні.
Нарешті, якщо вам цікаво дізнатися більше про це, ви можете ознайомитися з деталями в за наступним посиланням.