# ECC Point Multiplication of Product

I can calculate $Q = a\,b\,G$ in several ways: $Q = a \, (b \, G)$ or $Q = b \, (a \, G)$. These give the same result, as expected.

But if I do $c = (a \, b) \bmod n$ where $a \, b$ is much greater than $n$, then $Q = c \, G$, I get a different point.

Should I have expected this? Or does this difference indicate a problem in my code?

-
Where do you get $n$ from? What do you get when you compute $nG$? – fgrieu Jun 4 '13 at 5:28
Are you using bigintegers? With double you'll get loss of precision, with small integers you get overflows. – CodesInChaos Jun 4 '13 at 6:57
What are you using for n? The order of the curve? Or the modulus of the prime field? Scalars need to be reduced modulo the order. – CodesInChaos Jun 4 '13 at 6:58
My elliptic curve cryptography is implemented for ARM Cortex-M3/M4 processors. I have only implemented NIST p-256. The n in my post is its eponymous prime and G is its generator point. (I assume G stands for generator.) My point multiply is a simple double and add using Jacobian coordinates. FWIW on an 168 MHz Cortex-M4 (STM32 F4 Discovery if anyone cares) my point multiply averages ~25 milliseconds. – Peter Butler Jun 4 '13 at 15:05

To answer your question: it's expected, because you're using the wrong modulus.

CodesInChaos pretty much gave you the correct answer; I'll try to explain in more detail about what's actually going on.

We can define an elliptic curve based on any finite field $GF(p^k)$; in the case of P=256, we have p=FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF (in hex), and k=1.

The points on the elliptic curve are actually solutions to a specific cubic equation within the field (plus an artificial "point at infinity"); these solutions, plus a specific point addition operator +, form a finite mathematical group.

A mathematical group is set along with an operator for which certain identies always hold, such as $(A+B)+C = A+(B+C)$, for any group members $A, B, C$.

Because of these identities, we can uniquely define point multiplication $nG$ as the point $G$ added to itself $n$ times (for example, $5G$ is defined as $G+G+G+G+G$). And, we have the property $a(bG) = b(aG) = (ab)G$, as you have observed.

Now, for any finite group, if the group has $q$ members (that is, the set that makes up the elements of the group is of size $q$), when we know that $ab \equiv c \ (\bmod\ q)$ implies that $abG = cG$, for any group member $G$.

This value $q$ is known as the order of the curve. However, $q$ is not the value $p$ we used above; instead, for the curve P-256, it is the value q=FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551 (in hex).

That is, if you compute $c = ab \bmod q$ for that value of $q$, you'll find that $abG = cG$

-
Wow. Thank you. c=(ab) % q is not for needed ECDSA. But now that I know about % q I can focus better looking for the bug(s) in my ECDSA implementation. – Peter Butler Jun 4 '13 at 17:08
It’s interesting that q<n. Am I correct that all a<n have a square root % n? This would imply aG = bG does not necessarily imply that a = b. – Peter Butler Jun 4 '13 at 17:20
@PeterButler: Well, $q<n$ for this specific elliptic curve; there are other curves with $q>n$. Also, it is not at all true that all $a<n$ have a square root modulo n (that is, are quadratic residues mod n). In fact, exactly half the integers between 1 and n-1 are quadratic residues and half are not (because n is prime). Finally, q is prime (there are lots of curves that have a composite q; we pick one with a prime q because they have better cryptographic properties); hence $aG=bG$ implies either $a\equiv b (\bmod q)$ or $G$ is the point at infinity. – poncho Jun 4 '13 at 18:09