Computer Security and Cryptography

16.4 EL GAMAL'S EXTENSION OF DIFFIE–HELLMAN

Although Diffie–Hellman realized how keys could be exchanged securely if the DLP was infeasible to solve, they did not discover how to modify their idea to encipher data.

The Secure Electronic Exchange of Keys (SEEK) is a product of the CYLINK Corporation. It is based on an extension of the Diffie–Hellman scheme discovered by T. El Gamal [1985]

16.4.1 SEEK Cryptosystem

Public Parameters: p = 2r + 1 and r primes; q a primitive root of p.

1i.	User_ID[i] chooses a random key and computes xi = qki (modulo p).
1j.	User_IDj chooses a random key and computes xj = qki (modulo p).
2.	User_ID[i] and User_ID[j] exchange xi and xj.
3i.	User_ID[i] computes (modulo p).
3j.	User_ID[j] computes (modulo p).
4.	xi,j = xi,j is used to derive the common session key
5.	Each user computes the multiplicative inverse di,j modulo p − 1 of ei,j by evaluating ...