1
$\begingroup$

So I need to write a piece for school about ECDSA and how it is secure. Now I thought I had a simple question, however, I can't seem to find an answer anywhere:

Why does the p in the formula need to be a prime number?

Now I understand how you can only have modular inverses of prime numbers, and I thought maybe that had something to do with it, but I can't see how though.

This is the site where I found the formula from the ECDSA algorithm: https://andrea.corbellini.name/2015/05/23/elliptic-curve-cryptography-finite-fields-and-discrete-logarithms/

Site with encryption forumulas

$\endgroup$
  • 3
    $\begingroup$ fgrieu gives the correct answer to your question; my meta-answer would be that, for an intro paper on ECDSA, you needn't go into the details of how you add two elliptic curve points. Instead of giving into those gory details, you can just assume the existing of EC points and EC addition and EC point multiplication (with certain properties, such as multiplying a point by an integer is easy, but computing the inverse (discrete log) is difficult), and work on the ECDSA algorithm from there... $\endgroup$ – poncho Feb 27 at 15:35
2
$\begingroup$

Why does $p$ need to be a prime number?

That's necessary for arithmetic modulo $p$ to be a field. For non-prime modulo, we only get a ring.

That's important because we want to compute modular multiplicative inverses, and need a field for that to work consistently.

More specifically: if $q$ is such that $0<q<p$ and $\gcd(p,q)\ne1$ (which is possible when $p$ is not prime), then there exists no $r$ with $q\,r\equiv1\pmod p$, that is $q$ has no multiplicative inverse. This would invalidate formulas with the term $(x_P-x_Q)^{-1}\bmod p$ when $\gcd(p,x_P-x_Q)\ne1$, as used when performing point addition. With $p$ prime, that can only occur for $x_P\equiv x_Q\pmod p$, which can be handled as a special case in point addition.

you can only have modular inverses of prime numbers

Uh, no. Counterexamples abound. Say $1$, which is not prime, and is its own modular inverse; and $4$, which is not prime, and has modular inverse $7$ modulo $9$, since $4\times7=3\times9+1$.

Correct formulation: reliable modular inversion requires prime modulus.

More precisely: all integers from $1$ to one less than the modulus have a multiplicative modular inverse if and only if the modulus is prime.


Note: for different (security) reasons, the number $n$ of points on the curve (including the neutral, also known as the point at infinity) needs to be a prime too (as it is in ECDSA), or at least to have a large prime factor.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Why is it important for arithmetic modulo p to be a field? $\endgroup$ – Sander Honig Feb 27 at 15:42
  • 2
    $\begingroup$ Another potentially useful point, we actually use the failure to come up with inversions for EC operations as a way to factor numbers. $\endgroup$ – SEJPM Feb 27 at 15:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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