Cryptography Reference
In-Depth Information
Theorem 9.2.1
The points on an elliptic curve together with
O
have cyclic subgroups. Under certain conditions
all
points on an
elliptic curve form a cyclic group.
Please note that we have not proved the theorem. This theorem is extremely use-
ful because we have a good understanding of the properties of cyclic groups. In
particular, we know that by definition a primitive element must exist such that its
powers generate the entire group. Moreover, we know quite well how to build cryp-
tosystems from cyclic groups. Here is an example for the cyclic group of an elliptic
curve.
Example 9.5.
We want to find all points on the curve:
E
:
y
2
x
3
+ 2
≡
·
x
+ 2 mod 17
.
It happens that all points on the curve form a cyclic group and that the order is
#
E
= 19. For this specific curve the group order is a prime and, according to Theo-
rem 8.2.4, every element is primitive.
As in the previous example we start with the primitive element
P
=(5
,
1).We
compute now all “powers” of
P
. More precisely, since the group operation is addi-
tion, we compute
P
,
2
P
,...,
(#
E
)
P
. Here is a list of the elements that we obtain:
2
P
=(5
,
1)+(5
,
1)=(6
,
3)
11
P
=(13
,
10)
3
P
= 2
P
+
P
=(10
,
6)
12
P
=(0
,
11)
4
P
=(3
,
1)
13
P
=(16
,
4)
5
P
=(9
,
16)
14
P
=(9
,
1)
6
P
=(16
,
13)
15
P
=(3
,
16)
7
P
=(0
,
6)
16
P
=(10
,
11)
8
P
=(13
,
7)
17
P
=(6
,
14)
=(7
,
6)
18
P
=(5
,
16)
9
P
10
P
=(7
,
11)
19
P
=
O
From now on, the cyclic structure becomes visible since:
20
P
= 19
P
+
P
=
O
+
P
=
P
21
P
= 2
P
.
It is also instructive to look at the last computation above, which yielded:
18
P
+
P
=
O
.
This means that
P
=(5
,
1) is the inverse of 18
P
=(5
,
16), and vice versa. This is
easy to verify. We have to check whether the two
x
coordinates are identical and
that the two
y
coordinates are each other's additive inverse modulo 17. The first
