lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1)

[COBRAS]

For take 2^30 key from 2^130 will be needs a 2^100 "operations", operations ad a subtract, operation as a subtract and divide , all ways will be need a 2^100

fir take key in 2^65 will bee need  a 2^65:for pub 2^230


(((((

[whanau]

I wrote the both scripts:

create_database_arulbero.py
search_key_arulbero.py

Both scripts appear identical or is it me? 

[arulbero]

I wrote the both scripts:

create_database_arulbero.py
search_key_arulbero.py

Both scripts appear identical or is it me? 

You're right, I  copied twice the same file. Now there are 2 different scripts.

[mcdouglasx]

I wrote the both scripts:

create_database_arulbero.py
search_key_arulbero.py

parameters:

private key interval: from 1 to 2^32
keys stored: 2^32 / 2^7 = 2^25 (1 each 128)
bits for each key = 64
size of database: 257 MB

time to create the database: 3 min 55 s

time to find the private key of a single random public key in the db: 0.1 - 0.3 s




create_database_arulbero.py

Code:

#!/usr/bin/env python3
# 2023/Dec/03, create_database_arulbero.py
import secp256k1 as ice

#############################################################################
# Set the number of public keys to generate
#############################################################################
start_key = 1
num_public_keys = 2**32 #(about 4 billions of keys)
bits_to_store = 64
bytes_to_store = bits_to_store//8
rate_of_key_to_generate = 128
rate_of_key_to_store = rate_of_key_to_generate

interval_to_generate = range(start_key, start_key + num_public_keys, rate_of_key_to_store)
interval_to_store = range(start_key,start_key + num_public_keys,rate_of_key_to_store)

binary_mode = 1

#############################################################################


if (binary_mode == 1):

	f = open("public_keys_database.bin", "wb") #binary mode

	########################################generation#############################################
	public_keys=[]

	
	public_keys_complete=list(map(ice.scalar_multiplication,interval_to_generate)) #generates the public keys complete
	public_keys=list(map(lambda w: int(w[33-bytes_to_store:33].hex(),16),public_keys_complete)) #extract only the last bytes_to_store
	
	
	
	########################################writing the db##########################################
	for i in range(0,len(interval_to_store)):
		f.write(public_keys[i].to_bytes(bytes_to_store,byteorder='big'))  #writes each key
		
	f.close()
	
else:

	f = open("public_keys_database.txt", "w")
	
	#generation
	public_keys=[] 

	for i in interval_to_generate:
		P4 = ice.scalar_multiplication(i)
		public_keys.append(P4[33-bytes_to_store:33].hex())

	#writing the db
	for i in range(0,len(interval_to_store)):
		f.write(public_keys[i])
		
	f.close()

search_key_arulbero.py

Code:

# 2023/Dec/03, search_key_arulbero.py
import secp256k1 as ice
import random
import sys

#############################################################################
# Set the number of public keys to generate
#############################################################################

start_key = 1
num_public_keys = 2**32 
bits_to_store = 64
bytes_to_store = bits_to_store//8
rate_of_key_to_generate = 128
rate_of_key_to_store = rate_of_key_to_generate

split_database = 16 #read only a fraction of the database to speedup the finding of the string 

interval_to_generate = range(start_key,start_key + num_public_keys, rate_of_key_to_store)

interval_to_store = range(start_key,start_key + num_public_keys,rate_of_key_to_store)

binary_mode = 1



#########################################################################################

#pk = 0x3243 = 12867
#P = ice.scalar_multiplication(12867)
#P="0x6800b#b8a9dffe1709ceac95d7d06646188c2cb656c09cd2e717ec67487ce1be3"


#############generates random private key and public key#################################
pk= random.randint(start_key, start_key + num_public_keys)
P = ice.scalar_multiplication(pk)
print()
print("This is the public key: " + P[1:33].hex())
print("I need to find this private key: "+str(pk))


###################subtraction of : P - 1G,  P - 2G, ..., P - rate_of_key*G################
substract_pub = ice.scalar_multiplication(1)
complete_pub= ice.point_loop_subtraction(rate_of_key_to_generate, P, substract_pub)


partial_pub=[] #need only the last bytes_to_store
P2=int(P[33-bytes_to_store:33].hex(),16).to_bytes(bytes_to_store,byteorder='big')
partial_pub.append(P2)

for i in range(1,rate_of_key_to_store+1):
	partial_pub.append(int(complete_pub[(i-1)*65+33-bytes_to_store:(i-1)*65+33].hex(),16).to_bytes(bytes_to_store,byteorder='big'))
	
	


################search in database##########################################################
with open("public_keys_database.bin", 'r+b') as f:

	s = f.read()
	l=len(s)
	
	for k in range(0,l, l//split_database):
		j=1
		for i in partial_pub:
			n = s[k:k+l//split_database].find(i)
			if n > -1:
				print()
				print("Private key found!!!")
				private_key = (n+k)//bytes_to_store*rate_of_key_to_generate + j
				print(private_key)
				P3 = ice.scalar_multiplication(private_key)
				pub_key=P3[1:33].hex() 
				print((pub_key)[:])
				f.close()
				sys.exit(0)
			j=j+1
		
		
print("string not found")

		
f.close()

 

Do you store fewer keys and more bits? When we use bytes we search in byte packets, so you are closer to traditional databases than to the idea presented here.
so you can take any pub, and store its first bytes without going through bit counting and it would give the same result because you have to find an explicit pk that meets certain parameters, which was the main problem.

[whanau]

Very Interesting scripts. Thank you for publishing.
I thought I would try them out with a couple of format tweaks..

Using a key in the 30 bit range: 3d94cd64

The result,
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
This is the public key: 0d282cf2ff536d2c42f105d0b8588821a915dc3f9a05bd98bb23af67a2e92a5b
I need to find this private key: 0x3d94cd64

Private key found!!!
0x594cd64
a152cbd0f4fdb5caf73c1ef6469896a760461bb0d297075962b40b7f5e93d2fd
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

0x5  94cd64 the last 6 are correct but the 5 of course is wrong, so produces the wrong public key.
Not sure why

I thought it might be a false positive, but ran through the whole database, but no other string was found.

[WanderingPhilospher]

I thought I would try them out with a couple of format tweaks..

Can't help without knowing the tweaks.

[whanau]

Just decimal to hex  print output

[bjpark]

Thank you for providing the great program for testing purposes.
 As a student learning Python, I've been experimenting with ChatGPT and making several modifications.
The program here generates a public key by knowing the private key (starting from 1) and incrementing it by 1.
However, what I want to create is a program where I only know the public key without knowing the private key. In essence, I aim to find a situation where:

Public Key + 1 = Public Key
Public Key + 2 = Public Key
...
Public Key + 10000 = Public Key

Public Key(1000) + 1 = Public Key(1001)
Public Key(1000) + 2 = Public Key(1002)
...
Public Key(1000) + 10000 = Public Key(11000)

Thank you

[mcdouglasx]

Thank you for providing the great program for testing purposes.
 As a student learning Python, I've been experimenting with ChatGPT and making several modifications.
The program here generates a public key by knowing the private key (starting from 1) and incrementing it by 1.
However, what I want to create is a program where I only know the public key without knowing the private key. In essence, I aim to find a situation where:

Public Key + 1 = Public Key
Public Key + 2 = Public Key
...
Public Key + 10000 = Public Key

Public Key(1000) + 1 = Public Key(1001)
Public Key(1000) + 2 = Public Key(1002)
...
Public Key(1000) + 10000 = Public Key(11000)

Thank you

Look at my previous posts, I'm sure you'll find what you need.

[WanderingPhilospher]

You are right, no match.
It must be a problem with the reading of bytes.
You definitely found a bug.
Because, it is in the DB but does not get it.
I'll fix it.

Edit:
The curious part is that if we start at 6 we get 3092000006
and match.

Any update? I've been trying tweaks to the search script, but I have not been successful.

Sorry, I've been busy, basically the problem is when we look in bytes, if we stop using bytes we find it.


edit: for incremental

Code:

#@mcdouglasx
import secp256k1 as ice
import random
from bitstring import BitArray



print("Scanning Binary Sequence")



start=0
end= 4000000000

#1:4000000000
for i in range(start, end,4000000):
    
    target = ice.scalar_multiplication(i)

    num = 64 # collision margin.

    sustract= 1 # #amount to subtract each time.

    sustract_pub= ice.scalar_multiplication(sustract)

    res= ice.point_loop_subtraction(num, target, sustract_pub)
        
    binary = ''
        
    for t in range (num):
            
        h= (res[t*65:t*65+65]).hex()
        hc= int(h[2:], 16)
            
            
        if str(hc).endswith(('0','2','4','6','8')):
            A="0"
            binary+= ''.join(str(A))
                
        if str(hc).endswith(('1','3','5','7','9')):
            A="1"
            binary+= ''.join(str(A))
        
            
    my_str = binary

    b = BitArray(bin=my_str)
    c = bytes(b)

    file = open("data-base.bin", "rb")
    dat= BitArray(file.read())
    

    if b  in dat:
        
        print("found")
        s = c
        f = dat
        inx = f.find(s)
        inx_1=str(inx).replace(",", "")
        inx_0=str(inx_1).replace("(", "")
        inx_2=str(inx_0).replace(")", "")
        
        Pk = (int(i) + int(inx_2))
            
        data = open("win.txt","a")
        data.write("Pk:"+" "+str(Pk)+"\n")
        data.close()
        break

Yoooo OP.

This is crazy lol.

Your revised search script you posted above, is over 7 times slower now.
I implemented a different way to search when your original search script didn't find the key using an increment, and when I run it compared to your revised version, mine is 7 times faster.
Now I have to unpeel it all and see what's going on.

I think this is what slows down your search script:

dat= BitArray(file.read())
versus
dat = bytes(file.read())

[bjpark]

Thank you for providing the great program for testing purposes.
 As a student learning Python, I've been experimenting with ChatGPT and making several modifications.
The program here generates a public key by knowing the private key (starting from 1) and incrementing it by 1.
However, what I want to create is a program where I only know the public key without knowing the private key. In essence, I aim to find a situation where:

Public Key + 1 = Public Key
Public Key + 2 = Public Key
...
Public Key + 10000 = Public Key

Public Key(1000) + 1 = Public Key(1001)
Public Key(1000) + 2 = Public Key(1002)
...
Public Key(1000) + 10000 = Public Key(11000)

Thank you

Look at my previous posts, I'm sure you'll find what you need.

Thank you so much. I found the code

[mcdouglasx]

Yoooo OP.

This is crazy lol.

Your revised search script you posted above, is over 7 times slower now.
I implemented a different way to search when your original search script didn't find the key using an increment, and when I run it compared to your revised version, mine is 7 times faster.
Now I have to unpeel it all and see what's going on.

I think this is what slows down your search script:

dat= BitArray(file.read())
versus
dat = bytes(file.read())

Yes I know it's slower, I apologize for that.

I did it this way to work with bits, because that's the way I think it should be done. While working with bits you are certain that you will find the key, without these keys being masked within the bytes.
My intention was not to do this to brute force directly with Python, as I said from the beginning, I am demonstrating an idea, C is better for this, unfortunately everything is against me.

- I don't have fiber optics, you can imagine what it would take me with 100kb/s to download what I need.
-my pc is an intel i5 4gb ddr 3 laptop.
- I live in an underdeveloped country where installing fiber costs $120 and is very difficult to find, not to mention a new PC.

I would love to do it in C, as soon as I have how I will do it, while I read about cuda, I learn things, I take notes on how games and software use the GPU in an efficient way.

I have other ideas how to apply this to bsgs, but while I write them in python as a draft.

[WanderingPhilospher]

Yoooo OP.

This is crazy lol.

Your revised search script you posted above, is over 7 times slower now.
I implemented a different way to search when your original search script didn't find the key using an increment, and when I run it compared to your revised version, mine is 7 times faster.
Now I have to unpeel it all and see what's going on.

I think this is what slows down your search script:

dat= BitArray(file.read())
versus
dat = bytes(file.read())

Yes I know it's slower, I apologize for that.

I did it this way to work with bits, because that's the way I think it should be done. While working with bits you are certain that you will find the key, without these keys being masked within the bytes.
My intention was not to do this to brute force directly with Python, as I said from the beginning, I am demonstrating an idea, C is better for this, unfortunately everything is against me.

- I don't have fiber optics, you can imagine what it would take me with 100kb/s to download what I need.
-my pc is an intel i5 4gb ddr 3 laptop.
- I live in an underdeveloped country where installing fiber costs $120 and is very difficult to find, not to mention a new PC.

I would love to do it in C, as soon as I have how I will do it, while I read about cuda, I learn things, I take notes on how games and software use the GPU in an efficient way.

I have other ideas how to apply this to bsgs, but while I write them in python as a draft.

Understood.

My search script is faster and only uses 0s and 1 like yours, but my binary files are about 4 times larger than yours because I’m not using the bitarray.

With all that said, this is a brilliant way to store large amounts of keys. And yes, I am also thinking on how to implement it with different programs.

Keep up the imagination; best breakthrough I’ve used/tested in awhile!

[digaran]

So $120 for fiber, why not adsl? And how much would you say is enough to get a PC,  to work on CUDA? I have no doubts about your ingenuity and perseverance and I'm sure you will have a bright future.@OP.

[mcdouglasx]

So $120 for fiber, why not adsl? And how much would you say is enough to get a PC,  to work on CUDA? I have no doubts about your ingenuity and perseverance and I'm sure you will have a bright future.@OP.

The signal with copper pairs is deteriorated and obsolete, therefore they have recently changed to fiber that is why the price of installation + moden + ROUTER, the ADSL lines have a lot of noise, it is to be expected that they are more than 40 years old. antiquity.
and as for CUDA cores, it is not worth having a high-end GPU to program, although the high-ends have interesting technologies, which perhaps can be extrapolated to brute force.

[WanderingPhilospher]

I modified the script to match what arulbero did; create a random priv/pubkey and find it.

Results for a key in the 32 bit range:

Code:

This is the public key: 034a2c855cd562b2865ba5fafa6b8b9cd26d3276269f2ad314077675dca3dcce81
I need to find this private key: 0xfd4f6f66
Making Binary Data-Base


 Building the Binary Database

 Targeting PubKey:      034a2c855cd562b2865ba5fafa6b8b9cd26d3276269f2ad314077675dca3dcce81
 Number of PubKeys:     1,000,000
 Writing to file every: 1,000,000 keys
 Subtract Value:        1

 Scanning Incrementally

 Current Incr Location:  0xfd429840   Jumps Made:  4,249
 PK Found: 4249841510
 PK Found: 0xfd4f6f66

Total Time:  0:00:08.831704

and

Code:

This is the public key: 02bbbe90761d7c7ec3dabb3d64448ecdb5fa6f704ff06bcf7643176a74ffa69a4b
I need to find this private key: 0xff821c74
Making Binary Data-Base


 Building the Binary Database

 Targeting PubKey:      02bbbe90761d7c7ec3dabb3d64448ecdb5fa6f704ff06bcf7643176a74ffa69a4b
 Number of PubKeys:     1,000,000
 Writing to file every: 1,000,000 keys
 Subtract Value:        1

 Scanning Incrementally

 Current Incr Location:  0xff772b80   Jumps Made:  4,286
 PK Found: 4286717044
 PK Found: 0xff821c74

Total Time:  0:00:08.782662

From start to finish. But it's not the speed, it's the size of the DB, only 121kb
Well I mean the speed is good for a single core. DB creation and search for the key and find it in under 9 seconds, 100% of the time.

[COBRAS]

I modified the script to match what arulbero did; create a random priv/pubkey and find it.

Results for a key in the 32 bit range:

Code:

This is the public key: 034a2c855cd562b2865ba5fafa6b8b9cd26d3276269f2ad314077675dca3dcce81
I need to find this private key: 0xfd4f6f66
Making Binary Data-Base


 Building the Binary Database

 Targeting PubKey:      034a2c855cd562b2865ba5fafa6b8b9cd26d3276269f2ad314077675dca3dcce81
 Number of PubKeys:     1,000,000
 Writing to file every: 1,000,000 keys
 Subtract Value:        1

 Scanning Incrementally

 Current Incr Location:  0xfd429840   Jumps Made:  4,249
 PK Found: 4249841510
 PK Found: 0xfd4f6f66

Total Time:  0:00:08.831704

and

Code:

This is the public key: 02bbbe90761d7c7ec3dabb3d64448ecdb5fa6f704ff06bcf7643176a74ffa69a4b
I need to find this private key: 0xff821c74
Making Binary Data-Base


 Building the Binary Database

 Targeting PubKey:      02bbbe90761d7c7ec3dabb3d64448ecdb5fa6f704ff06bcf7643176a74ffa69a4b
 Number of PubKeys:     1,000,000
 Writing to file every: 1,000,000 keys
 Subtract Value:        1

 Scanning Incrementally

 Current Incr Location:  0xff772b80   Jumps Made:  4,286
 PK Found: 4286717044
 PK Found: 0xff821c74

Total Time:  0:00:08.782662

From start to finish. But it's not the speed, it's the size of the DB, only 121kb
Well I mean the speed is good for a single core. DB creation and search for the key and find it in under 9 seconds, 100% of the time.

And were is your code ?

[arulbero]

From start to finish. But it's not the speed, it's the size of the DB, only 121kb
Well I mean the speed is good for a single core. DB creation and search for the key and find it in under 9 seconds, 100% of the time.

My results:

-------------------------------------------------------------------------------
2^32 range

1 key each 2^20 (1 million)

time to generate the DB: 0.060 s
size of DB: 32kB

max time to find the private key : less than 2 seconds.
-------------------------------------------------------------------------------
2^36 range

1 key each 2^20 (1 million)

time to generate the DB: 0.5 s
size of DB: 512kB

max time to find the private key : less than 2 seconds.
-------------------------------------------------------------------------------
2^40 range

1 key each 2^20 (1 million)

time to generate the DB: 7.3 s
size of DB: 8 MB

max time to find the private key : less than 2 seconds.
-------------------------------------------------------------------------------
2^44 interval

1 key each 2^20 (1 million)

time to generate the DB: 2 m
size of DB: 129 MB

max time to find the private key : less than 4 seconds.
-------------------------------------------------------------------------------
2^44 range

1 key each 2^24 (16 millions)

time to generate the DB: 7.3 s
size of DB: 8 MB

max time to find the private key : 30 seconds.
-------------------------------------------------------------------------------

The problem with my implementation is that the time search goes up with the size of DB and with the number of the keys I skip in the database creation.

The goal is to have a faster implementation for large intervals, not for small intervals

I updated my search_key script. Now it is a little faster.

Using a key in the 30 bit range: 3d94cd64

The result,
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
This is the public key: 0d282cf2ff536d2c42f105d0b8588821a915dc3f9a05bd98bb23af67a2e92a5b
I need to find this private key: 0x3d94cd64

Private key found!!!
0x594cd64
a152cbd0f4fdb5caf73c1ef6469896a760461bb0d297075962b40b7f5e93d2fd
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

0x5  94cd64 the last 6 are correct but the 5 of course is wrong, so produces the wrong public key.
Not sure why

I thought it might be a false positive, but ran through the whole database, but no other string was found.

Are you sure you have changed the parameters in both scripts (same parameters in both): create_database and seach_pk ?
Anyway I updated the search_pk (it is in the same post)

[GR Sasa]

Could this script be faster than BSGS (Baby Step Giant Step)?

Or Are they similar to each other?

[arulbero]

From start to finish. But it's not the speed, it's the size of the DB, only 121kb
Well I mean the speed is good for a single core. DB creation and search for the key and find it in under 9 seconds, 100% of the time.

My results:

-------------------------------------------------------------------------------

I managed to get another improvement, using the symmetrie.

Instead of generating a interval [1 -> 2^40], if we shift the interval to [-2^39,2^39] then the 'positive' part has the same x-coordinates of the 'negative' part, so I can store only half keys (and have the same information).

Now these are my results:

-------------------------------------------------------------------------------
2^32 range

1 key each 2^20 (1 million)

time to generate the DB: 0.055 s
size of DB: 16kB

max time to find the private key : less than 2 seconds.
-------------------------------------------------------------------------------
2^36 range

1 key each 2^20 (1 million)

time to generate the DB: 0.26 s
size of DB: 256kB

max time to find the private key : less than 2 seconds.
-------------------------------------------------------------------------------
2^40 range

1 key each 2^20 (1 million)

time to generate the DB: 3.65 s
size of DB: 4 MB

max time to find the private key : 2 seconds.
-------------------------------------------------------------------------------
2^44 range

1 key each 2^20 (1 million)

time to generate the DB: 59 s
size of DB: 65 MB

max time to find the private key :  3 seconds.
-------------------------------------------------------------------------------
2^44 range

1 key each 2^24 (16 millions)

time to generate the DB: 3.65 s
size of DB: 4 MB

max time to find the private key : 31 seconds.
-------------------------------------------------------------------------------



I didn't upload the script yet.

Next step could be find a way to speed up the search, probably storing the keys in a different order.

Could this script be faster than BSGS (Baby Step Giant Step)?

Or Are they similar to each other?

Faster than BSGS ? No.