cryptodeeptech Aug 12 2022 at 14:42

Уменьшение приватного ключа через скалярное умножение используем библиотеку ECPy + Google Colab

8 min

Decentralized networks*Cryptography*Python*

Recovery Mode

В этой статье мы постараемся показать как можно уменьшить приватный ключ зная только утечку из списка «BLOCKCHAIN FOLBIT LEAKS» и публичный ключ из «UTXO».

В экспериментальной части мы воспользуемся скриптами 08ReducePrivateKey и восстановим Биткоин Кошелек.

Скалярное умножение на эллиптической кривой — это операция добавления точки P на кривую k раз.
Q=kP=P+P+P, k times

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

Воспользуемся библиотекой ECPy

ECPy предоставляет:

подписи ECDSA
подписи Ed25519
подписи ECSchnorr
подписи Borromean
операции с точками

Во многих наших исследованиях мы используем библиотеку ECPy и Google Colab

Откроем [TerminalGoogleColab].

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

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

cd CryptoDeepTools/08ReducePrivateKey/

ls

Установим библиотеку ECPy:

pip3 install ECPy

Python скрипт: maxwell.py , сохраним код и запустим в терминале Google Colab

from ecpy.curves     import Curve,Point

cv = Curve.get_curve('secp256k1')
G  = Point(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,
           0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8,
           cv)
x  = 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1

PUBKEY  = x*G

print(PUBKEY)

Команда запуска:

python3 maxwell.py

Результат:

(0x3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63 , 0xc0c686408d517dfd67c2367651380d00d126e4229631fd03f8ff35eef1a61e3c)

Обратите внимание на координату x:

x value = 3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63

0200000000000000000000003B78CE563F89A0ED9414F5AA28AD0D96D6795F9C63

Этот публичный ключ называют "Maxwell's vanity public key"

0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0 --> 0x3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63, 0x3f3979bf72ae8202983dc989aec7f2ff2ed91bdd69ce02fc0700ca100e59ddf3
0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1 --> 0x3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63, 0xc0c686408d517dfd67c2367651380d00d126e4229631fd03f8ff35eef1a61e3c

p = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

((p-1)/2) = 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0

0200000000000000000000003B78CE563F89A0ED9414F5AA28AD0D96D6795F9C63

Мы ещё вернемся к этому публичному ключу!

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

У нас есть три разных Биткоин Адреса с балансом 100 BTC и выше из списка Bitcoin Rich List

1KpHWkpG7BGxDuSJKYPYVvNSC6womEZdTu
1MjGyKiRLzq4WeuJKyFZMmkjAv7rH1TABm
1GrTCkqqcXhVTXoQkPJjU5LuFKgAvC3iqJ

Получим UTXO для этих Биткоин Адресов и теперь у нас есть три подписи ECDSA (Применим скрипты 01BlockchainGoogleDrive)

c1ea2c9e48ce632488817781f89730d77cd4121f1c8f70a4be44d2a15e8e08d0
37dadae30c6f7c6c4a2c930db979494783005a8e94d6861039fed21e3fa859b9
9dacfc8243109475383d5b30e8d5f0ba23d023bd47649064c208d4586b278436

Получим RawTX для трех разных Биткоин Адресов

01000000017fbdd4c9991d0ba4fb0a0c06f6933442c17678bce6dfa4bf80e22ed530bb933c010000008a47304402206d0ab626a7e477c27602ed63b2651517af077e6f3fafda671dd9952dfcb5f0b90220168eb51a48ce7496a699a800299f15638e0a7f36ae84e84e26df0cd2a280a70e014104b3fdc0e84cd77cd018ced1fdd3ea4110d6beb942cfd38c0f6feaffc246e08b97fe779e87e4743f55168a476433100abd4cac064be5915cf828185319480b3fb4feffffff0240597307000000001976a914211090b628fa6351fa8240232e3c2753fd5eece588ac700369d2050000001976a914ce639943ce1602e30b249faf74388ee0eeb1d3c588ac84b90700
01000000014666d430766d611cc7f2c21494e68e463ac4be8bb2f70b91693728324849e1c3010000008a473044022057a02a4abc38e2e3e1809b05402cf52faef7e101d6364d43bb0305f8796b0fb202203d1934a016c91072ffe137575734454161284ab3371a0cfc6767db7f27f24a75014104ea7c9e85d4fb089e0b2901cd5c77f3149aa4cf711ed29a3318a4e153a67ea9cd1a22c24c8e05b66eb122db74d26fddf2cb184033fb586743ea330e15eeb8240cffffffff01b0feea0b000000001976a9148300ab0caebb6e85cf9e6b287a57924d1ac7c82f88ac00000000
01000000019d8e5e1bfac780b813e41517926aca95048e1dea92cbbe2a98475ff53ad38ccd000000008c493046022100c7b76326879a5ec7df2ffedb292a45c13c6f154982fc2cd7e05f0d0d0dce2d05022100d7fd43416608eaeb6356f04b601ac6edd23e0f82de44689fe5a7aa2f576637a001410480edda62d055008c28de19f4908cd052ccf63a10d708b5866b7a5b340bde49e2b5e7be50412afb83a6c774ed5b45fdf9ad5cbbd98b7f1964f1cb180b7bc6d56cffffffff01a93de702000000001976a914119fb35bad07974c1a8d47d210ca3048bb13be8788ac00000000

Установим все нужные модули:

bitcoin
ecdsa
utils
base58


pip2 install -r requirements.txt

С помощью скрипта breakECDSA.py мы узнаем публичные ключи для Биткоин Адресов

python2 breakECDSA.py 01000000017fbdd4c9991d0ba4fb0a0c06f6933442c17678bce6dfa4bf80e22ed530bb933c010000008a47304402206d0ab626a7e477c27602ed63b2651517af077e6f3fafda671dd9952dfcb5f0b90220168eb51a48ce7496a699a800299f15638e0a7f36ae84e84e26df0cd2a280a70e014104b3fdc0e84cd77cd018ced1fdd3ea4110d6beb942cfd38c0f6feaffc246e08b97fe779e87e4743f55168a476433100abd4cac064be5915cf828185319480b3fb4feffffff0240597307000000001976a914211090b628fa6351fa8240232e3c2753fd5eece588ac700369d2050000001976a914ce639943ce1602e30b249faf74388ee0eeb1d3c588ac84b90700 >> PublicKeys.txt
python2 breakECDSA.py 01000000014666d430766d611cc7f2c21494e68e463ac4be8bb2f70b91693728324849e1c3010000008a473044022057a02a4abc38e2e3e1809b05402cf52faef7e101d6364d43bb0305f8796b0fb202203d1934a016c91072ffe137575734454161284ab3371a0cfc6767db7f27f24a75014104ea7c9e85d4fb089e0b2901cd5c77f3149aa4cf711ed29a3318a4e153a67ea9cd1a22c24c8e05b66eb122db74d26fddf2cb184033fb586743ea330e15eeb8240cffffffff01b0feea0b000000001976a9148300ab0caebb6e85cf9e6b287a57924d1ac7c82f88ac00000000 >> PublicKeys.txt
python2 breakECDSA.py 01000000019d8e5e1bfac780b813e41517926aca95048e1dea92cbbe2a98475ff53ad38ccd000000008c493046022100c7b76326879a5ec7df2ffedb292a45c13c6f154982fc2cd7e05f0d0d0dce2d05022100d7fd43416608eaeb6356f04b601ac6edd23e0f82de44689fe5a7aa2f576637a001410480edda62d055008c28de19f4908cd052ccf63a10d708b5866b7a5b340bde49e2b5e7be50412afb83a6c774ed5b45fdf9ad5cbbd98b7f1964f1cb180b7bc6d56cffffffff01a93de702000000001976a914119fb35bad07974c1a8d47d210ca3048bb13be8788ac00000000 >> PublicKeys.txt

После запуска мы получаем публичные ключи на все три Биткоин Адреса.

Результат будет сохранен в файл: PublicKeys.txt

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

cat PublicKeys.txt

PUBKEY = 04b3fdc0e84cd77cd018ced1fdd3ea4110d6beb942cfd38c0f6feaffc246e08b97fe779e87e4743f55168a476433100abd4cac064be5915cf828185319480b3fb4
PUBKEY = 04ea7c9e85d4fb089e0b2901cd5c77f3149aa4cf711ed29a3318a4e153a67ea9cd1a22c24c8e05b66eb122db74d26fddf2cb184033fb586743ea330e15eeb8240c
PUBKEY = 0480edda62d055008c28de19f4908cd052ccf63a10d708b5866b7a5b340bde49e2b5e7be50412afb83a6c774ed5b45fdf9ad5cbbd98b7f1964f1cb180b7bc6d56c

Сделаем эти публичные ключи в виде точек координат (x,y):

(0xb3fdc0e84cd77cd018ced1fdd3ea4110d6beb942cfd38c0f6feaffc246e08b97 , 0xfe779e87e4743f55168a476433100abd4cac064be5915cf828185319480b3fb4)
(0xea7c9e85d4fb089e0b2901cd5c77f3149aa4cf711ed29a3318a4e153a67ea9cd , 0x1a22c24c8e05b66eb122db74d26fddf2cb184033fb586743ea330e15eeb8240c)
(0x80edda62d055008c28de19f4908cd052ccf63a10d708b5866b7a5b340bde49e2 , 0xb5e7be50412afb83a6c774ed5b45fdf9ad5cbbd98b7f1964f1cb180b7bc6d56c)

Сохраним точки координат (x,y) в файле: Coordinates.txt

BLOCKCHAIN FOLBIT LEAKS

Откроем список известных блокчейн утечек на 2019 год «BLOCKCHAIN FOLBIT LEAKS»

Скопируем значение:

dac19ec586ea8aa454fd2e7090e3244cdf75a73bdb1aa970d8b0878e75df3cae

Теперь проведем скалярное умножение по всем координатам точек (x,y) применив значение утечки: dac19ec586ea8aa454fd2e7090e3244cdf75a73bdb1aa970d8b0878e75df3cae

Изменим код maxwell.py и изменим название на scalarEC.py

Добавим with open("Coordinates.txt", "rt") as base:

Все новые координаты будут сохранены в файле: SaveBase.txt

B = 0xdac19ec586ea8aa454fd2e7090e3244cdf75a73bdb1aa970d8b0878e75df3cae

Добавим значение B из списка в код и сохраним как Python-скрипт: scalarEC.py

from ecpy.curves     import Curve,Point

with open("Coordinates.txt", "rt") as base:
    for line in base.read().splitlines():
        Gx, Gy = map(lambda v: int(v, 16), line[1: -1].split(" , "))

        cv = Curve.get_curve('secp256k1')
    
        P  = Point(Gx,Gy,cv)

        B  = 0xdac19ec586ea8aa454fd2e7090e3244cdf75a73bdb1aa970d8b0878e75df3cae

        A  = B*P

        with open("SaveBase.txt", "a") as file:
            file.write(str(A))
            file.write("\n")

Запустим скрипт:

python3 scalarEC.py

Результат сохранился в файле: SaveBase.txt

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

 cat SaveBase.txt

(0x92b9eeebb8c4fa108359bd31367e36b7fe65b4a7e06d533b476dee097572a4c0 , 0x4d2beb1835a2f8b85e3f61d32094dbf0b4c7a212bee42ee4612193c0653c6e56)
(0x65304d24c0edc862843587a96ea700f86e9e70e7801ac7df9efd2de84230c3e7 , 0x7af6d83573849d2368a021e835c5768e1b791c0c1b4cfafb9795058df5f27958)
(0x433c15b724948371877dd3c1014d59d1a13d76a29e4948903623a74767736b97 , 0x13f15f3bb28a4766952e10da9717aa3cc0bad90b0414f483718531d584721ea3)

После скалярного умножение на значение утечки по всем координатным точкам (x,y) мы получаем новые точки

Теперь переделаем эти координаты в форму несжатых публичных ключей.

Обратим внимание на этот публичный ключ:

0465304d24c0edc862843587a96ea700f86e9e70e7801ac7df9efd2de84230c3e77af6d83573849d2368a021e835c5768e1b791c0c1b4cfafb9795058df5f27958

Теперь для поиска приватного ключа применим метод Pollard's Kangaroo

Ранее мы публиковали статью: "Pollard's Kangaroo находим решения дискретного логарифма secp256k1 PRIVATE KEY + NONCES в известном диапазоне"

Воспользуемся новым кодом Pollard's Kangaroo от Telariust Python-скрипт: kangaroo.py

Установим модуль gmpy2 по команде:

sudo apt install python-gmpy2

Дальше запустим Python-скрипт: kangaroo.py

python2 kangaroo.py 32 0465304D24C0EDC862843587A96EA700F86E9E70E7801AC7DF9EFD2DE84230C3E77AF6D83573849D2368A021E835C5768E1B791C0C1B4CFAFB9795058DF5F27958

В терминале видим что мы сумели получить "prvkey":

[prvkey#32] 0x00000000000000000000000000000000000000000000000000000000795f9c63
[pubkey#32] 0465304d24c0edc862843587a96ea700f86e9e70e7801ac7df9efd2de84230c3e77af6d83573849d2368a021e835c5768e1b791c0c1b4cfafb9795058df5f27958

Результат сохранится в файл: Privkey.txt

Откроем файл командой: 

cat Privkey.txt

00000000000000000000000000000000000000000000000000000000795f9c63

Мы получили уменьшенный приватный ключ для публичного ключа:

0465304D24C0EDC862843587A96EA700F86E9E70E7801AC7DF9EFD2DE84230C3E77AF6D83573849D2368A021E835C5768E1B791C0C1B4CFAFB9795058DF5F27958

Обратите внимание на приватный ключ:

Последние 8 цифр в формате HEX совпадает с публичным ключом "Maxwell's vanity public key"

0200000000000000000000003B78CE563F89A0ED9414F5AA28AD0D96D6795F9C63

A = 0x00000000000000000000000000000000000000000000000000000000795f9c63
B = 0xdac19ec586ea8aa454fd2e7090e3244cdf75a73bdb1aa970d8b0878e75df3cae

Теперь чтобы получить приватный ключ для одного из трех Биткоин Адресов нам осталось сделать деление по модулю значение A на значение B
Privkey = ((A * modinv(B,N)) % N)

Воспользуемся Python-скриптом: calculate.py

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

A = 0x00000000000000000000000000000000000000000000000000000000795f9c63
B = 0xdac19ec586ea8aa454fd2e7090e3244cdf75a73bdb1aa970d8b0878e75df3cae


print (h(((A) * modinv(B,N)) % N))

Запустим Python-скрипт: calculate.py

python3 calculate.py

В итоге мы получим в терминале приватный ключ в формате HEX 38717b5161c2e817020a0933e1836dd0127bdef59732d77daca20ccfbf61a7ae

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

ADDR: 1MjGyKiRLzq4WeuJKyFZMmkjAv7rH1TABm
WIF:  5JF9ME7zdGLDd3oyuMG7RfwgA1ByjZb2LbSwRMwM8ZKBADFLfCx
HEX:  38717b5161c2e817020a0933e1836dd0127bdef59732d77daca20ccfbf61a7ae

Приватный ключ найден!

Биткоин кошелек восстановлен!

www.blockchain.com/btc/address/1MjGyKiRLzq4WeuJKyFZMmkjAv7rH1TABm

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

Исходный код

Telegram: https://t.me/cryptodeeptech

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

Источник: https://cryptodeep.ru/reduce-private-key

Tags:

Hubs: