0

Let's say we have a certain known public key to which we want to find the private key with a bad approach such as brute forcing.

Would it be possible that instead of computing the whole public key to check if it matches with a target one, to just compute the first (or any one) byte (or bytes) and if said byte matches the target's first byte to the to compute the full public key?

Implementing this would make sense if it would take much less time to compute it partially.

I am aware that the odds of finding anything are astronomical and that there are better ways of doing this. This is just for educational purposes.

0

1 Answer 1

1

One of the standard representations for a public key of the type used in Bitcoin (i.e. X9-style EC) is 'uncompressed' form, whose first octet (see below) is always 04 (to distinguish it from the other forms). Thus you can determine one byte of all public keys without any computation at all, but this provides exactly zero, zilch, nada information about the private keys.

Also to be super pedantic, 'byte' is not a fixed size. It can be as small as 1 bit (especially on the PDP-6 and -10 which had variable byte-field pointers, but now exist only in literal museums). However, the computers available for programming by most non-specialists today always have 8-bit bytes, so many people never even imagine the other possibilities. (This is why properly-written standards use 'octet' not 'byte' when they mean specifically 8 bits.)

So presumably you meant one 8-bit byte in the meaningful part (i.e. either coordinate) of a public key. Then the answer is: NO; you can't compute any part of either coordinate without doing the point multiplication, which always produces all of both coordinates. There are several different methods of doing this multiplication, with different speeds, but none is sped up by producing a partial result.

But let's consider the ideal case: you design and manufacture your own totally custom chips which can do a secp256k1 basepoint multiplication in one nanosecond; this probably costs only a few billion dollars. And you have a billion of these chips (almost one per person on Earth) and several thousand power plants, owned and controlled by you, plus sufficient fuel for types that require it. It would take 2 thousand trillion trillion trillion trillion years (using US trillion = 10^12) to search the secp256k1 private-key space -- that's so long that in comparison the entire existence of the universe, much less the Earth, is undetectably small.

3

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.