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 am creating some primitive demostration for ECDSA over small curve (p < 229). But my implementation have some weird issues. Verify process return false even if the signature is correct. Because I am testing it for some time, trying to find problem I discovered that verify work only if point order is prime.

So my question is, is there some condition for point order? And what about point with non prime order? Don't use?

I have been reading some papers about ECDSA, but I didn' t find anything about that.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Without more details, I can't be certain what's going on with your implementation. However, here is one thing that can certainly cause it to fail sometimes if $n$ is composite: the ECDSA verifier needs to compute $s^{-1} \bmod n$ (where $s$ is effectively a random number between 1 and $n-1$). If $n$ is composite, then $s$ might not be relatively prime to $n$; if it is not, then $s^{-1}$ won't exist (because there's no number $t$ such that $s \cdot t = 1 \mod n$). If this happens during the verification, then either your modular inversion routine (which computes $s^{-1} \bmod n$) will fail, or it will claim to succeed, and return some incorrect value (which will cause later calculations to fail).

If the order of your generator is composite, you'll run into a second problem; it'll be easier to break. ECDSA can be broken if you can solve the 'discrete log' problem; that is, given the generator $G$ and a point $Q$, you can compute the value $d$ such that $Q = dG$. Now, if the order of the generator $G$ is composite (say, $pq$), then an attacker could compute $pG$, $qG$, $pQ$, $qQ$, and solve these two discrete log problems $pQ = d_p(pG)$ and $qQ = d_q(qG)$, and given the values $d_p, d_q$, reconstruct $d$. Solving these two discrete log problems would be considerably easier than solving the single discrete log problem (because the orders of the points involved are smaller); and hence we've just made things easier for the attacker.

Because generators with composite order can cause the verify to fail, and because they're cryptographically weaker, we always use generators with prime order.

share|improve this answer
    
Thanks for the answer. As I mentioned before, it is for education purpose so security is not really issue. So I can simple remove points with composite order, and use only with prime ones. I did not know if it could be correct "solution" :) –  eXPi May 24 '12 at 16:49

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.