Bitcoin Forum

Bitcoin => Development & Technical Discussion => Topic started by: dexizer7799 on April 11, 2024, 06:54:58 AM



Title: Private Key FInder / Lattice Attack
Post by: dexizer7799 on April 11, 2024, 06:54:58 AM
This script find nonce up to 125 bits need to increase it to 256 or more bits

Quote
import ecdsa
import random
import libnum
import olll
import hashlib
import sys
 
G = ecdsa.SECP256k1.generator
order = G.order()

print ("Curve detail")
print (G.curve())
print ("Order:",order)
print ("Gx:",G.x())
print ("Gy:",G.y())

priv = random.randrange(1, 2 ** 256)
 
Public_key = ecdsa.ecdsa.Public_key(G, G * priv)
Private_key = ecdsa.ecdsa.Private_key(Public_key, priv)
 
k1 = random.randrange(1, 2 ** 125)
k2 = random.randrange(1, 2 ** 125)
k3 = random.randrange(1, 2 ** 100)

m1 = random.randrange(1, 2 ** 256)
m2 = random.randrange(1, 2 ** 256)
m3 = random.randrange(1, 2 ** 256)
 
sig1 = Private_key.sign(m1, k1)
sig2 = Private_key.sign(m2, k2)
sig3 = Private_key.sign(m3, k3)

print ("Private key: ",priv)

r1 = sig1.r
r1_inv = libnum.invmod(sig1.r, order)

s1 = sig1.s
s1_inv = libnum.invmod(sig1.s, order)

r2 = sig2.r
r2_inv = libnum.invmod(sig2.r, order)

s2 = sig2.s
s2_inv = libnum.invmod(sig2.s, order)

r3 = sig3.r
r3_inv = libnum.invmod(sig3.r, order)

s3 = sig3.s
s3_inv = libnum.invmod(sig3.s, order)

for i in range(1, 257):
   print(i)
   
   matrix = [
      [int(order), 0, 0, 0],
      [0, int(order), 0, 0],
      [int(r1 * s1_inv), 0, float((2 ** i)), 0],
      [int(m1 * s1_inv), 0, 0, 1]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print('5555')
         
         exit()
   
   matrix = [
      [int(order), 0, 0, 0],
      [0, int(order), 0, 0],
      [int(r1 * s1_inv), 0, float((2 ** i)), 0],
      [int(m1 * s1_inv), 0, 0, order]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print('222')
         
         exit()
   
   matrix = [
      [int(order), 0, 0, 0],
      [0, int(order), 0, 0],
      [int(r1 * s1_inv), 0, float((2 ** i) / order), 0],
      [int(m1 * s1_inv), 0, 0, order]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print('wwww')
         
         exit()
         
   matrix = [
      [int(order), 0, 0, 0],
      [0, int(order), 0, 0],
      [int(r1 * s1_inv), 0, float((2 ** i) / order), 0],
      [int(m1 * s1_inv), 0, 0, 1]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()
         
   matrix = [
      [int(order), 0, 0, 0],
      [0, int(order), 0, 0],
      [int(r1 * s1_inv), 0, 1, 0],
      [int(m1 * s1_inv), 0, 0, order]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()
         
   matrix = [
      [int(order), 0, 0, 0],
      [0, 1, 0, 0],
      [int(r1 * s1_inv), 0, 1, 0],
      [int(m1 * s1_inv), 0, 0, int(order)]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()
         
   matrix = [
      [1, 0, 0, 0],
      [0, 1, 0, 0],
      [int(r1 * s1_inv), 0, 1, 0],
      [int(m1 * s1_inv), 0, 0, int(order)]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")
         
         print (try_private_key)
         
         exit()
         
   matrix = [
      [1, 0, 0, 0],
      [0, 1, 0, 0],
      [int(r1 * s1_inv), 0, 1, 0],
      [int(m1 * s1_inv), 0, 0, 1]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()
         
   matrix = [
      [1, 0, 0, 0],
      [0, float((2 ** i) / order), 0, 0],
      [int(r1 * s1_inv), 0, 1, 0],
      [int(m1 * s1_inv), 0, 0, int(order)]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")
         
         print (try_private_key)
         
         exit()
         
   matrix = [
      [1, 0, 0, 0],
      [0, 1, 0, 0],
      [int(r1 * s1_inv), 0, int(order), 0],
      [int(m1 * s1_inv), 0, 0, float((2 ** i) / order)]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()
         
   matrix = [
      [float((2 ** i) / order), 0, 0, 0],
      [0, 1, 0, 0],
      [int(r1 * s1_inv), 0, int(order), 0],
      [int(m1 * s1_inv), 0, 0, float((2 ** i) / order)]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()
   
   matrix = [
      [int(order), 0, 0, 0],
      [0, int(order), 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), float((2 ** i)), 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, 1]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print('qewqweew')
         
         exit()
   
   matrix = [
      [int(order), 0, 0, 0],
      [0, int(order), 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), float((2 ** i)), 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, order]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print('bccvcv')
         
         exit()
   
   matrix = [
      [int(order), 0, 0, 0],
      [0, int(order), 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), float((2 ** i) / order), 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, order]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print('888888')
         
         exit()
         
   matrix = [
      [int(order), 0, 0, 0],
      [0, int(order), 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), float((2 ** i) / order), 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, 1]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()
         
   matrix = [
      [int(order), 0, 0, 0],
      [0, int(order), 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), 1, 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, order]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()
         
   matrix = [
      [int(order), 0, 0, 0],
      [0, 1, 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), 1, 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, int(order)]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()
         
   matrix = [
      [1, 0, 0, 0],
      [0, 1, 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), 1, 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, int(order)]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")
         
         print (try_private_key)
         
         exit()
         
   matrix = [
      [1, 0, 0, 0],
      [0, 1, 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), 1, 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, 1]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()
         
   matrix = [
      [1, 0, 0, 0],
      [0, float((2 ** i) / order), 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), 1, 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, int(order)]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")
         
         print (try_private_key)
         
         exit()
         
   matrix = [
      [1, 0, 0, 0],
      [0, 1, 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), int(order), 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, float((2 ** i) / order)]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()
         
   matrix = [
      [float((2 ** i) / order), 0, 0, 0],
      [0, 1, 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), int(order), 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, float((2 ** i) / order)]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()

   matrix = [
      [float((2 ** i) / order), 0, 0, 0],
      [0, 1, 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), 1, 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, float((2 ** i) / order)]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()
         
   matrix = [
      [float((2 ** i)), 0, 0, 0],
      [0, 1, 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), 1, 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, float((2 ** i))]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()
   
   matrix = [
      [float((2 ** i)), 0, 0, 0],
      [0, 1, 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), int(order), 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, float((2 ** i))]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()

   matrix = [
      [int(order), 0, 0, 0],
      [0, int(order), 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), float((2 ** i)), 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, 1]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print('qweqe')
         
         exit()
   
   matrix = [
      [int(order), 0, 0, 0],
      [0, int(order), 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), float((2 ** i)), 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, order]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print('asdffsd')
         
         exit()
   
   matrix = [
      [int(order), 0, 0, 0],
      [0, int(order), 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), float((2 ** i) / order), 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, order]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")
         
         exit()
         
   matrix = [
      [int(order), 0, 0, 0],
      [0, int(order), 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), float((2 ** i) / order), 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, 1]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()
         
   matrix = [
      [int(order), 0, 0, 0],
      [0, int(order), 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), 1, 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, order]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()
         
   matrix = [
      [int(order), 0, 0, 0],
      [0, 1, 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), 1, 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, int(order)]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()

   matrix = [
      [int(order), 0, 0, 0],
      [0, 1, 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), 1, 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, int(order)]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()


But when I increase it up to 130 or more bits it do not find the right key we need to rewrite the script to make it up to 256 bits or more. Script written by me.

Quote
import ecdsa
import random
import libnum
import olll
import hashlib
import sys
 
G = ecdsa.SECP256k1.generator
order = G.order()

print ("Curve detail")
print (G.curve())
print ("Order:",order)
print ("Gx:",G.x())
print ("Gy:",G.y())

priv = random.randrange(1, 2 ** 256)
 
Public_key = ecdsa.ecdsa.Public_key(G, G * priv)
Private_key = ecdsa.ecdsa.Private_key(Public_key, priv)
 
k1 = random.randrange(1, 2 ** 135)
k2 = random.randrange(1, 2 ** 135)
k3 = random.randrange(1, 2 ** 100)

m1 = random.randrange(1, 2 ** 256)
m2 = random.randrange(1, 2 ** 256)
m3 = random.randrange(1, 2 ** 256)
 
sig1 = Private_key.sign(m1, k1)
sig2 = Private_key.sign(m2, k2)
sig3 = Private_key.sign(m3, k3)

print ("Private key: ",priv)

r1 = sig1.r
r1_inv = libnum.invmod(sig1.r, order)

s1 = sig1.s
s1_inv = libnum.invmod(sig1.s, order)

r2 = sig2.r
r2_inv = libnum.invmod(sig2.r, order)

s2 = sig2.s
s2_inv = libnum.invmod(sig2.s, order)

r3 = sig3.r
r3_inv = libnum.invmod(sig3.r, order)

s3 = sig3.s
s3_inv = libnum.invmod(sig3.s, order)

for i in range(1, 257):
   print(i)
   
   matrix = [
      [int(order), 0, 0, 0],
      [0, int(order), 0, 0],
      [int(r1 * s1_inv), 0, float((2 ** i)), 0],
      [int(m1 * s1_inv), 0, 0, 1]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print('5555')
         
         exit()
   
   matrix = [
      [int(order), 0, 0, 0],
      [0, int(order), 0, 0],
      [int(r1 * s1_inv), 0, float((2 ** i)), 0],
      [int(m1 * s1_inv), 0, 0, order]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print('222')
         
         exit()
   
   matrix = [
      [int(order), 0, 0, 0],
      [0, int(order), 0, 0],
      [int(r1 * s1_inv), 0, float((2 ** i) / order), 0],
      [int(m1 * s1_inv), 0, 0, order]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print('wwww')
         
         exit()
         
   matrix = [
      [int(order), 0, 0, 0],
      [0, int(order), 0, 0],
      [int(r1 * s1_inv), 0, float((2 ** i) / order), 0],
      [int(m1 * s1_inv), 0, 0, 1]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()
         
   matrix = [
      [int(order), 0, 0, 0],
      [0, int(order), 0, 0],
      [int(r1 * s1_inv), 0, 1, 0],
      [int(m1 * s1_inv), 0, 0, order]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()
         
   matrix = [
      [int(order), 0, 0, 0],
      [0, 1, 0, 0],
      [int(r1 * s1_inv), 0, 1, 0],
      [int(m1 * s1_inv), 0, 0, int(order)]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()
         
   matrix = [
      [1, 0, 0, 0],
      [0, 1, 0, 0],
      [int(r1 * s1_inv), 0, 1, 0],
      [int(m1 * s1_inv), 0, 0, int(order)]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")
         
         print (try_private_key)
         
         exit()
         
   matrix = [
      [1, 0, 0, 0],
      [0, 1, 0, 0],
      [int(r1 * s1_inv), 0, 1, 0],
      [int(m1 * s1_inv), 0, 0, 1]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()
         
   matrix = [
      [1, 0, 0, 0],
      [0, float((2 ** i) / order), 0, 0],
      [int(r1 * s1_inv), 0, 1, 0],
      [int(m1 * s1_inv), 0, 0, int(order)]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")
         
         print (try_private_key)
         
         exit()
         
   matrix = [
      [1, 0, 0, 0],
      [0, 1, 0, 0],
      [int(r1 * s1_inv), 0, int(order), 0],
      [int(m1 * s1_inv), 0, 0, float((2 ** i) / order)]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()
         
   matrix = [
      [float((2 ** i) / order), 0, 0, 0],
      [0, 1, 0, 0],
      [int(r1 * s1_inv), 0, int(order), 0],
      [int(m1 * s1_inv), 0, 0, float((2 ** i) / order)]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()
   
   matrix = [
      [int(order), 0, 0, 0],
      [0, int(order), 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), float((2 ** i)), 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, 1]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print('qewqweew')
         
         exit()
   
   matrix = [
      [int(order), 0, 0, 0],
      [0, int(order), 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), float((2 ** i)), 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, order]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print('bccvcv')
         
         exit()
   
   matrix = [
      [int(order), 0, 0, 0],
      [0, int(order), 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), float((2 ** i) / order), 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, order]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print('888888')
         
         exit()
         
   matrix = [
      [int(order), 0, 0, 0],
      [0, int(order), 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), float((2 ** i) / order), 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, 1]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()
         
   matrix = [
      [int(order), 0, 0, 0],
      [0, int(order), 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), 1, 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, order]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()
         
   matrix = [
      [int(order), 0, 0, 0],
      [0, 1, 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), 1, 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, int(order)]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()
         
   matrix = [
      [1, 0, 0, 0],
      [0, 1, 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), 1, 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, int(order)]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")
         
         print (try_private_key)
         
         exit()
         
   matrix = [
      [1, 0, 0, 0],
      [0, 1, 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), 1, 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, 1]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()
         
   matrix = [
      [1, 0, 0, 0],
      [0, float((2 ** i) / order), 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), 1, 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, int(order)]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")
         
         print (try_private_key)
         
         exit()
         
   matrix = [
      [1, 0, 0, 0],
      [0, 1, 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), int(order), 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, float((2 ** i) / order)]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()
         
   matrix = [
      [float((2 ** i) / order), 0, 0, 0],
      [0, 1, 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), int(order), 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, float((2 ** i) / order)]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()

   matrix = [
      [float((2 ** i) / order), 0, 0, 0],
      [0, 1, 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), 1, 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, float((2 ** i) / order)]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()
         
   matrix = [
      [float((2 ** i)), 0, 0, 0],
      [0, 1, 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), 1, 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, float((2 ** i))]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()
   
   matrix = [
      [float((2 ** i)), 0, 0, 0],
      [0, 1, 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), int(order), 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, float((2 ** i))]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()

   matrix = [
      [int(order), 0, 0, 0],
      [0, int(order), 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), float((2 ** i)), 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, 1]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print('qweqe')
         
         exit()
   
   matrix = [
      [int(order), 0, 0, 0],
      [0, int(order), 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), float((2 ** i)), 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, order]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print('asdffsd')
         
         exit()
   
   matrix = [
      [int(order), 0, 0, 0],
      [0, int(order), 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), float((2 ** i) / order), 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, order]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")
         
         exit()
         
   matrix = [
      [int(order), 0, 0, 0],
      [0, int(order), 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), float((2 ** i) / order), 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, 1]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()
         
   matrix = [
      [int(order), 0, 0, 0],
      [0, int(order), 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), 1, 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, order]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()
         
   matrix = [
      [int(order), 0, 0, 0],
      [0, 1, 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), 1, 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, int(order)]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()

   matrix = [
      [int(order), 0, 0, 0],
      [0, 1, 0, 0],
      [int(r1 * s1_inv), int(r2 * s2_inv), 1, 0],
      [int(m1 * s1_inv), int(m2 * s2_inv), 0, int(order)]
   ]

   search_matrix = olll.reduction(matrix, 0.75)
   
   for search_row in search_matrix:
      possible_k1 = search_row[0]
      try_private_key = (r1_inv * ((possible_k1 * s1) - m1)) % order
   
      if ecdsa.ecdsa.Public_key(G, G * try_private_key) == Public_key:
         print("\nThe private key has been found")

         print (try_private_key)
         
         exit()



Title: Re: Private Key FInder / Lattice Attack
Post by: iceland2k14 on April 11, 2024, 11:51:26 AM
This is because you have hardcoded your script to use 3 signatures. When the Leakage bits decreases below 128 you might need more and more signatures as you move up.

Check here  https://github.com/iceland2k14/rsz/blob/main/LLL_nonce_leakage.py  (https://github.com/iceland2k14/rsz/blob/main/LLL_nonce_leakage.py)
for the generalized Matrix form reduction and also the function Minimum_Signature_Required for each Leakage bits.


Title: Re: Private Key FInder / Lattice Attack
Post by: dexizer7799 on April 11, 2024, 12:10:31 PM
This is because you have hardcoded your script to use 3 signatures. When the Leakage bits decreases below 128 you might need more and more signatures as you move up.

Check here  https://github.com/iceland2k14/rsz/blob/main/LLL_nonce_leakage.py  (https://github.com/iceland2k14/rsz/blob/main/LLL_nonce_leakage.py)
for the generalized Matrix form reduction and also the function Minimum_Signature_Required for each Leakage bits.

Hi sir, I tried to construct my script with 3 signatures but each time I got wrong private keys so I tried to use your script it works perfectly but when I change this variable it don't work

this

nonces = [random.randrange(1, 2**kbits) + fixed_k_prefix for i in range(n)]

to this one

nonces = [random.randrange(1, N) for i in range(n)]


Title: Re: Private Key FInder / Lattice Attack
Post by: dexizer7799 on April 11, 2024, 01:01:55 PM
This is because you have hardcoded your script to use 3 signatures. When the Leakage bits decreases below 128 you might need more and more signatures as you move up.

Check here  https://github.com/iceland2k14/rsz/blob/main/LLL_nonce_leakage.py  (https://github.com/iceland2k14/rsz/blob/main/LLL_nonce_leakage.py)
for the generalized Matrix form reduction and also the function Minimum_Signature_Required for each Leakage bits.

Hi sir, I tried to construct my script with 3 signatures but each time I got wrong private keys so I tried to use your script it works perfectly but when I change this variable it don't work

this

nonces = [random.randrange(1, 2**kbits) + fixed_k_prefix for i in range(n)]

to this one

nonces = [random.randrange(1, N) for i in range(n)]

Ok sir I understand you now I solve up to 210 bits! Thank You.