<p>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 <em>always</em> 04 (to distinguish it from the other forms). Thus you can determine one byte of <em>all</em> public keys without any computation at all, but this provides exactly zero, zilch, nada information about the private keys.</p>
<p>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.)</p>
<p>So presumably you <em>meant</em> 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.</p>
<p>But let's consider the ideal case: you design and manufacture your own totally custom chips which can do a secp256k1 basepoint multiplication in <em>one nanosecond</em>; 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.</p>

CC BY-SA 4.0
2022-03-23T14:45:33.000Z
You can compute the private key for a given public key with approximately 2^128 group operations using e.g. https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm_for_logarithms. That's *much* less than 2^256 full point multiplications.
Pieter Wuille
CC BY-SA 4.0
2022-03-25T01:34:45.963Z
@PieterWuille: True, but that's not done by 'sped-up' bruteforce, which is explicitly the question here.
dave_thompson_085
CC BY-SA 4.0
2022-03-25T03:17:32.717Z
Fair point, I missed that part of the question.
Pieter Wuille
CC BY-SA 4.0
2022-03-23T05:02:12.150Z
2022-03-23T05:02:12.150Z
dave_thompson_085
<p>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.</p>
<p>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?</p>
<p>Implementing this would make sense if it would take much less time to compute it partially.</p>
<p>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.</p>

<private-key><cryptography>
Is it possible to compute just a byte of the public key by having the private key?
JKS
# Is it possible to compute just a byte of the public key by having the private key?

(Asked by: username_0 on 2022-03-22)

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.

**Tags:** private-key, cryptography


---

## 1 answers

### Answer by username_1 on 2022-03-23. Score: 1 | Accepted answer

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.

> **Comments:**
> **username_2**: You can compute the private key for a given public key with approximately 2^128 group operations using e.g. https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm_for_logarithms. That's *much* less than 2^256 full point multiplications.  
> **username_1**: @username_2: True, but that's not done by 'sped-up' bruteforce, which is explicitly the question here.  
> **username_2**: Fair point, I missed that part of the question.  

---

