Lecture
Public-key encryption and digital-signature algorithms were published by T. ElGamal (Taher Elgamal) in 1984. The ElGamal cryptosystem uses the same mathematical foundation as the Diffie — Hellman key-distribution scheme discussed earlier. Encryption is in fact carried out by multiplying the message by the shared secret key of the Diffie — Hellman system.
Unlike the Shamir cipher, the ElGamal cipher is single-pass, i.e. it solves the problem of transmitting an encrypted message in just one exchange.
The security of the ElGamal scheme is likewise based on the difficulty of computing discrete logarithms in a finite field.
Suppose there are subscribers A and B who want to exchange secret messages without having a secure communication channel. The ElGamal system generalises easily to the case of several subscribers. For the whole group of subscribers a large prime number p and a number g are chosen, such that 1 < g
1, all numbers from the set {1,2, ...,p - 1} can be represented as distinct powers of g modulo p. The numbers p and g are chosen the same way as in the Diffie — Hellman system.
The numbers p and g are transmitted to subscribers in the open and can be used by every subscriber on the network. Each subscriber in the group then chooses their own private key — a random number x,: 1 < xi < p - 1, which is kept secret. The public keys y;. are then computed.
As a result, a directory of subscribers' public keys can be compiled, similar to a telephone directory (Fig. 3.5).
Fig. 3.5. Directory of subscriber keys in the ElGamal system
As in the Shamir cipher, the message is assumed to be represented as a number M < p.
The process of transmitting a secret message M from subscriber A to subscriber B:
1) A chooses a random number k, and computes the numbers:
A sends the pair of numbers (r, s) to subscriber B. The pair (r, s) is the ciphertext;
2) subscriber B, upon receiving the pair (r, s), computes
Let us show that M' = M. Substituting into the expression for computing M the expressions for S, r and yB, we obtain
since, by Fermat's theorem, modp = Hmod p = 1.
The values r and s can be transmitted openly, since deriving the secret value k from them is practically infeasible (this claim rests on the computational complexity of the discrete logarithm problem for large values of p).
Any subscriber who knows subscriber B's public key can send B encrypted messages. However, no one other than subscriber B can compute the value M and read these messages, since the computation uses subscriber B's secret key. Computing the secret key x from the known public key yi is likewise a discrete logarithm problem and is practically infeasible for large p.
It should be noted that the size of the cryptogram is twice the size of the plaintext message, but only a single data transmission is required (provided the public-key directory is already known to all subscribers in advance).
A distinctive feature of the ElGamal cryptosystem is that a random number k, takes part in the encryption process, so re-encrypting the same plaintext message produces different cryptograms each time.
Example 3.22
Suppose we need to transmit the message M = 15 from subscriber A to B using
the ElGamal cipher. The parameters chosen are p = 23, g = 5 (the same as in example 3.1
for the Diffie — Hellman system). Suppose B chose the secret key xB = 13
and published the public key yB = 513 mod 23 = 21.
Subscriber A chooses a random number k, for example k = 7, and computes:
A sends subscriber B the pair (17, 12).
Subscriber B computes
Subscriber B was able to decrypt the transmitted message.
Comments