Cryptography Reference
In-Depth Information
condition obviously hold and the second one too, since
−
1
≡
16 mod 17
.
To set up DL cryptosystems it is important to know the order of the group. Even
though knowing the exact number of points on a curve is an elaborate task, we know
the approximate number due to
Hasse's theorem
.
Theorem 9.2.2
Hasse's theorem
Given an elliptic curve E modulo p, the number of points on the
curve is denoted by
#
E and is bounded by:
2
√
p
p
+ 1 + 2
√
p
.
p
+ 1
−
≤
#
E
≤
Hasse's theorem, which is also known as
Hasse's bound
, states that the number of
points is roughly in the range of the prime
p
. This has major practical implications.
For instance, if we need an elliptic curve with 2
160
elements, we have to use a prime
of length of about 160 bit.
Let's now turn our attention to the details of setting up the discrete logarithm
problem. For this, we can strictly proceed as described in Chapter 8.
Definition 9.2.1
Elliptic
Curved
Discrete
Logarithm
Problem
(ECDLP)
Given is an elliptic curve E. We consider a primitive element P
and another element T . The DL problem is finding the integer d,
where
1
≤
d
≤
#
E, such that:
P
+
P
+
···
+
P
=
dP
=
T
.
(9.2)
dtimes
In cryptosystems,
d
is the private key which is an integer, while the public key
T
is a point on the curve with coordinates
T
=(
x
T
,
y
T
). In contrast, in the case of
the DL problem in
Z
p
, both keys were integers. The operation in Eq. (9.2) is called
point multiplication
, since we can formally write
T
=
dP
. This terminology can be
misleading, however, since we cannot directly multiply the integer
d
with a curve
point
P
. Instead,
dP
is merely a convenient notation for the repeated application of
the group operation in Equation (9.2).
3
Let's now look at an example for an ECDLP.
Example 9.6.
We perform a point multiplication on the curve
y
2
x
3
+ 2
x
+ 2mod
17 that was also used in the previous example. We want to compute
≡
3
Note that the symbol “+” was chosen arbitrarily to denote the group operation. If we had chosen
a multiplicative notation instead, the ECDLP would have had the form
P
d
=
T
, which would have
been more consistent with the conventional DL problem in
Z
p
.
