Cryptography Reference
In-Depth Information
The geometric interpretation of the plus operator is straightforward: the
straight line
PQ
intersects the elliptic curve at a third point
R
=(
x
3
,
y
3
),
and
R
=
P
+
Q
is the reflection of
R
in the
x
-axis. Alternatively speak-
ing, if a straight line intersects the elliptic curve at three points
P, Q, R
,then
P
+
Q
+
R
=0.
−
Consider the elliptic curve defined earlier. Let
P
=(3
,
10) and
Q
=(9
,
7).
Then
P
+
Q
=(
x
3
,y
3
) is computed as follows:
7
−
10
=
−
3
6
=
−
1
2
λ
∈
Z
23
=
=11
9
−
3
=11
2
x
3
−
3
−
9=6
−
3
−
9=
−
6
≡
17 (mod 23)
y
3
=
11(3
−
(
−
6))
−
10 = 11(9)
−
10 = 89
≡
20 (mod 23)
Z
23
).
On the other hand, if we want to add
P
=(3
,
10) to itself, then we have
P
+
P
=2
P
=(
x
3
,y
3
), and this point is computed as follows:
Consequently, we have
P
+
Q
=(17
,
20)
∈
E
(
3(3
2
)+1
20
5
20
=
1
4
=6
λ
=
=
∈
Z
23
=6
2
x
3
−
6=30
≡
7 (mod 23)
y
3
=6 3
−
7)
−
10 =
−
24
−
10 =
−
11
≡
12 (mod 23)
Consequently, 2
P
=(7
,
12), and the procedure can be iterated to compute
arbitrary multiples of point
P
(i.e., 3
P,
4
P,...
).
For every elliptic curve
E
(
Z
p
), the group of points on this particular curve
together with the point in infinity and the addition operation form a group,
30
and this
group can then be used in ECC (see Section 7.6).
3.5
FINAL REMARKS
In this chapter, we overviewed and discussed the aspects of discrete mathematics
that are relevant for contemporary cryptography. Most importantly, we elaborated
on integer arithmetic and modular arithmetic. We also looked at some algorithms
that are frequently used, such as the Euclidean algorithms and the square-and-
multiply algorithm. While we elaborated on modular arithmetic, we also came
30
This result was proven by Henri Poincare in 1901.
