[Math] Elliptic Curve Cryptography – why tangent line converted to modular form

cryptographyelliptic-curvesmodular arithmetic

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?

Best Answer

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.

Related Question