Imagine that you have one Single operation to check if some Publickey
P(x) is between some fixed range lets to say from 1 to 1M such operation will be like:
if 1 <= P(x) <= 1M
print "Found :)"
else
print "Not Found :("
That operation doesn't exist because Public keys are hidden numbers they hide the x value (Private key)
So, what happened if you have the Cache of the first million keys, you only need to have a function that let you know if some publickey is inside of one array
if is_publickey_in_array(P(x),array)
print "Found :)"
else
print "Not Found :("
to be computationally efficient, that function need to be fast O(1), There are a lot of Data structures that can do that, Hashtables, maps, bloomfilters etc, or some combinations between them.
What BSGS Do?The first step is try to translate the P(x) to the keyspace between 1 to 1M (This amount can be changed this depends of the available memory), this operation is done by one single subtraction.
Lets to say that the value of x is 100123987
P(100123987) = 03992723319651c25a1e3dc624af41a8625a90c3c455f806a4a2b385175750b211
P(100000000) = 03df77e24113f1c6093dc99e62e63737c97821c854bf03b171b7fefbd81acec408
P(100123987) - P(100000000) = P(123987)
P(123987) = 02ee35e4236c7b0b269c88b1da75b9a068a7227bd847a931c55587ec4017b2cd98
If we check for the function that value of P(123987) is in the array
is_publickey_in_array(P(x),array) then the the result will be that we found the key, you only need to find what of those Million of values is your key and then just do some additions to recover the original KEY.
For the previous example imagine that you start from 1 to reach 100M you only need 100 Point Subtractions and 100 checks in the arrays, so instead of bruteforce that publickey 100 Million times you only need 100 basic operations that is why bsgs is some fast
This is a basic example, the real BSGS need some extra considerations like work with Perfect squares numbers, and also will be better if we work with Base 2 numbers like 2^Y numbers
This is an example with One million of publickeys in cache, now imagine what you can do with with some Billions of keys in your cache.
you can read more of BSGS in
https://andrea.corbellini.name/2015/06/08/elliptic-curve-cryptography-breaking-security-and-a-comparison-with-rsa/I assume that in BSGS mode there no no such option as random changed key after a given key value searched?
The -R option enable the random search, every time that one thread do a search it chose a different random number, this is EVERY single cycle one random number is chossen.
Regards!
Show Posts
