3
$\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$
1
  • 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, 2020 at 15:35

2 Answers 2

4
$\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.

$\endgroup$
2
  • $\begingroup$ Why is it important for arithmetic modulo p to be a field? $\endgroup$ Feb 27, 2020 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, 2020 at 15:45
0
$\begingroup$

Here's a simplified explanation:

As fgrieu noted, calculating multiplicative modular inverses is necessary for elliptical cryptography calculations. Paraphrasing Schneier's "Applied Cryptography" p.246:

Finding the multiplicative inverse requires finding an x such that 1= a*x mod n. So for instance, the inverse of 5 mod 14 is 3, because when a = 5 and n = 14, we can see that 5 × 3 = 15, which leaves us a remainder/residue of 1 when we modularly reduce 15 mod 14, because 15 is 1 more than 14.

But since 14 is not prime, there is not a multiplicative inverse if a = 2 and n = 14, because there is no integer x that will give us a solution to 1 = 2*x mod 14.

Conversely, if n is prime, then for every integer between 1 and n (i.e. 1 to n-1), there exists exactly one modular multiplicative inverse.

If n were not prime, you'd have instances like the example above where n = 14 where there would be no solution to the modular multiplicative inverse problem. The field over which the elliptical curve is drawn is not over the normal set of integers we're accustomed to, but is instead a set of numbers bound by a prime number. However, in order for a field to be valid, operations performed within it need to behave in a way that corresponds to regular numbers. Thus, with regular numbers, every number has a multiplicative inverse, but with modular arithmetic, a number is only guaranteed to have a multiplicative inverse if it is prime (as shown above). Thus, since elliptical curves are plotted using modular arithmetic (e.g. Bitcoin's secp256k1 is y^2 mod p = (x^3 + 7) mod p where p is a very large prime number which is defined as a constant beforehand), elliptical curve cryptography requires the p to be a prime number because the modular arithmetic underlying the elliptical curve requires p to be prime in order to have valid solutions for every conceivable number one might plot.

So if p weren't prime, but instead nearly prime, elliptical curve cryptography might actually "work" for most keys, but would fail miserably for others. Since we want elliptical curve cryptography to work consistently in every case, a prime number (which will guarantee a solution to the modular multiplicative inverse problem in every case) is chosen.

$\endgroup$
1
  • $\begingroup$ FYI we have $\LaTeX$ / MathJax in our site. $\endgroup$
    – kelalaka
    Feb 9, 2022 at 19:15

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.