brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning]

[MrFreeDragon]

I did few optimizations (commited to github), I reached 13.6M giant steps of 2^30 per second on my Xeon X5647 2.93GHz with 12GB of RAM.
It solves the 16 keys of the odolvlobo's set in 3:35:53 from scratch, I mean without any precomputation.
If I convert to the Etar's unit: It does 14.6 PKey/s.
-snip-

Nice job! Thank you.
So, your total time for 16 keys is 216 minutes, including 9 minutes for 2^30 precomputations. That means that for 16 keys search you need 207 minutes, or approx. 13 minute per one 64bit key. As i saw from your results, the time per one 64 key varied from 2 min to 19 min.

Avg time 13minute is very good. I guess it is faster than the result reqched by Pollard Kangaroo method sahred in BurtW topic.

[Tamarindei]

I did few optimizations (commited to github), I reached 13.6M giant steps of 2^30 per second on my Xeon X5647 2.93GHz with 12GB of RAM.
It solves the 16 keys of the odolvlobo's set in 3:35:53 from scratch, I mean without any precomputation.
If I convert to the Etar's unit: It does 14.6 PKey/s.

I posted the result in the readme of my program:
https://github.com/JeanLucPons/BSGS/blob/master/README.md

Thanks to odolvlobo to provide this challenge.
Best wishes to Etar to optimize his program and fix his issue on GPU.

Thx. How long would it take you to solve 110 bit range key of puzzle transaction?

[Jean_Luc]

I published an exe file for Windows:
https://github.com/JeanLucPons/BSGS/releases/tag/1.0

To solve a 110bit puzzle, on my config, it would take a very very long time, ~4 billions years !

[Etar]

I published an exe file for Windows:
https://github.com/JeanLucPons/BSGS/releases/tag/1.0

To solve a 110bit puzzle, on my config, it would take a very very long time, ~4 billions years !

Thanks a lot for release.

[Jean_Luc]

Nice job! Thank you.

You're welcome

So, your total time for 16 keys is 216 minutes, including 9 minutes for 2^30 precomputations. That means that for 16 keys search you need 207 minutes, or approx. 13 minute per one 64bit key. As i saw from your results, the time per one 64 key varied from 2 min to 19 min.

Avg time 13minute is very good. I guess it is faster than the result reqched by Pollard Kangaroo method sahred in BurtW topic.

If you look at the key who has been solved in 19min, you see that ...7D0E6081C7E0E865 is close to ...8000000000000000 (end range of thread #3) and that it requires a total of 2^33.86 giant steps (max 2^34) so we are close to the end of the range.
It takes ~20 minutes to browse the full 2^64 range, so the theoretical average time to solve a key should be 10min without taking into account the baby step precalculation.

[Etar]

Nice job! Thank you.

You're welcome

So, your total time for 16 keys is 216 minutes, including 9 minutes for 2^30 precomputations. That means that for 16 keys search you need 207 minutes, or approx. 13 minute per one 64bit key. As i saw from your results, the time per one 64 key varied from 2 min to 19 min.

Avg time 13minute is very good. I guess it is faster than the result reqched by Pollard Kangaroo method sahred in BurtW topic.

If you look at the key who has been solved in 19min, you see that ...7D0E6081C7E0E865 is close to ...8000000000000000 (end range of thread #3) and that it requires a total of 2^33.86 giant steps (max 2^34) so we are close to the end of the range.
It takes ~20 minutes to browse the full 2^64 range, so the theoretical average time to solve a key should be 10min without taking into account the baby step precalculation.

I realy do not understand something))
I try to implement hashtable, because hashtable is more fast then binary search.
So, i use 24bit mask, like in your implementation.
total baby steps = 2^24 = 16777216. Just for test. In real usage it should more.
and i get a lot of collisions when fill table:

Code:

----------HashTable Info----------
Total unique hashes:10604491x12=127253892 bytes
Total items:16777216x4=67108864 bytes
Total 194362756 bytes
Total colisions:6172725
Max. colisions:10
----------------------------------

What i see from info:
there were unique 10604491  24 bit combinations from total of 16777216 combinations
24 bit combinations that has collision was 6172725
and maximum of collision was 10 on some of the hashes
i think it is terrible result of collisions  

[Jean_Luc]

f you use a 24bit hashtable and 2^30 keys for baby step:

You will have (in average) a list of 2^(30-24) = 64 items per hash.
Each items of this list contains the generator index and an additional part of the key.

Code:

typedef struct {
  uint32_t b0; // LSB key (24 bit) + HSB Offset (8 bit)
  uint32_t p;  // LSB Offset
} ENTRY;

The hash is 3 byte of MSB of the key.
b0 is 3 byte of LSB of the key.
So we store 48 bits of the key.
p (offset) is the "generator index" corresponding to the key p.G

Then to access it , you compute the hash (one simple & operation) and you have direct access to this small list.
You can sort each list according to the part of key and you will need 6 operations (in average) to get the generator index.
I did like this in HashTable::Get().

Then as I don't store the full X value of p.G, i have some false collision, than i need to check by a computePublicKey.
A false collision happens every 2^(24+24 - 30) = 2^18 giant steps, that means that I need to perform an extra EC multiplication every 262144 giant steps.

According to the memory you have, you may need to adjust the HASH size, and the number of bit of the key stored in the entry in order to have a minimum of false collision.

[Etar]

f you use a 24bit hashtable and 2^30 keys for baby step:

You will have (in average) a list of 2^(30-24) = 64 items per hash.
Each items of this list contains the generator index and an additional part of the key.

Code:

typedef struct {
  uint32_t b0; // LSB key (24 bit) + HSB Offset (8 bit)
  uint32_t p;  // LSB Offset
} ENTRY;

The hash is 3 byte of MSB of the key.
b0 is 3 byte of LSB of the key.
So we store 48 bits of the key.
p (offset) is the "generator index" corresponding to the key p.G

Then to access it , you compute the hash (one simple & operation) and you have direct access to this small list.
You can sort each list according to the part of key and you will need 6 operations (in average) to get the generator index.
I did like this in HashTable::Get().

Then as I don't store the full X value of p.G, i have some false collision, than i need to check by a computePublicKey.
A false collision happens every 2^(24+24 - 30) = 2^18 giant steps, that means that I need to perform an extra EC multiplication every 262144 giant steps.

According to the memory you have, you may need to adjust the HASH size, and the number of bit of the key stored in the entry in order to have a minimum of false collision.

Ah, I understand difference bettwen our hashtables.
When you make pubkey you compare pubkey (masked pubkey) with each of element of hashtable( in last optimisation you add sorting for this)
But i try to use other way. i don`t need to compare pubkey with each elements becouse i have table of 2^24
In that case  i need only 1 lookup to the table to get hash and i get result  - hash exist or not and if exist get pointer to memory where stored G counter or few G counters if collision.

[0zero0]

From what I have learnt about bitcoin I can say that deriving a private key from a public key is not possible.
The public key of is derived from a private key but that functionality is not backward compatible according to what I have learnt.
So deriving the private key from public key is not feasible in my opinion.

P.S : I have read this in some article on have watched youtube videos which say the same.

Also, if it is miraculously possible could you please explain it how, in Laymans terms.

[Jean_Luc]

Ah, I understand difference bettwen our hashtables.
When you make pubkey you compare pubkey (masked pubkey) with each of element of hashtable( in last optimisation you add sorting for this)
But i try to use other way. i don`t need to compare pubkey with each elements becouse i have table of 2^24
In that case  i need only 1 lookup to the table to get hash and i get result  - hash exist or not and if exist get pointer to memory where stored G counter or few G counters if collision.

Ok, If I understand well your startegy, you face the birthday paradox problem. When you fill your hashtable, you will start to have collision around the sqrt(2^24)=2^12th insertion. So for 2^24 G counters, you will need a hashtable of ~2^48 entries to avoid collision.

[MrFreeDragon]

-snip-
Thanks a lot for release.

Have you tested this release on your config? How is the progress compared with your code?

[Etar]

-snip-
Thanks a lot for release.

Have you tested this release on your config? How is the progress compared with your code?

Jean_Luc program much faster than my!
Because have big base hashrate. I mean for ex. base hashrate for i7 3770 is 14Mkey/s. I can`t get this speed on my program because i use simple language where big integer calculations used 3ty part library. In that case i have low base hashrate due to convertion for integers.

[COBRAS]

I published an exe file for Windows:
https://github.com/JeanLucPons/BSGS/releases/tag/1.0

To solve a 110bit puzzle, on my config, it would take a very very long time, ~4 billions years !

Hello respected Jean !!!

Then Lanch release on my 8 Gb memory PC, after memory was full used in release code, sped of working down to 0- zero. Can you please modyfy code for fine wlrking on PC with smole memory then 12 Gb.


?


Thanks

[Etar]

I published an exe file for Windows:
https://github.com/JeanLucPons/BSGS/releases/tag/1.0

To solve a 110bit puzzle, on my config, it would take a very very long time, ~4 billions years !

Hello respected Jean !!!

Then Lanch release on my 8 Gb memory PC, after memory was full used in release code, sped of working down to 0- zero. Can you please modyfy code for fine wlrking on PC with smole memory then 12 Gb.


?


Thanks

Yo can just decrease baby step counter in config in.txt
by default baby step = 2^30 = 40000000 in hex format
you can use for ex. 2^28 = 10000000 in hex
each step used 64bit of memory, so 2^28 need only 2Gb
2^29 around 4Gb
Decrease the baby step counter will proportionally increase the brute force time.

[MrFreeDragon]

-snip-
Thanks a lot for release.

Have you tested this release on your config? How is the progress compared with your code?

Jean_Luc program much faster than my!
Because have big base hashrate. I mean for ex. base hashrate for i7 3770 is 14Mkey/s. I can`t get this speed on my program because i use simple language where big integer calculations used 3ty part library. In that case i have low base hashrate due to convertion for integers.

Jean_Luc also made the vanity search program, and some guy modified it to work with pollard kangaroo method. The code is here: https://github.com/alek76-2/vs-kangaroo-hybrid

I beleive that this program should be faster. It uses GPU, not CPU. Of course it is not good to compare CPU and GPU, GPU will always be ahead.

Also for proper work of BSGS method the RAM is required; the more - the better.

[MrFreeDragon]

I published an exe file for Windows:
https://github.com/JeanLucPons/BSGS/releases/tag/1.0
To solve a 110bit puzzle, on my config, it would take a very very long time, ~4 billions years !

Hello respected Jean !!!

Then Lanch release on my 8 Gb memory PC, after memory was full used in release code, sped of working down to 0- zero. Can you please modyfy code for fine wlrking on PC with smole memory then 12 Gb.
-snip-

Etar already answered. I can confirm the same.
Just use the smaller baby step table. It is the 1st line in in.txt file. By default it is 40000000 in hex format (2^30), and it requitres approx. 9Gb RAM.

For your 8Gb memory you can use 20000000 (2^29), and in total you will need approx. 1 hour to find the private key for 64bit key. Jean tested with 12Gb RAM and 2^30 baby step and had approx 13 minutes. You will have 1 hour with your 8Gb RAM.

Just test, and say the result if 1 hour prediction was correct.

[COBRAS]

I published an exe file for Windows:
https://github.com/JeanLucPons/BSGS/releases/tag/1.0
To solve a 110bit puzzle, on my config, it would take a very very long time, ~4 billions years !

Hello respected Jean !!!

Then Lanch release on my 8 Gb memory PC, after memory was full used in release code, sped of working down to 0- zero. Can you please modyfy code for fine wlrking on PC with smole memory then 12 Gb.
-snip-

Etar already answered. I can confirm the same.
Just use the smaller baby step table. It is the 1st line in in.txt file. By default it is 40000000 in hex format (2^30), and it requitres approx. 9Gb RAM.

For your 8Gb memory you can use 20000000 (2^29), and in total you will need approx. 1 hour to find the private key for 64bit key. Jean tested with 12Gb RAM and 2^30 baby step and had approx 13 minutes. You will have 1 hour with your 8Gb RAM.

Just test, and say the result if 1 hour prediction was correct.

Big thanx all members for yours answers.

I will test today in the evening and show me results. I hope my PC without CUDA will can do something.

Again - big thanx to all.

[COBRAS]

Is any method for add Windos ReadyBost to Release ? I was tern up readyboost but release code not used them. Have someone sny ideas ?

[sssergy2705]

I published an exe file for Windows:
https://github.com/JeanLucPons/BSGS/releases/tag/1.0
To solve a 110bit puzzle, on my config, it would take a very very long time, ~4 billions years !

Hello respected Jean !!!

Then Lanch release on my 8 Gb memory PC, after memory was full used in release code, sped of working down to 0- zero. Can you please modyfy code for fine wlrking on PC with smole memory then 12 Gb.
-snip-

Etar already answered. I can confirm the same.
Just use the smaller baby step table. It is the 1st line in in.txt file. By default it is 40000000 in hex format (2^30), and it requitres approx. 9Gb RAM.

For your 8Gb memory you can use 20000000 (2^29), and in total you will need approx. 1 hour to find the private key for 64bit key. Jean tested with 12Gb RAM and 2^30 baby step and had approx 13 minutes. You will have 1 hour with your 8Gb RAM.

Just test, and say the result if 1 hour prediction was correct.

core i7 3770 8 RAM 28 mins

[Jean_Luc]

core i7 3770 8 RAM 28 mins

28 min per key with 8Gb RAM ?