Group Theory
Most cryptographic protocols operate over algebraic structures called groups. Understanding groups isn’t strictly necessary to use these protocols, but it’s necessary to understand why they work — and more importantly, why they’re secure.
Groups
A group is a set paired with an operation that satisfies four properties: closure (combining two elements gives another element in the set), associativity, the existence of an identity element, and the existence of inverses.
The group we encounter most often in cryptography is Z*_p — the integers from 1 to p-1 under multiplication mod p, where p is prime. For p = 7, the group is {1, 2, 3, 4, 5, 6} with multiplication mod 7. Its size (or order) is p - 1 = 6.
Subgroups
A subgroup is a subset of a group that is itself a group under the same operation. Not every subset qualifies — it must be closed, contain the identity, and contain inverses for all its elements.
Generators
An element g is a generator if its repeated powers — g^1, g^2, g^3, ... mod p — produce an entire subgroup. If g generates the full group Z*_p, it’s called a primitive root.
Order
The order of an element g is how many distinct powers it cycles through before returning to 1.
g^1, g^2, g^3, ..., g^q ≡ 1 mod p
^
order = q
After this point, everything repeats: g^(q+1) = g^1, g^(q+2) = g^2, and so on.
Two examples with p = 7 make this concrete.
g = 2:
2^1 mod 7 = 2
2^2 mod 7 = 4
2^3 mod 7 = 1 ← wraps
Subgroup: {1, 2, 4}. Order: 3.
g = 3:
3^1 mod 7 = 3
3^2 mod 7 = 2
3^3 mod 7 = 6
3^4 mod 7 = 4
3^5 mod 7 = 5
3^6 mod 7 = 1 ← wraps
Subgroup: {1, 2, 3, 4, 5, 6} — the entire group. Order: 6. Since 6 = p - 1, g = 3 is a primitive root of 7.
Lagrange’s Theorem
The order of any subgroup must divide the order of the full group.
For Z*_7 (order 6), the possible subgroup orders are 1, 2, 3, and 6. That’s why g = 2 has order 3 (divides 6) and g = 3 has order 6 (divides 6). You’ll never find a subgroup of order 4 or 5 in this group.
This isn’t a coincidence — it’s a structural constraint. It also means that if you know the order of the full group, you know exactly which subgroup sizes are possible.
Why This Matters for Cryptographic Protocols
Safe Primes
In the Schnorr protocol and many others, p is chosen such that p = 2q + 1 where both p and q are prime. This is called a safe prime.
The full group Z*_p has order p - 1 = 2q. By Lagrange’s theorem, the only possible subgroup orders are 1, 2, q, and 2q. Picking a generator g with order q gives a large prime-order subgroup — and prime-order subgroups have no non-trivial substructure an attacker could exploit.
Why Exponents Wrap Mod q
Since g^q = 1 mod p, raising g to any power is equivalent to raising it to that power reduced mod q:
g^(q+5) = g^q * g^5 = 1 * g^5 = g^5
This is why the Schnorr protocol computes z = r + e*w mod q — the modular reduction in the exponent is not a choice but a consequence of the group structure.
The Discrete Logarithm Problem
Given y = g^w mod p, computing the forward direction (g, w, p → y) is fast. Computing the reverse (g, y, p → w) is believed to be hard when q is large and prime. No efficient algorithm is known.
This asymmetry is the foundation of Schnorr, Diffie-Hellman, DSA, and ElGamal. The entire security model rests on the assumption that discrete logarithms in large prime-order subgroups are computationally infeasible.