Що таке алгоритм Shor і чому він загрожує крипто?

Алгоритм Shor, опублікований математиком Пітером Shor у 1994 році, є квантовим алгоритмом, який ефективно розв’язує задачі розкладання на множники та дискретного логарифмування. Ці математичні проблеми формують основу безпеки криптографії RSA, Diffie-Hellman і ECDSA, включаючи підписи, які захищають практично всі поточні криптовалюти.

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

Для криптовалюти загроза специфічна: алгоритм Shor може отримувати приватні ключі ECDSA із відкритих ключів. Bitcoin, Ethereum та більшість криптовалют використовують ECDSA із кривою secp256k1. Після відкриття відкритих ключів (що відбувається, коли витрачаються адреси), квантові комп’ютери, на яких працює алгоритм Shor, можуть обчислити відповідні закриті ключі.

Запуск алгоритму Shor проти 256-бітного ECDSA 1200–1450 логічних кубітів, поміщається всередину менше 500 000 фізичних кубітів, а завершує в хвилин — тест за березень 2026 року від Google Quantum AI, який співпрацює з фондом Ethereum та Стенфордським університетом. Це приблизно половина ~2330 логічних кубітів, які передбачалися раніше. Незалежний аналіз Caltech/Oratomic досяг такого ж розриву з приблизно 26 000 фізичних кубітів на обладнанні з нейтральними атомами протягом приблизно десяти днів. Факторинг RSA-2048 тепер займає менше 1 мільйона шумних кубітів і менше тижня (Гідней, травень 2025 року), порівняно з 20 мільйонами кубітів у 2019 році, але RSA не є найближчою ціллю, оскільки ECDSA-256 дешевший.

Найкраще загальнодоступне апаратне забезпечення на сьогодні приблизно 2500 фізичних кубітів, жоден із них не є відмовостійким у масштабі. Машина, яка заповнює прогалину, — це Blue Jay від IBM 2033, з понад 2000 логічних кубітів на приблизно 100 000 фізичних — передував Starling у 2029 році з ~200 логічними. Вікно прибуття є 2029–2033 роки.

Постквантова криптографія вирішує цю загрозу за допомогою математичних проблем, які алгоритм Shor не може ефективно вирішити. Криптографія на основі решітки (Kyber) і підписи на основі хешу (SPHINCS+) не мають відомих ефективних квантових атак.

SynX реалізує алгоритми Kyber-768 і SPHINCS+ саме тому, що алгоритм Shor не дає переваги перед ними. Це захищає криптовалютні авуари від неминучого прогресу технологій квантових обчислень.