# With the help of Lattice Attack, we received a Private Key to BITCOIN

By CryptoDeep | CRYPTODEEP | 1 Sep 2022

CRYPTO DEEP TECH

What do we know about the lattice attack?

To begin with, the  elliptic curve digital signature algorithm `(ECDSA)`  is a common digital signature scheme that we see in many of our code reviews. It has some desirable properties, but can also be very fragile to recover the private key with a side-channel attack that reveals less than one bit of the secret nonce.

`ECDSA` is a special form of the digital signature algorithm  `(DSA)``DSA` is a fairly common digital signature scheme, which is defined by three algorithms: key generation, signature, and verification. The key generation algorithm generates private and public keys;  the private key is responsible for creating signatures;  and the public key is responsible for verifying signatures.  The signature algorithm takes a message and a private key as input and generates a signature. The verification algorithm takes a message, a signature, and a public key as input and returns a value of  `true` or  `false`, indicating whether the signature is valid.

`DSA` is defined for any mathematical group, and this scheme is safe as long as the discrete logarithm problem is hard for that group. A commonly used group is the integers modulo a prime number p.

Along with this group, we will have a group generator g and some cryptographically secure  hash  function  `H`. We can assume that  `p , g` and  `H` will be common knowledge.

Key generation works by first randomly selecting a value  `x` from modulo integers  `p` . Then the value is calculated `y = g^x mod p`

The private key of the signature is  `x` , and the public key is  `y` . The signing key must be kept secret, as it is what allows signatures to be made.

The signature algorithm creates a signature from the message  `m` and the secret key x . First, a random group element is generated  `k` . This is known as a nonce, which is important when it comes to attacks.

Then the values ​​are calculated  `r = g^k mod p` and `s = ( k^-1 ( H ( m ) + xr )) mod p`

Here  `k^- 1` , is the inverse group, and  `H ( m )` is the result of computing the hash m, and interpreting the result as an integer modulo p .

The signature is defined as a pair of  `( r , s )`. (Note: if one of the  `r` or  values `s`​​is equal to  `0`, the algorithm restarts with the new value of  `k` ).

The verification algorithm receives a signature  `( r , s )`, a message  `m` and a public key y as input. Let  `ŝ = s^-1` , then the algorithm returns true if and only if  `r , s ≠ 0 и r = ( g H ( m ) y r ) ŝ` .

This validation check works because  `g^H( m ) y^r = g^H(m)+ xr = g^ks`, and therefore `(g^H(m)y^r)^ŝ = g^k = r`

A digital signature scheme is considered secure if it cannot be counterfeited.

Immutability has a formal cryptographic meaning, but at a high level it means that you cannot create signatures without knowing the secret key (unless you have copied an already existing signature created from the secret key). Proven to be  `DSA`impossible to fake under the assumption of a discrete log.

The digital signature is defined over the mathematical group. When  `DSA` used with the group of elliptic curves as this mathematical group, we call it  `ECDSA`The elliptic curve group  consists of elliptic curve points, which are pairs of  `( x , y )`, which satisfy the equation  `y^2 = x^3 + ax + b` for some  `a , b` . For this blog post, all you need to know is that using elliptic curves you can define a finite group, which means you get a group generator,  `g` (elliptic curve point) , and  addition  and  dot multiplication operations  exactly like this the same as you can with integers. Since they form a finite group, generator,`g` , will have a finite order,  `p`. This blog post will not explain or require you to know how these  elliptic curve operations work .

The secret key `x`  will still be a random value modulo integers  `p` . `ECDSA` works the same as  `DSA`, but with a different group. Now the public key  `y` is still computed as  `y = g^x` , except that g is now a point on the elliptic curve. This means that y will also be a point on the elliptic curve (previously y was an integer modulo p ). Another difference is how we calculate the value of r . We still generate a random nonce k as an integer modulo p as before. We will calculate  `g^k` , but again, `g` is a point of an elliptic curve, and, therefore,  `g^k` also. Therefore, we can calculate  `( x^k , y^k ) = g^k` and set  `r = x^k` . Now the meaning `s` can be computed as before, and we get our signature  `( r , s )`, which is still an integer modulo  `p` , as before. To check, we need to correct for the fact that we computed  `r` a little differently.

So, as before, we  compute  the value of  `( g^H(m)y^r)^ŝ` , but now that value is a point on the elliptic curve, so we take  `x`the -coordinate of that point and compare it to our value of  `r` .

Recovery  of secret keys  from reused nonces `NONCES`

Now that we understand what it is  `ECDSA` and how it works, let’s demonstrate its  fragility . Again, since this is a digital signature scheme, it is imperative that the  secret key  is never revealed to anyone other than the person signing the message.

However, if the signer ever issues the signature and also issues the used nonce, the  attacker  can immediately recover the  secret key .

Let’s say I release a signature  `( r , s )` for a message  `m` and accidentally discover that I’ve used a nonce  `k` .

Since  `s = ( k^-1 ( H ( m ) + xr )),` we can easily calculate the secret key:

`s = (k^-1(H(m) + xr))`

`ks = H(m) + xr`

`ks – H(m) = xr`

`x = r^-1(ks – H(m))`

Therefore, the signer must not only keep their  private key secret , but all of their nonces they have ever generated are secret.

Even if the signer keeps each  nonce `NONCES` secret , if he accidentally repeats one  nonce `NONCES`  (even for different messages),  the secret key  can also be  recovered immediately .

Let  `( r , s 1 )` and  `( r , s 2 )` be two signatures created on messages  `m 1` and  `m 2` (respectively) from the same nonce  `k` — since they have the same nonce, the r values ​​will be the same, so this is very easy for an attacker to detect:

`s1 = k^-1(H(m1) + xr) and s2 = k^-1(H(m2) + xr)`

`s1 – s2 = k^-1(H(m1) – H(m2))`

`k(s1 – s2) = H(m1) – H(m2)`

`k = (s1 – s2)^-1(H(m1) – H(m2))`

Once we have recovered the nonce  `k` using the above formula, we can recover the private key by performing the previously described attack.

## Let’s digest this for a moment.

If  the signing nonce `NONCES`  is ever disclosed, the  secret key can be immediately  recovered , which  breaks our entire signature scheme .

Also, if two nonces ever repeat, no matter what the messages are,  an attacker  can easily detect this and immediately  recover the secret key , again breaking our whole scheme.

It’s pretty fragile and it’s only  light attacks !

But there is a  new  Lattice At tack  which has been described in great detail  (Joachim Breitner and Nadia Heninger)`Йоахим Брайтнер и Надя Хенингер`

Document  [PDF] :  Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies

## In the Bitcoin blockchain, we found a certain transaction:

and we managed to multiply the fake signatures and apply the lattice

where using the  Python script  algorithmLLL.py  with the installation of packages in  GOOGLE COLAB

INSTALL >> SAGE + ECDSA + BITCOIN + algorithm LLL

We managed to get  `Private Key` to  `Bitcoin Wallet` from one weak transaction in  `ECDSA`.

Installation Run Bash script: lattice.sh Result in HEX format Private key found! File: ONESIGN.txt (ECDSA Signature R, S, Z Value) We propagated fake signatures for the Python script algorithmLLL.py File: PRIVATEKEY.txt File: ADDRESS.txt Checking the private key on the bitaddress website

Private key found!

``````ADDR: 15N1KY5ohztgCXtEe13BbGRk85x2FPgW8E
WIF:  5JCAmNLXeSwi2SCgNH7wRL5qSQhPa7sZvj8eDwxisY5hJm8Uh92

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

https://youtu.be/YP4Xj6gUcf4 — Video footage

[email protected] — Email for all questions

https://t.me/cryptodeep_tech — Technical support via Telegram

https://cryptodeeptech.ru/lattice-attack — Source

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.