Cryptography Reference
In-Depth Information
regard to module
p
. Though there is an effective algorithm to compute such
logarithms, it only works if (
p
−
1
)/
2 itself is not a prime number.
The encryption of a message,
m<p
, looks a bit unusual: the sender chooses
a random number,
k
, which must be relatively prime to
p
−
1, and computes
a=g
k
mod p and
b=y
k
mmodp.
The ciphertext consists of
two
numbers,
a
and
b
. The sender won't tell anybody
the value of
k
and doesn't have to know it any more later on. Otherwise,
anybody who knew
k
could solve the number-theory equation
y
k
m = b mod p
(4)
and find
m
. Conversely, we know
x
and can resolve the equation
a
x
m' = b mod p
toward
m
.
a
x
m'=g
kx
m' = g
xk
m' = y
k
m' = b mod p
holds now, and when comparing it with (4) (and due to the unique solvability
of this equation, modulo
p)
we can see that
m
m
in any event.
=
The fact that the ciphertext is twice as long as the plaintext doesn't matter,
because we only want to encrypt session keys.
The ElGamal encryption is closely related to the
Diffie-Hellman key ex-
change
, the first method that used public keys (see Section 6.1.1). ElGamal
methods are mainly used for digital signatures. We will not discuss them further
here and refer to [SchnCr] instead.
4.5.4 The Knapsack Story
You may be surprised to learn that the asymmetric methods commonly used
are solely based on the problems of factoring or computing discrete logarithms.
