Quote from: kTimesG on April 19, 2024, 12:01:45 AM

Quote from: satashi_nokamato on April 18, 2024, 10:08:59 AM

1 exakey per second means 1 and 18 zeros, a 4 GHz CPU could "count" up to a 11 digits number with no EC math involved, just pure counting per second. I would like to know how you can generate 4 exakey/s using keyhunt?

If you have a binary tree with 4 billion values, and you search if a specific one is in the tree, it takes at most 32 steps to do so. That means you searched 4 billion keys, but only did 32 CPU "goto next node" operations. So, in a sense, a speed of "4 billion keys / 32 cpu operations". You don't need to go through all of the nodes to know if something is in the tree or not.

Ofcourse, this is really misleading. Such exakeys/s numbers mean nothing in context of how big the parent keyspace really is, it's more like a click bait. You might as well apply the same logic to a pollard kangaroo evolving program and end up with ridiculous speeds as well the more data points you store, but it would not be a speed of group operations anymore, just like it's not for keyhunt.

Yeah exakeys is nothing compared with the keyspace that is begin scannig.

I really like the binary tree analogy as example it is good.

With BSGS the important number is the precalculated data in the bloom filter if we have 4 billion keys in a bloom filter we easily can know if the key is not in our bloom filter doing less than 20 hashes. so that means we discard a subrange of 4 billion keys with only 20 CPU Operations.

https://andrea.corbellini.name/2015/06/08/elliptic-curve-cryptography-breaking-security-and-a-comparison-with-rsa/