12.7 Elliptic Curve Cryptography
215
0 = x
3
− s
2 x
2
+
a + 2s
2 x A − 2sy 1
x +
b − s
2 x
2
A − y
2
A + 2sx A y A
= (x − x A )(x − x B )(x − x C )
(12.31)
= x
3
− [x A + x B + x C ] x
2
+ [x A x B + x A x C + x B x C ] x − x A x B x C
The second equality is valid, because the third-order equation in the first equality
has three roots—the horizontal coordinates of the points, where the straight line
and the elliptic curve intersect. We already know two of the three roots and can
therefore determine the coefficients from the quadratic term alone. We find x C =
s
2
− x A − x B . Inserting into the equation for the straight line yields the vertical
coordinate of C
. Inverting the sign leads to y C = −s(x C − x A ) − y A . If the two
points A and B are equal with x A = x B and y A = y B we have to replace the slope s
by the derivative s = dy/dx = (3x
2
A + a)/2y A at point A = B. To summarize, we
first have to determine the slope from
s =
y B − y A
x B − x A
for A = B or s =
3x
2
A + a
2y A
for A = B
(12.32)
and then calculate the coordinates of point C from
x C = s
2
− x A − x B
and
y C = −s(x C − x A ) − y A .
(12.33)
In order to visualize this operation, we repeatedly add the same point A, shown as
a red asterisk on the right-hand side in Fig. 12.6, and calculate A 2 = A ⊕ A, A 3 =
A 2 ⊕ A, . . . for hundred iterations. The black dots show that points are scattered all
over the elliptic curve, but not enough to provide the randomness needed for efficient
encryption.
Instead of operating with real numbers when calculating the coordinates of point
C we will use modular arithmetic over a finite field with base p in (12.32) and (12.33).
This will increase the apparent randomness of the “jumping around” dramatically.
We choose p to be a prime number, because this guarantees that multiplying the
Fig. 12.6 Left: Illustrating the method of adding two points “A” and “B” on the elliptic curve to
obtain C = A ⊕ B. Right: if the underlying field are the real numbers, repeatedly adding the same
point, indicated by the red asterisk, jumps to many points on the curve, indicated by black dots
215
0 = x
3
− s
2 x
2
+
a + 2s
2 x A − 2sy 1
x +
b − s
2 x
2
A − y
2
A + 2sx A y A
= (x − x A )(x − x B )(x − x C )
(12.31)
= x
3
− [x A + x B + x C ] x
2
+ [x A x B + x A x C + x B x C ] x − x A x B x C
The second equality is valid, because the third-order equation in the first equality
has three roots—the horizontal coordinates of the points, where the straight line
and the elliptic curve intersect. We already know two of the three roots and can
therefore determine the coefficients from the quadratic term alone. We find x C =
s
2
− x A − x B . Inserting into the equation for the straight line yields the vertical
coordinate of C
. Inverting the sign leads to y C = −s(x C − x A ) − y A . If the two
points A and B are equal with x A = x B and y A = y B we have to replace the slope s
by the derivative s = dy/dx = (3x
2
A + a)/2y A at point A = B. To summarize, we
first have to determine the slope from
s =
y B − y A
x B − x A
for A = B or s =
3x
2
A + a
2y A
for A = B
(12.32)
and then calculate the coordinates of point C from
x C = s
2
− x A − x B
and
y C = −s(x C − x A ) − y A .
(12.33)
In order to visualize this operation, we repeatedly add the same point A, shown as
a red asterisk on the right-hand side in Fig. 12.6, and calculate A 2 = A ⊕ A, A 3 =
A 2 ⊕ A, . . . for hundred iterations. The black dots show that points are scattered all
over the elliptic curve, but not enough to provide the randomness needed for efficient
encryption.
Instead of operating with real numbers when calculating the coordinates of point
C we will use modular arithmetic over a finite field with base p in (12.32) and (12.33).
This will increase the apparent randomness of the “jumping around” dramatically.
We choose p to be a prime number, because this guarantees that multiplying the
Fig. 12.6 Left: Illustrating the method of adding two points “A” and “B” on the elliptic curve to
obtain C = A ⊕ B. Right: if the underlying field are the real numbers, repeatedly adding the same
point, indicated by the red asterisk, jumps to many points on the curve, indicated by black dots