Cryptography Reference
In-Depth Information
ECDH Domain Parameters
1. Choose a prime
p
and the elliptic curve
E
:
y
2
x
3
+
a
≡
·
x
+
b
mod
p
2. Choose a primitive element
P
=(
x
P
,
y
P
)
The prime
p
, the curve given by its coefficients
a
,
b
, and the primitive ele-
ment
P
are the domain parameters.
Note that in practice finding a suitable elliptic curve is a relatively difficult task.
The curves have to show certain properties in order to be secure. More about this
is said below. The actual key exchange is done the same way it was done for the
conventional Diffie-Hellman protocol.
Elliptic Curve Diffie-Hellman Key Exchange (ECDH)
Alice
Bob
choose
k
prA
=
a
∈{
2
,
3
,...,
#
E
−
1
}
choose
k
prB
=
b
∈{
2
,
3
,...,
#
E
−
1
}
compute
k
pubA
=
aP
=
A
=(
x
A
,
y
A
)
compute
k
pubB
=
bP
=
B
=(
x
B
,
y
B
)
A
−−−−−−−−−−−−−−→
B
←−−−−−−−−−−−−−−
compute
aB
=
T
AB
compute
bA
=
T
AB
Joint secret between Alice and Bob:
T
AB
=(
x
AB
,
y
AB
).
The correctness of the protocol is easy to prove.
Proof.
Alice computes
aB
=
a
(
bP
)
while Bob computes
bA
=
b
(
aP
)
.
Since point addition is associative (remember that associativity is one of the group
properties), both parties compute the same result, namely the point
T
AB
=
abP
.
As can be seen in the protocol, Alice and Bob choose the private keys
a
and
b
, respectively, which are two large integers. With the private keys both generate
their respective public keys
A
and
B
, which are points on the curve. The public
keys are computed by point multiplication. The two parties exchange these public
parameters with each other. The joint secret
T
AB
is then computed by both Alice
and Bob by performing a second point multiplication involving the public key they
received and their own secret parameter. The joint secret
T
AB
can be used to derive
a session key, e.g., as input for the AES algorithm. Note that the two coordinates
(
x
AB
,
y
AB
) are not independent of each other: Given
x
AB
, the other coordinate can be
computed by simply inserting the
x
value in the elliptic curve equation. Thus, only
one of the two coordinates should be used for the derivation of a session key. Let's
look at an example with small numbers:
