Quote from: albert0bsd on March 06, 2021, 02:13:56 PM

I want to open this thread to talk about the tool that i develop Keyhunt available on github.

https://github.com/albertobsd/keyhunt

Keyhunt use the BSGS algorimth to find privatekeys with the publickey, the program runs on CPU and make several use of RAM to boost the speed.

To try to find the privatekey from the 120 puzzle you need to add this publickey "uncompress" to a txt file:

How to use

Add the publickey to a file

120.txt

Code:

02CEB6CBBCDBDF5EF7150682150F4CE2C6F4807B349827DCDBDD1F2EFA885A2630

you can run the tool agains that file:

Code:

./keyhunt -m bsgs -f 120.txt -b 120 -R

output

Code:

[+] Version 0.1.20210321 K*BSGS
[+] Setting mode BSGS
[+] Min range: 800000000000000000000000000000
[+] Max range: ffffffffffffffffffffffffffffff
[+] Setting random mode.
[+] Opening file 120.txt
[+] Added 1 points from file
[+] Bit Range 120
[+] Setting N up to 17592186044416.
[+] Init 1st bloom filter for 4194304 elements : 14.00 MB
[+] Init 2nd bloom filter for 209716 elements : 0.00 MB
[+] Allocating 128.0 MB for 4194304 aMP Points
[+] Precalculating 4194304 aMP points
[+] Allocating 3.00 MB for 209716 bP Points
[+] precalculating 4194304 bP points
[+] Sorting 209716 elements
[+] Thread 0: 000000000000000000000000000000000092dd2b47cff81ad94120bf853ef87f
[+] Thread 0: 0000000000000000000000000000000000f7fe7fccb98e136a97c2fa9d41de7b
[+] Thread 0: 00000000000000000000000000000000008d4882d7f596851a73ae35543c4dcd
Total 35184372088832 keys in 30 seconds: 1172812402961 keys/s
[+] Thread 0: 00000000000000000000000000000000009e80f97d3e3ff0fddbdcf02894e41d
^C

Speed: 1 Terakeys/s

Well in that example (same in github) we can reach 1Terakeys/s with one thread.

Wan to more speed? use the "-k value" param to boots the speed

Code:

./keyhunt -m bsgs -f 120.txt -b 120 -R -k 20

Output:

Code:

[+] Version 0.1.20210321 K*BSGS
[+] Setting mode BSGS
[+] Min range: 800000000000000000000000000000
[+] Max range: ffffffffffffffffffffffffffffff
[+] Setting random mode.
[+] Setting k factor to 20
[+] Opening file 120.txt
[+] Added 1 points from file
[+] Bit Range 120
[+] Setting N up to 17592253153280.
[+] Init 1st bloom filter for 83886080 elements : 287.00 MB
[+] Init 2nd bloom filter for 4194304 elements : 14.00 MB
[+] Allocating 6.0 MB for 209716 aMP Points
[+] Precalculating 209716 aMP points
[+] Allocating 64.00 MB for 4194304 bP Points
[+] precalculating 83886080 bP points

[+] Sorting 4194304 elements
(Thread output omited....)
Total 703690126131200 keys in 30 seconds: 23456337537706 keys/s
(More thread output omited....)
Total 2814760504524800 keys in 120 seconds: 23456337537706 keys/s

Speed: ~23 Terekeys/s

Tips

you can quiet the thread output with -q
you can load the precalcutalted bPtable -p yourfile.bin

Do you still want to more speed? Well Use more RAM, the -k 128 will use some 2.5 GB of RAM

This file will take some minutes for the value -k 128, but the speed worth it!

Code:

./keyhunt -m bsgs -f 120.txt -b 120 -R -k 128 -p ./bPfile.bin

Output:

Code:

[+] Version 0.1.20210321 K*BSGS
[+] Setting mode BSGS
[+] Min range: 800000000000000000000000000000
[+] Max range: ffffffffffffffffffffffffffffff
[+] Setting random mode.
[+] Setting k factor to 128
[+] Opening file 120.txt
[+] Added 1 points from file
[+] Bit Range 120
[+] Setting N up to 17592186044416.
[+] Init 1st bloom filter for 536870912 elements : 1840.00 MB
[+] Init 2nd bloom filter for 26843546 elements : 92.00 MB
[+] Allocating 1.0 MB for 32768 aMP Points
[+] Precalculating 32768 aMP points
[+] Allocating 409.00 MB for 26843546 bP Points
[+] Reading 536870912 bP points from file ./bPfile.bin
[+] Sorting 26843546 elements
(Thread output omited....)
Total 4345269952970752 keys in 30 seconds: 144842331765691 keys/s
(More thread output omited....)
Total 17539409486282752 keys in 120 seconds: 146161745719022 keys/s

Speed: ~146 Terakeys/s one single thread

OK at this point maybe you want to use ALL your RAM memory to solve the puzzle 120, just a bigger -k value

I already tested it with some 24 GB used with -k 1024 and I get 1.16 Petakeys/s per thread.

Using the same configuration with 4 threads I get 4.5 Petakeys/s total

Image:
https://albertobsd.dev/uploads/1616428067_bd1fc052-9441-4cbb-9bd1-d2e393489e18.jpg

FAQ

Q: Why the Progress is not displayed?
R: The speed depent of the number of target publickeys if you load 1000 publickeys, it will take some more time, the speed is only displayed when at least one thread finish one of his cycles

Q: Can we faster this code with Gpu?
R: Well yes, but the BSGS algo use RAM, only high end video cards have a lot of RAM, for GPU is better to use Kangaroo

Q: How long will take the scan the 120 bit range?
R: Human brain usually can't handle big numbers, the 120 bit space have 664613997892457936451903530140172287 (six hundred sixty four decillion...) and we speed is about 1000000000000 (one trillion or one terakey/s) the spected time acording with your speed is:

Code:

Puzzle 120 @ 1 Terakeys/s : 21074771622667996 years
Puzzle 120 @ 1 Petakeys/s : 21074771622667 years

Q: Why should i keep using brute force tools?
R: You should not, but people hope in luck.

Q: Is avaible for Windows?
R: Natively no, but you can install the ubuntu shell for windows and compile it from there

Q: It have dependencies?
R: Just libgmp for BigIntegers install it with

Code:

apt-get install libgmp3-dev

Q: Why your program use alot of RAM?
R: Actuallly i keep in RAM two things (Bloomfilter and a Full bPTable ) im working in one way to remove or reduce the bPTable.

Nexts releases

~~BSGS with K factor~~ Release in 6/March
Network/Pool versión
Pollard rho

Best regards!

Great information to share!! How to use pfile??