Cyclic Groups and Generators: The Engine Behind Diffie-Hellman

Terminology

What & Why

A cyclic group is a group that can be generated by a single element. Starting from one element g and repeatedly applying the group operation, you can reach every element in the group. This makes cyclic groups the simplest possible groups, yet they are the algebraic engine behind some of the most important protocols in computer science.

Formally, a group G is cyclic if there exists a generator g \in G such that:

where $n = |G|$ is the order of the group and $g^0 = e$ is the identity.

The classic example is \mathbb{Z}_n (integers mod n under addition). The element 1 generates the entire group: 0, 1, 2, \ldots, n-1 are just 1 added to itself 0, 1, 2, \ldots, n-1 times.

Why does this matter for CS?

• Diffie-Hellman key exchange works by choosing a large prime p and a generator g of the cyclic group \mathbb{Z}_p^*. Security depends on the discrete logarithm problem being hard in this group.
• Elliptic curve cryptography uses cyclic subgroups of elliptic curve point groups, achieving equivalent security with smaller key sizes.
• Hash function design and pseudorandom number generators exploit the uniform distribution properties of cyclic group elements.

How It Works

Generating a Cyclic Group

Consider $\mathbb{Z}_7^* = \{1, 2, 3, 4, 5, 6\}$ under multiplication mod 7. Let us check whether $g = 3$ is a generator:

Since the powers of 3 produce all 6 elements, $g = 3$ is a generator and $\mathbb{Z}_7^*$ is cyclic of order 6.

Lagrange's Theorem

Lagrange's theorem states that for any finite group $G$ and subgroup $H \leq G$:

A direct consequence: the order of any element divides $|G|$. In $\mathbb{Z}_7^*$ (order 6), element orders can only be 1, 2, 3, or 6. An element of order 6 is a generator.

The Discrete Logarithm Problem

Given a generator $g$ and a group element $h = g^x$, finding $x$ is the discrete logarithm problem (DLP). In $\mathbb{Z}_p^*$ for large primes $p$, no efficient classical algorithm is known. The best general-purpose algorithm (number field sieve) runs in sub-exponential time:

This computational hardness is what makes Diffie-Hellman secure.

Diffie-Hellman Key Exchange

Alice and Bob agree on a public prime $p$ and generator $g$. Alice picks secret $a$, sends $g^a \bmod p$. Bob picks secret $b$, sends $g^b \bmod p$. Both compute the shared secret $g^{ab} \bmod p$. An eavesdropper sees $g^a$ and $g^b$ but cannot efficiently compute $g^{ab}$ without solving the DLP.

Complexity Analysis

The gap between the $O(\log n)$ cost of exponentiation and the sub-exponential cost of discrete logarithm is the asymmetry that makes public-key cryptography possible.

Implementation

ALGORITHM FindGenerator(p, prime_factors_of_p_minus_1)
INPUT:  p: a prime number
        prime_factors_of_p_minus_1: array of prime factors of (p - 1)
OUTPUT: a generator g of the cyclic group Z*_p

BEGIN
  // Euler's criterion: g is a generator of Z*_p if and only if
  // g^((p-1)/q) != 1 (mod p) for every prime factor q of (p-1)

  REPEAT
    g := RANDOM(2, p - 1)
    is_generator := TRUE

    FOR EACH q IN prime_factors_of_p_minus_1 DO
      exponent := (p - 1) / q
      IF RepeatedSquaring(g, exponent, p) = 1 THEN
        is_generator := FALSE
        BREAK
      END IF
    END FOR
  UNTIL is_generator

  RETURN g
END

ALGORITHM DiffieHellman(p, g)
INPUT:  p: a large prime
        g: a generator of Z*_p
OUTPUT: shared_secret known to both Alice and Bob

BEGIN
  // Alice's side
  a := RANDOM(2, p - 2)           // Alice's private key
  A := RepeatedSquaring(g, a, p)  // Alice's public value

  // Bob's side
  b := RANDOM(2, p - 2)           // Bob's private key
  B := RepeatedSquaring(g, b, p)  // Bob's public value

  // Exchange: Alice sends A to Bob, Bob sends B to Alice

  // Alice computes shared secret
  secret_alice := RepeatedSquaring(B, a, p)   // B^a = g^(ba)

  // Bob computes shared secret
  secret_bob := RepeatedSquaring(A, b, p)     // A^b = g^(ab)

  // Both arrive at the same value: g^(ab) mod p
  ASSERT secret_alice = secret_bob
  RETURN secret_alice
END

Real-World Applications

• TLS/HTTPS: the Diffie-Hellman key exchange (and its elliptic curve variant ECDH) is used in TLS handshakes to establish session keys for encrypted web traffic
• SSH key exchange: OpenSSH uses Diffie-Hellman or ECDH to negotiate encryption keys when you connect to a remote server
• Signal Protocol: the Double Ratchet algorithm in Signal, WhatsApp, and other messaging apps uses repeated Diffie-Hellman exchanges for forward secrecy
• Pseudorandom number generation: linear congruential generators cycle through elements of $\mathbb{Z}_m$, and the cycle length depends on the group structure
• Digital signatures (DSA, ECDSA): signing algorithms operate in cyclic subgroups, using the generator to create and verify signatures

Key Takeaways

• A cyclic group is generated by a single element: every member is a power of the generator
• Lagrange's theorem constrains element orders to divide the group order, limiting the possible structure
• The discrete logarithm problem (finding $x$ from $g^x$) is computationally hard in well-chosen cyclic groups, forming the security basis of Diffie-Hellman and elliptic curve cryptography
• Finding a generator is efficient (polynomial time) while breaking the DLP is believed to require sub-exponential time, creating the asymmetry that public-key crypto depends on
• Cyclic groups appear in TLS, SSH, digital signatures, and pseudorandom number generation