Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
ElGamal encryption
Summary
In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange. It was described by Taher Elgamal in 1985. ElGamal encryption is used in the free GNU Privacy Guard software, recent versions of PGP, and other cryptosystems. The Digital Signature Algorithm (DSA) is a variant of the ElGamal signature scheme, which should not be confused with ElGamal encryption.
ElGamal encryption can be defined over any cyclic group , like multiplicative group of integers modulo n. Its security depends upon the difficulty of a certain problem in related to computing discrete logarithms.
The algorithm can be described as first performing a Diffie–Hellman key exchange to establish a shared secret , then using this as a one-time pad for encrypting the message. ElGamal encryption is performed in three phases: the key generation, the encryption, and the decryption. The first is purely key exchange, whereas the latter two mix key exchange computations with message computations.
The first party, Alice, generates a key pair as follows:
Generate an efficient description of a cyclic group of order with generator . Let represent the identity element of .
It is not necessary to come up with a group and generator anew for each new key. Indeed, one may expect a specific implementation of ElGamal to be hardcoded to use a specific group, or a group from a specific suite. The choice of group is mostly about how large keys you want to use.
Choose an integer randomly from .
Compute .
The public key consists of the values . Alice publishes this public key and retains as her private key, which must be kept secret.
A second party, Bob, encrypts a message to Alice under her public key as follows:
Map the message to an element of using a reversible mapping function.
Choose an integer randomly from .
Compute . This is called the shared secret.
Compute .
Compute .
Bob sends the ciphertext to Alice.
Note that if one knows both the ciphertext and the plaintext , one can easily find the shared secret , since .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Ontological neighbourhood
Related courses (9)
COM-401: Cryptography and security
This course introduces the basics of cryptography. We review several types of cryptographic primitives, when it is safe to use them and how to select the appropriate security parameters. We detail how
MATH-489: Number theory II.c - Cryptography
The goal of the course is to introduce basic notions from public key cryptography (PKC) as well as basic number-theoretic methods and algorithms for cryptanalysis of protocols and schemes based on PKC
COM-501: Advanced cryptography
This course reviews some failure cases in public-key cryptography. It introduces some cryptanalysis techniques. It also presents fundamentals in cryptography such as interactive proofs. Finally, it pr