1
$\begingroup$

I need to store a public key in a variable of maximum 32 bytes.

I recover the compressed key and remove its prefix, but then I have to do the opposite: I have to rebuild the compressed address from it without the prefix.

I know that the prefix depends on the last two characters of the uncompressed key.

Prefix = 0x03 if the last two characters are odd or 0x02 if even.

but I can't store the uncompressed key.

Any idea how to get the prefix from the compressed key?

thank you to those who will take the time to reply !!

example keys

  • Public Key uncompressed : 0x046c409d418f9f35322c7bc0e262da2d01d2d4643121c40682d8dfa54434690d24680ca09c51340eaef3f365bfaf42f27e620088884525fa9de07df1685a0411f7

  • Public Key : 0x036c409d418f9f35322c7bc0e262da2d01d2d4643121c40682d8dfa54434690d24

  • 32 bytes Public key : 0x6c409d418f9f35322c7bc0e262da2d01d2d4643121c40682d8dfa54434690d24

Improve this question
$\endgroup$
1
  • $\begingroup$ There is no way to decide if the prefix should be 0x02 or 0x03 from what's in the question. For a standard secp2256k1 public key, both the 0x02 and 0x03 prefix are possible for any given 32-byte value such that either the 0x02 or 0x03 prefix is possible. Depending on the context, their might be a way; e.g. if a valid signature is known, if the prefix obeys some convention. $\endgroup$
    – fgrieu ♦
    Sep 27 at 9:24

1 Answer 1

Reset to default
1
$\begingroup$

I know that the prefix depends on the last two characters of the uncompressed key.

Not the last; is it prefixed,i.e. added to the beginning.

In secp256k1, for compression we have the following rule;

  • prefix 04 means no compression
  • prefix 02 means compression with $y$ coordinate is even
  • prefix 03 means compression with $y$ coordinate is odd

How to determine the prefix of a SECP256K1 compressed public key

Take the compressed key;

0x036c409d418f9f35322c7bc0e262da2d01d2d4643121c40682d8dfa54434690d24

then look at the first byte; 03 and this mean there is compression and $y$ coordinate is odd.

Take the uncompressed key;

First decompose the first byte then divide the rest into two 32 bytes, first 32-byte is the $x$-coordinate and the last 32-byte is the $y$-coordinate.

0x04 
6c409d418f9f35322c7bc0e262da2d01d2d4643121c40682d8dfa54434690d24
680ca09c51340eaef3f365bfaf42f27e620088884525fa9de07df1685a0411f7

so the prefix is 0x04

I need to store a public key in a variable of maximum 32 bytes.

You can't! You need a little more than 32 bytes, you need at most 33 bytes. The reason for this is;

The secp256k1 curve has the $E: y^2 = x^3+7$ equation over $\mathbb{F}_p$ where it is defined by:

$p = 2^{256}-2^{32}-977 = 115792089237316195423570985008687907853269984665640564039457584007908834671663$

If you place the $x$-coordinate value and solve it over $\mathbb{F}_p$ then you will have at most two solutions. So, one needs to determine at least one bit to resolve this - 2 bits is needed since we have three options.

I know that the prefix depends on the last two characters of the uncompressed key.

Less than that; last bit of the y-coordinate.

Any idea how to get the prefix from the compressed key?

Already answered, however, I read this as how to determine the prefix from uncompressed key. In this case look at the last bit of $y$-coordinate.

How to reduce the size ( comments integration)

  • The obvious solution is the agreement to always use even $y$ so that when people agreed to use always compression, then we no need to prefix byte to indicate compression and $y$'s selection.

    Dave Thompson indicated that Bitcoin Taproot (bip-0340) do this and now every public key has two secret keys.

    $$d[G]= (x,y) \text { and } (n-d)[G]= (x,n-y)$$

    to see this

    $$(n-d)[G] = [n]G - [d][G] = \mathcal{O} - [d]G = - (x,y) = (x, -y)$$

  • Another one is; for a random ~256 keys, we will have the leading or trailing of the public key will have zero byte. So, one generates random private keys until leading byte is zero ( pre-determined to be leading or trailing ). This only reduces the private key space around one byte. So, for one it we loose one bit, and for one byte we loose one byte.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Would it be possible to restrict the choice of private keys to make it possible for the public keys to fit into 32 bits? Like retrying private key generation until the (compressed) public key matches into a certain format, then omit some bits? Or would this introduce dangerous weaknesses? $\endgroup$
    – Paŭlo Ebermann
    Sep 26 at 10:54
  • $\begingroup$ @PaŭloEbermann You mean 32 bytes, I think one possible and simple way is always use the positive $y$? This can eliminate at most half of the keys. To be honest, I would do this for the sake of people since programmers are prone to make mistake. I've to think more other possible cases. $\endgroup$
    – kelalaka
    Sep 26 at 11:33
  • $\begingroup$ thank you for your answer @kelalaka, I think the best method would be to store the prefix in a 1 byte variable. 32 bytes Public key : 0x6c409d418f9f35322c7bc0e262da2d01d2d4643121c40682d8dfa54434690d24 1 bytes Prefix: 0x03 $\endgroup$
    – Sino
    Sep 26 at 14:54
  • $\begingroup$ That is really how you want to store. You need this 1-bit information if you always use compression, however, be careful when you transfer this public information. $\endgroup$
    – kelalaka
    Sep 26 at 14:59
  • 1
    $\begingroup$ @PaŭloEbermann: yes, just negate; if $dQ=(x,y)$ with y even then $(n-d)Q=(x,p-y)$ with p-y odd (and vice versa). A recent addition to Bitcoin, Taproot, uses exactly this method (and on secp256k1 to boot). $\endgroup$
    – dave_thompson_085
    Sep 26 at 23:46

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.