| +11 голос |
|
Зʼявилось дослідження, в якому стверджується, що можна зламати 2048-бітний ключ RSA, хоча це ще не зроблено, це те, що потрібно сприймати серйозно. Це може бути некоректно, але це не очевидно неправильно.
Ось що пише Брюс Шайер (Bruce Scheier) - технолог, який займається громадськими інтересами і працює на стику безпеки, технологій і людей, про цей анонс групи китайських дослідників,
З алгоритму Шора відомо, що факторизація за допомогою квантового комп’ютера проста. Але потрібен великий квантовий комп’ютер, розміром у мільйони кубітів, щоб розкласти будь-що, що нагадує розміри ключів, які використовуються сьогодні. Те, що дослідники зробили, це поєднали класичні методи факторизації решітки (алгебраїчне поняття) з алгоритмом квантової наближеної оптимізації. Це означає, що їм потрібен квантовий комп’ютер лише з 372 кубітами, що цілком можливо сьогодні. (Наприклад, IBM Osprey — це 433-кубітний квантовий комп’ютер).
У китайської групи не було такого великого квантового комп’ютера для роботи. Вони змогли розкласти 48-бітні числа за допомогою 10-кубітного квантового комп’ютера. І хоча при масштабуванні чогось подібного до 50 разів завжди виникають потенційні проблеми, очевидних перешкод немає.
Однак виникає неприємне питання, чому китайський уряд не засекретив це дослідження. Але… вау… можливо… і ой! Чи ні.
Алгоритм Шора поставив серйозний виклик інформаційній безпеці на основі криптосистем з відкритим ключем. Однак, щоб зламати широко використовувану схему RSA-2048, потрібні мільйони фізичних кубітів, що далеко перевищує поточні технічні можливості. Тут ми повідомляємо про універсальний квантовий алгоритм для цілочисельної факторизації шляхом поєднання класичної редукції решітки з квантовим алгоритмом наближеної оптимізації (QAOA). Потрібна кількість кубітів дорівнює O(logN/loglogN), яка сублінійна щодо довжини біта цілого числа N, що робить його найбільш економним алгоритмом факторизації на сьогоднішній день.
Запропонований алгоритм демонструється експериментально шляхом розкладу цілих чисел до 48 біт на десяти надпровідних кубітів, найбільше ціле число, розкладене на квантовому пристрої. Дослідження показує великі перспективи для прискорення застосування сучасних шумних квантових комп’ютерів і відкриває шлях до розкладання великих цілих чисел реалістичного криптографічного значення.
В електронному листі Роджер Граймс (Roger A. Grimes), який спеціалізується на безпеці хостів і запобіганні хакерам, сказав: «Мабуть, те, що трапилося, — інший хлопець, який раніше оголосив, що зміг зламати традиційне асиметричне шифрування за допомогою класичних комп’ютерів… але рецензенти знайшли недолік у його алгоритмі, і цьому хлопцеві довелося відкликати свою статтю. Але ця китайська команда зрозуміла, що крок, який убив усе, можна вирішити за допомогою маленьких квантових комп’ютерів. Тож вони перевірили, і це спрацювало».
Одна з проблем алгоритму полягає в тому, що він покладається на нещодавню статтю про факторізацію німецького математика и криптографа Пітера Шнорра (Claus-Peter Schnorr). Це суперечлива стаття; і незважаючи на абстрактну заяву «це руйнує криптосистему RSA», нічого подібного не робить. Алгоритм Шнорра добре працює з меншими модулями — приблизно такого ж порядку, як і ті, які перевірила китайська група, — але розпадається при більших розмірах. На даний момент ніхто не розуміє чому. Китайська газета стверджує, що їхні квантові методи обходять це обмеження (я думаю, що це те, що стоїть за коментарем Граймса), але не надають жодних деталей — і вони не перевіряли це з більшими модулями. Отже, якщо це правда, що китайська стаття залежить від цієї техніки Шнорра, яка не масштабується, методики в цій китайській статті також не будуть масштабуватися. (З іншого боку, якщо це масштабується, я думаю, що це також ламає купу криптосистем із відкритим ключем на основі решітки).
Я набагато менше хвилююся, що тепер ця методика працюватиме. Але це те, що спеціалісти з квантових обчислень IBM можуть перевірити прямо зараз.
Стратегія охолодження ЦОД для епохи AI
| +11 голос |
|
