Score:2

Why is r used in ECDSA signature while R in Schnorr signature?

br flag

In Schnorr signature (R, s), R is used. But in ECDSA signature (r, s), r is used, which is the x-coordinate of R. Why the difference?

kelalaka avatar
in flag
Patent of the Schnorr!
br flag
ECDSA cannot use R due to the patent?
Score:4
ng flag

In Schnorr signature $(R,s)$, $R$ is used. But in ECDSA signature $(r,s)$, $r$ is used, which is the x-coordinate of $R$.

That assertion is technically incorrect:

  • In Schnorr signature (alt.) as originally defined, the first component of the signature is a hash, not a group element, much less a “point” on an Elliptic Curve group, which use in cryptography was not common.
  • In the definition of the ECDSA signature, the first component $r$ of the signature is the x-coordinate $x_R$ of a point on an Elliptic Curve, turned into an integer, then reduced modulo the group order $n$ (then turned to a bytestring, but we'll leave that aside); it's not just $x_R$.

However, the meat of that assertion stands with a few adaptations:

  • Modern textbook Schnorr signature is defined for an arbitrary group where the Discrete Logarithm Problem is hard, with two main variants according to if the first component of the signature is
    • A hash of (at least) the message and a group element $R$, as in the original Schnorr signature.
    • A (unique bit representation of a) group element $R$, as in e.g. EdDSA. That's the variant the assertion applies to.
  • Said group is commonly an Elliptic Curve subgroup of prime order $n$ of an Elliptic Curve on a field $\mathbb F_{p^m}$, and commonly $m=1$, thus the x-coordinate $x_R$ of $R$ is an integer in $[0,p)$.
  • For common such curves $n\approx p$, thus with $r:=x_R\bmod n$ it holds $r=x_R$ with high probability even when $n<p$ (e.g. secp256k1, secp256r1), or we can choose an Elliptic Curve with $n>p$.

Now that we have a true assertion, we can ask:

Why the difference?

Because ECDSA is an adaptation to Elliptic Curve group of DSA, where the first component of the signature is a group element reduced modulo the prime order of the group. In DSA, that reduction was in order to shorten the first component of the signature. Reasons why DSA use that technique rather than the hash, as in the original Schnorr signature, may be

  • The original Schnorr signature was covered by a patent, including in the USA, and there was thus an interest in a different method¹.
  • DSA was closer to the already well studied ElGamal signature.
  • The original Schnorr signature, due to its narrow $k$-bit hash (and contrary to modern Schnorr signature with a wider hash, in both variants above):
    • Is not safely usable as a commitment of the message signed: the holder of a private key signing a message and able to chose it in part (e.g. alter a few bytes in the end) can deliberately do so in a way such that another message with another meaning of their choice has the same signature. The attack is a chosen-prefixes collision attack on the $k$-bit hash, of expected cost less than $2^{k/2+1.4}$ hashes. This increases the risk of signature repudiation, and legitimately can cause Fear, Uncertainty and Doubt.
    • Would be vulnerable to an hypothetical (first or second) preimage attack on the message input of the hash, including for hashes among a thin subset of $\{0,1\}^k$, of expected cost $2^k$ hashes; when DSA (thanks to it's much wider hash) has a lot of margin on that.

DSA uses a Schnorr group, that is a cyclic subgroup of the multiplicative group modulo a prime $p$. ECDSA essentially changes that to an Elliptic Curve group over a Galois field, which allows smaller public key and faster computation. DSA's principle of reducing the first component of the signature modulo the group order is kept. The necessary pre-conversion from field element to integer is made by the x-coordinate $x_R$, ignoring $y_R$. Incidentally, that leads to loss of a security property: ECDSA is not sEUF-CMA, when DSA is, because $R$ and the opposite of $R$ in the Elliptic Curve group share the same $x_R$, allowing to turn a valid ECDSA signature into a different valid signature for the same message by changing $s$ to $-s$ modulo the group order.


¹ Claus-Peter Schnorr asserted DSA's method fells under his patent. That never went to the test of court. While much of DSA can be read in the patent's description, claiming infringement would have been impossible with the claims as they are, and an uphill battle with rewritten claims. In particular, it's described a hash with an input beside the message, when only the message is hashed in DSA.

br flag
So technically, ECDSA could also use (R, s) as signature?
fgrieu avatar
ng flag
@sinoTrinity: yes, we could slightly modify ECDSA to have a binary representation of $R$ as the first component of the signature, and have the verifier turn that into an integer then used modulo $n$. It seems that could restore sEUF-CMA [ but would do so by increasing signature size by at least 1 bit, rather than reducing it by 1 bit as does replacing $s$ by $\min(s,n-s)$ ]. And that still would not be any of the two forms of EC-Schnorr signature, since only the message enters ECDSA's hash, rather than message and point in EC-Schnorr signature (all variants).
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.