|
Title: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on November 27, 2023, 03:40:06 AM creating the lightweight database, billions keys.
last edit: 12/06/2023 1-we generate a bin file with the publickeys represented in 1s and 0s. 0=even, 1=odd. single publickey Code: #@mcdouglasx If you want to create a longer database than your memory supports For example, 1000 million keys and your memory limit is 100 million, divide by 10 changing this variable: Code: Low_m= 10 - You should use numbers like this: Code: num = 10000000000000 Code: num = 20000000000000 Avoid doing this or you will find private keys with the last numbers changed Code: num = 14678976447 we did it! We have a huge database, with little disk space. Because there is no sequence between even and odd pubkeys we can set a collision margin of 64, 128, 256.... By this I mean that as you increase the collision margin, the probability of finding an identical binary sequence decreases. What's the use of this? We just need to randomly generate binary sequences and check if they exist in the Database. searching single pubkey Code: #@mcdouglasx for multiple pubkeys - first we create the database by making random subtractions in a range specified by us, you can create your own list at your discretion Code: #@mcdouglasx Db multi-pubkeys -we create our database for multiple keys. Code: #@mcdouglasx scan multiple publickeys, bit version Code: #@mcdouglasx scan multiple publickeys, version bytes (faster). Code: #@mcdouglasx The difference between bit version and byte version is that with bytes some bits are masked within a byte, and it does not detect some collisions. This does not happen in the bit version. -------------------------------------------------------------------------- This code is just a demonstration that may not be optimized correctly, preferably make your own version in C. Don't forget to say thank you, to motivate me to contribute other ideas. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: ymgve2 on November 27, 2023, 04:01:40 AM What's the advantage of this over storing full public keys at specific intervals?
Also as you target a larger number of keys, your time spent scanning for the bit sequence increases, unless you use some smarter data structures (which would not be as small as 3.81mb anymore) Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on November 27, 2023, 04:12:00 AM What's the advantage of this over storing full public keys at specific intervals? Also as you target a larger number of keys, your time spent scanning for the bit sequence increases, unless you use some smarter data structures (which would not be as small as 3.81mb anymore) generating sequences 01001.... The possibility of finding an identical sequence is very low. The traditional way limits you in space, and it works the same. If you choose 64 as the collision margin you will divide your computing power/64, but with a huge database, you would still find the key faster than using xpoint. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: ymgve2 on November 27, 2023, 04:19:37 AM If you sort and store partial keys you can search by using binary search, cutting search time from linear to log. For larger number of keys, this becomes much faster than your single bit storage. To reduce space requirements, only store public keys that fit a criteria (like ending with the six lower bits zero) when building. When searching, subtract until you hit the bit criteria, then look up with binary search.
Also, the fact that the public keys you "store" have to be sequential makes these methods much less efficient than kangaro/BSGS etc. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on November 27, 2023, 04:58:24 AM If you sort and store partial keys you can search by using binary search, cutting search time from linear to log. For larger number of keys, this becomes much faster than your single bit storage. To reduce space requirements, only store public keys that fit a criteria (like ending with the six lower bits zero) when building. When searching, subtract until you hit the bit criteria, then look up with binary search. Also, the fact that the public keys you "store" have to be sequential makes these methods much less efficient than kangaro/BSGS etc. You only store binary sequences in large spaces, if you want to spread your database over the entire range, and not in the same consecutive range. Using jump addition and subtraction to your target. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: sssergy2705 on November 27, 2023, 03:04:08 PM generating sequences 01001.... The possibility of finding an identical sequence is very low. The traditional way limits you in space, and it works the same. If you choose 64 as the collision margin you will divide your computing power/64, but with a huge database, you would still find the key faster than using xpoint. Tested for 35 bit range, 50 million keys. You write that the probability of false collisions is small, but I see something else. Code: Pk: 0x4a6af41c8 Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on November 27, 2023, 03:15:03 PM generating sequences 01001.... The possibility of finding an identical sequence is very low. The traditional way limits you in space, and it works the same. If you choose 64 as the collision margin you will divide your computing power/64, but with a huge database, you would still find the key faster than using xpoint. Tested for 35 bit range, 50 million keys. You write that the probability of false collisions is small, but I see something else. Code: Pk: 0x4a6af41c8 If so, you must increase the collision margin from 64 to 128 or higher and problem solved. It is still random+ scalar so you can increase the margin of precision thanks to scalar multiplication. Edit: Although I tested it with a collision margin of 64 and I did not get false positives. Maybe you are doing something wrong if you modified the code, share details and we will find a solution. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: sssergy2705 on November 27, 2023, 03:20:51 PM What is that? I don't understand, are they false positives? If so, you must increase the collision margin from 64 to 128 or higher and problem solved. It is still random+ scalar so you can increase the margin of precision thanks to scalar multiplication. Code: import secp256k1 as ice Code: #@mcdouglasx Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: sssergy2705 on November 27, 2023, 03:27:17 PM By the way, for the 40-bit range there are no collisions at all.
What database size is required for higher ranges? How can one calculate the size for a specific range? Is it possible to parallelize work across physical processor cores? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: sssergy2705 on November 27, 2023, 03:38:07 PM You already deleted the message, but I saw it in the mail.
Here are other options. But I don't see any difference. Code: num = 1024 Although knowing the first digit and 50% of the second, this greatly facilitates further work) Thanks for the work done, I will continue testing. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: digaran on November 27, 2023, 04:13:38 PM Told you not to share anything public, no actually working script. ☠
So it only takes 1 bit to store a key? I can't imagine what would that be like with 100TB space to store, and with enough fire power + bsgs or keyhunt it should be easy to solve large keys. Can you also change n to secp256k1 n - leading f's? To check if you can figure something out of it. I'd say there will be no floats if you do that. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on November 27, 2023, 07:40:01 PM You already deleted the message, but I saw it in the mail. I'm sorry, I deleted the message because I'm not very sure of the solution, try this.Here are other options. But I don't see any difference. Code: num = 1024 Although knowing the first digit and 50% of the second, this greatly facilitates further work) Thanks for the work done, I will continue testing. inx = f.find(s) replace inx = f.find(s)*sustract Let me know if it gives you the correct pk at collision margin 64. my apologies. edit apparently it has to do with the jump of 10 in subtraction, not with the collision margin edit2: fixed Told you not to share anything public, no actually working script. ☠ Can you also change n to secp256k1 n - leading f's? To check if you can figure something out of it. I'd say there will be no floats if you do that. To change N directly to secp256k1.dll you can do it with a hex editor. The script works, the problem lies when it makes subtraction jumps other than 1, I hope it is solved. So it only takes 1 bit to store a key? I can't imagine what would that be like with 100TB space to store, and with enough fire power + bsgs or keyhunt it should be easy to solve large keys. This is a good option, the FUDs say that it is of no use, they do not see further, nor do they deign to try (blah blah), they only limit themselves to criticizing Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: sssergy2705 on November 27, 2023, 08:45:26 PM The script works, the problem lies when it makes subtraction jumps other than 1, I hope it is solved. I checked that the script is working correctly now. But in the high ranges of 40 and above, there are no coincidences yet. In principle, up to 40 bits and simple random can cope with the same success. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on November 27, 2023, 09:13:47 PM The script works, the problem lies when it makes subtraction jumps other than 1, I hope it is solved. I checked that the script is working correctly now. But in the high ranges of 40 and above, there are no coincidences yet. In principle, up to 40 bits and simple random can cope with the same success. you mean this range? 549755813887 :1099511627775 take into account: pubkey is in range? if you make jumps in database subtract= 10, in scan set it the same. Use 64 collision margin as long as you do not receive false positives, otherwise increasing it too much decreases your search speed. At high ranges use multiple objectives to cover more space in the range. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: NotATether on November 28, 2023, 07:37:53 AM I think you are writing the ones and zeros as bytes, when you should be writing them out as bits.
Here's what you should do to make your program faster. set a counter like i to 0, and then each time you perform a subtraction, do byte_value |= 0 [or 1] << i; i = (i + 1) % 8. Then only do a write after every 8 iterations. Although, you can make the writing process even faster by waiting until you fill thousands of bytes like this, and then just write them all at once in one batch. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on November 28, 2023, 02:04:24 PM I think you are writing the ones and zeros as bytes, when you should be writing them out as bits. This will depend on the amount of RAM you have, of course.Here's what you should do to make your program faster. set a counter like i to 0, and then each time you perform a subtraction, do byte_value |= 0 [or 1] << i; i = (i + 1) % 8. Then only do a write after every 8 iterations. Although, you can make the writing process even faster by waiting until you fill thousands of bytes like this, and then just write them all at once in one batch. However, That's what I did, I wrote 2^26 keys at once. Ate up at highest point, 14GB of RAM. If limited RAM you could do the counter as you suggested. I have found a key in the 44 bit range in about 3-4 minutes, 5 or 6 times. It's an interesting script. It's interesting in the way it can store massive amounts of "keys" in such a little file. For 2^26 keys, it only uses a file size of 8,192 kb. That is impressive. The searching method is not great in terms of speed. Also, you do not/should not use a start range of 1 (unless you are subtracting from original key and shrinking the key). When I generated 2^26 keys with a num = 64 option, I set the start range to 8796093022208-(2^26-64) = 8796025913408. I do not know where the key is but I know it's max (17592186044415) and it's minimum (8796093022208) and since my subtraction was set at 1 (sequential with no steps such as using a subtraction as 7 or 10, etc) I know the target priv/pubkey will only be from Target down to - 2^26 (keys generated) - 64 (num option). start (min) = 8796025913408 end (max) = 17592186044415 That's how I approached this script when running tests. You could also speed the script up using an upfront pub subtraction to cut the range in half. Example, if we know the key is in the 44 bit range, we can do an upfront subtraction of 0x80000000000, and then use that newly generated pub in this script and then search in a max 43 bit range. Now to ponder how to add this script's storage size function to an existing GPU script... Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on November 28, 2023, 03:23:37 PM I think you are writing the ones and zeros as bytes, when you should be writing them out as bits. Here's what you should do to make your program faster. set a counter like i to 0, and then each time you perform a subtraction, do byte_value |= 0 [or 1] << i; i = (i + 1) % 8. Then only do a write after every 8 iterations. Although, you can make the writing process even faster by waiting until you fill thousands of bytes like this, and then just write them all at once in one batch. This script speeds up the creation of the database. Code: #@mcdouglasx but as @WanderingPhilospher says This will depend on the amount of RAM you have, of course. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on November 28, 2023, 09:15:01 PM I think you are writing the ones and zeros as bytes, when you should be writing them out as bits. Here's what you should do to make your program faster. set a counter like i to 0, and then each time you perform a subtraction, do byte_value |= 0 [or 1] << i; i = (i + 1) % 8. Then only do a write after every 8 iterations. Although, you can make the writing process even faster by waiting until you fill thousands of bytes like this, and then just write them all at once in one batch. This script speeds up the creation of the database. Code: #@mcdouglasx but as @WanderingPhilospher says This will depend on the amount of RAM you have, of course. How would you break it up as NotA was saying: "|= 0 [or 1] << i; i = (i + 1) % 8" for those with smaller RAM. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: Kpot87 on November 28, 2023, 09:40:14 PM I think you are writing the ones and zeros as bytes, when you should be writing them out as bits. Here's what you should do to make your program faster. set a counter like i to 0, and then each time you perform a subtraction, do byte_value |= 0 [or 1] << i; i = (i + 1) % 8. Then only do a write after every 8 iterations. Although, you can make the writing process even faster by waiting until you fill thousands of bytes like this, and then just write them all at once in one batch. This script speeds up the creation of the database. Code: #@mcdouglasx but as @WanderingPhilospher says This will depend on the amount of RAM you have, of course. Hi! get this error num = 128000000 Traceback (most recent call last): File "D:\BTC\lightweight-database\lightweight-database\binary_Db.py", line 20, in <module> hc= int(h[2:], 16) ^^^^^^^^^^^^^^ ValueError: invalid literal for int() with base 16: '' Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on November 28, 2023, 10:12:18 PM Hi! get this error Traceback (most recent call last): File "D:\BTC\lightweight-database\lightweight-database\binary_Db.py", line 20, in <module> hc= int(h[2:], 16) ^^^^^^^^^^^^^^ ValueError: invalid literal for int() with base 16: '' I just tested and works, apparently that mistakes occurs when you try to put an additional line if you have an previous script, update. How would you break it up as NotA was saying: "|= 0 [or 1] << i; i = (i + 1) % 8" for those with smaller RAM. The script works like this: You have a database like this 1010100010110101000101101010001010101000101101000101101010101010001011010100010 1101010001010101000101101010001011011010100010000 target is = 1101010001011010100010101010001 The target is in: 10101000101101010001011010100010101010001011010001011010101010100010110101000101101010001010101000101101010001011011010100010000 If we separate in bits: 10101000 1011010 10001011 01010001 01010100 01011010 00101101 01010101 00010110 10100010 11010100 01010101 00010110 10100010 11011010 10001000 No coincidences were found. edit: I update. - Script aggregate that solves the memory limit Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on November 28, 2023, 10:16:58 PM Quote The script works like this: Lol, say what?You have a database like this 1010100010110101000101101010001010101000101101000101101010101010001011010100010 1101010001010101000101101010001011011010100010000 target is = 1101010001011010100010101010001 The target is in: 1010100010110101000101101010001010101000101101000101101010101010001011010100010 1101010001010101000101101010001011011010100010000 If we separate in bits: 10101000 1011010 10001011 01010001 01010100 01011010 00101101 01010101 00010110 10100010 11010100 01010101 00010110 10100010 11011010 10001000 No coincidences were found. I was asking this: If I want to generate 2^27 keys, but I am limited on RAM, how can I write say 2^20 keys to file, then the next 2^20 keys to file, until all 2^27 keys have been written to file? Using the suggestion or your own, like NotATether was suggesting... i = (i + 1) % 8 Make sense? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on November 28, 2023, 11:44:50 PM Quote The script works like this: Lol, say what?You have a database like this 1010100010110101000101101010001010101000101101000101101010101010001011010100010 1101010001010101000101101010001011011010100010000 target is = 1101010001011010100010101010001 The target is in: 1010100010110101000101101010001010101000101101000101101010101010001011010100010 1101010001010101000101101010001011011010100010000 If we separate in bits: 10101000 1011010 10001011 01010001 01010100 01011010 00101101 01010101 00010110 10100010 11010100 01010101 00010110 10100010 11011010 10001000 No coincidences were found. I was asking this: If I want to generate 2^27 keys, but I am limited on RAM, how can I write say 2^20 keys to file, then the next 2^20 keys to file, until all 2^27 keys have been written to file? Using the suggestion or your own, like NotATether was suggesting... i = (i + 1) % 8 Make sense? Lol, Sorry. Added the new script, which solves it. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: GR Sasa on November 29, 2023, 08:54:33 AM - Can this script be useful for puzzles that don't have public key revealed?
- I wish someone can implement mcdouglasx script in C, it will be faster and more efficient in term of speed and RAM usage. EDIT: I don't know how this script can be useful against the massive monster #130. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on November 29, 2023, 12:36:04 PM Regarding the scan script; if I use any subtract other than one, it always gets a false positive.
I've used subtract values from 16 up to in the thousands and always get a wrong result (false positive). If you use a large subtraction number, the result shows up way out of the upper limit range. Can you shed any wisdom as to why? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: Kpot87 on November 29, 2023, 01:33:26 PM Regarding the scan script; if I use any subtract other than one, it always gets a false positive. have you possible to generate DB more than 2**28? I've used subtract values from 16 up to in the thousands and always get a wrong result (false positive). If you use a large subtraction number, the result shows up way out of the upper limit range. Can you shed any wisdom as to why? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on November 29, 2023, 02:43:33 PM Regarding the scan script; if I use any subtract other than one, it always gets a false positive. have you possible to generate DB more than 2**28? I've used subtract values from 16 up to in the thousands and always get a wrong result (false positive). If you use a large subtraction number, the result shows up way out of the upper limit range. Can you shed any wisdom as to why? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on November 29, 2023, 02:51:54 PM Regarding the scan script; if I use any subtract other than one, it always gets a false positive. If in subtraction you used 16 to create the db in the search script you should do the same, it is not that they are false positives, it is that the pk calculation is deconfigured if it does not have the correct values.I've used subtract values from 16 up to in the thousands and always get a wrong result (false positive). If you use a large subtraction number, the result shows up way out of the upper limit range. Can you shed any wisdom as to why? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: Kpot87 on November 29, 2023, 03:00:07 PM Regarding the scan script; if I use any subtract other than one, it always gets a false positive. have you possible to generate DB more than 2**28? I've used subtract values from 16 up to in the thousands and always get a wrong result (false positive). If you use a large subtraction number, the result shows up way out of the upper limit range. Can you shed any wisdom as to why? 3 hours nothing changed? no file *.bin created... what can be wrong& @mcdouglasx Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: sssergy2705 on November 29, 2023, 03:08:36 PM Regarding the scan script; if I use any subtract other than one, it always gets a false positive. have you possible to generate DB more than 2**28? I've used subtract values from 16 up to in the thousands and always get a wrong result (false positive). If you use a large subtraction number, the result shows up way out of the upper limit range. Can you shed any wisdom as to why? 3 hours nothing changed? no file *.bin created... what can be wrong& @mcdouglasx I have the same. Range 45 bits, 100000000 keys. More than 12 hours of work, but still no database file... The old version of the database creation script worked, the one that first saved it to a text file. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: sssergy2705 on November 29, 2023, 03:10:38 PM I have generated a DB with 2**32 Keys in it. Can you tell me how you created the database? Apparently you have a different method for creating a database. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on November 29, 2023, 03:14:46 PM Regarding the scan script; if I use any subtract other than one, it always gets a false positive. If in subtraction you used 16 to create the db in the search script you should do the same, it is not that they are false positives, it is that the pk calculation is deconfigured if it does not have the correct values.I've used subtract values from 16 up to in the thousands and always get a wrong result (false positive). If you use a large subtraction number, the result shows up way out of the upper limit range. Can you shed any wisdom as to why? A few of what I am talking about. Code: Pk: 11739509615 The correct result should have been = 0xB862A62E Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on November 29, 2023, 03:17:33 PM Regarding the scan script; if I use any subtract other than one, it always gets a false positive. have you possible to generate DB more than 2**28? I've used subtract values from 16 up to in the thousands and always get a wrong result (false positive). If you use a large subtraction number, the result shows up way out of the upper limit range. Can you shed any wisdom as to why? 3 hours nothing changed? no file *.bin created... what can be wrong& @mcdouglasx Quote Can you tell me how you created the database? How many keys are you trying to generate?!Apparently you have a different method for creating a database. For me to make a 2^32 DB, it took over 5 hours. I used the low memory script and wrote to file 2^26 keys, roughly every 5 minutes. 64 (2^32 / 2^26) x 5 minutes = 320 minutes Also, just for info, a DB with 2^32 values = 524 MB (incredible!) Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on November 29, 2023, 03:45:28 PM Regarding the scan script; if I use any subtract other than one, it always gets a false positive. If in subtraction you used 16 to create the db in the search script you should do the same, it is not that they are false positives, it is that the pk calculation is deconfigured if it does not have the correct values.I've used subtract values from 16 up to in the thousands and always get a wrong result (false positive). If you use a large subtraction number, the result shows up way out of the upper limit range. Can you shed any wisdom as to why? A few of what I am talking about. Code: Pk: 11739509615 The correct result should have been = 0xB862A62E I'll check the script, maybe there's something I'm missing, do you use the "single key"? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: sssergy2705 on November 29, 2023, 03:46:38 PM How many keys are you trying to generate?! For me to make a 2^32 DB, it took over 5 hours. I used the low memory script and wrote to file 2^26 keys, roughly every 5 minutes. 64 (2^32 / 2^26) x 5 minutes = 320 minutes Also, just for info, a DB with 2^32 values = 524 MB (incredible!) Can you share your script to create the database file? I want to create a file of size 2000000000 keys to test on puzzle 65. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on November 29, 2023, 03:51:18 PM How many keys are you trying to generate?! For me to make a 2^32 DB, it took over 5 hours. I used the low memory script and wrote to file 2^26 keys, roughly every 5 minutes. 64 (2^32 / 2^26) x 5 minutes = 320 minutes Also, just for info, a DB with 2^32 values = 524 MB (incredible!) Can you share your script to create the database file? I want to create a file of size 2000000000 keys to test on puzzle 65. I have it prefilled out for you: Code: #@mcdouglasx It will write to file, every 10,000,000 keys. Let me know if it works for you. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on November 29, 2023, 04:02:40 PM Quote I'll check the script, maybe there's something I'm missing, do you use the "single key"? Yes, the single key. I am pretty sure I was getting the bad results when using the low memory script to generate the database. I can run tests later, but maybe something is throwing it off when using the low memory script and writing to database file every x amount of keys? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: digaran on November 29, 2023, 04:07:52 PM @WP, do you notice anything in these keys?
Code: Pk: 11739509615 Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: sssergy2705 on November 29, 2023, 04:09:17 PM How many keys are you trying to generate?! For me to make a 2^32 DB, it took over 5 hours. I used the low memory script and wrote to file 2^26 keys, roughly every 5 minutes. 64 (2^32 / 2^26) x 5 minutes = 320 minutes Also, just for info, a DB with 2^32 values = 524 MB (incredible!) Can you share your script to create the database file? I want to create a file of size 2000000000 keys to test on puzzle 65. I have it prefilled out for you: Code: #@mcdouglasx It will write to file, every 10,000,000 keys. Let me know if it works for you. binary_file = open('130Bit.bin', 'wb') ---------------------------------------- binary_file = open('65Bit.bin', 'ab') I understand the meaning, only the names of the files need to be changed) Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on November 29, 2023, 04:23:33 PM How many keys are you trying to generate?! For me to make a 2^32 DB, it took over 5 hours. I used the low memory script and wrote to file 2^26 keys, roughly every 5 minutes. 64 (2^32 / 2^26) x 5 minutes = 320 minutes Also, just for info, a DB with 2^32 values = 524 MB (incredible!) Can you share your script to create the database file? I want to create a file of size 2000000000 keys to test on puzzle 65. I have it prefilled out for you: Code: #@mcdouglasx It will write to file, every 10,000,000 keys. Let me know if it works for you. binary_file = open('130Bit.bin', 'wb') ---------------------------------------- binary_file = open('65Bit.bin', 'ab') I understand the meaning, only the names of the files need to be changed) Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on November 29, 2023, 04:32:47 PM Quote I'll check the script, maybe there's something I'm missing, do you use the "single key"? Yes, the single key. I am pretty sure I was getting the bad results when using the low memory script to generate the database. I can run tests later, but maybe something is throwing it off when using the low memory script and writing to database file every x amount of keys? I just created a db with low memory and all the results were correct. share your script Maybe you are not putting this part the same as when you created the db. Code: sustract= 16 #amount to subtract each time. If you create a db with subtract= 16 in scan it should be the same. If everything is correct and you continue to receive different pk, raise the collision margin a little from 64 to 80 (the higher the range you scan, the more likely a false positive is). Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on November 29, 2023, 05:18:12 PM Something strange is definitely happening.
I have to calmly review the error. -definitely not the collision margin. -python expresses results wrong sometimes (I don't think so) -the script gives good results but in certain cases it doesn't. -Does the "bitstring" module sometimes fail? - At a certain point in the database, bits are skipped and the calculations are not correct? -does the script misinterpret some bytes? Pk: 1033162084 Pk: 1033162084 Pk: 1033379684 Pk: 1033162084 Pk: 1033162084 Pk: 1033597284 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033379684 Pk: 1033488484 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033597284 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033488484 Pk: 1033597284 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033597284 Pk: 1033162084 edit: These lines are definitely interfering. Code: Low_m= 16 Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on November 29, 2023, 05:32:42 PM Something strange is definitely happening. Can you not rewrite lowmem script to something easier (less code)I have to calmly review the error. -definitely not the collision margin. -python expresses results wrong sometimes (I don't think so) -the script gives good results but in certain cases it doesn't. -Does the "bitstring" module sometimes fail? - At a certain point in the database, bits are skipped and the calculations are not correct? -does the script misinterpret some bytes? Pk: 1033162084 Pk: 1033162084 Pk: 1033379684 Pk: 1033162084 Pk: 1033162084 Pk: 1033597284 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033379684 Pk: 1033488484 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033597284 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033488484 Pk: 1033597284 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033597284 Pk: 1033162084 edit: These lines are definitely interfering. Code: Low_m= 16 And without bringing in the Bitcoin library? Something like NotATether was mentioning? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on November 30, 2023, 01:28:34 AM Something strange is definitely happening. Can you not rewrite lowmem script to something easier (less code)I have to calmly review the error. -definitely not the collision margin. -python expresses results wrong sometimes (I don't think so) -the script gives good results but in certain cases it doesn't. -Does the "bitstring" module sometimes fail? - At a certain point in the database, bits are skipped and the calculations are not correct? -does the script misinterpret some bytes? Pk: 1033162084 Pk: 1033162084 Pk: 1033379684 Pk: 1033162084 Pk: 1033162084 Pk: 1033597284 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033379684 Pk: 1033488484 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033597284 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033488484 Pk: 1033597284 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033162084 Pk: 1033597284 Pk: 1033162084 edit: These lines are definitely interfering. Code: Low_m= 16 And without bringing in the Bitcoin library? Something like NotATether was mentioning? fixed, please delete previous db. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on November 30, 2023, 02:13:12 AM Quote fixed, please delete previous db. So when using num and Low_m, we should use numbers that leave no remainder, correct?Such as 2^32 / 2^26 = 64; this would be ok, right? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on November 30, 2023, 02:49:03 AM Quote fixed, please delete previous db. So when using num and Low_m, we should use numbers that leave no remainder, correct?Such as 2^32 / 2^26 = 64; this would be ok, right? yes. A quick way to try without complete DB is: You load your configuration. example: You choose a PK within the range: PK: 4294960000 NUM = 4294967296 Low_m = 67108864 You start the script After a minute cancel. Then in the search script you choose a range close to your test PK. So: #range START = 4294950000 END = 4294990000 You start the search If you get PK: 4294960000 It means that your database will be executed without errors and without false positives. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 01, 2023, 05:12:28 PM After numerous, 100s of tests, I really do not understand the scan script.
If I generate 2^20 keys using the database script (with a subtraction of 1); it should take my target pubkey and generate/subtract 2^20 consecutive keys from my target pubkey. OK, I got that. But when I run the scan script, if the random hits anywhere in the range of target pubkey - 2^20, it should result in a hit/match/key found. However, it does not. I even tested with incrementing the pk (private key/integer position), versus random. Again, if I have 2^20 generated keys in database, I should be able to start pk position at 0 or 1, and increment by 2^20 private keys, and always get a hit/match/key found. But that was not the case. Help me understand why this is so, thanks. Also, why does the script need a margin collision on the scan script? My understanding is takes the pk that the rand generator has landed on, and does a subtraction loop 64 times (default). Again, If I land on any key within target pub - 2^20, it should result in a hit. Why would I need to do 64 subtraction loops. Thanks. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on December 01, 2023, 06:46:12 PM After numerous, 100s of tests, I really do not understand the scan script. If I generate 2^20 keys using the database script (with a subtraction of 1); it should take my target pubkey and generate/subtract 2^20 consecutive keys from my target pubkey. OK, I got that. But when I run the scan script, if the random hits anywhere in the range of target pubkey - 2^20, it should result in a hit/match/key found. However, it does not. I even tested with incrementing the pk (private key/integer position), versus random. Again, if I have 2^20 generated keys in database, I should be able to start pk position at 0 or 1, and increment by 2^20 private keys, and always get a hit/match/key found. But that was not the case. Help me understand why this is so, thanks. Also, why does the script need a margin collision on the scan script? My understanding is takes the pk that the rand generator has landed on, and does a subtraction loop 64 times (default). Again, If I land on any key within target pub - 2^20, it should result in a hit. Why would I need to do 64 subtraction loops. Thanks. We import the modules. Code: #@mcdouglasx We select the range where our privatekey is supposed to be located. Code: #range we open the loop Code: while True: We generate a random pk within the chosen range and generate the upub. Code: pk= random.randint(start, end) Here we subtract from the pk 64 times "G" or the number that we chose to subtract when we created the database (it must be the same one with which you created the database) Code: num = 64 # collision margin. Why 64 in collision margin? because we need to store 64 pubkeys identified with 1s and 0s. so as we will see: Code: my_str ="1010100010110101000101101010001010101000101101000101101010101010" Why not less than 64?, 16? Code: my_str ="1010100010110101" because if it is less, you can find equal sequences belonging to other pks (false positives). -we transform this sequence into bytes: Code: b = bytes(BitArray(bin=my_str)) we look for a match in the database Code: file = open("data-base.bin", "rb")We find the position of "b" in the database and multiply by the chosen subtraction. Code: inx = f.find(s)*sustract we get the correct pk adding (pk obtained randomly + (position of the target in the database* the subtraction)) + (position of the target in the database* the subtraction)* 7) where seven is the maximum number of bits in a byte that are counted like this (01234567). Code: Pk = (int(pk) + int(inx_0))+int(inx_0)*7 we save the result. Code: data = open("win.txt","a")Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 01, 2023, 07:05:51 PM Ok, but you didn't answer my most important question lol.
If my target pubkey's priv key is (TPK) is 123456789 and I generate 2^20 keys, with subtraction value of 1, then the database now contains TPK - 2^20 consecutive keys. In other words, TPK - 1, TPK - 2, TPK - 3,...TPK - 2^20. So in the database now are the corresponding pubkeys to, 123456788, 123456787, 123456786, ...., 122408213. Now, when I run the scan and I land on any priv keys from 123456788 to 122408213, I should get a match/solved key. But that has not been the case. When I run an increment test (only way I know the above doesn't result in a match); I should be able to start my priv key counter at 1 and increment by 2^20 and eventually get a match. priv key = 1; no match priv key = 1+1048576 (last position of priv key plus increment of 2^20); no match ... priv key = 122683392 (increment * 117); should be a match because 122683392 is within the range of 123456788 to 122408213. But program skips the match and keeps on going. Why would this be? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on December 01, 2023, 08:07:38 PM Ok, but you didn't answer my most important question lol. If my target pubkey's priv key is (TPK) is 123456789 and I generate 2^20 keys, with subtraction value of 1, then the database now contains TPK - 2^20 consecutive keys. In other words, TPK - 1, TPK - 2, TPK - 3,...TPK - 2^20. So in the database now are the corresponding pubkeys to, 123456788, 123456787, 123456786, ...., 122408213. Now, when I run the scan and I land on any priv keys from 123456788 to 122408213, I should get a match/solved key. But that has not been the case. When I run an increment test (only way I know the above doesn't result in a match); I should be able to start my priv key counter at 1 and increment by 2^20 and eventually get a match. priv key = 1; no match priv key = 1+1048576 (last position of priv key plus increment of 2^20); no match ... priv key = 122683392 (increment * 117); should be a match because 122683392 is within the range of 123456788 to 122408213. But program skips the match and keeps on going. Why would this be? I'm going to test it. -- update: On my side everything is going well, you should receive matches unless there is an error or you search in the wrong range. You can share this data to emulate your search: for the database. target= num = subtract= Low_m= edit= 2 for your example start= 122408213-64 end= 123456789-64 they all match. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 01, 2023, 08:45:15 PM Im not doing a random like in your initial scan script. I am doing an increment.
Did you do an increment test? There is no range; start at priv key 1 and increment by number of keys generated during database build. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on December 01, 2023, 09:08:48 PM Im not doing a random like in your initial scan script. I am doing an increment. Did you do an increment test? There is no range; start at priv key 1 and increment by number of keys generated during database build. for your example pk= 123456789 start= 122408213+64 end= 123456789-64 they all match. If you start from pk 1 you will have a first match at start= 122408213+64 If you want to test a single pk it would be like this: Code: #@mcdouglasx If you want to obtain incremental matching you must change the order of the database, because its order is reversed. 111000 incremental you get 000111 do not match. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 01, 2023, 09:18:32 PM Quote If you want to obtain incremental matching you must change the order of the database, because its order is reversed. 111000 incremental you get 000111 do not match. I'm still lost lol. You are still giving an example of a range. I am not using a range. I am using the start as pk = 0; then increment by the number of keys generated. If increment was 7 (if I only generated 7 keys in the database), the pk's would look like: 0 7 14 21 28 35 ... 763 770 If the target pubkey's pk was 777; when my increment reaches pk 770, that should be a match (777 - 770 = 7) Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on December 01, 2023, 09:30:19 PM Quote If you want to obtain incremental matching you must change the order of the database, because its order is reversed. 111000 incremental you get 000111 do not match. I'm still lost lol. You are still giving an example of a range. I am not using a range. I am using the start as pk = 0; then increment by the number of keys generated. If increment was 7 (if I only generated 7 keys in the database), the pk's would look like: 0 7 14 21 28 35 ... 763 770 If the target pubkey's pk was 777; when my increment reaches pk 770, that should be a match (777 - 770 = 7) What are you increasing? if you create an incremental database 1:1000000 for search you must do sums in loop of +64 and you will get matches from 1 to (1000000-64) Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 01, 2023, 09:35:15 PM Quote What are you increasing? The private key! Your script has a random range for the private key: Code: start= 1033100000 I am incrementing the pk! pk = 0 ------ pk = pk + 7 (or however many keys created during database creation. Again, I am talking about your scan / search script; the script that searches for a match lol. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on December 01, 2023, 09:46:28 PM Quote What are you increasing? The private key! Your script has a random range for the private key: Code: start= 1033100000 I am incrementing the pk! pk = 0 ------ pk = pk + 7 (or however many keys created during database creation. Again, I am talking about your scan / search script; the script that searches for a match lol. I know you are talking about the search script but I mention the database because they work in pairs, you cannot subtract 1 million from the target and then search incrementally. because in database the bits obtained would be inverted database sequence 01011110 incremental 01111010 so you won't get matches. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 01, 2023, 09:50:52 PM Quote What are you increasing? The private key! Your script has a random range for the private key: Code: start= 1033100000 I am incrementing the pk! pk = 0 ------ pk = pk + 7 (or however many keys created during database creation. Again, I am talking about your scan / search script; the script that searches for a match lol. I know you are talking about the search script but I mention the database because they work in pairs, you cannot subtract 1 million from the target and then search incrementally. because in database the bits obtained would be inverted database sequence 01011110 incremental 01111010 so you won't get matches. Why does it matter how I reached (my example above with 777) pk 770, whether I reached it by landing on it incrementally or by random? That makes no sense. If I land on 770 regardless of how I landed on it, I should get a match. If I am incrementing my search rather than random, when I land on 770, the script should calculate 770-64 and that should be a match. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on December 01, 2023, 10:10:50 PM Quote What are you increasing? The private key! Your script has a random range for the private key: Code: start= 1033100000 I am incrementing the pk! pk = 0 ------ pk = pk + 7 (or however many keys created during database creation. Again, I am talking about your scan / search script; the script that searches for a match lol. I know you are talking about the search script but I mention the database because they work in pairs, you cannot subtract 1 million from the target and then search incrementally. because in database the bits obtained would be inverted database sequence 01011110 incremental 01111010 so you won't get matches. Why does it matter how I reached (my example above with 777) pk 770, whether I reached it by landing on it incrementally or by random? That makes no sense. If I land on 770 regardless of how I landed on it, I should get a match. If I am incrementing my search rather than random, when I land on 770, the script should calculate 770-64 and that should be a match. if you only modify: Code: pk= random.randint(start, end) you create your database from 777:1 in search incremental match 65, 66,67,68......until 777 Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 01, 2023, 10:13:55 PM I give up lol.
It doesnt work with incrementing pk versus random pk. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on December 01, 2023, 10:18:24 PM I give up lol. It doesnt work with incrementing pk versus random pk. You are doing something wrong in your incremental script. If you post it maybe I'll see your mistake. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 01, 2023, 10:47:34 PM I give up lol. It doesnt work with incrementing pk versus random pk. You are doing something wrong in your incremental script. If you post it maybe I'll see your mistake. I just tried again lol. Use this as target pub = 0209c58240e50e3ba3f833c82655e8725c037a2294e14cf5d73a5df8d56159de69 Create 4,000,000 keys in database with subtraction of 1, and Low_m = 1 Start your pk at 0 and then increment by 4,000,000 I use: pk = 0 (start) and then in the while true or the main: pk = pk + 4000000 (increment) I ran a test in the 28 bit range with 1 million keys and incremented and it worked. But the above test did not. ? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on December 01, 2023, 11:23:26 PM Use this as target pub = 0209c58240e50e3ba3f833c82655e8725c037a2294e14cf5d73a5df8d56159de69 Create 4,000,000 keys in database with subtraction of 1, and Low_m = 1 With this you find it in incremental. Code: #@mcdouglasx Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 01, 2023, 11:54:35 PM Use this as target pub = 0209c58240e50e3ba3f833c82655e8725c037a2294e14cf5d73a5df8d56159de69 Create 4,000,000 keys in database with subtraction of 1, and Low_m = 1 With this you find it in incremental. Code: #@mcdouglasx You are merely incrementing by 1. Apparently you do not understand what I am saying. If I save those 4,000,000 pubs to a file; and increment like I was telling you to do, via how many keys you generated, it would find the key. If a key cannot be found with increment other than 1; in which I am still baffled by this, then its merely a cool database script. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 02, 2023, 12:17:26 AM I even tried your way but with an increment other than 1.
All pks print correctly but key is not found. Code: start= 0 I am still baffled lol. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on December 02, 2023, 12:18:12 AM Use this as target pub = 0209c58240e50e3ba3f833c82655e8725c037a2294e14cf5d73a5df8d56159de69 Create 4,000,000 keys in database with subtraction of 1, and Low_m = 1 With this you find it in incremental. Code: #@mcdouglasx You are merely incrementing by 1. Apparently you do not understand what I am saying. If I save those 4,000,000 pubs to a file; and increment like I was telling you to do, via how many keys you generated, it would find the key. If a key cannot be found with increment other than 1; in which I am still baffled by this, then its merely a cool database script. If you have a database of 1-10000 Whatever you have add, subtract, multiply, equation, blow the numbers (LOL), if it results in a PK within the database range, you will find it! you can do it, Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on December 02, 2023, 12:25:48 AM I even tried your way but with an increment other than 1. All pks print correctly but key is not found. Code: start= 0 I am still baffled lol. Do you want to look for 4000000, 8000000, 12000000? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: digaran on December 02, 2023, 12:34:32 AM If you store 2 bits instead of 1 bit per key, would that help to find a key?
Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 02, 2023, 12:43:41 AM I even tried your way but with an increment other than 1. All pks print correctly but key is not found. Code: start= 0 I am still baffled lol. Do you want to look for 4000000, 8000000, 12000000? Answer me this, if I have generated 4,000,000 keys in the database, 1:4000000 as you call it, if the target pubkey's pk is: 3093472814 and this pk is landed on during a search: 3092000000 Would the key not be found? 3093472814 - 3092000000 = 1472814 (1,472,814); which is within 1:4000000 What am I missing man? Lol. Would the key not be found?! Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 02, 2023, 12:45:26 AM If you store 2 bits instead of 1 bit per key, would that help to find a key? It can find a key when using random and/or incrementing by 1; I am trying to use an increment other than 1.Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 02, 2023, 01:10:23 AM OP doesn't understand the program/script.
I used your single key check and it didn't even find a match. Check it yourself: With 4,000,000 keys in database I ran this for a single key check. pk = 3093472814 - 62500 No results. But I think I figured it out. Whatever pk is landed on, whether random or increment, it has to be a multiple of the collision margin. because if you run single key check using: pk= 3093472814 - 3999936 pk= 3093472814 - 640 pk= 3093472814 - 64 you will get a match. I'm even more lost now lol. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on December 02, 2023, 02:20:42 AM OP doesn't understand the program/script. I used your single key check and it didn't even find a match. Check it yourself: With 4,000,000 keys in database I ran this for a single key check. pk = 3093472814 - 62500 No results. But I think I figured it out. Whatever pk is landed on, whether random or increment, it has to be a multiple of the collision margin. because if you run single key check using: pk= 3093472814 - 3999936 pk= 3093472814 - 640 pk= 3093472814 - 64 you will get a match. I'm even more lost now lol. 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. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: COBRAS on December 02, 2023, 04:43:36 AM OP doesn't understand the program/script. I used your single key check and it didn't even find a match. Check it yourself: With 4,000,000 keys in database I ran this for a single key check. pk = 3093472814 - 62500 No results. But I think I figured it out. Whatever pk is landed on, whether random or increment, it has to be a multiple of the collision margin. because if you run single key check using: pk= 3093472814 - 3999936 pk= 3093472814 - 640 pk= 3093472814 - 64 you will get a match. I'm even more lost now lol. 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. Good day. What is a "magic" of your algorithm ? Do you think about make backward operation ? Take a 3 mb of base, check all base and generate 2^60 pubkeys ? I call sach algo as "multipliers". p.s. Looks like your DB can not oly archive pubkeys, but posible to generate pub keys too ???? Looks like, what for generate 35 Mk tou need only 3.81 MB :-)) Thank you I like your thread, Thread , I think is a bast of the all past year Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: Kpot87 on December 02, 2023, 11:45:06 AM OP doesn't understand the program/script. You just miss your key when substract 40000.000 in you DBI used your single key check and it didn't even find a match. Check it yourself: With 4,000,000 keys in database I ran this for a single key check. pk = 3093472814 - 62500 No results. But I think I figured it out. Whatever pk is landed on, whether random or increment, it has to be a multiple of the collision margin. because if you run single key check using: pk= 3093472814 - 3999936 pk= 3093472814 - 640 pk= 3093472814 - 64 you will get a match. I'm even more lost now lol. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 02, 2023, 05:19:30 PM Quote You are right, no match. Any update? I've been trying tweaks to the search script, but I have not been successful.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. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: Kpot87 on December 02, 2023, 10:43:07 PM @macduglasx if during creating DB, suddenly switch off light , DB valid or its must be recreated?
Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 03, 2023, 02:19:12 AM @macduglasx if during creating DB, suddenly switch off light , DB valid or its must be recreated? The keys in the DB are valid. If you were trying to create 10M and power went out at 6M, youll have 6M valid keys. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 03, 2023, 07:21:22 AM It's definitely how the bytes(BitArray(bin=binary)), BitArray stores the strings.
I have successfully implemented a spinoff script that works 100% of the time with random or increment. However, 32 Million Keys creates a 15.62MB file/database; not as good as your original 3.81MB file/database, but everything works. Would love to shrink the database more, but the BitArray is messing things up writing or reading. None the less, your idea is great and I learned something from it. Hopefully you can figure out the BitArray error and I can test your script(s) once again. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 03, 2023, 08:47:26 AM It's definitely how the bytes(BitArray(bin=binary)), BitArray stores the strings. I have successfully implemented a spinoff script that works 100% of the time with random or increment. However, 32 Million Keys creates a 15.62MB file/database; not as good as your original 3.81MB file/database, but everything works. Would love to shrink the database more I see that this script creates a db with 1 bit for each key, to reduce the db size of 256. 32 million keys = 2^25 keys x 1 bit = 2^25 bits = 4 MB instead of 32 million keys = 2^25 keys x 256 bits = 2^33 bits = 1GB If the goal is to keep low the size of the database by a factor of 1/256, instead of generating all the keys (from 1 to 2^25), simply you can generate half million of keys and store 4 bytes each. If you generate only a key each 64 keys: 1*2^6, 2*2^6, 3*2^6, 4*2^6, 5*2^6, ..... , 2^19*2^6 and store the last 64 bits (8 bytes) of each keys, your database will contain: 0.5 million keys = 2^19 keys * 8 bytes = 2^22 bytes = 4MB. CONS: maybe the search will be more slow, because for each of the 64 keys you have to search through the entire database, instead of search a single string made by all the 64 keys. But you can perform the search in parallel, and scan the database only once. And you don't have to search through 2^31 strings of 64 bits, but only through 2^19 windows of 64 bits. PROS: 1) you generate the database in less time 2) you can use a simple array, no need of conversion bits->bytes 3) you can strech this idea, and obtain a even more tiny db if you accept to do more computation a) only when you do the search b) when you create the db and when you do the search a) generate only a key each 128 keys (and store 64 bits each) -> size of db = 2 MB you spend half time to produce a db with half size; in the search script, you have to check 128 consecutive keys instead of 64 (double work). b) generate all the keys, and store only the keys with the first 8 bits = 0 in a 2^25 keys, there are about 2^17 keys with this property. You store only 7 bytes (56 bits) of these special keys (in this way the probability of a collision remains the same). Now you have a database of 2^17 keys x 7 bytes = about 896 kB. In this db you have to add the private keys too (2^17 * 32 bit = ) for a total of 1408kB. In the search script, now you have to produce at least 256 consecutive keys to find a match, until you find a key with the first 8 bits = 0 (you have to do x4 search work), but: - the file to scan is less than 1/4 of 4 MB - you generate only 1 key with the first 8 bits equal to zero, then the search will be more fast ------------------------------------------------------------------------------------------------------------------------------------ How does scale this approach? Let's say we want to store the information about 2^32 keys (4 billions), usually we would need to store 2^32 keys x 32 bytes = 2^37 bytes, 128 GB Instead: generate all the keys, and store only the keys with the first 16 bits = 0 in a interval of 2^32 keys, there are about 2^16 keys with this property. You store 8 bytes (64 bits) of these special keys (in this way you have 64 + 16 = 80 bits of informations for each key stored). Now you have a database of 2^16 keys x 8 bytes = about 512 kB + 2^16 x 4 bytes for the private keys for a total of 768 kB. You have to compute about 2^16 = 64k keys from your public key to find a public key with the first 16 bits = 0, but it takes less than 0.05 seconds to generate 64000 consecutive keys. The tradeoff between time and space is: if you want to halve the number of computation in the search, you have to double the size of the db (and viceversa). If you accept a db size of 6 MB (= 768 kB x 8 ), then you have to store 2^19 keys (with the first 13 bits = 0) and you can compute only 2^13 = 8k keys in the search. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 03, 2023, 04:39:54 PM arulbero
I understand what you are saying as far as time and space and the examples given. Can you give me a concrete example of how or what keys you would store (making the filesize smaller) and how you could use it in a search? My example to you is: If I generate 2^25 keys in the database, it's size will be 16MB. Now I can start at any point and skip 2^25 points. If I start at 0, I jump 2^25 points and do 64 consecutive subs and if the key is in that range, the script will find it. So basically, 2^25 keys = 16MB, jump 2^25 points, compute 64 sub loops. 100% find if key is in that range. If not, jump to the next 2^25 point; 0+2^25, 2^25+2^25, etc. Each point landed on, only requires 64 computations. I generated 40,000,000,000 keys in a database and it took just under a second to do the 64 computations and check the DB for a match. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: ecdsa123 on December 03, 2023, 04:40:33 PM for small int it works. but for huge number like 2**64 hmm , yeap.
Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 03, 2023, 04:43:02 PM This script generates a database of 32 million keys (3.9 MB) in 3.5 seconds,
it stores only 1 key each 64 keys, and only 8 bytes for each key Code: #!/usr/bin/env python3 If you want to read the data, switch to "binary_mode = 0". With 2^32 keys (4 billions), it takes about 4 minutes to generates a db of 257 MB (1 key each 128 keys, 64 bits for key). Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 03, 2023, 04:54:35 PM Can you give me a concrete example of how or what keys you would store (making the filesize smaller) and how you could use it in a search? My example to you is: If I generate 2^25 keys in the database, it's size will be 16MB. 2^25 keys -> 16MB means : you store 4 bits for each key? 2^25 * 4 bits = 2^27 bits = 2^24 bytes = 16MB. Or you store only some keys? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 03, 2023, 04:56:00 PM This script generates a database of 32 million keys (3.9 MB) in 3.5 seconds, But how does this help you do a search for a key?it stores only 1 key each 64 keys, and only 8 bytes for each key Code: #!/usr/bin/env python3 If you want to read the data, switch to "binary_mode = 0". With 2^32 keys (4 billions), it takes about 4 minutes to generates a db of 257 MB (1 key each 128 keys, 64 bits for key). What search would you run with this script? The OPs (and my modified script) basically stores wilds a known pubkeys offset keys. And the search script can land in any key space, do 64 key computations, and find the key of the key is in that range. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 03, 2023, 04:58:09 PM Can you give me a concrete example of how or what keys you would store (making the filesize smaller) and how you could use it in a search? My example to you is: If I generate 2^25 keys in the database, it's size will be 16MB. 2^25 keys -> 16MB means : you store 4 bits for each key? 2^25 * 4 bits = 2^27 bits = 2^24 bytes = 16MB. Or you store only some keys? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 03, 2023, 05:12:32 PM I store every key, 2^25 keys, represented with a 0 or a 1. Ok, then you are using the idea of this thread. But how does this help you do a search for a key? What search would you run with this script? The OPs (and my modified script) basically stores wilds a known pubkeys offset keys. And the search script can land in any key space, do 64 key computations, and find the key of the key is in that range. The idea is: if you know that a public key P is in your db, of course you need only 64 key computations. The same for my script. ( I didn't write a script "search" so far, I made only a script to build the database as small as possible). Your idea: store a bit of any key My idea: store several bits of some keys The general case is: 1) I have a public keys P. I don't know the private key, but I know it is in range [1 - 2^64] (example). But this range is too big, I cant store or build a such huge database. There are 2 main possibilities: a) I generate a database of 2^32 public keys [from 1*G to 2^32*G] (baby steps) and I store all of them, then I compute P1 = P - 2^32*G and verify if it is in my db, otherwise I compute P2 = P - 2*(2^32*G) and so on (giant steps). This is baby-giant steps algorithm, about 2^32 computation but a huge size database. b) I generate a database of 2^32 public keys [from 1*G to 2^32*G], but I store only 1 key each 64 (to save space). Then I compute P1 = P - 2^32G and I verify if it is in my db. Now I have to perform 64 subtraction from P1: P1 - G, P1 - 2G, P3 - G , .... P3 - 64*G because P1 could be in interval [1*G -> (2^32)*G] but not in my db (I don't store all the keys). These 64 subtraction are the price we have to pay to have a smaller database. to be sure that P1 is or is not in the interval [1->2^32]. If P1 or the other 64 keys are not in my db, I compute P2 = P - 2*(2^32*G) and so on. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 03, 2023, 05:22:37 PM I store every key, 2^25 keys, represented with a 0 or a 1. Ok, then you are using the idea of this thread. But how does this help you do a search for a key? What search would you run with this script? The OPs (and my modified script) basically stores wilds a known pubkeys offset keys. And the search script can land in any key space, do 64 key computations, and find the key of the key is in that range. The idea is: if you know that a public key P is in your db, of course you need only 64 key computations. The same for my script. ( I didn't write a script "search" so far, I made only a script to build the database as small as possible). The general case is: 1) I have a public keys P. I don't know the private key, but I know it is in range [1 - 2^64] (example). But this range is too big, I cant store or build a such huge database. There are 2 main possibilities: a) I generate a database of 2^32 public keys [from 1*G to 2^32*G] (baby steps) and I store all of them, then I compute P1 = P - 2^32*G and verify if it is in my db, otherwise I compute P2 = P - 2*(2^32*G) and so on (giant steps). This is baby-giant steps algorithm, about 2^32 computation but a huge size database. b) I generate a database of 2^32 public keys [from 1*G to 2^32*G], but I store only 1 key each 64 (to save space). Then I compute P1 = P -2^32G and I verify if it is in my db. I have to perform 64 subtraction from P1: P1 - G, P1 - 2G, P3 - G , .... P3 - 64*G to be sure that P1 is or is not in the interval [1->2^32]. If P1 or the other 64 keys are not in my db, I compute P2 = P - 2*(2^32*G) and so on. I have a database with 63,570,000,000 keys stored in it, with a size of only 7.7GB. This one was created using the BitArray function, but it has flaws when doing a search so I am not using it at the moment. But when I run the search script, it uses the equivalent in RAM, roughly 7.7GB of RAM used during the search. But I can make jumps the size of 63,570,000,000 (almost 2^36), do 64 computations, and know within a second if key is in that range or not. So every less than a second, it jumps 2^36 keys and checks for a match. But this is using python, could be much faster in C, C++, and a lot faster with GPU support. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 03, 2023, 05:35:23 PM Understood. I have a database with 63,570,000,000 keys stored in it, with a size of only 7.7GB. This one was created using the BitArray function, but it has flaws when doing a search so I am not using it at the moment. But when I run the search script, it uses the equivalent in RAM, roughly 7.7GB of RAM used during the search. But I can make jumps the size of 63,570,000,000 (almost 2^36), do 64 computations, and know within a second if key is in that range or not. So every less than a second, it jumps 2^36 keys and checks for a match. But this is using python, could be much faster in C, C++, and a lot faster with GPU support. Then, you can reduce the space and increase the costs of search computations. With my script a db of 2^36 keys utilizes about 4GB. In that case I store 1 key each 128. It takes about 1 hour. And 128 computations are very fast for the 'search part'. And searching 64 bit --> shift 64 bit --> next 64 bit --> shift 64 bit should be faster than 64 bit -> shift 1 bit -> 64 bit (If I understand your script) Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: sssergy2705 on December 03, 2023, 05:52:15 PM This script generates a database of 32 million keys (3.9 MB) in 3.5 seconds, it stores only 1 key each 64 keys, and only 8 bytes for each key Code: #!/usr/bin/env python3 If you want to read the data, switch to "binary_mode = 0". With 2^32 keys (4 billions), it takes about 4 minutes to generates a db of 257 MB (1 key each 128 keys, 64 bits for key). This is quite interesting, but how can we use it, for example, to find puzzle 65? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: digaran on December 03, 2023, 05:57:02 PM @arulbero, I get the error for int too big to convert, can your script work on mobile?
Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 03, 2023, 06:18:14 PM Understood. I have a database with 63,570,000,000 keys stored in it, with a size of only 7.7GB. This one was created using the BitArray function, but it has flaws when doing a search so I am not using it at the moment. But when I run the search script, it uses the equivalent in RAM, roughly 7.7GB of RAM used during the search. But I can make jumps the size of 63,570,000,000 (almost 2^36), do 64 computations, and know within a second if key is in that range or not. So every less than a second, it jumps 2^36 keys and checks for a match. But this is using python, could be much faster in C, C++, and a lot faster with GPU support. Then, you can reduce the space and increase the costs of search computations. With my script a db of 2^36 keys utilizes about 4GB. In that case I store 1 key each 128. It takes about 1 hour. And 128 computations are very fast for the 'search part'. And searching 64 bit --> shift 64 bit --> next 64 bit --> shift 64 bit should be faster than 64 bit -> shift 1 bit -> 64 bit (If I understand your script) What would be the false positives for the way you store keys? Mine is almost 0%. I've ran hundreds of tests now with zero false positives. Also, why can't you store keys as a 0 or a 1? To make your DB even smaller? My search script is like the OPs original but I added incremental. In random, it lands on random point, does 64 comps, goes to next random point, 64 comps, etc. Incremental is the same way except if you start at 0 and your stride/jump size is 2^20, then land on point 2^20, do 64 comps, jump to 2^20+2^20 point, do 64 comps, etc. The script can also spread the keys out like you are saying. Save only every other 128 keys, the keys do not have to be sequential. I'm curious to your false positives and any search script you would create. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 03, 2023, 06:42:36 PM What would be the false positives for the way you store keys? Mine is almost 0%. I've ran hundreds of tests now with zero false positives. Also, why can't you store keys as a 0 or a 1? To make your DB even smaller? My search script is like the OPs original but I added incremental. In random, it lands on random point, does 64 comps, goes to next random point, 64 comps, etc. Incremental is the same way except if you start at 0 and your stride/jump size is 2^20, then land on point 2^20, do 64 comps, jump to 2^20+2^20 point, do 64 comps, etc. The script can also spread the keys out like you are saying. Save only every other 128 keys, the keys do not have to be sequential. I store 64 bits for each key, you store 64 bits for 64 keys; in my database there are less strings of 64 bits to compare with, then I think my probability is almost zero too. For smaller databases (like 2^30 keys) I could use even less than 64 bits for keys (like 48 bits) without problems. If I implemented the "first x bits = 0" then the probability of collisions (at the same size of database) would be even lower (but it would take much longer to build the database). I'm curious to your false positives and any search script you would create. Me too.Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: ecdsa123 on December 03, 2023, 06:46:16 PM What would be the false positives for the way you store keys? Mine is almost 0%. I've ran hundreds of tests now with zero false positives. Also, why can't you store keys as a 0 or a 1? To make your DB even smaller? My search script is like the OPs original but I added incremental. In random, it lands on random point, does 64 comps, goes to next random point, 64 comps, etc. Incremental is the same way except if you start at 0 and your stride/jump size is 2^20, then land on point 2^20, do 64 comps, jump to 2^20+2^20 point, do 64 comps, etc. The script can also spread the keys out like you are saying. Save only every other 128 keys, the keys do not have to be sequential. I store 64 bits for each key, you store 64 bits for 64 keys; in my database there are less strings of 64 bits to compare with, then I think my probability is almost zero too. For smaller databases (like 2^30 keys) I could use even less than 64 bits for keys (like 48 bits) without problems. If I implemented the "first x bits = 0" then the probability of collisions (at the same size of database) would be even lower (but it would take much longer to build the database). I'm curious to your false positives and any search script you would create. Me too.and if database is larger and larger -> it creating then too many false positives. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 03, 2023, 07:27:28 PM and if database is larger and larger -> it creating then too many false positives. Then simply you have to store more bits per key; if you want to have 0 collisions, store 256 bits for key. It works always. And if you want a smaller database, you can store 1 key each 1024 keys. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 03, 2023, 07:32:17 PM and if database is larger and larger -> it creating then too many false positives. Then simply you have to store more bits per key; if you want to have 0 collisions, store 256 bits for key. It works always. And if you want a smaller database, you can store 1 key each 1024 keys. The DB, when checked, is checked against 64 or 128 or 256, or however high you want to go. If you were checking the entire 2^256 keys, then yes, but when checking smaller range sizes (up to 160 bits) then I dont think a larger DB creates more false positives. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: ecdsa123 on December 03, 2023, 07:57:55 PM I have one idea , writing those database directly to memory and seek in as the object. of course as a custom bytearray
seeking as dword Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: COBRAS on December 03, 2023, 08:15:33 PM and if database is larger and larger -> it creating then too many false positives. Then simply you have to store more bits per key; if you want to have 0 collisions, store 256 bits for key. It works always. And if you want a smaller database, you can store 1 key each 1024 keys. I agree with you Alberto, you more experienced then ather im this talk Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 03, 2023, 10:05:53 PM Quote Then, you can reduce the space and increase the costs of search computations. With my script a db of 2^36 keys utilizes about 4GB. In that case I store 1 key each 128. It takes about 1 hour. And 128 computations are very fast for the 'search part'. And searching 64 bit --> shift 64 bit --> next 64 bit --> shift 64 bit should be faster than 64 bit -> shift 1 bit -> 64 bit (If I understand your script) You say 4GB but you aren't comparing apples to apples. In your scenario of only saving every 128 keys out of 2^36 keys, your DB does not contain 2^36, but 2^36 / 2^7 = 2^29 keys. If I spread out my keys to every 128 inside a 2^36 range and only store 2^29 keys, my DB size would be about 63MB. Big difference, huge. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 04, 2023, 12:39:09 AM 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 search_key_arulbero.py Code: # 2023/Dec/03, arulbero_search_key.py Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 04, 2023, 12:46:01 AM You say 4GB but you aren't comparing apples to apples. In your scenario of only saving every 128 keys out of 2^36 keys, your DB does not contain 2^36, but 2^36 / 2^7 = 2^29 keys. If I spread out my keys to every 128 inside a 2^36 range and only store 2^29 keys, my DB size would be about 63MB. Big difference, huge. If the goal is finding the private key of a public key that is in a interval for which you have precomputed the public key, AND at the same time the goal is to keep the size of the db as small as possible, why don't you reduce your db size to 63 MB then? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 04, 2023, 01:37:50 AM Quote Activity: 1863 Merit: 2039 View Profile Personal Message (Online) Ignore Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Today at 12:39:09 AM Reply with quote +Merit #97 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 For a known public key; it could be unknown like your script (I would just need to generate the random pk/pub like you did, but the time results would be the same), but here are my script results for a key within the 2^32 bit range. Generated 2,000,000 keys in less than 4 seconds. Size of database = 977kb (less than 1MB) time to find private key in the db: less than 2 seconds Total time = less than 6 seconds. I could adjust the number of keys generated, but there's no need in such a small range. With more keys generated, the search time would go down significantly. I will run it with 2^25 keys and report back generation and search times. UPDATE: I generated 2^25 keys in 65 seconds. Search took less than a second. Total time = 66 seconds. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on December 04, 2023, 02:04:28 AM Quote You are right, no match. Any update? I've been trying tweaks to the search script, but I have not been successful.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. 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 Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: COBRAS on December 04, 2023, 04:07:36 AM 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 :(((((( Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: whanau on December 04, 2023, 04:43:43 AM I wrote the both scripts: create_database_arulbero.py search_key_arulbero.py Both scripts appear identical or is it me? ;D Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 04, 2023, 11:52:14 AM I wrote the both scripts: create_database_arulbero.py search_key_arulbero.py Both scripts appear identical or is it me? ;D You're right, I copied twice the same file. Now there are 2 different scripts. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on December 04, 2023, 06:01:49 PM 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 search_key_arulbero.py Code: # 2023/Dec/03, search_key_arulbero.py 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. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: whanau on December 04, 2023, 07:50:39 PM 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. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 04, 2023, 08:33:12 PM Quote I thought I would try them out with a couple of format tweaks.. Can't help without knowing the tweaks.Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: whanau on December 04, 2023, 10:40:28 PM Just decimal to hex print output
Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: bjpark on December 04, 2023, 10:43:39 PM 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 Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on December 04, 2023, 10:55:44 PM 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. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 04, 2023, 11:49:47 PM Quote You are right, no match. Any update? I've been trying tweaks to the search script, but I have not been successful.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. 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 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()) Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: bjpark on December 04, 2023, 11:54:53 PM 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 Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on December 05, 2023, 12:54:37 AM 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. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 05, 2023, 01:13:18 AM 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. 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 Im 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 Ive used/tested in awhile! Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: digaran on December 05, 2023, 01:22:19 AM 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.
Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on December 05, 2023, 01:51:47 AM 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. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 05, 2023, 02:32:11 AM 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 and Code: This is the public key: 02bbbe90761d7c7ec3dabb3d64448ecdb5fa6f704ff06bcf7643176a74ffa69a4b 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. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: COBRAS on December 05, 2023, 02:42:32 AM 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 and Code: This is the public key: 02bbbe90761d7c7ec3dabb3d64448ecdb5fa6f704ff06bcf7643176a74ffa69a4b 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 ? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 05, 2023, 09:15:00 AM 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) Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: GR Sasa on December 05, 2023, 10:02:05 AM Could this script be faster than BSGS (Baby Step Giant Step)?
Or Are they similar to each other? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 05, 2023, 11:02:01 AM 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. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 05, 2023, 01:16:13 PM 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) How did you manage to make your database smaller compared to your original script? And why does it go up in size with the same amount of keys? Edit: I read it wrong as if you were storing 1 Mil keys every time lol. Also, does your search script find the key every time? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 05, 2023, 03:14:22 PM Impressive! How did you manage to make your database smaller compared to your original script? And why does it go up in size with the same amount of keys? Edit: I read it wrong as if you were storing 1 Mil keys every time lol. Also, does your search script find the key every time? 1) my original script (create_database) is not changed 2) not with the same amount of keys, range is not equal to number of keys number of keys stored = range / 2^20 in one case, and number_of_keys = range / 2^24 in other case 3) my script is basically BSGS: big steps -> database : 1*G, 1*G+2^20*G, 1*G+2*2^20*G, 1*G+3*2^20*G, ...., range*G small steps --> search: P=k*G, k*G-G, k*G-2*G, k*G-3*G, ...., k*G-2^20*G the only difference is: I'm triyng to reduce the size of database, storing only 64 bits for each key and other improvements. 4) my script finds the key every time? So far, yes. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: COBRAS on December 05, 2023, 03:25:55 PM Impressive! How did you manage to make your database smaller compared to your original script? And why does it go up in size with the same amount of keys? Edit: I read it wrong as if you were storing 1 Mil keys every time lol. Also, does your search script find the key every time? 1) my original script (create_database) is not changed 2) not with the same amount of keys, range is not equal to number of keys number of keys stored = range / 2^20 in one case, and number_of_keys = range / 2^24 in other case 3) my script is basically BSGS: big steps -> database : 1*G, 1*G+2^20*G, 1*G+2*2^20*G, 1*G+3*2^20*G, ...., range*G small steps --> search: P=k*G, k*G-G, k*G-2*G, k*G-3*G, ...., k*G-2^20*G the only difference is: I'm triyng to reduce the size of database, storing only 64 bits for each key and other improvements. 4) my script finds the key every time? So far, yes. publick you scrypts pls ? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 05, 2023, 03:26:51 PM Quote 4) my script finds the key every time? So far, yes. Ok, when I ran your original script, it was less than 20% of the time the key was found.Keep working on the database size. I know you will get it down! If you can get it down to 1 bit per key like the OPs, then you're onto something. His DB is unmatched so far. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 05, 2023, 03:30:12 PM Quote 4) my script finds the key every time? So far, yes. Ok, when I ran your original script, it was less than 20% of the time the key was found.Keep working on the database size. I know you will get it down! If you can get it down to 1 bit per key like the OPs, then you're onto something. His DB is unmatched so far. Less than 20%? Did you try with the last version? Maybe the first version was not correct, I fixed some stuff. I don't understand why: 1 bit for 2^32 keys is better than 64bits for 2^32/2^20 = 2^12 keys. Less size, less search time, 100% keys found. To speed up the serch, I need to store more information per byte, more density of information/work per byte stored. For example, If I generated all 2^44 keys and I stored only the keys with the first 20 bit = 0, I would get a database with the same size of a databse created with 1 key each 1 million. But the search time would be faster, cause I would need to check only 1 key against the database instead of 1 million. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: sssergy2705 on December 05, 2023, 03:34:21 PM Quote 4) my script finds the key every time? So far, yes. Ok, when I ran your original script, it was less than 20% of the time the key was found.Keep working on the database size. I know you will get it down! If you can get it down to 1 bit per key like the OPs, then you're onto something. His DB is unmatched so far. Less than 20%? Did you try with the last version? Maybe the first version was not correct, I fixed some stuff. I don't understand why: 1 bit for 2^32 key is better than 64bits for 2^32/2^20 = 2^12 keys. Less size, less search time, 100% keys found. The first version of the script worked, the second does not find matches. There may be an error in the code. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 05, 2023, 03:39:15 PM 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, .... ??? Did you set the same parameters in both scripts? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: sssergy2705 on December 05, 2023, 03:56:48 PM 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, .... ??? 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. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 05, 2023, 04:36:54 PM 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, .... ??? 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 Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 05, 2023, 04:41:09 PM Quote 1 bit for 2^32 keys is better than 64bits for 2^32/2^20 = 2^12 keys. Less size, less search time, 100% keys found. To speed up the serch, I need to store more information per byte, more density of information/work per byte stored. For example, If I generated all 2^44 keys and I stored only the keys with the first 20 bit = 0, I would get a database with the same size of a databse created with 1 key each 1 million. But the search time would be faster, cause I would need to check only 1 key against the database instead of 1 million. I think you are looking at it from a small interval size. I am looking at it from a larger standpoint. For #115, DP size of 25, had 2^33.5 points; a file size of over 350GB. I have a file with 2^36 keys stored, but at only 8GB. Do you see the difference? We are looking at using a smaller DB size in different ways. If you ran a DP of 20 in a 2^44 range, you would wind up with roughly 2^24 keys stored. As far as finding DPs, I have the fastest script, not on the market lol. GPU script. I can find all DPs (of any size), in a 2^44 range in a little less than 16 minutes. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 05, 2023, 04:53:14 PM Quote 1 bit for 2^32 keys is better than 64bits for 2^32/2^20 = 2^12 keys. Less size, less search time, 100% keys found. To speed up the serch, I need to store more information per byte, more density of information/work per byte stored. For example, If I generated all 2^44 keys and I stored only the keys with the first 20 bit = 0, I would get a database with the same size of a databse created with 1 key each 1 million. But the search time would be faster, cause I would need to check only 1 key against the database instead of 1 million. I think you are looking at it from a small interval size. I am looking at it from a larger standpoint. For #115, DP size of 25, had 2^33.5 points; a file size of over 350GB. I have a file with 2^36 keys stored, but at only 8GB. Do you see the difference? We are looking at using a smaller DB size in different ways. If you ran a DP of 20 in a 2^44 range, you would wind up with roughly 2^24 keys stored. As far as finding DPs, I have the fastest script, not on the market lol. GPU script. I can find all DPs (of any size), in a 2^44 range in a little less than 16 minutes. Yes, if you are trying to reduce the size of a DP database, the task is different. You want to know if a certain DP key is in DP database as fast as possible, right? Then you need a small size and fast search algorithm that works with a group of non consecutive keys. Your 2^33.5 keys are spread in a 2^115 space, not in a 2^34 space. The task is very different. You don't need the private key, you need only to know if you have hit a DP already in database? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 05, 2023, 05:00:09 PM Quote Yes, if you are trying to reduce the size of a DP database, the task is different. You want to know if a certain DP key is in DP database as fast as possible, right? Then you need a small size and fast search algorithm that works with a group of non consecutive keys. Your 2^33.5 keys are spread in a 2^115 space, not in a 2^34 space. The task is very different. Who said my keys or this script's keys are limited to a 2^34 space? I can spread them out as little or as much as wanted. Example: I can generate 2^34 keys spread out every 1000000000 keys or I can mimic Kangaroo jumps; spread the keys out every (for #130) 130 / 2 + 1 = 66; so I could spread the keys out every 2^66 key. For the DB that has 2^36 keys stored in it, the search script generates 64 subs and checks entire DB in 1 second. I'm not concerned about speed when a DB has over 68 Billion keys in it. It's a lot faster than the merging of files to check for a collision (JLPs Kangaroo version). Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 05, 2023, 05:04:04 PM Quote Yes, if you are trying to reduce the size of a DP database, the task is different. You want to know if a certain DP key is in DP database as fast as possible, right? Then you need a small size and fast search algorithm that works with a group of non consecutive keys. Your 2^33.5 keys are spread in a 2^115 space, not in a 2^34 space. The task is very different. Who said my keys or this script's keys are limited to a 2^34 space? I can spread them out as little or as much as wanted. Example: I can generate 2^34 keys spread out every 1000000000 keys or I can mimic Kangaroo jumps; spread the keys out every (for #130) 130 / 2 + 1 = 66; so I could spread the keys out every 2^66 key. For the DB that has 2^36 keys stored in it, the search script generates 64 subs and checks entire DB in 1 second. I'm not concerned about speed when a DB has over 68 Billion keys in it. It's a lot faster than the merging of files to check for a collision (JLPs Kangaroo version). But the distance between 2 keys must be the same, otherwise I don't understand how can you know if a key is in your database. And the DP keys in DP database are not equally spaced. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 05, 2023, 05:30:04 PM Quote But the distance between 2 keys must be the same, otherwise I don't understand how can you know if a key is in your database. And the DP keys in DP database are not equally spaced. The keys in DB are/can be equally spaced. DP keys arent equally spaced because points with DPs are not equally spread. Imagine running Kangaroo with DP 0 and space wasnt an issue. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 05, 2023, 05:40:08 PM Quote But the distance between 2 keys must be the same, otherwise I don't understand how can you know if a key is in your database. And the DP keys in DP database are not equally spaced. The keys in DB are/can be equally spaced. DP keys arent equally spaced because points with DPs are not equally spread. Ok, we agree on these facts. But you said: For #115, DP size of 25, had 2^33.5 points; a file size of over 350GB. I have a file with 2^36 keys stored, but at only 8GB. Do you see the difference? You (not me) are comparing 2 different type of sets, but you can't apply the idea of this thread to the DP keys, because they are not equally spaced. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 05, 2023, 05:49:00 PM Quote You (not me) are comparing 2 different type of sets, but you can't apply the idea of this thread to the DP keys, because they are not equally spaced. Lol, ok. With Kangaroo, it does not matter if they are or are not equally spaced. However, if you think the keys stored in a Kangaroo DB must be NOT equally spaced, then that is also achievable with this script. You just mimic different starting keys, like Kangaroo does. To me, I have a DB full of DP 0 bits, wilds. Now I run only tames, and check for collisions. In my mind, it does not matter if the keys in the DB are equally spaced or not, but that is easily achieved by offsetting the target pubkey before running DB creation. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 05, 2023, 06:00:54 PM Quote You (not me) are comparing 2 different type of sets, but you can't apply the idea of this thread to the DP keys, because they are not equally spaced. Lol, ok. With Kangaroo, it does not matter if they are or are not equally spaced. However, if you think the keys stored in a Kangaroo DB must be NOT equally spaced, then that is also achievable with this script. You just mimic different starting keys, like Kangaroo does. To me, I have a DB full of DP 0 bits, wilds. Now I run only tames, and check for collisions. In my mind, it does not matter if the keys in the DB are equally spaced or not, but that is easily achieved by offsetting the target pubkey before running DB creation. Then: you have a DB full of DP 0 bits (no DP) wilds equally spaced when you run tames, you want to check for collisions every step using the idea of this thread? And if the wilds DP (DB bits > 0) are not equally spaced, how can you perform a check against the wild DB using 1 bit per key? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: ecdsa123 on December 05, 2023, 06:06:50 PM @WanderingPhilospher:
I think is the time to publish your modification script for creating database and for seeking in database. I think -> to better optimised you need use mmap library in 2 GB files I have up to 2 seconds for "finding the str" Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 05, 2023, 06:09:49 PM Then:
you have a DB full of DP 0 bits (no DP) wilds equally spaced when you run tames, you want to check for collisions every step using the idea of this thread? No, not necessarily. I have other ideas how to check for collisions that doesn't require a check every step; but it would work. And if the wilds DP (DB bits > 0) are not equally spaced, how can you perform a check against the wild DB using 1 bit per key? During creation of Dbs; pubkey - create pubkey - some random number - create pubkey - some random number again - create .......... pubkey - some random number again - create While each create is evenly spaced, we have several creations (could be hundreds or thousands, it's unlimited) I am trying to think of ways to lessen the space trade off of traditional kangaroo, that's all. I'm sure you have ideas. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 05, 2023, 06:16:40 PM @WanderingPhilospher: Mine is only different from the OPs in that I don't use the BitArray, I stick to bytes.I think is the time to publish your modification script for creating database and for seeking in database. I think -> to better optimised you need use mmap library in 2 GB files I have up to 2 seconds for "finding the str" Tradeoff, my DB is 4 times as large, but search is faster. mmap increases search time? With a 2GB DB file, I could find a key in less than a second (in the smaller ranges we've been discussing here) I have a Db that is 488MB that contains 1,000,000,000 keys; that means I can check an entire 2^29.89 range in less than a second. So at 2GB (roughly) 4 times that speed, so a 2^31.89 range checked in less than a second. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on December 05, 2023, 07:03:14 PM There are many options when we work with bits:
could use this with bits PUBKEY - RANDOM NUMBER = CREATE -1024 Pubs, as my publication (1 bit per key). Repeat 1 million times. We save a database that we will call "A" where all pubs and random number are saved from the random subtractions. We save a database that we will call "B" where only the bits obtained are saved. We scan 64 -bit collision margin If there is match We identify the pub found counting the bits in the DB using the % 1024 to calculate the PK found (because each operation is different and 1024 was the number of sequential keys for each pub). We would basically have 1 million mini dB of 1024 keys stored in 1 1000000*1024 bits database. With the difference that they would not be in sequences and could cover the target range randomly. . Then that match (pub) we will find in database "A" and add to the RANDOM NUMBER to obtain pk from the main target Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 05, 2023, 07:35:23 PM There are many options when we work with bits: Did you ever tinker or mess with your multi-pub binary and search scripts?could use this with bits PUBKEY - RANDOM NUMBER = CREATE -1024 Pubs, as my publication (1 bit per key). Repeat 1 million times. We save a database that we will call "A" where all pubs and random number are saved from the random subtractions. We save a database that we will call "B" where only the bits obtained are saved. We scan 64 -bit collision margin If there is match We identify the pub found counting the bits in the DB using the % 1024 to calculate the PK found (because each operation is different and 1024 was the number of sequential keys for each pub). We would basically have 1 million mini dB of 1024 keys stored in 1 1000000*1024 bits database. With the difference that they would not be in sequences and could cover the target range randomly. . Then that match (pub) we will find in database "A" and add to the RANDOM NUMBER to obtain pk from the main target That would work as well. Generate pubs and offsets (random number subtracted by of original pubkey) and save in a file and load the new gen pubs in another and run the multi pub script against the pub only file. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: ecdsa123 on December 05, 2023, 07:42:31 PM @WanderingPhilospher
can you publish your version? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: whanau on December 06, 2023, 12:18:46 AM 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. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on December 06, 2023, 12:25:09 AM There are many options when we work with bits: Did you ever tinker or mess with your multi-pub binary and search scripts?could use this with bits PUBKEY - RANDOM NUMBER = CREATE -1024 Pubs, as my publication (1 bit per key). Repeat 1 million times. We save a database that we will call "A" where all pubs and random number are saved from the random subtractions. We save a database that we will call "B" where only the bits obtained are saved. We scan 64 -bit collision margin If there is match We identify the pub found counting the bits in the DB using the % 1024 to calculate the PK found (because each operation is different and 1024 was the number of sequential keys for each pub). We would basically have 1 million mini dB of 1024 keys stored in 1 1000000*1024 bits database. With the difference that they would not be in sequences and could cover the target range randomly. . Then that match (pub) we will find in database "A" and add to the RANDOM NUMBER to obtain pk from the main target That would work as well. Generate pubs and offsets (random number subtracted by of original pubkey) and save in a file and load the new gen pubs in another and run the multi pub script against the pub only file. added binary version. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: COBRAS on December 06, 2023, 03:13:49 AM There are many options when we work with bits: Did you ever tinker or mess with your multi-pub binary and search scripts?could use this with bits PUBKEY - RANDOM NUMBER = CREATE -1024 Pubs, as my publication (1 bit per key). Repeat 1 million times. We save a database that we will call "A" where all pubs and random number are saved from the random subtractions. We save a database that we will call "B" where only the bits obtained are saved. We scan 64 -bit collision margin If there is match We identify the pub found counting the bits in the DB using the % 1024 to calculate the PK found (because each operation is different and 1024 was the number of sequential keys for each pub). We would basically have 1 million mini dB of 1024 keys stored in 1 1000000*1024 bits database. With the difference that they would not be in sequences and could cover the target range randomly. . Then that match (pub) we will find in database "A" and add to the RANDOM NUMBER to obtain pk from the main target That would work as well. Generate pubs and offsets (random number subtracted by of original pubkey) and save in a file and load the new gen pubs in another and run the multi pub script against the pub only file. added binary version. Thank you very much, Mister ;!) Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: sssergy2705 on 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, .... ??? 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 Code: This is the public key: f5c03157f4a489ed71c0df0f37799431b3f432654a9bd6efdbb79ba767b62e81 For example, I got a collision, how to calculate the private key? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 06, 2023, 05:43:16 PM Code: This is the public key: f5c03157f4a489ed71c0df0f37799431b3f432654a9bd6efdbb79ba767b62e81 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: Code: start_key = 1 Did you use bits_to_store = 64? And the other parameters? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on 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? Code: start_key = 1 Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: sssergy2705 on December 06, 2023, 06:02:09 PM Code: This is the public key: f5c03157f4a489ed71c0df0f37799431b3f432654a9bd6efdbb79ba767b62e81 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: Code: start_key = 1 Did you use bits_to_store = 64? And the other parameters? Code: start_key = 2**49 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 Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 06, 2023, 06:08:55 PM Code: start_key = 2**49 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. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: whanau on December 06, 2023, 08:43:10 PM 0x80 = 128 What are you parameters? Like these? Code: start_key = 1 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 Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: Kpot87 on December 07, 2023, 10:18:37 AM Code: start_key = 2**49 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 ? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on 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. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: Kpot87 on 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. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on 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. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: COBRAS on 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 :) 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: Code: Making Binary Data-Base create_database.py Code: #@mcdouglasx modified by arulbero Can you provide your BSGS scrypt ? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: Kpot87 on December 09, 2023, 09:54:03 AM @macduglasx hi, how you provide working with mulpubs, about ram its clear and what about threads ? 1pub=1th? Tnx
Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 09, 2023, 06:35:05 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 MB The script search takes less than 1 second to retrieve a key in this space. create_database.py Code: #@mcdouglasx modified by arulbero search_pk.py Code: #@mcdouglasx modified by arulbero Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: COBRAS on 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 MB The script search takes less than 1 second to retrieve a key in this space. create_database.py Code: #@mcdouglasx modified by arulbero search_pk.py Code: #@mcdouglasx modified by arulbero Good day, what about 2^65 range, posible or not ? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on 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 MB The script search takes less than 1 second to retrieve a key in this space. create_database.py Code: #@mcdouglasx modified by arulbero search_pk.py Code: #@mcdouglasx modified by arulbero 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: Code: space_search_start = 0x80000000 #pk_orig - space_covered 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. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 09, 2023, 10:02:17 PM When I run a 2^36 key test with my modified OP script, the results:
Code: This is the public key: 02b3e772216695845fa9dda419fb5daca28154d8aa59ea302f05e916635e47b9f6 Under 20 seconds to create DB and find the key. Maybe I am missing something in your script arulbero. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 10, 2023, 10:56:52 AM 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: Code: This is the public key: 02b3e772216695845fa9dda419fb5daca28154d8aa59ea302f05e916635e47b9f6 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 :) 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) Code: > time python3 create_database.py ########################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 Code: > time python3 search_pk.py 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. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 10, 2023, 03:38:03 PM Quote 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. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 10, 2023, 04:24:40 PM Quote 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. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 10, 2023, 04:28:48 PM Quote 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. It's been running for 2 minutes now with no key found. Maybe you changed up all the other parameters? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 10, 2023, 04:38:12 PM Quote 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. It's been running for 2 minutes now with no key found. Maybe you changed up all the other parameters? Did you copy again the create_database.py ? There was a bug. These are my parameters: 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 num = 128 # collision margin in bits (multiple of 64 bits) split_total_keys = 1 total_search_keys_to_generate = sustract multiple_search_keys_at_once = total_search_keys_to_generate//split_total_keys bytes_for_key = num//8 split_database = 2**0 #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 = 42387769980 space_search_start = 0x800000000 space_search_stop = 0x1000000000 Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 10, 2023, 04:41:03 PM Quote 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. It's been running for 2 minutes now with no key found. Maybe you changed up all the other parameters? Did you copy again the create_database.py ? There was a bug. I am running 2^23 keys with a spread of 2^4. That shouldn't matter, just wanted to let you know my params. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 10, 2023, 04:44:28 PM Did you copy again the create_database.py ? There was a bug. Yes, I did. I am running 2^23 keys with a spread of 2^4. That shouldn't matter, just wanted to let you know my params. Are you sure to have set prefix = '23_4' in both scripts? In the script I posted, there was '32_0' do this check: Code: du -sh data-base23_4.bin Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 10, 2023, 04:49:22 PM Did you copy again the create_database.py ? There was a bug. Yes, I did. I am running 2^23 keys with a spread of 2^4. That shouldn't matter, just wanted to let you know my params. Are you sure to have set prefix = '23_4' in both scripts? In the script I posted, there was '32_0' Two tests one took 4 minutes the other 3 min 30 sec. Running a 3rd now. Ok, I stopped the 3rd test and changed this line: num = 1024+512# collision margin in bits to num = 128 #1024+512# collision margin in bits Maybe that is the difference lol. Ok, 3rd test with 128 = 52 seconds search time. Changing it to 64 (why 128? that is crazy high, collisions shouldn't happen with 64) and rerunning test. Changing it to 64 = 44 seconds search time. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 10, 2023, 04:53:20 PM Did you copy again the create_database.py ? There was a bug. Yes, I did. I am running 2^23 keys with a spread of 2^4. That shouldn't matter, just wanted to let you know my params. Are you sure to have set prefix = '23_4' in both scripts? In the script I posted, there was '32_0' Two tests one took 4 minutes the other 3 min 30 sec. Running a 3rd now. I'm pretty sure you are using parameters for 2^28 or for 2^32 search space. These are my parameters: 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 num = 128 # collision margin in bits (multiple of 64 bits) split_total_keys = 1 total_search_keys_to_generate = sustract multiple_search_keys_at_once = total_search_keys_to_generate//split_total_keys bytes_for_key = num//8 split_database = 2**0 #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 = 42387769980 space_search_start = 0x800000000 space_search_stop = 0x1000000000 Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 10, 2023, 04: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. :) Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 10, 2023, 05:02:37 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; doneand 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. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 10, 2023, 05:23:21 PM 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%! Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 10, 2023, 05:44:01 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. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on December 10, 2023, 06:15:39 PM @macduglasx hi, how you provide working with mulpubs, about ram its 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://bitcointalk.org/index.php?topic=5477342 (https://bitcointalk.org/index.php?topic=5477342) Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: ecdsa123 on December 11, 2023, 09:05:54 PM Edited:
Test 1: Code: without pucked res= 1011011010010000111100101010100010100101111101011010101101111111 len= 64 Test2: Code: without pucked res= 1011011010010000111100101010100010100101111101011010101101111111101101101001000011110010101010001010010111110101101010110111111110110110100100001111001010101000101001011111010110101011011111111011011010010000111100101010100010100101111101011010101101111111 len= 256 Code:
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...:) Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 11, 2023, 11:17:08 PM 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 EDIT: If I use the BitArray option, as in original code, 20,000,000 keys generated into DB takes right at 4 seconds. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 11, 2023, 11:19:42 PM Edited: Test 1: Code: without pucked res= 1011011010010000111100101010100010100101111101011010101101111111 len= 64 Test2: Code: without pucked res= 1011011010010000111100101010100010100101111101011010101101111111101101101001000011110010101010001010010111110101101010110111111110110110100100001111001010101000101001011111010110101011011111111011011010010000111100101010100010100101111101011010101101111111 len= 256 Code:
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? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: ecdsa123 on December 11, 2023, 11:33:54 PM Yes i know not puck but pack:-) sorry
everything is going on fly and database and search. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on December 12, 2023, 12:19:16 AM Has anyone compared this with the bsgs version that I updated? It would be interesting.
Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 12, 2023, 12:43:24 AM 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 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 Code: Found the Baby Steps Table file: baby_steps__binary.bin. Will be used directly 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. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on December 12, 2023, 01:11:59 AM 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 Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 12, 2023, 01:19:40 AM 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. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on December 12, 2023, 01:42:12 AM 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. 2^64 or 18446744073709551616 is the possibility of collision not 64^2. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 12, 2023, 01:58:28 AM 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. 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? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on December 12, 2023, 02:02:34 AM 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 You are doing something wrong, my results on intel i5 4gb ddr3. BSGS FOUND PrivateKey : 3093472813 Time Spent : 0.25 seconds Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 12, 2023, 02:09:06 AM 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 You are doing something wrong, my results on intel i5 4gb ddr3. BSGS FOUND PrivateKey : 3093472813 Time Spent : 0.25 seconds Im just telling you my results, from 20,000,000 and 60,000,000 keys. Maybe you generated more keys? And why didnt you show your starting key and how many keys. Something tells me you arent telling the whole truth. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 12, 2023, 02:22:36 AM Code: Found the Baby Steps Table file: baby_steps__binary.bin. Will be used directly 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. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on December 12, 2023, 02:34:31 AM 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. 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 If I am, its your script lol. Im just telling you my results, from 20,000,000 and 60,000,000 keys. Maybe you generated more keys? And why didnt you show your starting key and how many keys. Something tells me you arent 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. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on December 12, 2023, 02:46:19 AM Code: Found the Baby Steps Table file: baby_steps__binary.bin. Will be used directly 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. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 12, 2023, 02:56:44 AM Code: Found the Baby Steps Table file: baby_steps__binary.bin. Will be used directly 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. Its like you told me I was wrong when the other script wouldnt find the key when doing an increment and even a single key check. Which as you know, you found out to be true and fixed the bug. Also, if using random, you could skip over the target key and miss it altogether, and that would result in a false negative. I like to learn so I break down each script to understand it and test it. If something is wrong or broke, I let the OP know. No witch hunts lol. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 12, 2023, 03:01:10 AM I really don't understand the differences in the two scripts, when doing an incremental like I did.
Anywho, results for same 36 bit test using the other script: Code: This is the public key: 02b3e772216695845fa9dda419fb5daca28154d8aa59ea302f05e916635e47b9f6 BSGS results: Code: creating Baby Step Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: COBRAS on December 12, 2023, 03:18:14 AM I really don't understand the differences in the two scripts, when doing an incremental like I did. Anywho, results for same 36 bit test using the other script: Code: This is the public key: 02b3e772216695845fa9dda419fb5daca28154d8aa59ea302f05e916635e47b9f6 BSGS results: Code: creating Baby Step Maybe you yse Celeron cpu ?)) Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: COBRAS on December 12, 2023, 04:31:05 AM Code: Found the Baby Steps Table file: baby_steps__binary.bin. Will be used directly 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. Definitely, not only Keyhunt will be with binary DB, Mister ;) Your binary DB is real good. Thank you very mach for your binary DB !!! Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on December 12, 2023, 04:34:27 AM I really don't understand the differences in the two scripts, when doing an incremental like I did. The problem with your tests may possibly be that the script that I uploaded as an example uses BitArray and using bitarray is much slower than using bytes (in python) and as the database increases, python becomes even slower, but I leave it that way. because my intention is to demonstrate how the use of bits should really be, with bytes it is faster but you ignore certain bits, and that is not what I intend.Anywho, results for same 36 bit test using the other script: Code: This is the public key: 02b3e772216695845fa9dda419fb5daca28154d8aa59ea302f05e916635e47b9f6 BSGS results: Code: creating Baby Step baby step is a simple incremental database from point a to b (although you could make jumps but that would involve changing some things to the script Since bsgs is a mathematical algorithm, you cannot be so close or so far from your objective, that is, you could believe that with a larger database you would reach the objective faster, but this is not the case in all cases because sometimes many bits of that database are useless for the calculation, you could spend hours looking for a match, in a pk that with the other script you find in a few seconds if you do not configure it correctly, That is why a simple search with a larger database finds you faster than when you use BSGS because you are not taking into account the mathematical point of view. My intention was to prove that we can eliminate the hash table and use a 1 bit per key binary database, but this did not prove fast. For speed there is no other way than to use C. or if you feel comfortable with python, create a dll that reads the bits in the database and integrate it with ctypes. just like iceland does in his scripts. Surely someone is using this in C, because there are programmers and developers and once the idea is developed, the programmers execute it without problems. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 12, 2023, 05:49:37 AM Another modified script using a modified version of your DB script.
Incremental, BSGS, Meet in the Middle, lol. 48 Bit Range Results: Code: This is the public key: 0291bee5cf4b14c291c650732faa166040e4c18a14731f9a930c1e87d3ec12debb Code: Scanning Incrementally (BSGS?! Maybe Meet In The Middle?) Not bad. Under 2 seconds to find the key in a 48 bit range. Less than 33 seconds combined with generating the DB. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: sssergy2705 on December 12, 2023, 03:11:38 PM Another modified script using a modified version of your DB script. Incremental, BSGS, Meet in the Middle, lol. 48 Bit Range Results: Code: This is the public key: 0291bee5cf4b14c291c650732faa166040e4c18a14731f9a930c1e87d3ec12debb Code: Scanning Incrementally (BSGS?! Maybe Meet In The Middle?) Not bad. Under 2 seconds to find the key in a 48 bit range. Less than 33 seconds combined with generating the DB. Testing different versions of the script, I can't get a result in puzzles higher than 42. How are you doing with your modified versions of the script? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 12, 2023, 04:15:21 PM Another modified script using a modified version of your DB script. Incremental, BSGS, Meet in the Middle, lol. 48 Bit Range Results: Code: This is the public key: 0291bee5cf4b14c291c650732faa166040e4c18a14731f9a930c1e87d3ec12debb Code: Scanning Incrementally (BSGS?! Maybe Meet In The Middle?) Not bad. Under 2 seconds to find the key in a 48 bit range. Less than 33 seconds combined with generating the DB. Testing different versions of the script, I can't get a result in puzzles higher than 42. How are you doing with your modified versions of the script? Are you using OPs github script versions? Or did you make any changes? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: sssergy2705 on December 12, 2023, 06:24:24 PM How many keys are you generating in your DB? Are you using OPs github script versions? Or did you make any changes? Code: import secp256k1 as ice Code: import multiprocessing The scripts have changed a little, but the general meaning is the same. Perhaps I made a mistake somewhere? Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 12, 2023, 10:16:41 PM 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 EDIT: If I use the BitArray option, as in original code, 20,000,000 keys generated into DB takes right at 4 seconds. Are you using multithreading? It works only for consecutive keys? With multithreading and 16 cores, I get 2**24 (16.77M) keys in 4.35 seconds. Non consecutive keys. EDIT: multithread (16 cores), 2^25 keys (33.5M) with distance = 16 (using ice.point_loop_subtraction): 5.15 seconds multithread (16 cores), 2^25 consecutive keys (using ice.point_sequential_decrement): 1.39 seconds EDIT2: multithread (16 cores), 2^25 keys (33.5M) with distance = 16 (using ice.point_loop_subtraction): 4.8 seconds multithread (16 cores), 2^25 consecutive keys (using ice.point_sequential_decrement): 1.06 seconds EDIT3: multithread (16 cores), 2^25 keys (33.5M) with distance = 16 (using ice.point_loop_subtraction): 4.67 seconds multithread (16 cores), 2^25 consecutive keys (using ice.point_sequential_decrement): 0.89 seconds Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: mcdouglasx on December 13, 2023, 02:48:55 PM Be careful with those who use multithreading to create the db, if you do something wrong and write the bits where they don't belong, they could obtain partially correct keys, such as:
private key = 32685509 private key = 33435509 when you should really get: target = 33185509 Test your codes first, before believing that it is a false positive when it is really a human error. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 14, 2023, 04:55:08 PM Quote EDIT2: multithread (16 cores), 2^25 keys (33.5M) with distance = 16 (using ice.point_loop_subtraction): 4.8 seconds multithread (16 cores), 2^25 consecutive keys (using ice.point_sequential_decrement): 1.06 seconds Wow, impressive! My results have all been single core. I have not attempted to do anything with multi-core yet. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: arulbero on December 14, 2023, 05:29:00 PM Quote EDIT2: multithread (16 cores), 2^25 keys (33.5M) with distance = 16 (using ice.point_loop_subtraction): 4.8 seconds multithread (16 cores), 2^25 consecutive keys (using ice.point_sequential_decrement): 1.06 seconds Wow, impressive! My results have all been single core. I have not attempted to do anything with multi-core yet. Then your results are better than mine. With only 1 cpu in 4 seconds I get around 16.5 M consecutive keys, not 20 M. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: WanderingPhilospher on December 14, 2023, 06:50:55 PM Quote EDIT2: multithread (16 cores), 2^25 keys (33.5M) with distance = 16 (using ice.point_loop_subtraction): 4.8 seconds multithread (16 cores), 2^25 consecutive keys (using ice.point_sequential_decrement): 1.06 seconds Wow, impressive! My results have all been single core. I have not attempted to do anything with multi-core yet. Then your results are better than mine. With only 1 cpu in 4 seconds I get around 16.5 M consecutive keys, not 20 M. Thats probably just because of the different CPUs. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: ElDalmatino on December 14, 2023, 07:47:14 PM Hi new to this topic, asking if there is a newer single core script that we can try, than the one in the first post.
Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: ElonMusk_ia on April 08, 2024, 03:23:13 PM Does anyone have C or C++ code to create databases faster?
Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: whanau on April 10, 2024, 03:08:06 AM what is the highest scalar (private key) you have found with this method?
What were your settings?. Thanks Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: studyroom1 on April 10, 2024, 09:17:49 AM lol tried to even find where is working codes but all seems like chit chat and no solid code are available not even on github
please provide all working codes or update it in github Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: ElonMusk_ia on April 10, 2024, 12:43:39 PM lol tried to even find where is working codes but all seems like chit chat and no solid code are available not even on github please provide all working codes or update it in github I wrote to the OP, but I think he died according to his last post, or maybe he's a troll, I don't know. Title: Re: lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1) Post by: whanau on April 10, 2024, 06:10:36 PM 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 search_key_arulbero.py Code: # 2023/Dec/03, arulbero_search_key.py This code works very well as does the code on the OP's Github page. |