Quote from: nomachine on Today at 09:44:15 AM

Quote from: bestie1549 on August 17, 2023, 01:42:59 PM

Quote from: unpluggedcoin on August 17, 2023, 12:13:32 PM

Quote from: digaran on August 14, 2023, 03:42:47 PM

Also for checkpoint.txt I just need to paste x coordinates on one line per key and save their private keys? What else do I need to change on the script?

I appreciate it.

Edit, I got it running, I just need to know what to change for addition and subtraction, should I put values in decimal? And why it won't show anything on screen? Lol it just blinks endlessly.

Here is how to tune script as per your needs:
1. xy.txt file must have x and y coordinates in decimal format with a single space between them, as I clarified earlier.
2. In checkpoints.txt file you don't need to save their private keys, why? that is whole point, because we keep starting 100 million or 1 billion pub keys' x coordinates which will work as 2 billions, so it is obvious that their private keys are from 2 to 1 billion or the last 1 billion.
3. There are 3 things that you can change, step size to be subtracted, number of steps, and number of iterations.
all these are in numbers not in points.
4. Finally, why script was blinking, is because it was loading checkpoints.txt file, In my case I had 8 GB RAM with around 5.5 GB checkpoints.txt file, on a dual core system. It was taking around half an hour before printing steps.... Be patient, if no error occur, it will start printing within half an hour.

I was also able to update the existing code to utilize almost all available CPU in your machine though leaving space for other activities and it's now 10 times faster...

Code:

from multiprocessing import Pool, cpu_count

Pcurve = 2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 -1 # The proven prime
N=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 # Number of points in the field
Acurve = 0; Bcurve = 7 # These two defines the elliptic curve. y^2 = x^3 + Acurve * x + Bcurve
Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240
Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424
GPoint = (Gx,Gy) # This is our generator point. Trillions of dif ones possible

def modinv(a, n=Pcurve):
   lm, hm = 1, 0
   low, high = a % n, n
   while low > 1:
   ratio = high // low
   nm, new = hm - lm * ratio, high - low * ratio
   lm, low, hm, high = nm, new, lm, low
   return lm % n

def ECadd(a, b):
   if a == 'O':
   return b
   if b == 'O':
   return a
   if a == b:
   LamAdd = ((3 * a[0] * a[0] + Acurve) * modinv(2 * a[1], Pcurve)) % Pcurve
   else:
   LamAdd = ((b[1] - a[1]) * modinv(b[0] - a[0], Pcurve)) % Pcurve
   x = (LamAdd * LamAdd - a[0] - b[0]) % Pcurve
   y = (LamAdd * (a[0] - x) - a[1]) % Pcurve
   return (x, y)

def ECsub(a, b):
   if b == 'O':
   return a
   if isinstance(a, str):
   a = tuple(map(int, a.split()))
   if isinstance(b, str):
   b = tuple(map(int, b.split()))
   neg_b = (b[0], -b[1] % Pcurve)
   return ECadd(a, neg_b)

def ECmul(a, b):
   result = 'O'
   while b > 0:
   if b % 2 == 1:
   result = ECadd(result, a)
   a = ECadd(a, a)
   b = b // 2
   return result

# Read the x, y coordinates from xy.txt
with open("xy.txt", "r") as f:
   x, y = map(int, f.read().strip().split())
   point = (x, y)

# Read the checkpoint x-coordinates from checkpoints.txt
with open("checkpoints.txt", "r") as f:
   checkpoints = set(map(int, f.read().strip().split()))

filename_out = "results.txt"

sub_count = 0

# read the last value of j from file
try:
   with open("j_value.txt", "r") as f:
   last_j_value = int(f.readline())
except:
   last_j_value = 0

def process_iteration(args):
   j, last_j_value, point, checkpoints, filename_out = args
   found_match = False
   sub_count = 160000000 * j
   for k in range(100001):
   if k == 0:
   pass
   else:
   sub_count += 212676479325586539664609129644855
   result = ECmul(GPoint, sub_count)
   result = ECsub(point, result)
   print(sub_count)
   if result[0] in checkpoints:
   with open(filename_out, "w") as f_out:
   subtractions = sub_count // 212676479325586539664609129644855
   f_out.write("{} {} {}".format(result[0], result[1], subtractions))
   found_match = True
   break
   return found_match

def main():
   # Read the x, y coordinates from xy.txt
   with open("xy.txt", "r") as f:
   x, y = map(int, f.read().strip().split())
   point = (x, y)

   # Read the checkpoint x-coordinates from checkpoints.txt
   with open("checkpoints.txt", "r") as f:
   checkpoints = set(map(int, f.read().strip().split()))

   filename_out = "results.txt"

   # read the last value of j from file
   try:
   with open("j_value.txt", "r") as f:
   last_j_value = int(f.readline())
   except:
   last_j_value = 0

   # Determine the number of processes to use
   num_processes = min(cpu_count(), 8) # You can adjust the number of processes

   args_list = [(j, last_j_value, point, checkpoints, filename_out) for j in range(last_j_value, 10000001)]

   with Pool(processes=num_processes) as pool:
   results = pool.map(process_iteration, args_list)

   if any(results):
   print("Found match!")
   else:
   print("No match found.")

if __name__ == "__main__":
   main()

All we need now is the checkpoint generation techniques to have enough checkpoints for the code to run even faster and maximize RAM usage

You can use ecmultiply_memo to store the results of previously computed point multiplications in the elliptic curve
group to compute the multiplication of a point a by an integer b.

Memoization helps optimize the code by storing the results of ECmul in the ecmultiply_memo dictionary for a given a and b pair.
The montgomery_ladder function takes the scalar k and point P as inputs and returns the result of the point multiplication k * P.
It uses a loop that processes each bit of the scalar k and combines point additions and doublings to compute the final result.

This algorithm is more efficient than the simple double-and-add method .

Also gmpy2 to perform modinv even faster.

Something like this :

Code:

from multiprocessing import Pool, cpu_count
import gmpy2

Pcurve = 2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 - 1 # The proven prime
N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 # Number of points in the field
Acurve = 0
Bcurve = 7 # These two define the elliptic curve. y^2 = x^3 + Acurve * x + Bcurve
Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240
Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424
GPoint = (Gx, Gy) # This is our generator point. Trillions of different ones possible

def modinv(a, n=Pcurve):
   return int(gmpy2.invert(a, n))

ecmultiply_memo = {} # Memoization dictionary for ECmul

def ECadd(a, b):
   if a == 'O':
   return b
   if b == 'O':
   return a
   if a == b:
   LamAdd = ((3 * a[0] * a[0] + Acurve) * modinv(2 * a[1], Pcurve)) % Pcurve
   else:
   LamAdd = ((b[1] - a[1]) * modinv(b[0] - a[0], Pcurve)) % Pcurve
   x = (LamAdd * LamAdd - a[0] - b[0]) % Pcurve
   y = (LamAdd * (a[0] - x) - a[1]) % Pcurve
   return (x, y)

def ECsub(a, b):
   if b == 'O':
   return a
   if isinstance(a, str):
   a = tuple(map(int, a.split()))
   if isinstance(b, str):
   b = tuple(map(int, b.split()))
   neg_b = (b[0], -b[1] % Pcurve)
   return ECadd(a, neg_b)

def ECmul(a, b):
   if a in ecmultiply_memo:
   return ecmultiply_memo[a]

   result = 'O'
   while b > 0:
   if b % 2 == 1:
   result = ECadd(result, a)
   a = ECadd(a, a)
   b = b // 2

   ecmultiply_memo[a] = result
   return result

def montgomery_ladder(k, P):
   R0, R1 = 'O', P
   for i in range(k.bit_length()):
   if k & 1:
   R0, R1 = ECadd(R0, R1), ECmul(R0, R1)
   else:
   R0, R1 = ECmul(R0, R1), ECadd(R0, R1)
   k >>= 1
   return R0

def process_iteration(args):
   j, last_j_value, point, checkpoints, filename_out = args
   found_match = False
   sub_count = 160000000 * j
   for k in range(100001):
   if k == 0:
   pass
   else:
   sub_count += 212676479325586539664609129644855
   result = montgomery_ladder(sub_count, GPoint) # Use Montgomery ladder
   result = ECsub(point, result)
   print(sub_count)
   if result[0] in checkpoints:
   with open(filename_out, "w") as f_out:
   subtractions = sub_count // 212676479325586539664609129644855
   f_out.write("{} {} {}".format(result[0], result[1], subtractions))
   found_match = True
   break
   return found_match

def main():
   # Read the x, y coordinates from xy.txt
   with open("xy.txt", "r") as f:
   x, y = map(int, f.read().strip().split())
   point = (x, y)

   # Read the checkpoint x-coordinates from checkpoints.txt
   with open("checkpoints.txt", "r") as f:
   checkpoints = set(map(int, f.read().strip().split()))

   filename_out = "results.txt"

   # read the last value of j from file
   try:
   with open("j_value.txt", "r") as f:
   last_j_value = int(f.readline())
   except:
   last_j_value = 0

   # Determine the number of processes to use
   num_processes = min(cpu_count(), 8) # You can adjust the number of processes

   args_list = [(j, last_j_value, point, checkpoints, filename_out) for j in range(last_j_value, 10000001)]

   with Pool(processes=num_processes) as pool:
   results = pool.map(process_iteration, args_list)

   if any(results):
   print("Found match!")
   else:
   print("No match found.")

if __name__ == "__main__":
   main()

While I may not be proficient in mathematical terms, I'm certainly willing to give it a try.

jessica.roy

Posts

Merits