|
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? dont use? I read some papers about ecdsa but I didnt read anything about that. Thanks |
|||
|
|
|
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. |
|||
|
