3
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Where do you want to define the curve in $\mathbb R$ or $\mathbb C$? In cryptography, it is easy to work with $\mathbb Z_p$ since there is no floating point ssues. $\endgroup$
    – kelalaka
    Mar 5 at 14:11
  • $\begingroup$ so basically, if we don't do modulus, values of y can also be floating points and public key(i.e nG) could end up a floating point ? That's the only reason right ? it doesn't have anything to do with avoiding attacks ? $\endgroup$ Mar 5 at 14:15
  • 1
    $\begingroup$ $y^2 = (x^3 + 7 )$% $5$ - this still gives "y" values to be floating. i.e when x = 0, $y^2 = 2$ and $y = \sqrt{2}$ $\endgroup$ Mar 5 at 14:18
  • $\begingroup$ Or, generally Finite GaloisField. Your modulus is $5$. Also, Curve's over $\mathbb C$ in general doesn't form a cyclic structure so solving Dlog is easiers. $\endgroup$
    – kelalaka
    Mar 5 at 14:28
  • 1
    $\begingroup$ @GiorgiLagidze There is no square root of 2 in $\mathbb{Z}_5$, the same way there is no square root of -2 in $\mathbb{R}$. There is no point with x = 0 on the curve you defined, just as there is no point with x = 0 on the curve of y^2 = x - 1 over the reals $\endgroup$ Mar 5 at 23:06

3 Answers 3

7
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ If both parties are using the same programming language/architecture, then for sure, they would end up with the same results, correct ? and if so, everything would be great(even attacks would be "impossible"). correct ? just asking so i understand it fully $\endgroup$ Mar 5 at 16:13
  • 1
    $\begingroup$ @GiorgiLagidze: no, the problem pointed in the answer is not programming language/architecture, it's using floating point, which addition is not associative. But that's only one reason not to use reals and floating point. $\endgroup$
    – fgrieu
    Mar 5 at 16:35
  • $\begingroup$ I get that, but why are you saying that alice and bob will end up with different results ? how can these two kb x (ka x G) and ka x (kb x G) yield different results ? $\endgroup$ Mar 5 at 16:55
  • 1
    $\begingroup$ The Intel x86 has two ways to handle floating point numbers: the historical x87 unit (which internally uses 80-bit numbers) and SSE-based instructions (which use max 64-bit numbers). Also you may be using different libraries (even for the same compiler), which may also affect results. $\endgroup$ Mar 5 at 22:33
  • $\begingroup$ @GiorgiLagidze: it's a basic property of floating point addition that for some floating point numbers A B C, (A+B)+C is not equal to A+(B+C), even if the same kind of floating point representation (e.g. 64-bit IEEE 754) is used, and no exception is raised. Again that's one (and not the main) reason not to use reals and floating point. $\endgroup$
    – fgrieu
    Mar 6 at 8:22

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.