ElGamal cryptography: public-key security on discrete logarithms

Ideas Made

تعمية الجمل: التشفير بمفتاح عمومي على اللوغاريتمات المتقطعة

A public-key cryptosystem and digital signature scheme proposed by the Egyptian-American cryptographer Taher Elgamal in his 1985 paper 'A public key cryptosystem and a signature scheme based on discrete logarithms': built on the Diffie-Hellman key exchange in a cyclic group, its security resting on the difficulty of the discrete logarithm problem, with a fresh ephemeral key for every message; his signature scheme became the basis of the Digital Signature Algorithm ⁦(DSA)⁩ adopted by NIST, and the encryption is used in GNU Privacy Guard and recent PGP versions 1 2.

Depth

At a glance

Era
The Contemporary Era
Region
Egypt & Nile · Americas & Oceania

MathematicsEngineering and technologyScience in Muslim societies today

Quick facts

Domain
Modern technology
Kind
Algorithm
First attested
1985 CE · 1405 AH (derived)
Era
Twentieth century
Where
California
Attribution
Original

Who made it

The claim and its basis

He alone is credited with the encryption system and the signature scheme that carry his name; both built on the pre-existing Diffie-Hellman exchange, so the documented creation is the two schemes, not the logarithm problem itself {cite:wikipedia-elgamal-encryption-en} {cite:wikipedia-taher-elgamal-en}.

The recorded encryption article names him as the system's 1985 describer, and the biography lists the paper's title and venue — IEEE Transactions on Information Theory vol. 31 no. 4 ⁦(July 1985, pp. 469-472)⁩ — and records that the signature scheme underlies the NIST-standard DSA.

Sources: Taher Elgamal — English Wikipedia · ElGamal encryption — English Wikipedia · T. Elgamal, A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms (1985)

Before it

  • The Diffie-Hellman key exchange ⁦(1976)⁩
  • The discrete logarithm problem in cyclic groups

Built on it

  • The Digital Signature Algorithm ⁦(DSA)⁩ and the Digital Signature Standard
  • GNU Privacy Guard and recent PGP versions
  • The SSL and TLS protocols and HTTPS browsing

How it works

Record relationship chain

Summary

ElGamal is the public-key cryptosystem and digital-signature scheme that Taher Elgamal, an Egyptian-American cryptographer, proposed in a single 1985 paper. Built on the Diffie-Hellman exchange and the hardness of discrete logarithms, the encryption still runs inside GnuPG and PGP, while the signature scheme became the ancestor of the US government's Digital Signature Algorithm — and its maker then drove SSL, the padlock of the web 1 2.

What it is

A pair of mathematical schemes: a public-key encryption system in which anyone can seal a message to a public key that only the private-key holder opens, and a signature scheme proving a message's origin. Security rests on the discrete logarithm problem — easy to compute in one direction, infeasible to reverse in a well-chosen cyclic group 1.

The world before it

Diffie and Hellman's 1976 key exchange had opened public-key cryptography, and RSA followed; but the field still needed a second family of schemes — encryption and signatures — resting on the discrete-logarithm hardness inside cyclic groups 1.

The story

Elgamal studied electrical engineering at Cairo University, then took his doctorate at Stanford in 1984 under Martin Hellman himself — a father of public-key cryptography — before joining HP Labs. In July 1985 IEEE Transactions on Information Theory published his four-page paper proposing both schemes. A decade later, as Netscape's chief scientist, he drove the SSL protocol that became the basis of TLS and HTTPS — earning him the title "father of SSL", the 2009 RSA lifetime award, the 2019 Marconi Prize and election to the National Academy of Engineering in 2022 2.

The maker(s)

Taher Elgamal ⁦(born 1955)⁩ is the sole author of the founding paper and the documented inventor: both schemes carry his name, and the encryption article records him as the system's describer in 1985 2 1.

How it works

Three phases: Alice publishes a public key made of a group, a generator and a value hiding her secret exponent; Bob picks a fresh ephemeral key for every message, derives a shared secret and masks the message with it; Alice's private key recovers the same secret and strips the mask. The new ephemeral each time is what keeps old ciphertexts safe 1.

The spread

The encryption lives on in GNU Privacy Guard and recent PGP versions; the signature scheme's variant was adopted by NIST as the Digital Signature Algorithm and Standard — and its maker's SSL at Netscape became the ancestor of the TLS that secures daily browsing 1 2.

What it was built on

The 1976 Diffie-Hellman key exchange — ElGamal performs that exchange first, then uses the shared secret as a one-time pad — and the mathematics of cyclic groups and the discrete logarithm problem 1.

What was built on it

The DSA and the Digital Signature Standard signed government and software documents for decades; elliptic-curve signatures are grandchildren of the same line; and the whole public-key infrastructure of encrypted mail carries its logic 2 1.

Impact on daily life

Whenever software signs itself, mail encrypts itself, or a browser proves a site's identity, machinery in the ElGamal-Diffie-Hellman family is at work — invisible infrastructure for private communication 1 2.

How it changed history

It gave cryptography a second great public-key family and the digital signature its standard form; with SSL its maker also seeded the protocol generation that made e-commerce possible 2 1.

Who invented it?

Uncontested: the paper is single-authored, both schemes bear the name ElGamal, and no rival claimant exists in the sources 1 2.

Today

Still implemented in GnuPG and PGP derivatives and ancestor of modern signature standards; its maker, meanwhile, remains one of the most decorated living cryptographers 1 2.

Surviving examples

The 1985 paper itself — IEEE Transactions on Information Theory vol. 31 no. 4, pp. 469-472 — and the running code in free software are the record's "survivors" 3 1.

In culture

"Father of SSL" made Elgamal a named figure in Internet history — and, in Egyptian and Muslim memory, proof that the makers of the modern world's security include the ummah's sons 2.

For young readers

Taher Elgamal is an Egyptian scientist who wrote a clever method in 1985: you can send a friend a secret message that nobody else can read even if everyone sees it, because solving it needs a very hard maths puzzle only your friend can answer. With this idea we send safe messages and shop on the Internet today.

References

English Wikipedia "ElGamal encryption" revision 1373205550 and "Taher Elgamal" revision 1371999818 (entity facts); T. Elgamal, "A public key cryptosystem and a signature scheme based on discrete logarithms", IEEE Trans. Inf. Theory 31(4), 1985 (bibliographic).

Connections

Explore the connections

Invented by
Taher Elgamal
Described by
Taher Elgamal

People and things also explored

Stanford· The MOSFET: Atalla and Kahng's transistor that made the digital age· The Elephant Clock· Hasan al-Jabarti· Taher Elgamal· The Maʾrib Dam· Nilometer of Rawda Island, Cairo· Abbasid tin-glazed ware

Sources

  1. ElGamal encryption — English Wikipedia
  2. Taher Elgamal — English Wikipedia
  3. T. Elgamal, A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms (1985)
Cite this page

islam.museum contributors. “ElGamal cryptography: public-key security on discrete logarithms”. islam.museum, https://islam.museum/en/invention/taher-elgamal-cryptography/. CC BY-SA 4.0. Last updated 2026-11-16.

Improve this page on GitHub · Report an error · Help complete it · JSON

Wing

Ideas

Beliefs, concepts, sciences and schools, explained in plain words.
Related

Stanford

Region (Wikidata Q173813).