Subgroup

As explained in Real-World Cryptography

A subgroup is a subset of a group that is itself a group under the same operation.

A subgroup is a group contained inside another group: its elements form a subset, operations stay within that subset, and every element has an inverse there. A cyclic subgroup can be generated from one element, called a generator or base. section 5.2.1

Generating a subgroup modulo 5

Using modular multiplication, 4 generates the subgroup {1, 4}: 4 mod 5 = 4, 4 × 4 mod 5 = 1, and the cycle repeats. The number of elements in a subgroup is its order. section 5.2.1

Subgroups matter in Diffie-Hellman because their sizes shape security. For a safe-prime modulus p = 2q + 1, the multiplicative group has order 2q, so its subgroups can have only orders 2 or q. This scarcity prevents small subgroup attacks, in which crafted public keys gradually reveal bits of a private key. section 5.4

Figure 5.6 The different subgroups of the multiplicative group modulo 5. These all include the number 1 (called the identity element) and have different orders (number of elements).

Compare the subgroups of the multiplicative group modulo 5, including their shared identity element and different orders. section 5.2.1

How Real-World Cryptography covers it

How deep it goes

Defines subgroups, works through modular generation, and connects subgroup orders to small subgroup attacks.

Examples

Uses generator 4 modulo 5, subgroup orders, safe-prime groups, and attacker-selected public key −1.

What it assumes

Assumes modular multiplication and group properties, while building subgroup intuition from a concrete modulo-5 example.

What you can do after

Evaluate Diffie-Hellman groups by their subgroup structure and recognize the conditions behind small subgroup attacks.

How it connects

Connects groups, cyclic subgroups, modular multiplication, Diffie-Hellman, safe primes, Lagrange theorem, and small subgroup attacks.

liveBookmanning.com

Read Real-World Cryptography on liveBook Get the book at manning.com

Related concepts

• cyclic subgroupincludes · A cyclic subgroup is a subgroup generated by repeatedly applying its operation to one generator element.
• cyclic grouppart of · A cyclic group is a group generated by a single element, with every element obtainable by applying the group operation repeatedly to that generator.

This explainer was generated by Manning's knowledge graph from the text of Real-World Cryptography. The section links point to the parts of the book it draws on.