0
$\begingroup$

Reaching the end of an ECDSA signature verification, we need to compute multiple point multiplication and addition as following: $R=(x_R, y_R) = u_1G + u_2Q$, where $u_1$ and $u_2$ are scalars, $G$ is the curve generator and $Q$ is the public key point. As we're using elliptic curve operations we're computing our curve operations $\mod q$, with $q$ being the field order.

If $R$ is a valid point on the curve and $R \neq\infty$, we need to compute $x_R\mod n$, with $n$ representing the order of the generator, and compare that to the $r$-part of the signature. Why do we need another reduction $\mod q$ if we have already reduced $\mod n$ after the multiplication part?

$\endgroup$
2
$\begingroup$

There are two different primes being used here.

Using your notation, $q$ should be the prime defining the field $\mathbb{F}_q$ over which the curve is defined.

$n$, instead, indicates the (prime) order of your generator $G$.

The coordinates of points, and therefore the computations of scalar multiplications and point addition, are done in $\mathbb{F}_q$.

So, your point $R$ will have coordinates $\bmod q$. But you still need to apply the modular reduction with respect to $n$ to $x_R$ in order to make verification work. This is because the $r$-part of the signature is also computed $\bmod n$ and $n$ is allowed to be smaller than $q$.

$\endgroup$
  • $\begingroup$ Thanks, yea that's what I thought. I was unsure because I had used OpenSSL to create a "great" number of testvectors and they all seemed to work without the last reduction $\mod n$. But apparently all the curves that I had been using had $n > q$. $\endgroup$ – TrinityTonic May 22 '17 at 9:27
  • $\begingroup$ Actually most standardized curves have $n < q$. The fact is that $n$ and $q$ are so close that random tests will rarely trigger the need of that reduction (see Hasse's Theorem for details here: en.wikipedia.org/wiki/Hasse%27s_theorem_on_elliptic_curves). $\endgroup$ – Ruggero May 22 '17 at 10:05
  • $\begingroup$ Hm, yup I checked. I had mostly used brainpoolP curves (256r1, 384r1, 512r1) and all of those actually had $n < q$. They start differing at approximately half the bit-size, e.g. after around 128 bits for the 256-bit curve. Would you say that's close? $\endgroup$ – TrinityTonic May 22 '17 at 10:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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