sssergy2705
Copper Member
Jr. Member
Offline
Activity: 197
Merit: 1
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 06, 2023, 11:17:30 AM |
|
The first version of the script worked, the second does not find matches. There may be an error in the code.
On my PC, 100 keys found out of 100, .... ![Huh](https://bitcointalk.org/Smileys/default/huh.gif) Did you set the same parameters in both scripts? About an hour and a half ago, I copied both scripts, created a database and launched the search script. I didn't change anything in the parameters. Ah, I uploaded a version of create_database that doesn't match with that version of the search_pk script Now it should work: To perform multiple search, for linux: time for i in {1..100}; do python3 search_pk_arulbero.py; done This is the public key: f5c03157f4a489ed71c0df0f37799431b3f432654a9bd6efdbb79ba767b62e81 I need to find this private key: 821480591424854
Private key found!!! Collision! 258530638003543 604085cce892dbb8bf9e70959ef178bc78fb123caaa4e9b1f3521139542da57f For example, I got a collision, how to calculate the private key?
|
|
|
|
arulbero
Legendary
Offline
Activity: 1915
Merit: 2074
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 06, 2023, 05:43:16 PM |
|
This is the public key: f5c03157f4a489ed71c0df0f37799431b3f432654a9bd6efdbb79ba767b62e81 I need to find this private key: 821480591424854
Private key found!!! Collision! 258530638003543 604085cce892dbb8bf9e70959ef178bc78fb123caaa4e9b1f3521139542da57f For example, I got a collision, how to calculate the private key? The key 821480591424854 is in the range 2^49 - 2^50 Try with these parameters: start_key = 1 num_public_keys = 2**50 bits_to_store = 64 bytes_to_store = bits_to_store//8 rate_of_key_to_generate = 2**24
Did you use bits_to_store = 64? And the other parameters?
|
|
|
|
arulbero
Legendary
Offline
Activity: 1915
Merit: 2074
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 06, 2023, 05:47:48 PM |
|
Ah, I uploaded a version of create_database that doesn't match with that version of the search_pk script Now it should work:
It works for me up to 0x81 and after that it does not seem to find any keys. I tried deleting and recreating the database from 0x80 but still nothing found. 0x80 = 128 What are you parameters? Like these? start_key = 1 num_public_keys = 2**32 bits_to_store = 64 bytes_to_store = bits_to_store//8 rate_of_key_to_generate = 2**20
|
|
|
|
sssergy2705
Copper Member
Jr. Member
Offline
Activity: 197
Merit: 1
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 06, 2023, 06:02:09 PM |
|
This is the public key: f5c03157f4a489ed71c0df0f37799431b3f432654a9bd6efdbb79ba767b62e81 I need to find this private key: 821480591424854
Private key found!!! Collision! 258530638003543 604085cce892dbb8bf9e70959ef178bc78fb123caaa4e9b1f3521139542da57f For example, I got a collision, how to calculate the private key? The key 821480591424854 is in the range 2^49 - 2^50 Try with these parameters: start_key = 1 num_public_keys = 2**50 bits_to_store = 64 bytes_to_store = bits_to_store//8 rate_of_key_to_generate = 2**24
Did you use bits_to_store = 64? And the other parameters? start_key = 2**49 num_public_keys = 2**50 bits_to_store = 64 bytes_to_store = bits_to_store//8 rate_of_key_to_generate = 2**20 In general, I already figured it out, the difference is 2**49). By the way, how to calculate this parameter? Calculate the golden mean. When you set it above 2**26, the search script eats up all the RAM. If you decrease it, the size of the database increases. rate_of_key_to_generate = 2**20
|
|
|
|
arulbero
Legendary
Offline
Activity: 1915
Merit: 2074
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 06, 2023, 06:08:55 PM |
|
start_key = 2**49 num_public_keys = 2**50 bits_to_store = 64 bytes_to_store = bits_to_store//8 rate_of_key_to_generate = 2**20 Actually, I already figured it out, the difference is just 2**49) 2**49 / 2**20 = 2**29 keys stored in DB. 2**20 keys generated in search script against 2**29 keys generated in create_database script = 2**49 couples. I presume that the probability of collision is not low with these numbers. The script is not optimized, it is only a proof of concept. It needs some work. Try with bits_to_store = 96, in this way the probability of collision is lower.
|
|
|
|
whanau
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 118
Merit: 36
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 06, 2023, 08:43:10 PM |
|
0x80 = 128 What are you parameters? Like these? start_key = 1 num_public_keys = 2**32 bits_to_store = 64 bytes_to_store = bits_to_store//8 rate_of_key_to_generate = 2**20
No I had 128 as per your original script instead of 2**20. I think I am not understanding how all these variables interact or when to change them. I changed to 2**20 and 0x82 (130) works. I will study some more. Thank you
|
|
|
|
Kpot87
Jr. Member
Offline
Activity: 40
Merit: 1
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 07, 2023, 10:18:37 AM |
|
start_key = 2**49 num_public_keys = 2**50 bits_to_store = 64 bytes_to_store = bits_to_store//8 rate_of_key_to_generate = 2**20 Actually, I already figured it out, the difference is just 2**49) 2**49 / 2**20 = 2**29 keys stored in DB. 2**20 keys generated in search script against 2**29 keys generated in create_database script = 2**49 couples. I presume that the probability of collision is not low with these numbers. The script is not optimized, it is only a proof of concept. It needs some work. Try with bits_to_store = 96, in this way the probability of collision is lower. Ok but how you image to work with bigger size of range, the nearest 2**130…? How much ram do you need to generate such equation ?
|
|
|
|
arulbero
Legendary
Offline
Activity: 1915
Merit: 2074
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 07, 2023, 12:03:23 PM |
|
Ok but how you image to work with bigger size of range, the nearest 2**130…? How much ram do you need to generate such equation ?
I don't image to work with bigger size of range. At this level the problem in my opinion is to shrink the size of database. That's all. To "cover" a 2**130 space, you need 2**65 keys with distance 2**65. 2**65 keys with 128 bits (at least) for each key means 2**73 bit = 2**70 bytes, 1 Billions of TB. If you use the script of the OP, 2**65 keys = 2**65 bits = 2**62 bytes = 4 Millions of TB. These are the numbers. These script are made for fun, not to become rich.
|
|
|
|
Kpot87
Jr. Member
Offline
Activity: 40
Merit: 1
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 07, 2023, 12:36:35 PM |
|
Ok but how you image to work with bigger size of range, the nearest 2**130…? How much ram do you need to generate such equation ?
I don't image to work with bigger size of range. At this level the problem in my opinion is to shrink the size of database. That's all. To "cover" a 2**130 space, you need 2**65 keys with distance 2**65. 2**65 keys with 128 bits (at least) for each key means 2**73 bit = 2**70 bytes, 1 Billions of TB. If you use the script of the OP, 2**65 keys = 2**65 bits = 2**62 bytes = 4 Millions of TB. These are the numbers. These script are made for fun, not to become rich. Nobody talk about to be reach, the question is like you told to shrink DB. But on big intervals … that’s all
|
|
|
|
mcdouglasx (OP)
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 252
Merit: 53
New ideas will be criticized and then admired.
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 07, 2023, 01:16:35 PM |
|
Ok but how you image to work with bigger size of range, the nearest 2**130…? How much ram do you need to generate such equation ?
I don't image to work with bigger size of range. At this level the problem in my opinion is to shrink the size of database. That's all. To "cover" a 2**130 space, you need 2**65 keys with distance 2**65. 2**65 keys with 128 bits (at least) for each key means 2**73 bit = 2**70 bytes, 1 Billions of TB. If you use the script of the OP, 2**65 keys = 2**65 bits = 2**62 bytes = 4 Millions of TB. These are the numbers. These script are made for fun, not to become rich. Although your numbers are correct, you forget about statistics and probabilities. because when you involve chance, the larger your sample, the larger your probabilities are, so when you sacrifice your sample size for speed, it can serve you well in small ranges but in high ranges the number of probable objects you can hit is always better. An example in the real world is rain, if the speed at which the water fell to the ground was double, it would wet less space on the earth, the drops would be larger. The fewer raindrops = the greater the proportion of dry soil. It's just the big problem with bsgs.
|
I'm not dead, long story... BTC bc1qxs47ttydl8tmdv8vtygp7dy76lvayz3r6rdahu
|
|
|
COBRAS
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 904
Merit: 22
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 08, 2023, 05:07:22 AM |
|
From start to finish. But it's not the speed, it's the size of the DB, only 121kb ![Smiley](https://bitcointalk.org/Smileys/default/smiley.gif) 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. I modified slightly the OP's 'create_database' script (1 bit for key, 128 kB), now it is a bit faster I tried with the search script too, but it is still slow (using bits, not bytes) Results: Making Binary Data-Base Keys generated: 1048576 Space covered by the keys spread with distance 16 in the database : 16777216
real 0m1,548s user 0m1,548s sys 0m0,000s
create_database.py #@mcdouglasx modified by arulbero import secp256k1 as ice import bitcoin import random from bitstring import BitArray
print("Making Binary Data-Base")
#pk = 25 498 121 788 = 0x5efce763c between 2**34 and 2**35, between 16 billions and 32 billions target_public_key = "029016f6bb53c86cbb410462bb01abdc258f5b9fb1e5528f19bc383685e1874391" target = ice.pub2upub(target_public_key)
numb = 2**20 # 1 million of keys. sustract= 2**4 #amount to subtract each time, If you modify this, use the same amount to scan. space_covered = numb*sustract #2**24 = 16 millions, space covered from the database print("Keys generated: " + str(numb)) print("Space covered by the keys spread with distance " + str(sustract) + " in the database : " + str(space_covered))
Low_m= 2**6 lm= numb // Low_m sustract_pub= ice.scalar_multiplication(sustract)
res= ice.point_loop_subtraction(lm, target, sustract_pub) my_str= BitArray(res[t*65+64]%2 for t in range(lm)) #0 if even, 1 if odd with open('data-base.bin', 'wb') as binary_file: my_str.tofile(binary_file)
for i in range (1,Low_m): lm_upub=ice.scalar_multiplication((lm*i)*sustract)
A1= ice.point_subtraction(target, lm_upub)
res=ice.point_loop_subtraction(lm, A1, sustract_pub) my_str= BitArray(res[t*65+64]%2 for t in range(lm)) #0 if even, 1 if odd
with open('data-base.bin', 'ab') as binary_file: my_str.tofile(binary_file)
Can you provide your BSGS scrypt ?
|
[
|
|
|
Kpot87
Jr. Member
Offline
Activity: 40
Merit: 1
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 09, 2023, 09:54:03 AM |
|
@macduglasx hi, how you provide working with mulpubs, about ram it’s clear and what about threads ? 1pub=1th? Tnx
|
|
|
|
arulbero
Legendary
Offline
Activity: 1915
Merit: 2074
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 09, 2023, 06:35:05 PM Last edit: December 10, 2023, 03:11:23 PM by arulbero |
|
I modified slightly the OP's 'create_database' script (1 bit for key, 128 kB, distance between 2 keys = 1) it takes about 111 minutes (less than 2 hours) to generate 2**32 keys (4 billions), size of the DB = 512 MBThe script search takes less than 1 second to retrieve a key in this space. create_database.py #@mcdouglasx modified by arulbero import secp256k1 as ice from bitstring import BitArray
#########################DATABASE PARAMETERS######################### prefix = '32_0' data_base_name = 'data-base'+prefix+'.bin'
num_public_keys = 2**32 # 4 billions of keys num_bytes_db = num_public_keys//8 # 1 bit for each key sustract= 2**0 #amount to subtract each time, If you modify this, use the same amount to scan. sustract_pub= ice.scalar_multiplication(sustract) space_covered = num_public_keys*sustract #2**32 = 4 billions, space covered
#pk = 32 294 923 307 823 = 0x1d5f3f6e8b2f between 2**44 and 2**45 target_public_key = "03f760d768600e639758836fda5da546c10b1d84886165a5a1a4586192518aaf77" target = ice.pub2upub(target_public_key)
Low_m= 2**8 #to save ram lm= num_public_keys // Low_m ###################################################################
print("Making Binary Data-Base") print()
res= ice.point_loop_subtraction(lm, target, sustract_pub) my_str= BitArray(res[t*65+64]%2 for t in range(lm)) #0 if even, 1 if odd
with open(data_base_name, 'wb') as binary_file: my_str.tofile(binary_file)
for i in range (1,Low_m): lm_upub=ice.scalar_multiplication((lm*i)*sustract)
A1= ice.point_subtraction(target, lm_upub)
res=ice.point_loop_subtraction(lm, A1, sustract_pub) my_str=BitArray(res[t*65+64]%2 for t in range(lm))
with open(data_base_name, 'ab') as binary_file: my_str.tofile(binary_file)
print("Keys generated: " + str(num_public_keys)) print("Space covered by the keys spread with distance " + str(sustract) + " in the database : " + str(space_covered))
search_pk.py #@mcdouglasx modified by arulbero import secp256k1 as ice from bitstring import BitArray import random import sys
#########################DATABASE PARAMETERS######################### prefix = '32_0' data_base_name = 'data-base'+prefix+'.bin'
num_public_keys = 2**32 # 4 billions of keys num_bytes_db = num_public_keys//8 # 1 bit for each key sustract= 2**0 #amount to subtract each time, If you modify this, use the same amount to scan. sustract_pub= ice.scalar_multiplication(sustract) space_covered = num_public_keys*sustract #2**32 = 4 billions, space covered
#pk = 32 294 923 307 823 = 0x1d5f3f6e8b2f between 2**44 and 2**45 target_public_key = "03f760d768600e639758836fda5da546c10b1d84886165a5a1a4586192518aaf77" target = ice.pub2upub(target_public_key) ###################################################################
########################SEARCH PARAMATERS########################## num = 1024+1024# collision margin in bits total_search_keys_to_generate = sustract split_total_keys = 1 #> 1 only if sustract > 1 multiple_search_keys_at_once = total_search_keys_to_generate//split_total_keys bytes_for_key = num//8
split_database = 2**9 #read only a fraction of the database to speedup the finding of the string and save RAM size_partial_db = num_bytes_db//split_database
pk_orig = 32294923307823 #pk = 32 294 923 307 823 = 0x1d5f3f6e8b2f between 2**44 and 2**45 space_search_start = pk_orig - space_covered #I'm assuming that the space search contains for sure the pk space_search_end = pk_orig + space_covered
##################################################################### print("Keys generated in DB: " + str(num_public_keys)) print("Space covered by the keys in DB (the keys are distributed in this space with distance " + str(sustract) + ") : " + str(space_covered)) print() print("This is the public key: " + target_public_key[2:]) print("I need to find this private key: " + str(pk_orig)) print() print("Scanning Binary Sequence") print("Looking in the range: "+str(space_search_start)+" " +str(space_search_end)) print()
while True: #pk0=random.randint(space_search_start, space_search_end) for t in range(split_total_keys): pk0=random.randint(space_search_start, space_search_end) b=BitArray() for r in range(multiple_search_keys_at_once): #how many different consecutive keys are generated at once against the keys in DB
target2 = ice.scalar_multiplication(pk0-t*multiple_search_keys_at_once-r) res=ice.point_loop_subtraction(2*num, target2, sustract_pub) b = b + (res[t*65+64]%2 for t in range(2*num)) #0 if even, 1 if odd #2*num -> means we utilize double size of collision margin for each key, in this way we can shift and obtain num windows of num bits b2 = () for r in range(multiple_search_keys_at_once): for j in range(num): b2 = b2 + b[(r*2*num)+j:(r*2*num)+j+num] #64 strings of 64 bits b3 = bytes(b2) b2_i = [ b3[j*bytes_for_key:j*bytes_for_key+bytes_for_key] for j in range(len(b3)//bytes_for_key)] set_search_keys = set(b2_i) with open(data_base_name, 'r+b') as f: for k in range(split_database): f.seek(0,1) partial_db = f.read(size_partial_db) dat_i = [partial_db[j*bytes_for_key:j*bytes_for_key+bytes_for_key] for j in range(size_partial_db//bytes_for_key)] set_database = set(dat_i) a = list(set_database & set_search_keys)
if(len(a) > 0): s = b2_i f = dat_i inx = f.index(a[0]) r_ind = s.index(a[0]) Pk = (pk0 - r_ind//num - (r_ind%num)*sustract - t*multiple_search_keys_at_once) + (k*size_partial_db*8 +(inx*num))*sustract print("Found!") if(Pk == pk_orig): print("The private key " + str(Pk)+ " was recovered successfully!") data = open("win.txt","a") data.write("Pk:"+" "+str(Pk)+"\n") data.close() sys.exit()
|
|
|
|
COBRAS
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 904
Merit: 22
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 09, 2023, 07:43:45 PM |
|
I modified slightly the OP's 'create_database' script (1 bit for key, 128 kB, distance between 2 keys = 1) it takes about 111 minutes (less than 2 hours) to generate 2**32 keys (4 billions), size of the DB = 512 MBThe script search takes less than 1 second to retrieve a key in this space. create_database.py #@mcdouglasx modified by arulbero import secp256k1 as ice from bitstring import BitArray
#########################DATABASE PARAMETERS######################### prefix = '28_0' data_base_name = 'data-base'+prefix+'.bin'
num_public_keys = 2**28 # 4 billions of keys num_bytes_db = num_public_keys//8 # 1 bit for each key sustract= 2**0 #amount to subtract each time, If you modify this, use the same amount to scan. sustract_pub= ice.scalar_multiplication(sustract) space_covered = num_public_keys*sustract #2**32 = 4 billions, space covered
#pk = 32 294 923 307 823 = 0x1d5f3f6e8b2f between 2**44 and 2**45 target_public_key = "03f760d768600e639758836fda5da546c10b1d84886165a5a1a4586192518aaf77" target = ice.pub2upub(target_public_key)
Low_m= 2**8 #to save ram lm= num_public_keys // Low_m ###################################################################
print("Making Binary Data-Base") print()
res= ice.point_loop_subtraction(lm, target, sustract_pub) my_str= BitArray(res[t*65+64]%2 for t in range(lm)) #0 if even, 1 if odd
with open(data_base_name, 'ab') as binary_file: my_str.tofile(binary_file)
for i in range (1,Low_m): lm_upub=ice.scalar_multiplication((lm*i)*sustract)
A1= ice.point_subtraction(target, lm_upub)
res=ice.point_loop_subtraction(lm, A1, sustract_pub) my_str=BitArray(res[t*65+64]%2 for t in range(lm))
with open(data_base_name, 'ab') as binary_file: my_str.tofile(binary_file)
print("Keys generated: " + str(num_public_keys)) print("Space covered by the keys spread with distance " + str(sustract) + " in the database : " + str(space_covered))
search_pk.py #@mcdouglasx modified by arulbero import secp256k1 as ice from bitstring import BitArray import random import sys
#########################DATABASE PARAMETERS######################### prefix = '32_0' data_base_name = 'data-base'+prefix+'.bin'
num_public_keys = 2**32 # 4 billions of keys num_bytes_db = num_public_keys//8 # 1 bit for each key sustract= 2**0 #amount to subtract each time, If you modify this, use the same amount to scan. sustract_pub= ice.scalar_multiplication(sustract) space_covered = num_public_keys*sustract #2**32 = 4 billions, space covered
#pk = 32 294 923 307 823 = 0x1d5f3f6e8b2f between 2**44 and 2**45 target_public_key = "03f760d768600e639758836fda5da546c10b1d84886165a5a1a4586192518aaf77" target = ice.pub2upub(target_public_key) ###################################################################
########################SEARCH PARAMATERS########################## num = 1024+512# collision margin in bits total_search_keys_to_generate = sustract split_total_keys = 2**0 #> 1 only if sustract > 1 multiple_search_keys_at_once = total_search_keys_to_generate//split_total_keys bytes_for_key = num//8
split_database = 2**3 #read only a fraction of the database to speedup the finding of the string and save RAM size_partial_db = num_bytes_db//split_database
pk_orig = 32294923307823 #pk = 32 294 923 307 823 = 0x1d5f3f6e8b2f between 2**44 and 2**45 space_search_start = pk_orig - space_covered #I'm assuming that all the space search is covered by keys in DB, space_search_end = pk_orig #otherwise we have to generate more than 'total_search_keys_to_generate = sustract' search_keys
##################################################################### print("Keys generated in DB: " + str(num_public_keys)) print("Space covered by the keys in DB (the keys are distributed in this space with distance " + str(sustract) + ") : " + str(space_covered)) print() print("This is the public key: " + target_public_key[2:]) print("I need to find this private key: " + str(pk_orig)) print() print("Scanning Binary Sequence") print("Looking in the range: "+str(space_search_start)+" " +str(space_search_end)) print()
while True: for t in range(split_total_keys): pk0=random.randint(space_search_start, space_search_end) b=BitArray() for r in range(multiple_search_keys_at_once): #how many different consecutive keys are generated at once against the keys in DB
target2 = ice.scalar_multiplication(pk0-t*multiple_search_keys_at_once-r) res=ice.point_loop_subtraction(2*num, target2, sustract_pub) b = b + (res[t*65+64]%2 for t in range(2*num)) #0 if even, 1 if odd #2*num -> means we utilize double size of collision margin for each key, in this way we can shift and obtain num windows of num bits b2 = () for r in range(multiple_search_keys_at_once): for j in range(num): b2 = b2 + b[(r*2*num)+j:(r*2*num)+j+num] #64 strings of 64 bits b3 = bytes(b2) b2_i = [ b3[j*bytes_for_key:j*bytes_for_key+bytes_for_key] for j in range(len(b3)//bytes_for_key)] set_search_keys = set(b2_i) with open(data_base_name, 'r+b') as f: for k in range(split_database): f.seek(0,1) partial_db = f.read(size_partial_db) dat_i = [partial_db[j*bytes_for_key:j*bytes_for_key+bytes_for_key] for j in range(size_partial_db//bytes_for_key)] set_database = set(dat_i) a = list(set_database & set_search_keys)
if(len(a) > 0): s = b2_i f = dat_i inx = f.index(a[0]) r_ind = s.index(a[0]) Pk = (pk0 - r_ind//num - (r_ind%num)*sustract - t*multiple_search_keys_at_once) + (k*size_partial_db*8 +(inx*num))*sustract print("Found!") if(Pk == pk_orig): print("The private key " + str(Pk)+ " was recovered successfully!") data = open("win.txt","a") data.write("Pk:"+" "+str(Pk)+"\n") data.close() sys.exit()
Good day, what about 2^65 range, posible or not ?
|
[
|
|
|
WanderingPhilospher
Full Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 1148
Merit: 236
Shooters Shoot...
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 09, 2023, 09:29:32 PM |
|
I modified slightly the OP's 'create_database' script (1 bit for key, 128 kB, distance between 2 keys = 1) it takes about 111 minutes (less than 2 hours) to generate 2**32 keys (4 billions), size of the DB = 512 MBThe script search takes less than 1 second to retrieve a key in this space. create_database.py #@mcdouglasx modified by arulbero import secp256k1 as ice from bitstring import BitArray
#########################DATABASE PARAMETERS######################### prefix = '28_0' data_base_name = 'data-base'+prefix+'.bin'
num_public_keys = 2**28 # 4 billions of keys num_bytes_db = num_public_keys//8 # 1 bit for each key sustract= 2**0 #amount to subtract each time, If you modify this, use the same amount to scan. sustract_pub= ice.scalar_multiplication(sustract) space_covered = num_public_keys*sustract #2**32 = 4 billions, space covered
#pk = 32 294 923 307 823 = 0x1d5f3f6e8b2f between 2**44 and 2**45 target_public_key = "03f760d768600e639758836fda5da546c10b1d84886165a5a1a4586192518aaf77" target = ice.pub2upub(target_public_key)
Low_m= 2**8 #to save ram lm= num_public_keys // Low_m ###################################################################
print("Making Binary Data-Base") print()
res= ice.point_loop_subtraction(lm, target, sustract_pub) my_str= BitArray(res[t*65+64]%2 for t in range(lm)) #0 if even, 1 if odd
with open(data_base_name, 'ab') as binary_file: my_str.tofile(binary_file)
for i in range (1,Low_m): lm_upub=ice.scalar_multiplication((lm*i)*sustract)
A1= ice.point_subtraction(target, lm_upub)
res=ice.point_loop_subtraction(lm, A1, sustract_pub) my_str=BitArray(res[t*65+64]%2 for t in range(lm))
with open(data_base_name, 'ab') as binary_file: my_str.tofile(binary_file)
print("Keys generated: " + str(num_public_keys)) print("Space covered by the keys spread with distance " + str(sustract) + " in the database : " + str(space_covered))
search_pk.py #@mcdouglasx modified by arulbero import secp256k1 as ice from bitstring import BitArray import random import sys
#########################DATABASE PARAMETERS######################### prefix = '32_0' data_base_name = 'data-base'+prefix+'.bin'
num_public_keys = 2**32 # 4 billions of keys num_bytes_db = num_public_keys//8 # 1 bit for each key sustract= 2**0 #amount to subtract each time, If you modify this, use the same amount to scan. sustract_pub= ice.scalar_multiplication(sustract) space_covered = num_public_keys*sustract #2**32 = 4 billions, space covered
#pk = 32 294 923 307 823 = 0x1d5f3f6e8b2f between 2**44 and 2**45 target_public_key = "03f760d768600e639758836fda5da546c10b1d84886165a5a1a4586192518aaf77" target = ice.pub2upub(target_public_key) ###################################################################
########################SEARCH PARAMATERS########################## num = 1024+512# collision margin in bits total_search_keys_to_generate = sustract split_total_keys = 2**0 #> 1 only if sustract > 1 multiple_search_keys_at_once = total_search_keys_to_generate//split_total_keys bytes_for_key = num//8
split_database = 2**3 #read only a fraction of the database to speedup the finding of the string and save RAM size_partial_db = num_bytes_db//split_database
pk_orig = 32294923307823 #pk = 32 294 923 307 823 = 0x1d5f3f6e8b2f between 2**44 and 2**45 space_search_start = pk_orig - space_covered #I'm assuming that all the space search is covered by keys in DB, space_search_end = pk_orig #otherwise we have to generate more than 'total_search_keys_to_generate = sustract' search_keys
##################################################################### print("Keys generated in DB: " + str(num_public_keys)) print("Space covered by the keys in DB (the keys are distributed in this space with distance " + str(sustract) + ") : " + str(space_covered)) print() print("This is the public key: " + target_public_key[2:]) print("I need to find this private key: " + str(pk_orig)) print() print("Scanning Binary Sequence") print("Looking in the range: "+str(space_search_start)+" " +str(space_search_end)) print()
while True: for t in range(split_total_keys): pk0=random.randint(space_search_start, space_search_end) b=BitArray() for r in range(multiple_search_keys_at_once): #how many different consecutive keys are generated at once against the keys in DB
target2 = ice.scalar_multiplication(pk0-t*multiple_search_keys_at_once-r) res=ice.point_loop_subtraction(2*num, target2, sustract_pub) b = b + (res[t*65+64]%2 for t in range(2*num)) #0 if even, 1 if odd #2*num -> means we utilize double size of collision margin for each key, in this way we can shift and obtain num windows of num bits b2 = () for r in range(multiple_search_keys_at_once): for j in range(num): b2 = b2 + b[(r*2*num)+j:(r*2*num)+j+num] #64 strings of 64 bits b3 = bytes(b2) b2_i = [ b3[j*bytes_for_key:j*bytes_for_key+bytes_for_key] for j in range(len(b3)//bytes_for_key)] set_search_keys = set(b2_i) with open(data_base_name, 'r+b') as f: for k in range(split_database): f.seek(0,1) partial_db = f.read(size_partial_db) dat_i = [partial_db[j*bytes_for_key:j*bytes_for_key+bytes_for_key] for j in range(size_partial_db//bytes_for_key)] set_database = set(dat_i) a = list(set_database & set_search_keys)
if(len(a) > 0): s = b2_i f = dat_i inx = f.index(a[0]) r_ind = s.index(a[0]) Pk = (pk0 - r_ind//num - (r_ind%num)*sustract - t*multiple_search_keys_at_once) + (k*size_partial_db*8 +(inx*num))*sustract print("Found!") if(Pk == pk_orig): print("The private key " + str(Pk)+ " was recovered successfully!") data = open("win.txt","a") data.write("Pk:"+" "+str(Pk)+"\n") data.close() sys.exit()
I like the creativity, but it seems like you already have to know the original pk. A lot of variables you have to sync up between the 2 scripts. I've been running a small 2^32 bit search and it's been running for 5 minutes with nothing found. That is with 2^21 keys generated with subtract of 2^4. This search should only take a few seconds. I should be able to give the DB script a pubkey, number of keys to generate and a subtract number, and then merely make sure the keys to generate and subtract number match up in the search script. Ok; your script is geared towards knowing the pk and searching from that pk - downwards. After changing these 2 lines: space_search_start = 0x80000000 #pk_orig - space_covered space_search_end = 0x100000000 #pk_orig
I was able to find the key. Running a search for the 2^36 key and it's been about 6 minutes with no key found. That is with 2^23 keys generated with subtraction of 2^4. This search takes way too long. Should be found within 10 seconds. Maybe I'm missing something.
|
|
|
|
WanderingPhilospher
Full Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 1148
Merit: 236
Shooters Shoot...
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 09, 2023, 10:02:17 PM |
|
When I run a 2^36 key test with my modified OP script, the results: This is the public key: 02b3e772216695845fa9dda419fb5daca28154d8aa59ea302f05e916635e47b9f6
Building the Binary Database
Targeting PubKey: 02b3e772216695845fa9dda419fb5daca28154d8aa59ea302f05e916635e47b9f6 Number of PubKeys: 9,000,000 Writing to file every: 900,000 keys Subtract Value: 9
Scanning Randomly
Current Random Key: 0x9dafa302d Jumps Made: 983 PK Found: 42387769980 PK Found: 0x9de820a7c
Total Time: 0:00:19.863232
Under 20 seconds to create DB and find the key. Maybe I am missing something in your script arulbero.
|
|
|
|
arulbero
Legendary
Offline
Activity: 1915
Merit: 2074
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 10, 2023, 10:56:52 AM Last edit: December 10, 2023, 03:20:48 PM by arulbero |
|
Running a search for the 2^36 key and it's been about 6 minutes with no key found. That is with 2^23 keys generated with subtraction of 2^4. This search takes way too long. Should be found within 10 seconds. Maybe I'm missing something.
There was a bug in the create_database script, now it is fixed (copy again that script) When I run a 2^36 key test with my modified OP script, the results: This is the public key: 02b3e772216695845fa9dda419fb5daca28154d8aa59ea302f05e916635e47b9f6
Building the Binary Database
Targeting PubKey: 02b3e772216695845fa9dda419fb5daca28154d8aa59ea302f05e916635e47b9f6 [b] Number of PubKeys: 9,000,000 Writing to file every: 900,000 keys Subtract Value: 9[/b]
Scanning Randomly
Current Random Key: 0x9dafa302d Jumps Made: 983 PK Found: 42387769980 PK Found: 0x9de820a7c
Total Time: 0:00:19.863232
Under 20 seconds to create DB and find the key.Maybe I am missing something in your script arulbero. And maybe I don't understand your script ![Smiley](https://bitcointalk.org/Smileys/default/smiley.gif) 9,000,000 keys with subtract value = 9 means that (in my language) you are covering a 9M * 9 = 81M = 2**27 range, then you want to find a key (42387769980, that is in 2**36 range) in a database that cover a 2**27 range, is it correct? Why you made: Jumps Made: 983? In which range you generate your random private keys? In my 2 scripts: space_covered in the DB = number of key stored in db * subtract value and search_space = [priv_key - size_of_space_covered_by_DB, priv_key + size_of_space_covered_by_DB] I generate: 1) in DB: only keys equally spaced 2) in the search script: consecutive keys (and for each of these keys, 128 subtractions); in your example, 16 * 128 subtractions In search script only 1 key is random generated, then I generate consecutive keys_search with number of consecutive keys_search = sustract value, in this way the random key has 50% to produce a sequence of 64 bits that falls in the DB. For each of these keys I perform 2*64 subtractions. You have to set the parameters in this way: ###DATABASE##### prefix = '23_4' data_base_name = 'data-base'+prefix+'.bin' num_public_keys = 2**23 # 8 millions of keys num_bytes_db = num_public_keys//8 # 1 bit for each key sustract= 2**4 #amount to subtract each time, If you modify this, use the same amount to scan. space_covered = num_public_keys*sustract #2**27 = 128 millions, space covered Low_m= 2**3 # writing to file every: 2**23/2**3 = 2**20 keys = 1M target_public_key = "02b3e772216695845fa9dda419fb5daca28154d8aa59ea302f05e916635e47b9f6" target = ice.pub2upub(target_public_key) > time python3 create_database.py Making Binary Data-Base
Keys generated: 8388608 Space covered by the keys spread with distance 16 in the database : 134217728
real 0m12,831s (but with Low_m = 2**7 it takes about 12s) user 0m12,030s sys 0m0,800s
> du -sh data-base23_4.bin 1,0M data-base23_4.bin
########################SEARCH PARAMATERS########################## num = 64# collision margin in bits (multiple of 64 bits) pk_orig = 42387769980 space_search_start = pk_orig - space_covered #in this way you know for sure that the space search contains the space covered space_search_end = pk_orig + space_covered > time python3 search_pk.py Keys generated in DB: 8388608 Space covered by the keys in DB (the keys are distributed in this space with distance 16) : 134217728
This is the public key: b3e772216695845fa9dda419fb5daca28154d8aa59ea302f05e916635e47b9f6 I need to find this private key: 42387769980
Scanning Binary Sequence Looking in the range: 42253552252 42521987708
Found! The private key 42387769980 was recovered successfully!
real 0m0,145s user 0m0,136s sys 0m0,009s
Then it takes about 13s to create the database and to retrieve the key. With: prefix = '28_4' num_public_keys = 2**28 #256 millions of keys num_bytes_db = num_public_keys//8 #1 bit for each key sustract= 2**4 #amount to subtract each time, If you modify this, use the same amount to scan. space_covered = num_public_keys*sustract #2**32 = 4 billions, space covered Low_m = 2**8 num = 256 #collision margin in bits (multiple of 64 bits) pk_orig = 42387769980 space_search_start = pk_orig - space_covered #in this way you know for sure that the space search contains the space covered space_search_end = pk_orig + space_covered it takes (on average) less than 1 second only to retrieve the key.
|
|
|
|
WanderingPhilospher
Full Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 1148
Merit: 236
Shooters Shoot...
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 10, 2023, 03:38:03 PM |
|
Why you made: Jumps Made: 983?
In which range you generate your random private keys?
In my 2 scripts: space_covered in the DB = number of key stored in db * subtract value and search_space = [priv_key - size_of_space_covered_by_DB, priv_key + size_of_space_covered_by_DB] Correct. My subtract value + keys generated only need to stay less than the search range; or more than 0x0. The difference is, my script doesn't need to know the private key to find a key, but yours does/did. I can't go from, priv key - search space, because I do not know the priv key. So in my example, my search was limited to 0x800000000 - 0x1000000000; because I do not know the private key, I have to run random checks all through the range. If my script used a known private key and I could narrow the range down to priv key - search space, I am sure it would find the key much faster. I may took a look and test your script(s) again and modify it so the priv key is not known and test results. DB creation will always be close to the same speed since we basically use the same coding; search time should also be close.
|
|
|
|
arulbero
Legendary
Offline
Activity: 1915
Merit: 2074
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 10, 2023, 04:24:40 PM |
|
Why you made: Jumps Made: 983?
In which range you generate your random private keys?
In my 2 scripts: space_covered in the DB = number of key stored in db * subtract value and search_space = [priv_key - size_of_space_covered_by_DB, priv_key + size_of_space_covered_by_DB] Correct. My subtract value + keys generated only need to stay less than the search range; or more than 0x0. The difference is, my script doesn't need to know the private key to find a key, but yours does/did. I can't go from, priv key - search space, because I do not know the priv key. So in my example, my search was limited to 0x800000000 - 0x1000000000; because I do not know the private key, I have to run random checks all through the range. If my script used a known private key and I could narrow the range down to priv key - search space, I am sure it would find the key much faster. I may took a look and test your script(s) again and modify it so the priv key is not known and test results. DB creation will always be close to the same speed since we basically use the same coding; search time should also be close. space_search_start = 0x800000000 space_search_stop = 0x1000000000 on average less than 2 seconds.
|
|
|
|
WanderingPhilospher
Full Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 1148
Merit: 236
Shooters Shoot...
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 10, 2023, 04:28:48 PM |
|
Why you made: Jumps Made: 983?
In which range you generate your random private keys?
In my 2 scripts: space_covered in the DB = number of key stored in db * subtract value and search_space = [priv_key - size_of_space_covered_by_DB, priv_key + size_of_space_covered_by_DB] Correct. My subtract value + keys generated only need to stay less than the search range; or more than 0x0. The difference is, my script doesn't need to know the private key to find a key, but yours does/did. I can't go from, priv key - search space, because I do not know the priv key. So in my example, my search was limited to 0x800000000 - 0x1000000000; because I do not know the private key, I have to run random checks all through the range. If my script used a known private key and I could narrow the range down to priv key - search space, I am sure it would find the key much faster. I may took a look and test your script(s) again and modify it so the priv key is not known and test results. DB creation will always be close to the same speed since we basically use the same coding; search time should also be close. space_search_start = 0x800000000 space_search_stop = 0x1000000000 on average less than 2 seconds. Yeah I don't get less than 2 seconds when I run the range with your script. It's been running for 2 minutes now with no key found. Maybe you changed up all the other parameters?
|
|
|
|
|