Cryptography Reference
In-Depth Information
learn exactly what value of temporary key
k
the sender used, but they will learn
enough to be able to remove its impact on the ciphertext. In the second step the
plaintext is extracted from the ciphertext using the private key
x
.
Why does this work
? Just as we did for RSA, we address this question in
the Mathematics Appendix, allowing the option of just accepting that it does!
However, it is worth noting that the explanation relies on nothing more than
simple rearrangements of the above formula and does not require any significant
results from mathematics.
Before looking at a simple example, we make one observation. The second
decryption step involves dividing one number by another modulo
p
. Formally
there is no such thing as 'division' inmodular arithmetic. This process of 'dividing'
a number
a
by a number
b
modulo
p
is instead carried out by multiplying
a
by
the
modular inverse
of
b
(a number that is usually represented by
b
−
1
and which
is discussed in more detail in the Mathematics Appendix). Thus it would strictly
be more accurate to describe the process of decrypting (
C
1
,
C
2
) using private
key
x
as:
1. compute (
C
1
)
x
mod
p
,
2.
(a) calculate the modular inverse of (
C
1
)
x
modulo
p
, which we write as
((
C
1
)
x
)
−
1
;
(b)
P
((
C
1
)
x
)
−
1
mod
p
=
C
2
×
.
The only potentially awkward decryption computation is thus calculating the
modular inverse. However, modular inverses can be calculated very easily using
the same Extended Euclidean Algorithm that we used to set up an RSA key pair
(see Section 5.2.1).
Continuing our example, to decrypt the ciphertext
C
=
(
C
1
,
C
2
)
=
(20
,
22)
=
using private key
x
6:
1. compute 20
6
=
16mod 23,
(a) calculate the modular inverse of 16 modulo 23, which we write as 16
−
1
;
using the Extended Euclidean Algorithm, we find that 16
−
1
2.
=
13mod 23;
(b)
P
=
22
×
13
=
10mod 23
.
Since
P
=
10 was indeed the plaintext that we started with, the decryption has
been successful.
5.3.3
Security of ElGamal
Just as we did for RSA in Section 5.2.3, we will consider two different approaches
that could be taken in order to break ElGamal.
DECRYPTING A CIPHERTEXT WITHOUT KNOWLEDGE
OF THE PRIVATE KEY
The most obvious attack on an ElGamal ciphertext (
C
1
,
C
2
) is to determine the
temporary key
k
. An attacker who can determine
k
can then compute
y
k
, and then
