Cryptography Reference
In-Depth Information
Compute the last part of the public key
. The value
y
is computed from the
parameters
p
,
g
and the private key
x
as follows:
g
x
mod
p
y
=
.
The ElGamal public key consists of the three parameters (
p
,
g
,
y
)
=
=
As an example, suppose that
p
11 (we confirm that 11 is a
primitive element modulo 23 in the Mathematics Appendix). The private key
x
can be any number bigger than 1 and smaller than 22, so we choose
x
23 and that
g
=
6. The
value
y
is then computed as follows:
y
=
11
6
=
9mod 23
.
Thus the private key is 6 and the public key is (23
,
11
,
9).
5.3.2
Encryption and decryption using ElGamal
While the generation of an ElGamal key pair is arguably simpler than the
equivalent process for RSA, encryption and decryption are slightly more complex
than RSA.
ELGAMAL ENCRYPTION
Suppose that we wish to send a plaintext to someone whose ElGamal public key is
(
p
y
). ElGamal encryption operates on numbers modulo
p
. Thus the first task
is to represent our plaintext as a series of numbers modulo
p
. Just as we did for
RSA, we assume that there is some agreed method of doing this.
Suppose that we now want to encrypt the first plaintext
P
, which we have
already represented as a number modulo
p
. The encryption process to obtain the
ciphertext
C
is as follows:
,
g
,
1. randomly generate a number
k
;
2. compute two values
C
1
and
C
2
, where:
C
1
g
k
mod
p
,
=
Py
k
mod
p
;
C
2
=
3. send the ciphertext
C
, where
C
consists of the two separate values (
C
1
,
C
2
),
sent together.
We now look more carefully at
C
1
and
C
2
in order to determine what role in the
ciphertext each plays:
• The value
k
is randomly generated for this ciphertext, and
only
for this ciphertext.
The next time a plaintext is encrypted, even if it is exactly the same plaintext as
before, a new
k
shouldbe randomly generated (we discusswhy this is important
in Section 5.3.4). Thus we can think of
k
as being a temporary (one-time) 'key'.
The first component
C
1
of the ciphertext is
g
k
mod
p
. Recall from Section 5.1.4
