Cryptography Reference
In-Depth Information
4. Alice then sends the ciphertext
c
=(
α
b
,mα
ab
) to Bob.
Deciphering stage
:
1. Bob uses his private key to compute (
α
b
)
−
a
(
α
b
)
p
−
1
−
a
(mod
p
).
≡
2. Then he deciphers
m
by computing (
α
b
)
−
a
mα
ab
(mod
p
).
Example 4.7
Suppose that Alice wants to send the message
m
= 1010
to Bob
using the ElGamal cipher.Bob chooses
p
= 1481
,
α
=3
, and
a
=7
, his
private key.He computes
α
a
3
7
706 (mod
p
)
.Bob's public key is therefore
(
p, α, α
a
) = (1481
,
3
,
706)
, which Alice downloads from some public database.
She chooses
b
=96
and computes both
α
b
≡
≡
3
96
737 (mod
p
)
and
mα
ab
≡
≡
≡
706
96
1010
521 (mod
p
)
.The ciphertext is
c
= (737
,
521)
, which Alice sends
to Bob.He uses his private key to compute
·
≡
(
α
b
)
p
−
1
−
a
737
1473
≡
≡
940 (mod
p
)
,
and
(
α
b
)
−
a
mα
ab
≡
940
·
521
≡
1010 (mod
p
)
,
thereby recovering
m
.
Analysis
Key Generation Options
: Although it is preferable in step 1 of key gen-
eration, one need not choose a primitive root, provided one chooses an element
α
)
∗
whose order is close to the size of
p
. In other words, the smallest
∈
(
Z
/p
Z
∈
N
such that
α
r
≡
r
1 (mod
p
) must be nearly as large as
p
. Such
α
are called
near-primitive roots
. In the case of a primitive root,
r
=
p
−
1.
SecurityIssues
: The random number
b
generated by Alice in step 2 of the
enciphering stage must be kept secret since one can recover
m
=
mα
ab
(
α
a
)
−
b
from knowledge of it, given that
mα
ab
and
α
a
are made public. Furthermore,
b
should never be used twice. Suppose that Alice uses
b
for two different messages
m
1
and
m
2
, and Eve knows
m
1
. Then this is how Eve can obtain
m
2
. The two
ciphertexts are
c
1
=(
α
b
,m
1
α
ab
) and
c
2
=(
α
b
,m
2
α
ab
). Then she calculates
that
m
2
α
ab
m
−
1
m
1
α
−
ab
=
m
2
.
We conclude the discussion of security issues with a detailed argument to
show that indeed the security of the ElGamal cipher is based upon the DLP.
To see this, we demonstrate first that the ElGamal cipher is equivalent to the
Di8e-Hellman key-exchange protocol. Assume Eve can solve the DHP (see
page 167), and she desires to get
m
from
c
=(
α
b
,mα
ab
). Since she can solve
the DHP, she can determine
β
α
ab
(mod
p
) from
α
a
and
α
b
. Therefore, she
≡
β
−
1
mα
ab
(mod
p
), In other words, if Eve can
break the Di8e-Hellman cipher, she can break the ElGamal.
can reconstruct the message
m
≡
Search WWH ::
Custom Search