В этой статье мы рассмотрим самый быстрый алгоритм для ECDLP из области вычислительной теории чисел, кенгуру Полларда также называют алгоритм лямбды Полларда.
Метод кенгуру Полларда вычисляет дискретные логарифмы в произвольных циклических группах. Он применяется, если известно, что дискретный логарифм лежит в определенном диапазоне, скажем [ a , b ], а затем имеет ожидаемое время выполнения групповой операции.
Преимущество Pollard's Kangaroo:
• использует очень мало памяти
• можно распараллелить с линейным ускорением
• можно эффективно отслеживать требования к объему памяти
Все это делает метод кенгуру самым мощным методом решения задачи дискретного логарифмирования.
Один из способов сломать схемы подписи ECDSA — это решить проблему дискретного логарифмирования.
В настройках ECDSA алгоритмы субэкспоненциального времени, такие как метод индексного исчисления, не применяются, а лучшим известным на сегодняшний день методом решения лежащем в их основе DLP являются метод кенгуру Полларда. Мы постараемся не нагружать вас с различными теоретическими аспектами. Перейдем сразу к экспериментальной части.
Как мы знаем в блокчейне Биткоина отправитель монет BTC всегда раскрывает свой публичный ключ.
Для метода кенгуру Полларда достаточно знать публичный ключ или значение сигнатуры R ( значение R - это тоже своего рода публичный ключ от Nonces т.к. это точка координата x на плоскости эллиптической кривой secp256k1)
Остается только определить диапазон PRIVATE KEY или диапазон NONCES.
Случается такое что некоторые устройства которые создают подписиECDSAв блокчейне Биткоина могут частично раскрывать байты информации о значение "K" (NONCES)
Мы считаем что это потенциальная угроза потери монет BTC и настоятельно рекомендуем всем всегда обновлять ПО и использовать только проверенные устройства.
В недалеком прошлом мы провели криптоанализ в блокчейне Биткоина и нашли несколько таких транзакции.
