Криптостойкость Биткоина против квантового компьютера QIANSHI от китайского гиганта поисковой системы Baidu Inc.

В погоне за кубитами Baidu Inc как лидер среди китайских поисковых систем не отстаёт от своего западного конкурента Alphabet Inc.

В августе 2022 года китайский гигант поисковой системы Baidu Inc разработал собственный квантовый компьютер, который вскоре получил название «Qianshi».

Все супермощные компьютеры используют квантовую физику для решения сложных задач, недоступных для традиционных устройств, с помощью кубитов – эволюции классического двоичного бита. Кубиты могут одновременно представлять значение 1 или 0, что обещает экспоненциальный рост вычислительной мощности.

Биткоин использует сразу несколько криптографических алгоритмов: алгоритм цифровой подписи на эллиптической кривой (ECDSA) для подписи транзакций и две хэширующие функции — SHA-256 и RIPEMD160.

Наиболее распространенный хэши функции используют вариант 128 ключей который может быть взломан квантовыми компьютерами. В обозримом будущем RIPEMD160 может оказаться так же под угрозой.

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

Новые приватные ключи будут генерироваться системой после успешного внедрения постквантового шифрования. Чтобы активировать переход на новый приватный ключ, пользователи должны будут подписать для утверждения свой старый приватный ключ. Однако неактивные пользователи Биткоина могут никогда не обновить свой приватный ключ, что может вызвать серьезные проблемы, так как бездействующие Биткоин Кошельки, такие как те, которые содержат более 1 миллиона монет BTC, которые предположительно принадлежат Сатоши Накамото, вероятно, никогда не увидят улучшения шифрования.

BitInfoCharts

Атака «дней рождения» (Birthday attack)

Один из наиболее часто упоминаемых способов атаки на Биткойн который может быть применим квантовыми компьютерами это атака «дней рождения» (Birthday attack)

Этот метод основан на поиске коллизий хеш-функций на основе парадокса дней рождения.

Он использует математику, стоящую за проблемой дня рождения в теории вероятностей. Успех этой атаки во многом зависит от более высокой вероятности коллизий между случайными попытками атаки и фиксированной степенью перестановок, как описано в проблеме парадокса дня рождения математическая модель для поиска частичных столкновений путем обнаружения коллизии между двумя Биткоин Адресами, которые создают один и тот же HASH160(чтобы попытаться найти коллизию для HASH160).

Алгоритм можно описать по аналогии со случайным блужданием

Пять случайных блужданий по восемь шагов с началом в центральной точке. Некоторые пути кажутся короче, чем 8 шагов: в этом случае путь дублирует некоторые шаги в обратном направлении. Материал из Википедии: «Случайное блуждание»

Используя принцип, согласно которому любая функция с конечным числом возможных выходов, помещенных в петлю обратной связи, будет циклически повторяться, можно использовать относительно небольшой объем памяти для хранения выходов с определенной структурой и использовать их в качестве «маркеров», чтобы лучше определять, когда маркер имеет место (было “пройдено” раньше). Эти маркеры называются выделенными точками , а точка в которой два входа дают один и тот же результат, называется точкой столкновения .

Перейдем к экспериментальной части:

Откроем [TerminalGoogleColab].

Воспользуемся репозиторием «11QianshiBTC».

git clone https://github.com/demining/CryptoDeepTools.git

cd CryptoDeepTools/11QianshiBTC/

ls

Установим все пакеты:

sudo apt-get install g++ -y
sudo apt-get install libgmp3-dev libmpfr-dev -y

Сборка:

make

Запустим команду ls и видим что qianshiBTC – инструмент для поиска коллизии Биткоин Адресов успешно создан!

Запуск:

Для запуска укажем первые 40 bits для поиска столкновения

./qianshiBTC 40

Из поиска мы видим что мы получили частичную коллизию Биткоин адресов на основе «Birthday Attack»

Откроем bitaddress и проверим:

--RESULT-(SECRET)---------------------------------------------------------------

priv_key[1] = 277C6CA6F6BD18E09BE149D02B73219E959F1F196EA053DA064F8AE87D937060
priv_key[2] = 9E233E554BBBCA4E0E487DBB108E8207F5E29C2203007A6C671F769C6EB56463

WIF[1] = KxYU1nx59KfPngSvDWU9B2hinhprnTT5pXiVZUEmjqdo41DuafPc
WIF[2] = L2X7Kn854vGj87rNQd1Kgz9p9powZ3iHebp8GdkK8tHuRMDjufJv

--RESULT-(SIGNATURES)-----------------------------------------------------------

message = "This is a real Bitcoin address."
sig[1] = H3RIf+MXNTt68hBxo6jNLMYFZVdGJYKucuE07P2EEcYnCT3MmeC7IZ7bib4GphG3oKph2Cg/t1KIoJShT1uLOfo=
sig[2] = ILWm8qSAacbS+ShcUohp5Nyw4/yFLMPRydPLLy8HNy3IVHRvRt58Rtr3511euQGT9tVIcv0QhetqydrB0txUxu8=

--RESULT-(PUBLIC)---------------------------------------------------------------

pub_key[1] = 023A7ABE886BF8A5E629C71449FA7B45F1A540A88C1321B32153002EE5DB6FCD
pub_key[2] = 024EE1DFCE7498EA0729EADFDC3428FF3D966509800A4C786A317B9E0CAABB44

bonus = 0bits
shared = 10chars
hash160[1] = 06df0a6506d559796b4e4bf11e5d37140151f631
hash160[2] = 06df0a6506264eae5f2727343b09f9b6b114d5ad

shared = 6chars
addr[1] = 1dLFHTpXawMMcFGd81ky7pjEcKDa9z3M8
addr[2] = 1dLFHToyYKVanuxG6XcC1BW9BLHuRugGt

warning: verify the keys/addresses before use!

В настоящее время код использует только CPU, но порт для GPU сделал бы возможными более 100 битные коллизии. Это похоже на добычу разделенных ключей Vanitygen. При достаточном количестве ядер возможно увеличить биты для поиска коллизии. В случае с квантовыми компьютерами хэш функция RIPEMD160 полностью обречена.

Литература:

• “Параллельный поиск столкновений с помощью криптоаналитических приложений” [“Parallel Collision Search with Cryptanalytic Applications”] Paul C. van Oorschot & Michael J. Wiener

Данный видеоматериал создан для портала CRYPTO DEEP TECH для обеспечения финансовой безопасности данных и криптографии на эллиптических кривых secp256k1 против слабых подписей ECDSA в криптовалюте BITCOIN

Исходный код

Telegram: https://t.me/cryptodeeptech

Видеоматериал: https://youtu.be/KqJcPSIZ5RM

Источник: https://cryptodeep.ru/quantum-computer-qianshi