Public-Key Cryptosystems Based on the Discrete Logarithm Problem

Articles · 2026 · Ioannis (John) Konstas

Public-key cryptography depends on trapdoor one-way functions: mathematical operations that are computationally efficient in the forward direction but intractable to reverse without specific private trapdoor knowledge. Alongside integer factorization (the basis of RSA), the Discrete Logarithm Problem (DLP) constitutes the primary mathematical foundation for secure key exchange, asymmetric encryption, and digital signature algorithms across the global internet infrastructure.

                    ┌────────────────────────────────────────────────────────┐
                    │               Discrete Logarithm Problem               │
                    │               Given (g, p, y), find x in:             │
                    │                    y ≡ gˣ (mod p)                      │
                    └───────────────────────────┬────────────────────────────┘
                                                │
       ┌────────────────────────┬───────────────┴───────────────┬────────────────────────┐
       ▼                        ▼                               ▼                        ▼
┌──────────────┐      ┌────────────────────┐          ┌────────────────────┐    ┌─────────────────┐
│ Multiplicative│     │   Diffie-Hellman   │          │      ElGamal       │    │ Elliptic Curves │
│ Group ℤₚ*    │      │    Key Exchange    │          │  Asymmetric Scheme │    │     E(𝔽ₚ)       │
│ • Order p-1  │      │ • Forward Secrecy  │          │ • IND-CPA Security │    │ • Chord & Tangent│
│ • Generators │      │ • CDH / DDH Proofs │          │ • Homomorphic Mult │    │ • ECDLP Hardness│
└──────────────┘      └────────────────────┘          └────────────────────┘    └─────────────────┘

1. The Multiplicative Group ℤ_p^* and the DLP

Group Structure & Algebraic Properties

For any prime p, the set of integers coprime to p forms a finite cyclic group under modular multiplication, denoted ℤ_p^*:

ℤp* = {1, 2, 3, ..., p − 1}

• Group Order: |ℤp*| = φ(p) = p − 1.
• Group Operation: Binary modular multiplication (a · b) mod p, satisfying closure, associativity, and commutativity.
• Identity Element: e = 1.
• Multiplicative Inverses: For every a ∈ ℤp*, there exists a unique a⁻¹ ∈ ℤp* satisfying a · a⁻¹ ≡ 1 (mod p), computed via the Extended Euclidean Algorithm or Fermat's Little Theorem (a^{p−2} mod p).
• Generators / Primitive Roots: The group is strictly cyclic. There exists at least one generator g whose successive powers generate all elements of the group:

  ⟨g⟩ = {g¹, g², g³, ..., g^{p−1}} = ℤp*
  

  The total number of primitive roots in ℤ_p^* is φ(p − 1).

The Discrete Logarithm Problem Formulation

Given a generator g ∈ ℤ_p^*, a modulus p, and a target element y ∈ ℤ_p^*, find the unique integer x ∈ ℤ_p−1 such that:

y ≡ gˣ (mod p)

• Forward Direction (Modular Exponentiation): Computing y ≡ gˣ (mod p) takes polynomial time O(log x · log² p) via repeated squaring.
• Reverse Direction (Discrete Logarithm): Extracting x = log_g(y) is computationally intractable for sufficiently large primes.

2. Diffie-Hellman Key Exchange (DHKE)

Introduced in 1976 by Whitfield Diffie and Martin Hellman, DHKE was the first published mechanism enabling two parties to establish a shared cryptographic secret over an unencrypted channel without transmitting the secret itself.

       Alice (Private: a)                                  Bob (Private: b)
  ─────────────────────────────                       ───────────────────────────
   Public Parameters: (p, g)                           Public Parameters: (p, g)
   
   Computes: A = gᵃ mod p          ─── Public A ───►   Computes: B = gᵇ mod p
                                   ◄─── Public B ───
   
   Computes Shared Secret:                             Computes Shared Secret:
   K = Bᵃ mod p                                        K = Aᵇ mod p
     = (gᵇ)ᵃ = gᵃᵇ mod p                                 = (gᵃ)ᵇ = gᵃᵇ mod p

Protocol Execution

1. Parameter Selection: Public prime p and generator g ∈ ℤ_p^*.
2. Key Generation:
   • Alice picks private exponent a ∈ [2, p − 2] and sends A = gᵃ mod p.
   • Bob picks private exponent b ∈ [2, p − 2] and sends B = gᵇ mod p.
3. Shared Secret Derivation:
   • Alice computes: K = Bᵃ mod p = gᵃᵇ mod p.
   • Bob computes: K = Aᵇ mod p = gᵃᵇ mod p.
   • Both arrive at identical secret K = g^ab mod p.

Why Diffie-Hellman Is Critical

• Eliminated Pre-Shared Secrets: Solved the foundational key exchange dilemma of cryptography.
• Perfect Forward Secrecy (PFS): In Ephemeral Diffie-Hellman (DHE / ECDHE), keys are generated per session and discarded immediately, preventing retroactive decryption if server private keys leak.
• Ubiquitous Deployment: Powers TLS 1.3, SSH-2, IPsec (IKEv2), Signal Protocol, and WireGuard.

3. ElGamal Public-Key Encryption

Published in 1985 by Taher Elgamal, this system adapted Diffie-Hellman into a full asymmetric encryption and digital signature scheme.

                                  ElGamal Encryption
  
   Public Key: (p, g, y = gˣ mod p)                    Private Key: x
  
   Sender (Alice):                                     Receiver (Bob):
   - Choose ephemeral random k                         - Receives (c₁, c₂)
   - Compute c₁ = gᵏ mod p                             - Computes shared mask: s = c₁ˣ mod p
   - Compute shared mask s = yᵏ mod p                  - Computes s⁻¹ mod p via EEA
   - Compute c₂ = m · s mod p                          - Recovers message: m = c₂ · s⁻¹ mod p
   
   Ciphertext: C = (c₁, c₂)

Mathematical Specification

1. Key Generation (Bob): Selects private key x ∈ [2, p − 2]; computes public key y = gˣ mod p. Full public key: (p, g, y).
2. Encryption (Alice): Plaintext m ∈ ℤp*, fresh ephemeral nonce k ∈ [2, p − 2] with gcd(k, p − 1) = 1:

   c₁ = gᵏ mod p
   c₂ = (m · yᵏ) mod p
   

3. Decryption (Bob): Computes mask s = c₁ˣ mod p = gᵏˣ mod p, inverts s⁻¹ mod p via Extended Euclidean Algorithm, and recovers plaintext:

   m = (c₂ · s⁻¹) mod p = m mod p
   

Distinct Capabilities

• Semantic Security (IND-CPA): Randomized encryption ensures identical plaintexts yield different ciphertexts.
• Multiplicative Homomorphism: (c₁,₁c₂,₁, c₁,₂c₂,₂) decrypts directly to m₁ · m₂ mod p — foundational for electronic voting tallying and privacy-preserving computation.
• Signature Origin: Direct precursor to the Digital Signature Algorithm (DSA) in NIST FIPS 186, ECDSA, and Schnorr (BIP-340).

4. Introduction to Elliptic Curves over Finite Fields E(𝔽_p)

Elliptic Curve Cryptography (ECC) transfers the discrete logarithm problem from the multiplicative group ℤ_p^* to the additive group formed by points on an algebraic curve.

Short Weierstrass Equation

Over a prime field 𝔽_p (for p > 3), an elliptic curve E(𝔽_p) is defined by the set of solutions (x, y) satisfying:

y² ≡ x³ + ax + b (mod p)

along with a point at infinity Ο acting as the group identity, subject to the non-singularity discriminant condition 4a³ + 27b² ≠ 0 (mod p).

        Point Addition (P ≠ Q)                      Point Doubling (P = Q)
   
        y │       . (Curve)                         y │       . (Curve)
          │      / \                                  │      / \
        P ┼─────/───\─── Q                          P ┼─────*   (Tangent Line)
          │    /     \                                │    / \
          │   /       \                               │   /   \
        ──┼──/─────────\────── x                    ──┼──/─────\────── x
          │ /           \                             │ /       \
      P+Q ┼* (Reflect -R)                         2P  ┼* (Reflect -R)
          │                                           │

The Group Law (Chord-and-Tangent)

For points P = (x₁, y₁) and Q = (x₂, y₂):

1. Identity: P + Ο = P and P + (−P) = Ο, where −P = (x₁, −y₁ mod p).
2. Slope λ:

   λ = (y₂ − y₁) / (x₂ − x₁) mod p    (if P ≠ Q: Secant Line)
   λ = (3x₁² + a) / (2y₁) mod p          (if P = Q: Tangent Line)
   

3. Point Sum R = P + Q = (x₃, y₃):

   x₃ ≡ λ² − x₁ − x₂ (mod p)
   y₃ ≡ λ(x₁ − x₃) − y₁ (mod p)
   

Elliptic Curve Discrete Logarithm Problem (ECDLP)

Given a generator base point P ∈ E(𝔽_p) of prime order n and a public point Q = [k]P = P + P + ... + P (k times), finding the scalar multiplier k ∈ ℤn is the ECDLP.

5. Bit Lengths of Public-Key Algorithms for Different Security Levels

Because subexponential algorithms (GNFS and Index Calculus) exist for integer factorization and finite field discrete logarithms, their key sizes must grow superlinearly to keep pace with security levels. In contrast, elliptic curves lack subexponential structure, allowing key lengths to scale linearly (2 × security bits):

6. Algebraic Correspondence & Cryptanalytic Comparison

The mathematical operations and security parameters compare directly:

Hardening Requirements

• Finite Fields: Use safe primes (p = 2q + 1 with q prime) to defend against Pohlig-Hellman factorization attacks.
• Elliptic Curves: Verify public points lie on the curve and have prime order n ([n]P = Ο) to avoid invalid-curve / small-subgroup attacks.
• Side-Channel Defense: Employ constant-time scalar multiplication (e.g., Montgomery Ladder) to prevent timing attacks (SPA/DPA).
• Post-Quantum Transition: Shor's algorithm solves both DLP and ECDLP in polynomial time O((log p)³) on quantum hardware, requiring migration to NIST Post-Quantum standards (ML-KEM-768 / ML-DSA).

← All articles

Research and direction by Ioannis (John) Konstas; compiled and finalized with AI assistance.