1
$\begingroup$

I'm trying to understand the basics for elliptic curve cryptography. From my understanding, going from the generator point $G$ to $2G$ requires taking the line tangent at point $G$, finding the intersection to the curve, and then reflecting over the x-axis.

I'm going through this example. I'll write it out here also:

The elliptic curve is:

$$y^2 \equiv x^3 + 2x + 2\ (\bmod 17\ )$$

$$G = (5,1)$$

So the gradient can be computed using implicit differentiation. I understand why it is defined as being:

$$s = \frac{3x_G^2 + a}{2y_G}$$

Here, this would be:

$$s \equiv \frac{3(5^2) + 2}{2(1)} $$

Therefore I would think the slope tangent to the graph at the generator point is $38.5$, but the lecturer converts this to being $13\ (\bmod 17\ )$ using the extended Euclidean algorithm. But the slope of the line tangent to the graph is actually $38.5$. Plotting with a slope of 38.5 is shown below:

enter image description here

So I'm curious why they use $13$ instead of $38.5$ if the latter is the slope tangent to the graph?

$\endgroup$
2
  • 2
    $\begingroup$ We have $26\equiv 77\pmod{17}$. Because $\gcd(2,17)=1$ we can divide this congruence by $2$, and arrive at $$13=\frac{26}2\equiv\frac{77}2=38\frac12.$$ In other words, when you do algebra modulo $17$ (or rather, geometry over the field $\Bbb{Z}/17\Bbb{Z}$) you should no longer entirely rely on pictures representing things over the real numbers. Yet in other words, for the purposes of finding other points on the tangent line the two values of the slope (that are actually the same value in the field you are working with!) lead to the same points of intersection and the same point doubling. $\endgroup$
    – Jyrki Lahtonen
    Commented Jul 16, 2017 at 8:06
  • $\begingroup$ @JyrkiLahtonen thank you! Can you please elaborate on how the two values of the slope lead to the same points of intersection? How would $38.5$ and $13$ both give you the same points of intersection? $\endgroup$
    – rb612
    Commented Jul 16, 2017 at 19:08

1 Answer 1

Reset to default
3
$\begingroup$

We are working over finite fields, so there is no notion of slope like in curves over the reals (the pictures involve limit processes, which make no sense over a finite (discrete) space). What is happening here, is we are treating the EC like it over $\mathbb{R}$, and deriving a formula for the slope, and from this a formula for $2X$ for a point $X$. Then we interpret this formula in the finite field we are actually working in, because that's our realm of computation. It turns out that this gives the correct doubling formula over finite fields.

So the interpretation was geometrical then turned into pure algebra that works over all suitable fields.

$\endgroup$
2
  • $\begingroup$ Ah thank you. So would you please explain a high level overview of how the geometric interpretation, involving the implicit differentiation, relates to the pure algebra interpretation? It seems like we deviate completely away from the notion of the tangent line while working in this finite field. $\endgroup$
    – rb612
    Commented Jul 16, 2017 at 19:13
  • 1
    $\begingroup$ It doesn't matter how we derive the formulae, they can be checked to work after we find them, i.e. that we get a valid group structure only depends on the definition, not how we find the group fomulae. The point is to have a finite group with supposedly hard discrete log problem. Tangent lines are besides the point. They're only motivation, not a proof of the group structure, so that the doubling formula does not appear "out of the blue", so for didactic reasons. $\endgroup$
    – Henno Brandsma
    Commented Jul 16, 2017 at 19:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .