CoreSource checked

ElGamal Signature

Signs messages with a discrete-log construction using a fresh random nonce.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Cryptography
Difficulty: Intermediate
Family: Digital Signatures
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 0
Relationships: 2
Code example: Ready
Visualization: Ready

Overview

The ElGamal signature scheme computes a signature pair from a message, private key, and one-time random value. Verification checks a modular exponentiation equation against the public key.

Core Concepts

digital signature generationdigital signaturesmodular arithmeticrandom samplingcryptography

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(k)

Average

O(k^2)

Worst

O(k^3)

Space

O(k)

When to Use

Use primarily for study or compatibility with a protocol that specifies it.
Use only when group parameters and nonce generation are well controlled.

When Not to Use

Avoid custom production implementations.
Avoid if nonce uniqueness and secrecy cannot be guaranteed.

What It Does

Chooses a fresh random signing value
Computes signature components in a multiplicative group
Verifies signatures with modular exponentiation

Use Cases

Studying discrete-log signature constructions
Comparing ElGamal-style signatures with DSA and Schnorr signatures
Educational implementations of nonce-sensitive signing

Inputs

Message, key, modulus, seed, or public parameters
Security parameter or nonce when required

Outputs

Cryptographic value such as signature, random bits, proof, or modular result

Pseudocode

1.Validate group parameters and key ranges
2.Hash the message to an integer h
3.Choose invertible fresh nonce k
4.Compute r from the generator raised to k
5.Compute s using h, the private key, r, and k inverse
6.Verify the public exponentiation equation

Canonical Example

Input: message digest h, private key x, nonce k, and public group parameters
Output: signature pair (r, s)
Explanation: The signature binds h to the public key through modular exponentiation and the one-time nonce.

Implementation Notes

Validate group parameters and public keys before verification.
Check nonce invertibility and never reuse signing randomness.
Use constant-time arithmetic in security-sensitive implementations.

Common Pitfalls

Reusing a nonce can expose the private key.
Choosing a nonce that is not invertible modulo the group order breaks signing.
Weak or unvalidated group parameters undermine the discrete-log assumption.

Interactive Mechanism Walkthrough

Graph Frontier & Edge Relaxation

Show combining a random exponent with modular inverse arithmetic on a small digital signature generation example.

Step 1 of 6: Validate group parameters and key ranges

cryptography-mechanism

Notes

ElGamal signatures are useful for understanding discrete-log signatures, but modern protocols usually specify more constrained schemes.

Sources (1)

What each reference supports for this entry.