Score:1

In ECDSA over K256, Why R.x should be less than the subgroup order, not field order? But in BIP340 over K256, should be less than field order

vn flag

I understand that R.x is a field element.

I don't understand why in ECDSA verification ie. FIPS 186-5 section 6.4.2 step 1, we check whether r is less than subgroup order.

If it has something to do with the curve (what?), then why in BIP340 Verification step 2 do we check whether r is less than the field order?

Score:2
my flag

Well, it has to do with the corresponding signature generation algorithms.

With the ECDSA signature algorithm (FIPS 186-5 section 6.4.1, step 8), it makes sure that $r$ is in the range $[0, n)$ (by taking the $x$ coordinate modulo $n$). Hence, any time you see a signature with an $r$ value outside that range, it was obviously not generated by the correct signature algorithm, and so can safely be rejected. I believe NIST left that modulo operation there in part because the original DSA algorithm had a modulo there as well, even though (in practice) the modulo operation leaves $n$ unaffected almost all the time (because with a cofactor 1 curve, $p \approx n$ rather closely).

The BIP340 signature algorithm (listed as the "Default Signing Algorithm") lacks such a modulo operation; hence its value of $r$ will still be in the range $[0, p)$

Score:2
ng flag

Why we check whether $r$ is less than subgroup order

In ECDSA, $r$ is reduced modulo the subgroup order $n$ when it is used at signature verification: sec1v2 §4.1.4 step 4 in the computation of $u_2=r\,s^{-1}\bmod n$. The check that $r<n$ thus insures that a signature can't be turned into another acceptable signature for the same message by replaving $r$ by $r+n$. In DSA signature verification, which has the same test, that test makes DSA strongly EUF-CMA (that is an adversary can't produce any new signature that passes verification). In ECDSA (which derives from DSA) the test was kept, but it's not quite enough‡ to make ECDSA sEUF-CMA because $(r,n-s)$ is a valid signature for the same message as $(r,s)$. The test $r<n$ still has a possible rationale: it insures that there is no special case in the computation $u_2=r\,s^{-1}\bmod n$. At least, that test does not harm, for the standard prescribes a reduction modulo $n$ at an earlier step in signature production: sec1v2 §4.1.3 step 3. In curve secp256k1, $p>n$, and this reduction changes $r$ for many points (yet such a tiny proportion that in practice it can't happen by chance). There even exist two points such that this reduction modulo $n$ turns the $x$ coordinate to $0$, and there's a test to catch that.

In the BIP340 variant of Schnorr signature, $r$ is the $x$ coordinate of a point on the elliptic curve, and the input of a hash (both on signature production and verification). Thus there is no reason to reduce it modulo $n$, and it's not. There is thus no reason to check that $r<n$, and with $p>n$ such test would make some signatures invalid. Instead it's only checked that $r<p$.


‡ Perhaps it's an oversight. At least that loss of a security property was not made clear when ECDSA was introduced. And it would have been quite easy to avoid that pitfall, which has been a concern in some applications including Bitcoin.

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.