1
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Where do you get $n$ from? What do you get when you compute $nG$? $\endgroup$
    – fgrieu ♦
    Commented Jun 4, 2013 at 5:28
  • $\begingroup$ Are you using bigintegers? With double you'll get loss of precision, with small integers you get overflows. $\endgroup$
    – CodesInChaos
    Commented Jun 4, 2013 at 6:57
  • 3
    $\begingroup$ 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. $\endgroup$
    – CodesInChaos
    Commented Jun 4, 2013 at 6:58
  • $\begingroup$ 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. $\endgroup$
    – Peter Butler
    Commented Jun 4, 2013 at 15:05

1 Answer 1

Reset to default
2
$\begingroup$

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$

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Peter Butler
    Commented Jun 4, 2013 at 17:08
  • $\begingroup$ 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. $\endgroup$
    – Peter Butler
    Commented Jun 4, 2013 at 17:20
  • $\begingroup$ @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. $\endgroup$
    – poncho
    Commented Jun 4, 2013 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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