Score:2

Does using only one sign of secp256k1 publc keys weaken security?

br flag

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.)

dave_thompson_085 avatar
cn flag
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$)
fadedbee avatar
br flag
@dave_thompson_085 My mistake - MtGox was the exchange attack which I was remembering, but I was confused as to what was negated.
Score:3
ng flag

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.

I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.