Why is a modulus used in Elliptic Curve Cryptography?

Question

In the eliptic curve cryptography, we use modulus $y^2 = (x^3 + ax + b) \ \ \text{mod} \ \ p$

So using modulus definitely changes the graph points completely - i.e gives a completely different graph than $y^2 = x^3 + ax + b$ would give.

What's the easy explanation of why we use modulus ? In Diffie-Hellman, I understand that we needed to get to discrete log so attackers would have hard time cracking it, but in elliptic curve, if Alice does $nG = Q$, where $n$ is her secret key and G generator, if attacker intercepts G and Q, would he be able to crack $n$ ? Note that we assume we don't use modulus. If not be able to crack it, then why do we use it ? and if attacker would crack it, how ? $nG$ is point addition/doubling on curve.

Answer 1

If one uses the fields $\mathbb R$ or $\mathbb C$ for the coordinates of the base point and curve coefficients then there is no exact representation of the point and we are not assured that the two computations $\mathrm{approx}(a\cdot\mathrm{approx}(b\cdot G))$ and $\mathrm{approx}(b\cdot\mathrm{approx}(a\cdot G))$ will give the same answer.

If one uses the field $\mathbb Q$ (or a finite extension thereof) then the coordinates can be exactly represented and the shared value can be consistently computed by both sides. However when working over $\mathbb Q$ the "distance" between two points i.e. the discrete logarithm in the elliptic curve group can be approximated. This is due to the Neron-Tate result on logarithmic height see e.g. section 2.4 of this paper. We define the logarithmic height $h(P)$ of a point $P$ with $x$-coordinate $a/b$ to be $\log\max(|a|,|b|)$. Then for most points $P$ and large $n$ we have $h(nP)/h(P)\approx 2n^2$. This allows us to compute a very good approximation to $n$ which we can then recover exactly with very few baby-step-giant-step iterations.

Answer 2

The question "why include the modulo operator" sounds potentially independent of the question "why restrict to integer values".

When operating in $\mathbb R$, very few integer points are encountered on an elliptic curve. The underlying difference is that division in a finite field always yields another integer, whereas it rarely does in $\mathbb R$. Obtaining exclusively bounded integer values (as in a finite field) is a boon for cryptography applications, as any point can be represented exactly using a fixed number of bits. Nonetheless, rational points on elliptic curves are their own topic of study and relate to Diophantine equations.

Answer 3

Suppose that Elliptic Curve Diffie Hellman will be used to exchange keys. Private key of Alice is ka, private key of bob is kb and the public base point is G. Alice calculates her public key as ka x G, and Bob calculates his public key as kb x G. Thereafter, each party share their public key to each other. Finally, Alice will calculate Bob's public key times her private key, and Bob will calculate Alice's public key times his private key. Long story short, Alice will have ka x (kb x G) and Bob will have kb x (ka x G).

Herein, if you are using the point addition or doubling formulas of elliptic curves to calculate kb x (ka x G) and ka x (kb x G) then both parties will not have same results because of rounding. Notice that programming languages tend to round the fractional calculations. On the other hand, if you calculate point addition & doubling on finite fields, then both parties will have same results.