1
$\begingroup$

Given a Schnorr Public Key (32 bytes) x, I'd like to generate a compressed ECDSA Public Key (33 bytes) and thus be able to generate the bitcoin address that the private key holder can generate with their private key.

  • A Schnorr Public Key is x (BIP340, https://bips.xyz/340 - more detail about the Schnorr signature.)

  • An uncompressed ECDSA public key has the starting byte 0x04 + x + y

  • A compressed ECDSA public key has a starting byte of either (0x02 or 0x03) + x

  • Thus the ECDSA compressed public key will be either 0x02 + x or 0x03 + x

Is there any possible way to deduce which one from just the x value?

Edit: Given @fgrieu point that it may not be safe to reuse a key in this way across two different signature schemes, I've decided against pursuing this approach out of an abundance of caution. I'll leave the question here as it may be of academic interest.

$\endgroup$
4
  • 2
    $\begingroup$ That question is highly specific to the conventions used in bitcoin, which should at least be linked (especially for the part on Schnorr signature, since there are so many variant of that). Is there a convention in Bitcoin that the same private key can be used for Schnorr and ECDSA signature? $\endgroup$
    – fgrieu
    Dec 24, 2022 at 17:39
  • $\begingroup$ Here's BIP340, bips.xyz/340 - this goes into detail about the Schnorr signature. Don't think there is any convention about using the same private key for both signatures, but I need to do it! $\endgroup$
    – FreeTrade
    Dec 24, 2022 at 18:00
  • $\begingroup$ please edit the body of the question, instead of giving information in the comment. any descriptive language would also be welcome. this makes the question and any answer useful to others $\endgroup$
    – kodlu
    Dec 24, 2022 at 22:17
  • $\begingroup$ Added to the body of the question. $\endgroup$
    – FreeTrade
    Dec 25, 2022 at 4:27

2 Answers 2

6
$\begingroup$

A Schnorr Public Key $K$ per the linked BIP340 is 32 bytes representing, in big-endian order, the X coordinates of any point on the Elliptic Curve secp256k1 not the point at infinity. As noted there,

every public key has two corresponding secret keys

namely some integer $d'\in[1,n)$ such that $d'\cdot G$ has X coordinate $K$, and $n-d'$ which also is such that $(n-d')\cdot G$ has X coordinate $K$.

Prefixing $K$ with $\text{02}$ and $\text{03}$ forms two valid ECDSA public keys in compressed form, which respective privates keys form the set $\{d',n-d'\}$, in some order.

$K$ does not correspond to any one of these two keys in particular. Knowing $d'$, we can compute $d'\cdot G$, and the parity of the $Y$ coordinate of the result is the same as the parity of the prefix of the matching public key. In other words, if $(d',K)$ is a valid BIP340 (private, public) key pair, one of $(d',02\mathbin\|G)$ or $(d',03\mathbin\|G)$ is a valid ECDSA key pair, and which can be told knowing $d'$.

When $d'$ is used to sign per BIP340, it first get converted as part of the signing process to $d$ equal to $d'$ or $n-d'$, whichever is such that the Y coordinate of $dG$ is an even integer in $(1,p)$. Thus if $(d',K)$ is a valid BIP340 (private, public) key pair, then $d$, as derived from $d'$ as part of the signing process, is such that $(d,02\mathbin\|K)$ is a valid ECDSA key pair. In that sense the $02$ prefix is preferred.


Notice that the standard security proof of ECDSA (resp. Schnorr) signature assumes the private key is not used for any other purpose than performing an ECDSA (resp. Schnorr) signature, therefore using the same key pair for both systems is not proven safe by these arguments (I'm not stating it's unsafe, only that standard proofs of security are invalidated). Absent more security argument, it would be contrary to good cryptography practices to use the same key for two signature systems. It raises a number of issues

  • can an adversary turn the signature of a known message under one system into the signature of the same message under the other system ?
  • what can an adversary do with the same message independently signed under both systems ?
$\endgroup$
7
  • $\begingroup$ >Prefixing K with 02 and 03 forms two valid ECDSA public keys in compressed form My understanding is that if you generate a ECDSA from a private key, one of these public keys will be preferred in a deterministic way. I assume because one is better than the other in some way. I wish to know if it is possible to know from just the K value which one it is. Appreciate the note about security. $\endgroup$
    – FreeTrade
    Dec 25, 2022 at 15:02
  • $\begingroup$ @FreeTrade: yes if you generate an ECDSA public key from a private key, only one of the two prefix is appropriate, and the answer explains how to determine which: "compute $d\cdot G$ and the parity of the $Y$ coordinate of the result is the same as the parity of the prefix of the matching public key". As explained in the answer, no it's not possible to determine which from $K$: "$K$ does not correspond to any one of these two keys in particular." $\endgroup$
    – fgrieu
    Dec 25, 2022 at 15:33
  • $\begingroup$ Thanks. I think that because one key is preferred over the other, there must be some intrinsic difference between the two, and therefore some test to distinguish between the two must exist. However, because of the security concern you raised, I've decided not to pursue this, so it's a moot point for me now. Thank you for the thoughtful reply. $\endgroup$
    – FreeTrade
    Dec 25, 2022 at 16:12
  • 1
    $\begingroup$ Weirdly, although each public key can be generated with by two secret keys, one of the secret keys cannot be used to generate BIP0340 legitimate signatures as the verification mechanism always expands the public key to a point corresponding to the other private key. If you think that it is reprehensible and dangerous to write specifications in this way, you are not alone. $\endgroup$
    – Daniel S
    Dec 28, 2022 at 22:30
  • 1
    $\begingroup$ @Daniel S: In defense of BIP0340, if we follow it's signature method to the letter, both secret keys $d'$ and $n-d'$ generate legitimate signatures. Admittedly, that's at the expense of having to compute $d'G$ and test the parity of the Y coordinate as part of the signature operation. $\endgroup$
    – fgrieu
    Dec 29, 2022 at 21:00
3
$\begingroup$

TL;DR

0x02 for an unmodified Schnorr signature scheme with typical implicit $y$ coordinates; with BIP0340 one can only convert if one has access to the private key (see fgrieu's answer).

Background

Elliptic curve cryptography schemes over prime fields historically worked with points $(x,y)$ which satisfy the curve equation modulo $p$ and with no other constraints. The Weierstrass equation $y^2=x^3+ax+b$ modulo $p$ for fixed $x$ reduces to a quadratic equation $y^2=C$ for some $C$. If $C\neq 0,\infty$ then there are either 0 or 2 solutions, so that for almost all $x$ values corresponding to a solution there are two possible $y$ values which are negations of each other modulo $p$. To save bandwidth the only the full $x$-coordinates was transmitted together with a prefix to determine which square root to use as $y$.

For some schemes (e.g. ECDH when the shared secret is the $x$-coordinate of the point $aB=bA=abG$) the prefix can even be omitted as both $y$ values would lead to the same answer. In other schemes the multiplicity of possible $y$ values caused issues such as signature malleability. The former phenomenon led to a desire to only communicate using $x$-coordinates and the latter to restricting the choice of $y$ to only one of the two possible values. The two desires are compatible if one uses implicit $y$ coordinates which is the approach taken in BIP0340. This note observes that the implicit choice of which $y$ coordinates to use can be achieved in 3 possible ways:

  1. Choosing $0\le y<p/2$ (recall that the two choices of $y$ coordinate are negations of each other modulo $p$)
  2. Choosing $0\le y<p$ and even (again this choice is permissible and unambiguous due to the negation property)
  3. Choosing $y$ so that $y$ itself is a square (this is only permissible and unambiguous if $p\equiv 3\pmod 4$ which is the case for the secp256k1 characteristic prime).

The writers specifically choose the second option precisely because of compatibility with the existing point compression schemes. This is because it corresponds to the $y$ coordinate obtained when decompressing a point that is prefixed with 0x02. Thus Schnorr public (verification) keys with correct implicit $y$-coordinates can be converted to secp256k1 ECDSA public (verification) keys simply by prepending 0x02. It also means that secp256k1 ECDSA public (verification) keys prefixed by 0x02 can be converted to Schnorr public (verification) keys by dropping the prefix. To convert secp256k1 ECDSA keys that are prefixed with 0x03 to Schnorr keys with correct implicit $y$-coordinates, the choice of $y$ needs to be changed which in turn requires a change of private (signing) key. Fortunately the two choices of $y$ correspond to negations of the private (signing) key modulo $\ell$ (the order of the curve group modulo $p$ and the conversion can be achieved by deleting the 0x03 prefix and changing the private key from the 256-bit value $s$ to the value $\ell-s$.

Alternatively, if a modified signing process such as BIP0340 is used which checks and corrects private (signing) keys with every signature, then the 0x03 can simply be dropped. Likewise if one has a BIP0340 private (signing) key which produces an incorrect implicit $y$ coordinate one can prepend 0x03 to generate an ECDSA key. Note that knowledge of the private key is necessary to do the conversion.

Summary

To convert secp256k1 ECDSA keys to BIP0340 keys and vice-versa:

BIP0340 to ECDSA Find out if the associated private key produces a correct or incorrect implicit $y$-coordinate. If correct prepend 0x02; if incorrect prepend 0x03.

ECDSA to BIP0340 Drop the prefix from the public (verification) key.

Acknowledgement

Apologies and thanks to fgrieu for pointing out the modified signing process in BIP0340

Comments on Security

TO FOLLOW (SPOILER: BEYOND THE USUAL CAVEATS ABOUT REPEATED EPHEMERAL VALUES AND LINEAR DEPENDENCIES BETWEEN SECRET EPHEMERAL VALUES, THERE IS NO EXTRA RISK).

$\endgroup$
1
  • 1
    $\begingroup$ After re-reading BIP0340, indeed it it selects $d$ such that $dG$ has even Y coordinate. But that selection is part of the signing process, not of the key generation process. $\endgroup$
    – fgrieu
    Dec 29, 2022 at 19:31

Your Answer

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

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