Cryptography Reference
In-Depth Information
During the actual protocol, we first have to choose the private keys
a
and
b
.
They should stem from a true random generator in order to prevent an attacker from
guessing them. For computing the public keys
A
and
B
as well as for computing the
session key, both parties can make use of the square-and-multiply algorithm. The
public keys are typically precomputed. The main computation that needs to be done
for a key exchange is thus the exponentiation for the session key. In general, since
the bit lengths and the computations of RSA and the DHKE are very similar, they
require a similar effort. However, the trick of using short public exponents that was
shown in Section 7.5 is not applicable to the DHKE.
What we showed so far is the classic Diffie-Hellman key exchange protocol in
the group
Z
p
, where
p
is a prime. The protocol can be generalized, in particular to
groups of elliptic curves. This gives rise to elliptic curve cryptography, which has
become a very popular asymmetric scheme in practice. In order to better understand
elliptic curves and schemes such as Elgamal encryption, which are also closely re-
lated to the DHKE, we introduce the discrete logarithm problem in the following
sections. This problem is the mathematical basis for the DHKE. After we have in-
troduced the discrete logarithm problem, we will revisit the DHKE and discuss its
security.
8.2 Some Algebra
This section introduces some fundamentals of abstract algebra, in particular the no-
tion of groups, subgroups, finite groups and cyclic groups, which are essential for
understanding discrete logarithm public-key algorithms.
8.2.1 Groups
For convenience, we restate here the definition of groups which was introduced in
the Chapter 4:
