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

mcdouglasx

member

Activity: 234

Merit: 51

New ideas will be criticized and then admired.

Quote from: WanderingPhilospher on December 11, 2023, 10:22:36 PM

Code:

Found the Baby Steps Table file: baby_steps__binary.bin. Will be used directly
Checking 3600000000000000 keys from 0x9de000a7c
BSGS FOUND PrivateKey : 42387769979
Time Spent : 0.13 seconds

Oh hey look, .13 seconds, but look where the checking keys from is.

Man you can bullchit some people, but not this dawg.

In your script you have:
k1 = random.randint(start, end)

so if the random key is close to the key, then you will find it faster, but if you do not know the key, you must start from at least the starting range of the bit range.

My results above clearly showed the starting key of 0x1 and the amount of keys. You purposely didn't add that in your snippet.

Not today OP, not today lol.

I don't have the need to lie, I work hard and I sleep little, I used another script, that's all, there is no need to create a witch hunt Lol, like Albertobsd, he told me I was a liar, he ignored me, i shut his mouth and surely in a while we will see keyhunt with binary DB.

mcdouglasx

member

Activity: 234

Merit: 51

New ideas will be criticized and then admired.

Quote from: WanderingPhilospher on December 11, 2023, 09:58:28 PM

Quote from: mcdouglasx on December 11, 2023, 09:42:12 PM

Quote from: WanderingPhilospher on December 11, 2023, 09:19:40 PM

Quote

in my few tests I noticed that searching for bsgs is a lot faster than in normal search like here

My 2 tests results are above. This BSGS is much slower than other search script. Slower as in finding the key.

Maybe at 48 bit BSGS would outperform.

Quote

pk obtained partially matches the one you are looking for

Yeah, I do not know the pk lol, it was for the #130 challenge. I ran a fast BSGS (GPU) 74 bits above and below the "false positive" and nada.

Also, with your way of setting up the DB, with 0s and 1s; if running 64, isn't a false positive possible every 4,096 checks? 64^2.

In BSGS it is always better to create your database from the lowest possible range for your target, if your range is 2000:5000 in the database you start from 2000.
2^64 or 18446744073709551616 is the possibility of collision not 64^2.

If you do not know your target private key, I'm going with lowest range number - number of keys. You had it set up to start from a random point, which was usually in the middle of the range and above the key. Took me a minute to figure out why it hadn't found a key after a few minutes.

Maybe I am wrong, but I do not agree with your 2^64. The way I structure my database, and its number of subtractions, is a legit 2^16; but in your script, if a pub is either a 0 or a 1, how is that 2^64?
2^64 or a 64 bit number means there are 16 possible combos in each digit, example, 0xf62918cd28ab0236 is a 2^64 number, anything in the hex range 0x8000000000000000 - 0xffffffffffffffff is 2^64, 16 x 4, 16 combos for each character, or 2^4 for each position.
But if it's just a string of 64 0s and/or 1s, each position can only be a possible 2 digits. 64 characters in length, only 2 possible digits/characters (0, 1) 64^2, no?

we are talking about bits: 2^64.
If you choose as collision 128= 2^128

Quote from: WanderingPhilospher on December 11, 2023, 10:09:06 PM

If I am, it’s your script lol.

I’m just telling you my results, from 20,000,000 and 60,000,000 keys.

Maybe you generated more keys? And why didn’t you show your starting key and how many keys. Something tells me you aren’t telling the whole truth.

Why would I need to lie?

BSGS is mainly a mathematical algorithm so we cannot do crazy searches.

this is random search it could have been coincidental.

edit:

sorry, my bad, I used my new script instead of using the published one.

WanderingPhilospher

full member

Activity: 1050

Merit: 219

Shooters Shoot...

Code:

Found the Baby Steps Table file: baby_steps__binary.bin. Will be used directly
Checking 3600000000000000 keys from 0x9de000a7c
BSGS FOUND PrivateKey : 42387769979
Time Spent : 0.13 seconds

Oh hey look, .13 seconds, but look where the checking keys from is.

Man you can bullchit some people, but not this dawg.

In your script you have:
k1 = random.randint(start, end)

so if the random key is close to the key, then you will find it faster, but if you do not know the key, you must start from at least the starting range of the bit range.

My results above clearly showed the starting key of 0x1 and the amount of keys. You purposely didn't add that in your snippet.

Not today OP, not today lol.

WanderingPhilospher

full member

Activity: 1050

Merit: 219

Shooters Shoot...

Quote from: mcdouglasx on December 11, 2023, 10:02:34 PM

Quote from: WanderingPhilospher on December 11, 2023, 08:43:24 PM

Quote from: mcdouglasx on December 11, 2023, 08:19:16 PM

Has anyone compared this with the bsgs version that I updated? It would be interesting.

Code:

Found the Baby Steps Table file: baby_steps__binary.bin. Will be used directly
Checking 400000000000000 keys from 0x1
BSGS FOUND PrivateKey : 3093472813
Time Spent : 21.40 seconds

You are doing something wrong, my results on intel i5 4gb ddr3.

BSGS FOUND PrivateKey : 3093472813
Time Spent : 0.25 seconds

If I am, it’s your script lol.

I’m just telling you my results, from 20,000,000 and 60,000,000 keys.

Maybe you generated more keys? And why didn’t you show your starting key and how many keys. Something tells me you aren’t telling the whole truth.

mcdouglasx

member

Activity: 234

Merit: 51

New ideas will be criticized and then admired.

Quote from: WanderingPhilospher on December 11, 2023, 08:43:24 PM

Quote from: mcdouglasx on December 11, 2023, 08:19:16 PM

Has anyone compared this with the bsgs version that I updated? It would be interesting.

Code:

Found the Baby Steps Table file: baby_steps__binary.bin. Will be used directly
Checking 400000000000000 keys from 0x1
BSGS FOUND PrivateKey : 3093472813
Time Spent : 21.40 seconds

You are doing something wrong, my results on intel i5 4gb ddr3.

BSGS FOUND PrivateKey : 3093472813
Time Spent : 0.25 seconds

WanderingPhilospher

full member

Activity: 1050

Merit: 219

Shooters Shoot...

Quote from: mcdouglasx on December 11, 2023, 09:42:12 PM

Quote from: WanderingPhilospher on December 11, 2023, 09:19:40 PM

Quote

in my few tests I noticed that searching for bsgs is a lot faster than in normal search like here

My 2 tests results are above. This BSGS is much slower than other search script. Slower as in finding the key.

Maybe at 48 bit BSGS would outperform.

Quote

pk obtained partially matches the one you are looking for

Yeah, I do not know the pk lol, it was for the #130 challenge. I ran a fast BSGS (GPU) 74 bits above and below the "false positive" and nada.

Also, with your way of setting up the DB, with 0s and 1s; if running 64, isn't a false positive possible every 4,096 checks? 64^2.

In BSGS it is always better to create your database from the lowest possible range for your target, if your range is 2000:5000 in the database you start from 2000.
2^64 or 18446744073709551616 is the possibility of collision not 64^2.

If you do not know your target private key, I'm going with lowest range number - number of keys. You had it set up to start from a random point, which was usually in the middle of the range and above the key. Took me a minute to figure out why it hadn't found a key after a few minutes.

Maybe I am wrong, but I do not agree with your 2^64. The way I structure my database, and its number of subtractions, is a legit 2^16; but in your script, if a pub is either a 0 or a 1, how is that 2^64?
2^64 or a 64 bit number means there are 16 possible combos in each digit, example, 0xf62918cd28ab0236 is a 2^64 number, anything in the hex range 0x8000000000000000 - 0xffffffffffffffff is 2^64, 16 x 4, 16 combos for each character, or 2^4 for each position.
But if it's just a string of 64 0s and/or 1s, each position can only be a possible 2 digits. 64 characters in length, only 2 possible digits/characters (0, 1) 64^2, no?

mcdouglasx

member

Activity: 234

Merit: 51

New ideas will be criticized and then admired.

Quote from: WanderingPhilospher on December 11, 2023, 09:19:40 PM

Quote

in my few tests I noticed that searching for bsgs is a lot faster than in normal search like here

My 2 tests results are above. This BSGS is much slower than other search script. Slower as in finding the key.

Maybe at 48 bit BSGS would outperform.

Quote

pk obtained partially matches the one you are looking for

Yeah, I do not know the pk lol, it was for the #130 challenge. I ran a fast BSGS (GPU) 74 bits above and below the "false positive" and nada.

Also, with your way of setting up the DB, with 0s and 1s; if running 64, isn't a false positive possible every 4,096 checks? 64^2.

In BSGS it is always better to create your database from the lowest possible range for your target, if your range is 2000:5000 in the database you start from 2000.
2^64 or 18446744073709551616 is the possibility of collision not 64^2.

WanderingPhilospher

full member

Activity: 1050

Merit: 219

Shooters Shoot...

Quote

in my few tests I noticed that searching for bsgs is a lot faster than in normal search like here

My 2 tests results are above. This BSGS is much slower than other search script. Slower as in finding the key.

Maybe at 48 bit BSGS would outperform.

Quote

pk obtained partially matches the one you are looking for

Yeah, I do not know the pk lol, it was for the #130 challenge. I ran a fast BSGS (GPU) 74 bits above and below the "false positive" and nada.

Also, with your way of setting up the DB, with 0s and 1s; if running 64, isn't a false positive possible every 4,096 checks? 64^2.

mcdouglasx

member

Activity: 234

Merit: 51

New ideas will be criticized and then admired.

Quote from: WanderingPhilospher on December 11, 2023, 08:43:24 PM

Quote from: mcdouglasx on December 11, 2023, 08:19:16 PM

Has anyone compared this with the bsgs version that I updated? It would be interesting.

For the script you have posted, without any tinkering, I imagine the DB creation (same as this script) and the search, will be slower at lower bits.

Looking at the script, there's no way to tell progress, etc.

I like your DB idea, the search part needs to be implemented into a different language to speed it up.

ON a funny note, I had a false positive with the script, even at 64. It ran for about 30 hours, so I guess after you check so many keys, even the 64 will give you a false positive lol.

Quick tweak to script and ran the DB generation part. For 20,000,000 keys:

Quote

creating Baby Step

DB Generation Time: 0:00:08.942671

The question is not based on the speed of creating the database, it is fixed with C and if you do not want to investigate in C, at least some dll that will do the job for you using ctypes, in my few tests I noticed that searching for bsgs is a lot faster than in normal search like here, and yes with cm 64 you could find false positives for every 8bits 256 possible combinations and then it becomes exponential which could be more likely an error when you create your database a few bits more or less what they change everything, you deduce this if the pk obtained partially matches the one you are looking for, this would definitely be a failure in the creation of the database and not a false positive, so I recommend saving those "false positives" because if it is a bug in your database you could be a few jumps below or above the target.

WanderingPhilospher

full member

Activity: 1050

Merit: 219

Shooters Shoot...

Quote from: mcdouglasx on December 11, 2023, 08:19:16 PM

Has anyone compared this with the bsgs version that I updated? It would be interesting.

For the script you have posted, without any tinkering, I imagine the DB creation (same as this script) and the search, will be slower at lower bits.

Looking at the script, there's no way to tell progress, etc.

I like your DB idea, the search part needs to be implemented into a different language to speed it up.

ON a funny note, I had a false positive with the script, even at 64. It ran for about 30 hours, so I guess after you check so many keys, even the 64 will give you a false positive lol.

Quick tweak to script and ran the DB generation part. For 20,000,000 keys:

Quote

creating Baby Step

DB Generation Time: 0:00:08.942671

Ran a 32 bit search (changed out your random start point because that seemed counterintuitive, especially since it could be higher than the priv key):

Code:

Found the Baby Steps Table file: baby_steps__binary.bin. Will be used directly
Checking 400000000000000 keys from 0x1
BSGS FOUND PrivateKey : 3093472813
Time Spent : 21.40 seconds

I ran another test, 36 bit with 60,000,000 keys.
I also changed the k value (start) to k = start (0x800000000, start of 36 bit range) - m (number of keys, since they are consecutive).

Code:

creating Baby Step

DB Generation Time: 0:00:25.307935

Code:

Found the Baby Steps Table file: baby_steps__binary.bin. Will be used directly
Checking 3600000000000000 keys from 0x7fc6c7900
BSGS FOUND PrivateKey : 42387769979
Time Spent : 61.94 seconds

Search is super slow right now. Not even close to the other search script with same amount of generated keys. At some bit, I am sure the BSGS would outperform the other search script.

mcdouglasx

member

Activity: 234

Merit: 51

New ideas will be criticized and then admired.

Has anyone compared this with the bsgs version that I updated? It would be interesting.

ecdsa123

full member

Activity: 211

Merit: 105

Dr WHO on disney+

Yes i know not puck but pack:-) sorry

everything is going on fly and database and search.

WanderingPhilospher

full member

Activity: 1050

Merit: 219

Shooters Shoot...

Quote from: ecdsa123 on December 11, 2023, 05:05:54 PM

Edited:

Test 1:

Code:

without pucked res= 1011011010010000111100101010100010100101111101011010101101111111 len= 64
with pucked once res= b690f2a8a5f5ab7f len= 16
maximum pucked res= ¶�ò¨¥õ« len= 8

Test2:

Code:

without pucked res= 1011011010010000111100101010100010100101111101011010101101111111101101101001000011110010101010001010010111110101101010110111111110110110100100001111001010101000101001011111010110101011011111111011011010010000111100101010100010100101111101011010101101111111 len= 256
with pucked once res= b690f2a8a5f5ab7fb690f2a8a5f5ab7fb690f2a8a5f5ab7fb690f2a8a5f5ab7f len= 64
maximum pucked res= ¶�ò¨¥õ«¶�ò¨¥õ«¶�ò¨¥õ«¶�ò¨¥õ« len= 32

Code:

directory={}
def make_combination(directory):
   result=0
   for i in range(2**4):
   comb = bin(i)[2:].zfill(4)
   #print(kombinacja)
   directory[comb]=str(hex(result)[2:])
   result+=1

def get_comb(data,directory):
   my_str=""
   for i in range(0, len(data), 4):
   fragment = data[i:i+4]
   my_str+=directory[fragment]
   return my_str
make_combination(directory)

def change(binary,data):
   len_bin=len(binary)
   gum=str(binary[len_bin-4:len_bin])
   data+=get_comb(gum,directory)
   return "",data

def maximum_pack(data):
   result=""
   if len(data)%2!=0:
   print("it must be divided by 2")
   else:
   for i in range(0, len(data), 2):
   value=data[i:i+2]
   dec_value = int(value, 16)
   result+=chr(dec_value)
   return result

res="1011011010010000111100101010100010100101111101011010101101111111"

result=""
res_help =""
for i in range(0,len(res)):
   val=res[i]
   res_help+=val
   if len(res_help)%4==0:
   res_help,result=change(res_help,result)



result_maximum=maximum_pack(result)

print("without pucked res=",res,"len=",len(res))
print("with pucked once res=",result,"len=",len(result))
print("maximum pucked res=",result_maximum,"len=",len(result_maximum))

If you database with 64 MB -> after maximum pucked -> you have 8 MB (eight time less)

if you have 256 MB - database is 32 MM
if you Have 2 GB ->256 MB

better don;'t you?

Edit : 8 TB in 1 TB database...

The only question/problem I can ask/see, how do you implement it on the fly and check the DB for a collision/found key?

You would create the DB, then "puck" it; then how do you run a search against the pucked DB?

WanderingPhilospher

full member

Activity: 1050

Merit: 219

Shooters Shoot...

After more script tweaking, I can generate a 20,000,000 key database in less than 10 seconds. Search time less than 2 seconds.

36 Bit Result:

Code:

This is the public key: 02b3e772216695845fa9dda419fb5daca28154d8aa59ea302f05e916635e47b9f6

Building the Binary Database

Targeting PubKey: 02b3e772216695845fa9dda419fb5daca28154d8aa59ea302f05e916635e47b9f6
Number of PubKeys: 20,000,000
Writing to file every: 20,000,000 keys
Subtract Value: 1
Space Covered: 20,000,000 / 0x1312d00

DB Generation Time: 0:00:09.604563

Scanning Randomly

Current Random Key: 0x9dd926219 Jumps Made: 291
PK Found: 42387769980
PK Found: 0x9de820a7c

Search Time: 0:00:01.815859

Total Time: 0:00:11.420422

EDIT: If I use the BitArray option, as in original code, 20,000,000 keys generated into DB takes right at 4 seconds.

ecdsa123

full member

Activity: 211

Merit: 105

Dr WHO on disney+

Edited:

Test 1:

Code:

without pucked res= 1011011010010000111100101010100010100101111101011010101101111111 len= 64
with pucked once res= b690f2a8a5f5ab7f len= 16
maximum pucked res= ¶�ò¨¥õ« len= 8

Test2:

Code:

without pucked res= 1011011010010000111100101010100010100101111101011010101101111111101101101001000011110010101010001010010111110101101010110111111110110110100100001111001010101000101001011111010110101011011111111011011010010000111100101010100010100101111101011010101101111111 len= 256
with pucked once res= b690f2a8a5f5ab7fb690f2a8a5f5ab7fb690f2a8a5f5ab7fb690f2a8a5f5ab7f len= 64
maximum pucked res= ¶�ò¨¥õ«¶�ò¨¥õ«¶�ò¨¥õ«¶�ò¨¥õ« len= 32

Code:

directory={}
def make_combination(directory):
   result=0
   for i in range(2**4):
   comb = bin(i)[2:].zfill(4)
   #print(kombinacja)
   directory[comb]=str(hex(result)[2:])
   result+=1

def get_comb(data,directory):
   my_str=""
   for i in range(0, len(data), 4):
   fragment = data[i:i+4]
   my_str+=directory[fragment]
   return my_str
make_combination(directory)

def change(binary,data):
   len_bin=len(binary)
   gum=str(binary[len_bin-4:len_bin])
   data+=get_comb(gum,directory)
   return "",data

def maximum_pack(data):
   result=""
   if len(data)%2!=0:
   print("it must be divided by 2")
   else:
   for i in range(0, len(data), 2):
   value=data[i:i+2]
   dec_value = int(value, 16)
   result+=chr(dec_value)
   return result

res="1011011010010000111100101010100010100101111101011010101101111111"

result=""
res_help =""
for i in range(0,len(res)):
   val=res[i]
   res_help+=val
   if len(res_help)%4==0:
   res_help,result=change(res_help,result)



result_maximum=maximum_pack(result)

print("without pucked res=",res,"len=",len(res))
print("with pucked once res=",result,"len=",len(result))
print("maximum pucked res=",result_maximum,"len=",len(result_maximum))

If you database with 64 MB -> after maximum pucked -> you have 8 MB (eight time less)

if you have 256 MB - database is 32 MM
if you Have 2 GB ->256 MB

better don;'t you?

Edit : 8 TB in 1 TB database...

mcdouglasx

member

Activity: 234

Merit: 51

New ideas will be criticized and then admired.

Quote from: Kpot87 on December 09, 2023, 05:54:03 AM

@macduglasx hi, how you provide working with mulpubs, about ram it’s clear and what about threads ? 1pub=1th? Tnx

I don't understand what you mean, but I will still upload a basic BSGS version for those in the know to explore with that.
since I'm busy.

edit:

basic BSGS version

https://bitcointalksearch.org/topic/binary-baby-step-giant-step-with-lightweight-database-brute-force-bsgs-5477342

arulbero

legendary

Activity: 1914

Merit: 2071

Quote from: WanderingPhilospher on December 10, 2023, 01:23:21 PM

I am currently working on trying to create the "wilds" in the DB and then run "tames" for the search.

Keep your ideas and scripts coming arulbero. Many thanks for all of your insights over the last few years. You are Way smarter than me with python and ecc math, 100%!

The ideas in my script are:

- put 2^23 keys in 2^23 bits (mcdouglasx's idea)

- then produce a random key P and from P get 128 (not 64) subtractions : P - sustract*G, P - 2*sustract*G, ..., P - 128*sustract*G

- I get in this way a large string of 128 bits; from this large string I extract 64 strings of consecutive 64 bits (from 1 to 64, from 2 to 65, from 3 to 66, ..., from 65 to 128)

- I do the same thing for: P-1G, P-2G, P-3G, ..., P -(sustract-1)*G

- now each key is represented not by 1 but by 64 strings of 64 bits each. In this way I can mantain low the size of the database.

- I compare all these strings (4 bytes each) against the database where the databases is divided in groups of 4 bytes each (in this case, the database is a set of 2^23/2^6 = 2^17 elements of 4 bytes each)

- to see if an element of 4 byte is in database, i intersect the set of the 4 bytes elements of the databases with the set of the 4 bytes elements generated in the search; this step is pretty fast, because python automatically creates an hashtable.

WanderingPhilospher

full member

Activity: 1050

Merit: 219

Shooters Shoot...

Quote

'Only' doesn't mean you have to set > 1, it is useful only if the db size is 2^28 keys or more, 2^23 is small.

Difference in language maybe.

But when I see something that says, split_total_keys = 1 #> 1 only if sustract > 1, it means if sustract is greater than 1, adjust, if not greater than 1, leave alone.

Whereas if it said, split_total_keys = 1 #> 1 is useful only if the db size is 2^28 keys or more, then I would know it's an optimized option if keys are more than 2^x.

All good. Your script works; very creative.

I am currently working on trying to create the "wilds" in the DB and then run "tames" for the search.

Keep your ideas and scripts coming arulbero. Many thanks for all of your insights over the last few years. You are Way smarter than me with python and ecc math, 100%!

arulbero

legendary

Activity: 1914

Merit: 2071

Quote from: WanderingPhilospher on December 10, 2023, 12:58:49 PM

Ok, I changed this back to 1:

split_total_keys = 1 #2**4 #> 1 only if sustract > 1

I had it at

split_total_keys = 2**4 #> 1 only if sustract > 1

based on your note of greater than 1 if sustract is greater than 1.

Now it's taking anywhere from 4 seconds to 15 seconds to find key.

Your code is good. Just not easy to follow at times.

'Only' doesn't mean you have to set > 1, it is useful only if the db size is 2^28 keys or more, 2^23 is small.

Now I run 40 times in a row:

Code:

time for i in {1..40}; do python3 search_pk.py; done

and I got 91s, then 2.28 s for each key.

Worst result: 8.5 s, but many other under 1 second.

My script is not optimized to random search, but to 'consecutive' search.

WanderingPhilospher

full member

Activity: 1050

Merit: 219

Shooters Shoot...

Ok, I changed this back to 1:

split_total_keys = 1 #2**4 #> 1 only if sustract > 1

I had it at

split_total_keys = 2**4 #> 1 only if sustract > 1

based on your note of greater than 1 if sustract is greater than 1.

Now it's taking anywhere from 4 seconds to 15 seconds to find key.

Your code is good. Just not easy to follow at times.

Topic: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) - page 2. (Read 2283 times)