Group theory

Recall the definition of a group:

https://en.wikipedia.org/wiki/Group_(mathematics)#Definition

There are tons and tons of groups.

Some are infinite and some are finite.

Cryptography is mostly concerned with finite groups.

Common groups in cryptography

• $\mathbb{Z}_n$ is addition modulo $n$.

• $\mathbb{Z}_n^*$ is multiplication modulo $n$ on elements coprime to $n$.

• The multiplicative part of $GF(p^k)$.

• Elliptic curve groups.

Multiplicative or additive notation

When we talk about a generic group $G$ we will sometimes think of the operation as being multiplication.

Other times we will think of it as being more like addition.

Additive notation: $(G,+)$

• The identity is 0

• The inverse of $a$ is $-a$

• $na = \underbrace{a+a+a+\cdots+a}_{n\,times}$.

• The DLP: Solve for $n$ in the equation: $na = b$.

Multiplicative or additive notation

When we talk about a generic group $G$ we will sometimes think of the operation as being multiplication.

Other times we will think of it as being more like addition.

Multiplicative notation: $(G,\cdot)$

• The identity is 1

• The inverse of $a$ is $a^{-1}$

• $a^n = \underbrace{a\cdot a \cdot a \cdots a}_{n\,times}$.

• The DLP: Solve for $n$ in the equation: $a^n = b$.

The order of an element

Given $a$ in $G$, the order of $a$ is the smallest positive integer $k$ such that $a^k = 1$.

Cyclic groups

The group $G$ is cyclic if it contains an element of order $|G|$.

In other words some single element generates $G$.

There is some $\alpha \in G$ such that every $\beta \in G$ is $\alpha^x$ for some index $x$.

Theorem

For every prime $p$, the group $(\mathbb{Z}_p^*,\cdot)$ is a finite cyclic group.

Theorem

For every element $g$ of a finite group $G$, the order of $g$ divides $|G|$.

Proof:

Let $g \in G$ be given:

$\displaystyle \prod_{a \in G} a = \prod_{a \in G} ga = g^{|G|} \prod_{a\in G} a$

Therefore

$1 = g^{|G|}$

This implies that the order of $g$ divides $|G|$.

It also generalizes FLT to finite groups.

Theorem

Let $G$ be a finite cyclic group. Then

1. The number of primitive elements of $G$ is $\varphi(|G|)$.

2. If $|G|$ is prime, then all elements $a \neq 1$ in $G$ are primitive.

Note that if $p$ is prime then $|\mathbb{Z}_p^*| = p-1$ is never prime.

But when $p$ is prime and $G=\mathbb{Z}_p$, then $|G|=p$, and any element is a generator.

Subgroups

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

Example of a subgroup

The powers of $7$ are a subgroup of the group $\mathbb{Z}_n^*$, whenever $\gcd(7,n)=1$.

Check closure:

Let $7^j$ and $7^k$ be two powers of 7 mod $n$ for integers $j,k$.

Then

$7^j\cdot 7^k \equiv 7^{j+k} \mod n$.

But $7^{j+k}$ is obviously a power of $7$.

Therefore the powers of 7 are closed under the group operation.

Therefore the powers of 7 form a subgroup.

In the above example there is nothing special about 7 (or even $\mathbb{Z}_n^*$) and so we get the following theorem of group theory:

Theorem: Cyclic subgroup theorem

Let $(G,\circ)$ be a finite group. Then every element $a \in G$ with $ord(a)=s$ is the generator of a cyclic subgroup with $s$ elements.

Proof:

In our subgroup example, replace $\mathbb{Z}_n^*$ with $G$ and $7$ with $a$.

Enumerating all cyclic subgroups

It's possible for two different elements of $G$ to generate the same cyclic subgroup.

Here is an example of that happening.

Observation

Notice that the group $\mathbb{Z}_{16}^*$ is not cyclic.

Also observe that some distinct subgroups have the same cardinality.

An example of this is $H=\{1,9\}$ and $K=\{1,15\}$.

We will see below that in a cyclic group this never happens: No two distinct subgroups have the same cardinality in a cyclic group.

Studying cyclic subgroups

In the above example where $n=16$, you can see that 3 and 11 generate the same subgroup.

This happens because 3 is itself a primitive element of the subgroup generated by 11 (and vice versa).

Observe that the intersection of two subgroups is always a subgroup!

$\mathbb{Z}_{16}^*$ is not cyclic and so no subgroup is equal to the whole group.

But the whole group is always a subgroup of itself.

Let's try the same experiment with a cyclic group.

Thinking about subgroups

In the above example we saw that most subgroups of $\mathbb{Z}_{23}^*$ are big.

That is because the orders of the elements determine the orders of the subgroups.

So any subgroup must be a size that divides $23-1 = 22$.

But $23$ is a safe prime because $22=2\cdot11$ ($p-1$ is twice a prime).

The point of a safe prime is exactly that $\mathbb{Z}_p^*$ only has big subgroups (except for the unique subgroup of size 2, $\{1,-1\}$).

Let's try the same experiment with an "unsafe" prime.

Thinking about subgroups

In the case of $p=37$, $p-1=36$ has lots of divisors.

For that reason it has many subgroups, and some of them are too small to be safe from brute force on DLP.

The following is an interesting group theoretic fact that is true even when $G$ and $H$ are not cyclic:

Theorem (Lagrange's Theorem)

Let $H$ be a subgroup of $G$. Then $|H|$ divides $|G|$.

Proof sketch

Sets of the form $gH = \{gh: h \in H\}$ partition $G$.

Cyclic Subgroup Theorem:

Let $G$ be a finite cyclic group of order $n$ and let $\alpha$ be a generator of $G$.

Then for every integer $k$ that divides $n$ there exists exactly one cyclic subgroup $H$ of $G$ of order $k$.

This subgroups is generated by $\alpha^{n/k}$.

$H$ consists exactly of the elements $a \in G$ that satisfy $a^k = 1$.

There are no other subgroups.

Safe primes again

Okay, so what are the subgroups of a safe prime?

Recall that $p$ is safe if $p-1 = 2q$ where $q$ is prime.

You can see from the definition that the only divisors of $p-1$ are 1, 2, $q$, and $p-1$.

Let's see an example.

Safe primes

You can see from the above output that the only really dangerous base for the DLP in this group is the element of order 2.

The number of bits in $q$ is only one less than $p$, so even if the base is in the subgroup of size $q$, this is okay.

And it's really easy to check whether $\alpha$ has order 2:

Just see if $\alpha^2 = 1$.

And since $p$ is prime this is only true for $\alpha = p-1$.

It's similarly easy to see if the order of $\alpha$ is $q$.

Thus for a safe prime we can find a verifiable generator.

Diffie Helman in openssl

Below we will verify that the Diffie Hellman parameters produced by OpenSSL yield a safe prime.

Because of this fact generating DH params takes much longer than RSA params, even if the bit length is the same.

Safe prime

In the above experiment $\alpha^q = p-1$.

Thus we can be sure that the order of $\alpha$ is $p$, because if it were in the subgroup of size $q$ its order would have to divide $q$.

But in that case we would have observed $\alpha^q =1$.

The general DLP

The DLP is a problem that can be stated in any group (not just our simple "mod p") groups.

Definition: The Generalized Discrete Logarithm Problem

Given is a finite cyclic group $G$ with the group operation $\circ$ and cardinality $n$.

We consider a primitive element $\alpha \in G$ and another element $\beta \in G$.

The DLP is finding the integer $x$ where $1 \leq x \leq n$ such that :

Elliptic Curve groups

In particular you can have the DLP in an elliptic curve group.

We won't give the details for this.

But: If we use DLP in $\mathbb{Z}_p^*$ and also DLP in elliptic curve groups, why are the keys for elliptic curve groups so much shorter?

We've seen that for elliptic curves, 256 bits gives 128 bit security, while for $\mathbb{Z}_p^*$ we need about 3000 bits.

Why is one group vulnerable to DLP attacks and the other group not?

Index calculus

The main reason key sizes for elliptic curve groups are smaller is that $\mathbb{Z}_p^*$ is vulnerable to an attack called the index calculus.

Again, we won't go into the details, but you can study this on your own if you want.

No one knows of any way to apply this attack to the DLP in elliptic curve groups.

There is some speculation however that the parameters for elliptic curve groups are backdoored by NSA.

However if this is true, they have not yet bothered to destroy any of the dozens of cryptocurrencies based on a NIST curve.

Cyclic group theorem applied to elliptic curves...

The Cyclic Group theorem still applies to $E$ even though $E$ is "weird".

That's because the theorem applies to any cyclic group, no matter how weird.

The cyclic group theorem applied to $GF(2^8)$

It turns out Galois Fields are cyclic. paper