2
$\begingroup$

As far as I understand, compressed public keys of secp256k1 can represent points either above or below the X axis, depending on whether they begin 0x02 or 0x03.

Am I correct in thinking that if you know a secret key for a public key beginning 0x02 you can trivially find the secret key for the identical public key, but beginning 0x03?

If so, is there any security loss in using only keys beginning 0x02? i.e. Throwing away all generated keypairs where the compressed public key begins 0x03?

(The motivation is to avoid an awkward extra bit/byte of public key length and to prevent attacks similar to an early bitcoin exchange attack where the opposite-sign public key was used.)

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ I've never heard of a bitcoin attack using negated publickey; can you give a reference? The MtGox failure was blamed on attack using transaction malleability due to negating S in signature, which is quite different (and we already have Qs on), and as result of which bitcoin now enforces a 'low-S' rule ($S < n/2$) $\endgroup$
    – dave_thompson_085
    Aug 23 at 2:52
  • $\begingroup$ @dave_thompson_085 My mistake - MtGox was the exchange attack which I was remembering, but I was confused as to what was negated. $\endgroup$
    – fadedbee
    Aug 23 at 4:40

1 Answer 1

Reset to default
3
$\begingroup$

If you know a secret key for a public key beginning 0x02 you can trivially find the secret key for the identical public key, but beginning 0x03

Indeed, there's a simple relation between private keys $d$ and $d'$ for public keys $Q$ and $Q'$ differing only by sign as coded by the 0x02 or 0x03 prefix when in compressed form. That is $d=n-d'$ and $d'=n-d$, where $n$ is the prime order of the secp256k1 elliptic curve group.

Is there any security loss in using only keys beginning 0x02?

No.

Argument: the prefix is public anyway, and by the above relation any algorithm that recovers the private key for public key restricted to 0x02 prefix can be trivially extended to public key with random prefix, with the same probability of success, and negligible extra effort. This is not a proof, because private key recovery is not the only possible attack.

More formal argument, in the context of use of the key with ECDSA: if $(r,s)$ passes the ECDSA verification for message $m$ and public key $Q$, then $(n-r,s)$ passes verification for message $m$ and public key $Q'$ differring from $Q$ by the prefix when in compressed form. Hence any algorithm that breaks ECDSA's EUF-CMA security for public key restricted to 0x02 prefix can be trivially extended to public key with random prefix, with the same probability of success, and negligible extra effort.

Throwing away all generated keypairs where the compressed public key begins 0x03?

That's a possibility, but we can simply replace the 0x03 by 0x02 and adjust the private key using $d'=n-d$, provided that (as anything during key generation) such adjustment is protected from side channels.

Improve this answer
$\endgroup$

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.