Cyclic Group & Generator

Now we know that with modulo, we can have a group with finite set that is what cryptography operation needs. We introduce a concept of Cyclic Group & generator

Definition

Cyclic Group & Generator

A group is cyclic if there exists an element ("a generator") such that every other element of the group can be written as a power of this generator.

Math Expression

Consider the Group $\mathbb{G} = \{1,2,3,...,p−1\}$ with "Modular Multiplication" Operation. $\mathbb{G}$ is cyclic if and only if there exists the element $𝑔$ (called a generator), such that $\{g^1 \ mod\ p\ , g^2 \ mod\ p\ , g^3 \ mod\ p\ , ...,\ g^{p-1}\ mod\ p\}$ = $\mathbb{S}$

Example

Let’s say we work in $\mathbb{Z^*_7}$ (integers modulo 7, excluding 0), which consists of 6. We can check if 3 is a generator as follows: $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$

Since 3 generates all elements of the group $\mathbb{Z^*_7}$, 3 is a generator. Not every element will do this — for instance, 2 in the same group only generates some elements.

The concept of Generator allows us to visit every possible element in our group by simple multiplication. This brings us to one of the most important assumptions in cryptography: the discrete logarithm assumption.”

Definition

Discrete Log Assumption

Hard to know $x$ from $y$ when $y = g^x\ mod\ p$, where $g$ is a generator, and $p$ is large prime

Discrete Log Problem

A specific math problem that asks you to solve $y = g^x\ mod\ p$, , where $g$ is a generator, and $p$ is large prime

Intuition Behind Difficulty

Imagine standing in a circle with numbered positions (the group elements) and repeatedly stepping forward (exponentiation) from some starting point. If I tell you where I end up (the result of exponentiation), it’s very hard for you to figure out how many steps I took (the exponent).

While it’s easy to compute $g^x\ mod\ p$ (even for very large 𝑝), going in reverse — that is, finding 𝑥 given $g^x\ mod\ p$ — is much harder. In the next chapter, we will see that this assumption is a cornerstone of cryptography and underpins protocols like Diffie-Hellman and elliptic curve cryptography.”