Cryptography Reference
In-Depth Information
20.2.3 Key derivation functions
The result of Diffie-Hellman key exchange is a group element
g
ab
. Typically this should
be transformed into an
l
-bit string for use as a symmetric key.
Definition 20.2.10
Let
G
be an algebraic group (or algebraic group quotient) and let
l
be an
integer. A
key derivation function
is a function
kdf
:
G
l
.The
output distribution
→{
0
,
1
}
l
induced by
kdf
(
g
) over
of a key derivation function is the probability distribution on
{
0
,
1
}
uniformly distributed
g
G
. A key derivation function is
preimage resistant
if there is
no polynomial-time algorithm known that, on input
x
∈
l
, computes
g
∈{
0
,
1
}
∈
G
such that
kdf
(
g
)
=
x
.
In general, a key derivation function should have output distribution statistically very
close to the uniform distribution on
{
0
,
1
}
l
. For many applications it is also necessary that
kdf
be preimage resistant.
A typical instantiation for
kdf
is to take a binary representation of
K
G
, apply a
cryptographic hash function (see Chapter
3
) to obtain a bit string and concatenate/truncate
as required. See the IEEE P1363 or ANSI X9.42 standards, Section 8 of Cramer and
Shoup [
149
] or Section 6.1 of Raymond and Stiglic [
445
] for more details; also see
Section 3 of [
43
] for a specific key derivation function for elliptic curves.
∈
20.3 Textbook Elgamal encryption
In this section we present
textbook Elgamal public key encryption
.
2
This is historically
the first public key encryption scheme based on the discrete logarithm problem. As we
will see, the scheme has a number of security weaknesses and so is not recommended for
practical use. In Chapter
23
we will present secure methods for public key encryption based
on computational problems in cyclic groups.
We actually present two “textbook” versions of Elgamal. The first we call “classic
textbook Elgamal” as it is essentially the version that appears in [
177
]. It requires
G
to be
a group (i.e., we cannot use algebraic group quotients) and requires the message
m
to be
encoded as an element of
G
. Encoding messages as group elements is not difficult, but it is
unnatural and inconvenient. The second version, which we call “semi-textbook Elgamal”,
is more practical as it treats messages as bitstrings. As we will see, the security properties
of the two versions are slightly different.
For both schemes,
κ
denotes a security parameter (so that all attacks should require
at least 2
κ
bit operations). Box
20.1
gives classic textbook Elgamal and Box
20.2
gives
semi-textbook Elgamal. We call the sender Bob and the recipient Alice. Messages in the
former scheme are group elements and in the latter are
l
-bit strings, where
l
depends on
the security parameter. Semi-textbook Elgamal also requires a cryptographic hash function
H
:
G
l
where
G
is the group.
→{
0
,
1
}
2
Some authors write “ElGamal” and others write “El Gamal”. Reference [
177
] uses “ElGamal”, but we follow the format
apparently used nowadays by Elgamal himself.
