Cryptography Reference
In-Depth Information
4.4 ElGamal
The best laid schemes o' mice and men Gang aft a-gley.
Robert Burns
(1759-96), Scottish poet
— from
Death and Dr.Hornbrook
(1787, st. 3)
The title for this section is the name of a major contributor to several cryp-
tographic schemes. Taher ElGamal was born in Cairo, Egypt, on August 18,
1955. He obtained his bachelor's degree in electrical engineering from Cairo
University, in 1977. Both his master's degree and his Ph.D. were obtained from
Stanford University in 1981 and 1984, respectively. His doctorate was done un-
der the supervision of Martin Hellman (see page 165). While at Stanford, he
helped to pioneer digital signatures and PKC. He founded Security Inc. in 1988,
which later became the Kroll-O'Gara Information Security Group, where he be-
came president of its Information Security Group. From 1991 to 1993, ElGamal
was the Director of Engineering at RSA Security, Inc., where he produced the
RSA cryptographic toolkits and the initial VeriSign certificate issuance prod-
ucts. From 1993 to 1995, he was Vice President of Advanced Technologies
at OKI Electric. From 1995 to 1998, he held the position of Chief Scientist of
Netscape Communications where he pioneered Internet security technology such
as Secure Sockets Layer (SSL), the standard for Web security, to be discussed in
Section 5.7. Other accomplishments include development of Internet credit card
payment schemes. He also serves on the boards of directors of Phoenix Tech-
nologies; RSA Security, Inc.; hi/fn, Inc.; Security Dynamics; ValiCert Inc.; and
Register.com, and is a member of the technical staff at Hewlett-Packard Labo-
ratories since 1984. ElGamal is a respected leader in the worldwide information
security industry.
The following cryptographic scheme bases its security upon the DLP (see
(4.2), page 164). The cryptosystem was first published in [74] in 1985.
The following is performed assuming that Alice wants to send a message
m
to Bob, and
m
(equivalent to the actual plaintext).
(I) ElGamal Key Generation
1. Bob chooses a large random prime
p
and a primitive root
α
modulo
p
.
∈{
0
,
1
,...,p
−
1
}
1 and computes
α
a
2. Bob then chooses a random integer
a
with 2
≤
a<p
−
(mod
p
).
3. Bob's public key is (
p, α, α
a
) and his private (session) key is
a
.
(II) ElGamal Public-Key Cipher
Enciphering stage
:
1. Alice obtains Bob's public key (
p, α, α
a
).
2. She chooses a random natural number
b<p
−
1.
3. She computes
α
b
(mod
p
) and
mα
ab
(mod
p
).
Search WWH ::
Custom Search