Cryptography Reference
In-Depth Information
that modular exponentiation (of which this is an example) is believed to be
a one-way function. This means that calculating C 1 is easy, but determining
k from C 1 is believed to be hard. Thus C 1 is best thought of as a one-way
representation of the temporary key k .
• The second ciphertext component C 2 is a function of the plaintext P , the public-
key component y and the temporary key k . More precisely, it is P multiplied by
y k , and then reduced modulo p . Thus C 2 can be thought of as the encryption of
P using both the public-key component y and the temporary key k .
Using the above interpretation, we see that C 2 is in some sense the 'real' encryption
of P using both y and a temporary key k . The receiver knows the matching private
key x , so it would be reasonable to assume that they should be able to reverse any
encryption process that uses the public-key component y . However, k is a one-
time value that the receiver does not know, since the sender generated it on the
fly during this particular encryption process. Thus the receiver must have some
means of 'removing' the impact of the temporary key k .
The importance of C 1 should now be clear. It is the means of communicating
information about the temporary key k to the receiver in a way that does not allow
an attacker, who can observe C 1 since it is part of the ciphertext, to determine k
from C 1 . Of course, the receiver cannot determine k directly from C 1 either, but
we will see shortly that this does not matter. ElGamal has been designed in a very
clever way that allows the holder of the private key to reverse both the use of y
and k in the encryption process.
Using the ElGamal key pair that we generated in the previous example, the
plaintext P
=
10 is encrypted as follows:
1. randomly generate a number, say k
3;
2. compute the two values C 1 and C 2 , where:
C 1
=
11 3
=
=
20mod 23
,
9 3
C 2
=
10
×
=
10
×
16
=
160
=
22mod 23
;
3. send the ciphertext C = ( C 1 , C 2 ) = (20 , 22).
ELGAMAL DECRYPTION
To decrypt the ciphertext ( C 1 ,
C 2 ) using private key x , the following two steps are
required:
1. compute ( C 1 ) x mod p ;
2. divide C 2 by the result of step 1:
C 2
( C 1 ) x mod p .
Once again there are good reasons for these two steps. The first step allows the
receiver to use their private key x to modify C 1 in a way that allows the effect of
the temporary key k to be 'removed' in the second step. The receiver will never
P =
 
Search WWH ::




Custom Search