Cryptography Reference
In-Depth Information
Step
#0
P
=
1
2
P
inital setting, bit processed:
d
4
= 1
#1
aP
+
P
= 2
P
=
10
2
P
DOUBLE, bit processed:
d
3
#1
b
2
P
+
P
= 3
P
= 10
2
P
+ 1
2
P
=
11
2
P
ADD, since
d
3
= 1
#2
a
3
P
+ 3
P
= 6
P
= 2(11
2
P
)=
110
2
P
DOUBLE, bit processed:
d
2
#2
b
no ADD, since
d
2
= 0
#3
a
6
P
+ 6
P
= 12
P
= 2(110
2
P
)=
1100
2
P
DOUBLE, bit processed:
d
1
#3
b
12
P
+
P
= 13
P
= 1100
2
P
+ 1
2
P
=
1101
2
P
ADD, since
d
1
= 1
#4
a
13
P
+ 13
P
= 26
P
= 2(1101
2
P
)=
11010
2
P
DOUBLE, bit processed:
d
0
#4
b
no ADD, since
d
0
= 0
It is instructive to observe how the binary representation of the exponent evolves.
We see that doubling results in a left shift of the scalar, with a 0 put in the rightmost
position. By performing addition with
P
, a 1 is inserted into the rightmost posi-
tion of the scalar. Compare how the highlighted exponents change from iteration to
iteration.
If we go back to elliptic curves over the real numbers, there is a nice geometric
interpretation for the ECDLP: given a starting point
P
, we compute 2
P
,3
P
,
...
,
dP
=
T
, effectively hopping back and forth on the elliptic curve. We then publish
the starting point
P
(a public parameter) and the final point
T
(the public key). In
order to break the cryptosystem, an attacker has to figure out how often we “jumped”
on the elliptic curve. The number of hops is the secret
d
, the private key.
9.3 Diffie-Hellman Key Exchange with Elliptic Curves
In complete analogy to the conventional Diffie-Hellman key exchange (DHKE) in-
troduced in Sect. 8.1, we can now realize a key exchange using elliptic curves. This
is referred to as elliptic curve Diffie-Hellman key exchange, or ECDH. First we
have to agree on domain parameters, that is, a suitable elliptic curve over which we
can work and a primitive element on this curve.
