Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
1  
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
3  
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
add comment

1 Answer

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$

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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