Hi All,
I've been reading this and other related topics for a few weeks and I'm trying to understand the complexity of the different algorithms and approaches.
https://andrea.corbellini.name/2015/06/08/elliptic-curve-cryptography-breaking-security-and-a-comparison-with-rsa/You are mixing operations per second and keys per second and those aren't the same.
In BSGS with a precalculated set of 100 million keys, you only need to do a single operation ( publcikey subtraction) to determine if a key is in some 100 million keys right, that is 1 single operation but it give you a speed of 100 million keys / time, that is the difference, while bsgs do some thousands of subtraction per second (operations) it will give you some petakeya/s (speed) it is different way to measure it.
Thanks Alberto, this is indeed what I was missing. I'm trying to understand the exact purpose of the
n and
k parameters of keyhunt. Is
n in this case the number of pre-calculated keys? I'm trying to understand the efficiency of the algorithm - how long it would take to finish a full scan of a given range. Is it as simple as
range size (keys) divided by
speed (keys/s reported by keyhunt)? I'm assuming not, since this is not a brute-force algorithm.
Every fifth range is 32 (2
5) times bigger than the last (e.g. the range for #130 has 32x more keys than the one for #125). If I could benchmark my system on how fast it could solve a simpler BSGS puzzle (say #125), how do I extrapolate on how fast it would do with #130? I assume it's faster than 32x the time it takes for #125.
Did you read his GitHub? He has ranges and keys to benchmark your speed.
And just because you could solve 120 in say a day, doesn’t mean you could solve 125 in 32 days. If the key is in the beginning of the range, before 120s, in relation, you’d solve faster than 32 days. If it was after, then more than 32 days.
Keep it easier,
If a key in the 120 bit range was in the 8s and it took you one day, if 124s key was in the Fs, it would take you longer than 16 days. Make sense?
To give a better, worse case scenario, determine your speed, then calculate time taken by taking the last possible check in a range, (based on how large your baby step file is) and divide it by your speed.