import hashlib
import secrets
import libnum

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
K = GF(p)
a = K(0x0000000000000000000000000000000000000000000000000000000000000000)
b = K(0x0000000000000000000000000000000000000000000000000000000000000007)
E = EllipticCurve(K, (a, b))
G = E(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
E.set_order(0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 * 0x1)

q = E.order()

privateKey = secrets.randbelow(int(q))

pub = privateKey * G

print("Private Key :=> " + str(privateKey))

def sign(m, d, k = None):
   z = int.from_bytes(hashlib.sha256(m).digest(), 'big')
   
   if k == None:
      k = secrets.randbits(256)
   
   P = k * G
   x1 = int(P.xy()[0])

   r = int(x1 % q)
   s = int(pow(k, -1, q) * (z + r * d) % q)
   
   return (r, s, z)

def _forgeSignature(r, s, z, bits = 256):
   newR, newS, newZ = None, None, None

   R = E.lift_x(Integer(r))

   r_ = int(((int(pow(4, -1, q)) * int(2 ** bits - 1) * G) - (int(pow(4, -1, q)) * R)).xy()[0])
   s_ = int((-r_ * s * int(pow(r, -1, q)) * 4) % q)
   z_ = int(int(pow(4, -1, q)) * s_ * int(2 ** bits - 1 - int(pow(s, -1, q)) * z) % q)
   
   w_ = pow(s_, -1, q)
   
   u1_ = int(z_ * w_ % q)
   u2_ = int(r_ * w_ % q)
   
   if (u1_ * G + u2_ * pub).xy()[0] == r_:
      newR = r_
      newS = s_
      newZ = z_

   return newR, newS, newZ

def forgeSignature(r, s, z, bits = 256):
   newR, newS, newZ = _forgeSignature(r, s, z, bits)
   
   return newR, newS, newZ

nonce = secrets.randbelow(int(q))

print("\nNonce :=> " + str(nonce))

r1, s1, z1 = sign(b'Hello World 1', privateKey, nonce)

r2, s2, z2 = sign(b'Hello World 2', privateKey, nonce)

r1, s1, z1 = forgeSignature(r1, s1, z1)

r2, s2, z2 = forgeSignature(r2, s2, z2)

temp = libnum.invmod((s1 - s2), q)

recoveredK = ((z1 - z2) * temp) % q

print("\n\nRecovered K :=> " + str(recoveredK))

recoveredPriv = (libnum.invmod(r1, q) * ((s1 * recoveredK) - z1)) % q

print("\nRecovered PrivateKey :=> " + str(recoveredPriv))

if privateKey == recoveredPriv:
   print("\nSuccessfully Recovered")

import hashlib
import secrets
import libnum

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
K = GF(p)
a = K(0x0000000000000000000000000000000000000000000000000000000000000000)
b = K(0x0000000000000000000000000000000000000000000000000000000000000007)
E = EllipticCurve(K, (a, b))
G = E(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
E.set_order(0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 * 0x1)

q = E.order()

privateKey = secrets.randbelow(int(q))

pub = privateKey * G

print("Private Key :=> " + hex(privateKey))

def sign(m, d, k = None):
   z = int.from_bytes(hashlib.sha256(m).digest(), 'big')
   
   if k == None:
      k = secrets.randbits(256)
   
   P = k * G
   x1 = int(P.xy()[0])

   r = int(x1 % q)
   s = int(pow(k, -1, q) * (z + r * d) % q)
   
   return (r, s, z)

def _forgSignature(r, s, z, bits = 256):
   newR, newS, newZ = 0, 0, 0

   R = E.lift_x(Integer(r))

   r_ = int(((int(pow(4, -1, q)) * int(2 ** bits - 1) * G) - (int(pow(4, -1, q)) * R)).xy()[0])
   s_ = int((-r_ * s * int(pow(r, -1, q)) * 4) % q)
   z_ = int(int(pow(4, -1, q)) * s_ * int(2 ** bits - 1 - int(pow(s, -1, q)) * z) % q)
   
   w_ = pow(s_, -1, q)
   
   u1_ = int(z_ * w_ % q)
   u2_ = int(r_ * w_ % q)
   
   if (u1_ * G + u2_ * pub).xy()[0] == r_:
      newR = r_
      newS = s_
      newZ = z_

   return int(newR), int(newS), int(newZ)

def forgeSignature(r, s, z, bits = 256):
   newR, newS, newZ = _forgSignature(r, s, z, bits)
   
   return int(newR), int(newS), int(newZ)

def getk1(r1, s1, z1, r2, s2, z2, m):
   nr = (s2 * m * r1 + z1 * r2 - z2 * r1) % q
   dr = (s1 * r2 - s2 * r1) % q

   return (nr * pow(dr, q - 2, q)) % q

def getpvk(r1, s1, z1, r2, s2, z2, m):
   x1 = (s2 * z1 - s1 * z2 + m * s1 * s2) % q
   xi = pow(s1 * r2 - s2 * r1, q - 2, q) % q
   x = (x1 * xi) % q

   return x

while True:
   try:
      nonce1 = secrets.randbelow(int(q))

      r1, s1, z1 = sign(b'Hello World 1', privateKey, nonce1)

      r1, s1, z1 = forgeSignature(r1, s1, z1, 250)

      r2, s2, z2 = forgeSignature(r1, s1, z1, 252)

      nonce1 = lift(mod((z1 + privateKey * Integer(r1)) * inverse_mod(s1, q), q))

      nonce2 = lift(mod((z2 + privateKey * Integer(r2)) * inverse_mod(s2, q), q))

      diff = (int(nonce2) - int(nonce1)) % q

      k = getk1(r1, s1, z1, r2, s2, z2, diff)
      x = getpvk(r1, s1, z1, r2, s2, z2, diff)

      print()

      print(f'Recovered Private Key :=> {hex(x)}')
      
      break;
   except:
      """"""

Even if there are 1000 signatures, but some of them have k values ​​of 250~256 bits
As long as there are some signatures with k between 254 ~ 256 ,
the lattice attack cannot solve it...
because we know nothing about k , not even 1 bit can't sure

Hi ,

I hope this message finds you well. I came across your project that involves recovering up to 249 bits for a 256-bit private key. Unfortunately, I found that the GitHub link you provided is not working.

Would you be able to share the script with me directly? I would really appreciate it, as I’m very interested in your work.

Thank you for your time!

Best regards,

fix this >>>User 'dexizer7799' has not chosen to allow messages from newbies. You should post in their relevant thread to remind them to enable this setting. 

"""

This code created by Dexizer

It will recover Ecdsa Secp256K1 private key up to 249 bits and with up to 256 bits k nonces.

"""

import random

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
K = GF(p)
a = K(0x0000000000000000000000000000000000000000000000000000000000000000)
b = K(0x0000000000000000000000000000000000000000000000000000000000000007)
E = EllipticCurve(K, (a, b))
G = E(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)

q = E.order()

n = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f

def identityPlus2(u, elem=1):
   result = [[0] * (u + 2) for _ in range(u)]
   
   for i in range(u):
      result = elem
   
   return result

def basis():
   matrix = identityPlus2(len(signatures), p)
   
   t = []
   
   for signature in signatures:
      t.append(signature[0] * inverse_mod(signature[1], p))
   
   t.append(B / q)
   t.append(0)
   
   a = []
   
   for signature in signatures:
      a.append(signature[2] * inverse_mod(signature[1], p))
   
   a.append(0)
   a.append(B)
   
   matrix.append(t)
   matrix.append(a)

   return Matrix(QQ, matrix)

def attack():
   M = basis()
   
   positiveKeys = []
   unPositiveKeys = []
   
   for r in M.LLL():
      for key in r:
         key = int(key)
      
         if key != 0 and key != q:
            if key > 0:
               positiveKeys.append(key)
            else:
               unPositiveKeys.append(key)

   recoveredPrivateKey = 0
   
   for key in positiveKeys:
      for signature in signatures:
         if key != 0:
            d = int((signature[1] * Mod(key, p) - signature[2]) * inverse_mod(signature[0], p))
            
            if d == secret:
               recoveredPrivateKey = d
   
   if recoveredPrivateKey == 0:
      k = M.LLL()[1][0]
   
      if k != 0:
         recoveredPrivateKey = (signatures[0][1] * Mod(k, p) - signatures[0][2]) * inverse_mod(signatures[0][0], p)

   return int(recoveredPrivateKey)

num = 180

secret = random.randrange(1, n)

Q = secret * G

print('Private Key:', secret, 'Bit Length:', int(secret).bit_length())

print()

kbits = 249

B = 1

z = [random.randrange(1, n) for i in range(num)]
nonces = [random.randrange(1, 2 ** kbits) for i in range(num)]
sigsR = [int((G * int(nonces)).xy()[0]) for i in range(num)]
modInvNonces = [inverse_mod(nonces, p) for i in range(num)]
sigsS = [(z + secret * sigsR) * modInvNonces % n for i in range(num)]
sinv = [inverse_mod(s, p) for s in sigsS]

signatures = []

for i in range(len(sigsR)):
   signatures.append([sigsR, sigsS, z])

d = attack()

print('Recovered Private Key:', d, 'Bit Length:', int(d).bit_length())

if d == secret:
   print()
   print('Private Key Found!!!')
   print('Private Key Successfully Recovered:', d, 'Bit Length:', int(d).bit_length())

Hello. Looks like topic deleted. Nothing to try. Can you provide script for testing?

Hello sir i saw your impressive work,it looks very complicated and much more apprpachable your lattice attack than other try-hards,do you have a way to contact you via internet?i tried to use wayback machine to access your github account but i didnt find nothing,i want to hear from you,i have some secrets of mine also to share

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f ** 2

I tried this P and I basically get like P * regular curves (I am not sure how to explain)

So the structure and order of points are the same nothing changes


so for
Private key 3 and private key fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364144
I get the same point

Maybe I am doing something wrong

Anyone here to discussion about change N order in secp256k1?

Are you sure this works? I'm getting the error:


Also I'm not quite sure this makes any sense when you're trying to define the cardinality, especially trying to set the same cardinality of the initial curve.

Are you sure this works? I'm getting the error:


Also I'm not quite sure this makes any sense when you're trying to define the cardinality, especially trying to set the same cardinality of the initial curve.

Could you please explain what do you mean by p^2 exactly?

Could you please explain what do you mean by p^2 exactly?

Hello,
I have 2 questions;
first; can a wallet with at least 10 pairs of transactions with only 5 characters in common in the R value be cracked with a Lattice attack etc. method?

second; for a single pair, the probability is approximately 1 in a million, how can it be 10 times.

I cannot create R in such a pattern even if I want to by giving the k(nonce) value weak. How could this have happened?

(I apologize for my translation English.)

Hello,
I have 2 questions;
first; can a wallet with at least 10 pairs of transactions with only 5 characters in common in the R value be cracked with a Lattice attack etc. method?

second; for a single pair, the probability is approximately 1 in a million, how can it be 10 times.

I cannot create R in such a pattern even if I want to by giving the k(nonce) value weak. How could this have happened?

(I apologize for my translation English.)

You have the curve equation in all cases: "y^2=x^3+b". So, to calculate x-value or y-value, you have that:
So, the most basic use case, is just to get a valid point on a curve. You pick x-value, and want to calculate y-value, or the other way around: for a given y-value, you want to get a valid x-value. And that means, when you generate a curve, you want to make those operations "easy". And I wonder, why it is the case in all three other curves, but doesn't work in case of secp224k1 specifically.

All point coordinates are in range from 1 to (p-1). And then, private keys are in range from 1 to (n-1), but n-value is calculated later, when you already know p-value.

For y²=x³+d (mod p), and d being non-zero integer, the group falls into one of these different sets:

1: 2x  2 * 3 * 20412485227 * 83380711482738671590122559 * 5669387787833452836421905244327672652059
2: 3x  3 * 13² * 3319 * 22639 * 1013176677300131846900870239606035638738100997248092069256697437031
3:     109903 * 12977017 * 383229727 * 211853322379233867315890044223858703031485253961775684523
4:     3 * 199 * 18979 * 5128356331187950431517 * 1992751017769525324118900703535975744264170999967
6: 14x 2 * 7 * 10903 * 5290657 * 10833080827 * 22921299619447 * 41245443549316649091297836755593555342121
7:     115792089237316195423570985008687907852837564279074904382605163141518161494337

Here 'x' is the torsion group - then the group is noncyclic (as a whole).

One can move between different d by multiplying the whole equation by k⁶, and getting the new coordinates with the new d (the usual isomorphism):

y² = x³ + d
k⁶*y² = k⁶*x³ + k⁶*d
(k³*y)² = (k²*x)³ + k⁶*d


Trying to move between these six groups doesn't work - either k³ and/or k² are outside the usual group of numbers mod p.

If one thinks a bit it is obvious. Groups have different number of points, so - when trying to map - every point from one group corresponds to all the points in another.

So, only thing needing in order to jump to an isomorphic equation is taking sixth root of some number a (mod p).

a^p = a
a^p+1 = a²
a^(p+1)/4 = a^1/2

a^p+2 = a³
a^(p+2)/9 = a^1/3

(a^(p+1)/4)^(p+2)/9 = a^1/6 = k

One should then check if this root exists, i.e. if k⁶=a

For y²=x³+d (mod p), and d being non-zero integer, the group falls into one of these different sets:

1: 2x  2 * 3 * 20412485227 * 83380711482738671590122559 * 5669387787833452836421905244327672652059
2: 3x  3 * 13² * 3319 * 22639 * 1013176677300131846900870239606035638738100997248092069256697437031
3:     109903 * 12977017 * 383229727 * 211853322379233867315890044223858703031485253961775684523
4:     3 * 199 * 18979 * 5128356331187950431517 * 1992751017769525324118900703535975744264170999967
6: 14x 2 * 7 * 10903 * 5290657 * 10833080827 * 22921299619447 * 41245443549316649091297836755593555342121
7:     115792089237316195423570985008687907852837564279074904382605163141518161494337

Here 'x' is the torsion group - then the group is noncyclic (as a whole).

One can move between different d by multiplying the whole equation by k⁶, and getting the new coordinates with the new d (the usual isomorphism):

y² = x³ + d
k⁶*y² = k⁶*x³ + k⁶*d
(k³*y)² = (k²*x)³ + k⁶*d


Trying to move between these six groups doesn't work - either k³ and/or k² are outside the usual group of numbers mod p.

If one thinks a bit it is obvious. Groups have different number of points, so - when trying to map - every point from one group corresponds to all the points in another.

So, only thing needing in order to jump to an isomorphic equation is taking sixth root of some number a (mod p).

a^p = a
a^p+1 = a²
a^(p+1)/4 = a^1/2

a^p+2 = a³
a^(p+2)/9 = a^1/3

(a^(p+1)/4)^(p+2)/9 = a^1/6 = k

One should then check if this root exists, i.e. if k⁶=a

I'm here again. I noticed a group of people still determined to somehow break Bitcoin wallets using this attack, especially the one implemented by
https://github.com/KrashKrash/Twist-Attack-Sub-Group-Attack

 First, how would this attack work?
 Partial Private Key Collection: 
- Calculate small subgroups of each twist curve and attempt to compute the discrete logarithm within these subgroups to obtain partial private keys. 

  Coprime Verification:
- After collecting all partial private keys, verify if the subgroup orders are pairwise coprime, which is a requirement for applying the CRT (Chinese Remainder Theorem). 

  Combining Partial Keys Using CRT:
- If the subgroup orders are pairwise coprime, calculate the combined modulus by multiplying all subgroup orders. 
- Use CRT to combine the partial private keys modulo their respective subgroup orders to obtain the private key modulo the combined modulus. 
- If the combined modulus is greater than the order n of the secp256k1 curve, the private key modulo n can be recovered. 

 Alright, but in practice, this doesn't work.
Why? Because the combined modulus is, in most cases (if not all), much smaller than n, making recovery impossible. 

  Second point:
The cofactors of the secp256k1 curve are 1. This means there are no small-order subgroups within the curve that could be exploited. Additionally, the twist of secp256k1 also has a large prime order, similar to the original curve. 

  Third point:
Bitcoin implementations, such as the "libsecp256k1" library, perform checks to ensure that the points used are indeed on the curve. This prevents you from, for example, using points belonging to the twist or off-curve points to try and extract private key information. 

  In summary, these characteristics make the attack unfeasible.


If I made any mistakes in my explanation or spelling (English is not my native language), feel free to correct me.