I do not want to create a new thread I just want to continue here...
I tried to figure out how BSGS works for scanning points and how it maybe can be improved...
Many BSGS scanners makes babystep file where you take starting point and the add +G+G+G+G+G+G to get for example 300.000.000 consecutive points
Then scanner will jump 300M per iteration and check if the current point is on the list...
But I think that there is no need for all points to be consecutive. You can spread them all over the range just make sure that when you generating the babystep file have the rule where
iteration * 300.000.000 * (some fixed number) + Iteration....
For example
For every point in theory if you do mod 300.000.000 of distance between start point and any generated point you will get all posible remainings for 300.000.000... so that means when you scan you can still jump regular jumps even if there is huge gap between points and you will find a solution sooner because points are not at the same place
I think this can be improved more....
--------------------------------------------------------
Also, for example, in puzzle 135 we have our goal point
X: 145D2611C823A396EF6712CE0F712F09B9B4F3135E3E0AA3230FB9B6D08D1E16
Y: 667A05E9A1BDD6F70142B66558BD12CE2C0F9CBC7001B20C8A6A109C80DC5330
From this point we can do subtraction 0x4000000000000000000000000000000000 * G
we will get some point and then we take simetrical point - the point in upper region
Then we make a list (babystep file) of all X values from 1G to 300.000.000G
So we can start scanning from a symmetrical point and we go UP... but then we can jump 600.000.000 keys per jump so we can double the speed - when we hit some X value we have 2 solutions and one of them is correct
I am not sure about the method where we put gaps between points in the babystep file because there is infinity point so after infinity point all points are moved by 1 so if you jump 600.000.000 keys per jump and you have only 300.000.000 points in BS file I am not sure that it will find a solution because other half of points are moved by 1
In regular BSGS that must work - it does not work only in case if you hit the infinity point when you jump for 600.000.000 keys... But I think the chances for that are small
I have only this code for generating lines
When I generate 300.000.000 keys I take only first 16 characters for matching. It is a simple code and can be improved on many ways. I am not so good at python I was working with PHP like 15 years
import secp256k1 as ice
import os
# Starting point
P = ice.pub2upub('02145d2611c823a396ef6712ce0f712f09b9b4f3135e3e0aa3230fb9b6d08d1e16')
batch_size = 30_000_000
max_lines = 300_000_000
babystep_file = "babystep.txt"
if os.path.exists(babystep_file):
with open(babystep_file, "r") as f:
line_count = sum(1 for _ in f)
else:
line_count = 0
with open(babystep_file, "a") as f:
while line_count < max_lines:
print(f"Generating {batch_size} BSGS points...")
bsgs_batch = ice.point_sequential_increment(batch_size, P)
for i in range(batch_size):
hex_string = bsgs_batch[i * 65: i * 65 + 65].hex()
x_hex = hex_string[2:18]
f.write(f"{x_hex}\n")
line_count += 1
if line_count >= max_lines:
break
P = ice.pub2upub(bsgs_batch[-65:].hex())
print(f"Current generating: {line_count}/{max_lines} lines.")
print("Generating of 300.000.000 lines completed.")
my idea is to create ONE babystep file and count that file twice because you can double the number of consecutive X values because they are going in one direction then in the reverse direction (with 0 point in the middle)
Our goal point
02145d2611c823a396ef6712ce0f712f09b9b4f3135e3e0aa3230fb9b6d08d1e16
I have this code for subtraction of points so I used it
import secp256k1 as ice
def ECsubtract(Q1,Q2):# compressed or uncompressed pubkey
Q1=ice.pub2upub(Q1)
Q2=ice.pub2upub(Q2)
sub=ice.point_negation(Q2)# -Q2
return (ice.point_addition(Q1,sub).hex()) #Q1 - Q2
public_key=ECsubtract('02145d2611c823a396ef6712ce0f712f09b9b4f3135e3e0aa3230fb9b6d08d1e16','02cbb434aa7ae1700dcd15b20b17464817ec11715050e0fa192ffe9c29a673059f')
print(public_key)
02cbb434aa7ae1700dcd15b20b17464817ec11715050e0fa192ffe9c29a673059f = 4000000000000000000000000000000000 * G
I got this point
04a8c204d9e0cd0e7f6da825d55b5c2b9d0093f96650bf37e67bc802189b3bc47837bbe3fd17f83a190242af1da9673c468f504b37ba276554a9724ea479124d87
Upper region point is
04a8c204d9e0cd0e7f6da825d55b5c2b9d0093f96650bf37e67bc802189b3bc478c8441c02e807c5e6fdbd50e25698c3b970afb4c845d89aab568db15a86edaea8
From this point we can start. Make babystep file from 1G to XG (how much RAM do you have) and then start scanning...
You are creating Babystep file from 1G to 10G in babystep file you only put X values (or part of it or I do not know)
You are jumping from 264G ----> inverse point n - 264
And you can jump 20G in one jump and try to match X values of the point...
number of line you hit is for example 3... you have 2 solutions ...
private key = n - nuber of jumps * 20 - 3
private key = n - nuber of jumps * 20 - 3 * 2 - 1(because of infinity point)
I mean this is something I am thinking about not sure
I also have another Idea like a Kangaroo that will use the infinity point as a referent point so the kangaroo will jump from the public key up and we will save X values of those points when the code jumps over the infinity point then the kangaroo will basically start jumping back because X values now have order in backward... and then when you find collision with itself you can calculate the private key
priv_key = (n - (G_added - G_at_collision) // 2 - G_at_collision) % n
So in my code I was looking for private key of
03440daba3905488f1b5ad2186f6ce2e9a9fe69327ac975dba1a93f8ed60d7813d
I know that private key is < n/2 so I took the even Y value to have a point > n/2
here is the code
import ecdsa
from ecdsa.ellipticcurve import Point
import time
# Parameters of the secp256k1 elliptic curve
curve = ecdsa.curves.SECP256k1.curve
G = ecdsa.curves.SECP256k1.generator
n = ecdsa.curves.SECP256k1.order
# Initial point
X = 0x440daba3905488f1b5ad2186f6ce2e9a9fe69327ac975dba1a93f8ed60d7813d
Y = 0x9d656a2ee1049d7bf9c4b48c4df47e92115b0a479c60ba1034c9c2e7a39d2f0c
P = Point(curve, X, Y)
visited_x = {} # Store X coordinates in RAM
G_added = 0 # Total G added
start_time = time.time() # Start time
last_print_time = start_time # Track last print time
iteration = 0 # Track current iteration
while True:
last5 = X & 0xFFFFF # Last 5 digits of X-axis
step = last5 + 1 # Step size
P = P + step * G # Jump forward
X = P.x()
G_added += step
iteration += 1
current_time = time.time()
if current_time - last_print_time >= 5:
print(f"Total G added: {hex(G_added)}, Current Iteration: {iteration}, Current step: {step}", end="\r")
last_print_time = current_time
if X in visited_x:
G_at_collision = visited_x[X]
priv_key = (n - (G_added - G_at_collision) // 2 - G_at_collision) % n
end_time = time.time()
elapsed_time = end_time - start_time
hours, rem = divmod(elapsed_time, 3600)
minutes, seconds = divmod(rem, 60)
print(f"\nPrivate key found: {hex(priv_key)}")
print(f"Time taken: {int(hours)}h {int(minutes)}m {int(seconds)}s")
break
else:
visited_x[X] = G_added
I know that the code is slow but it finds a solution
Total G added: 0x11a4b3bb783, Current Iteration: 2312884, Current step: 699786
Private key found: 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25d8a18d30c97
Time taken: 0h 3m 19s
So original private key is
n - fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25d8a18d30c97
hex 102B76334AA
dec 1111178294442
[moderator's note: consecutive posts merged]
Show Posts
)
