ECDSA Verification - Last Steps

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?

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

• 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$. – TrinityTonic May 22 '17 at 9:27
• 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). – Ruggero May 22 '17 at 10:05
• 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? – TrinityTonic May 22 '17 at 10:31