SharedCrypto_Fall_19 / slides / day18 / cyclic_groups.sagewsOpen in CoCalc
Author: Hunter Johnson
Views : 17
License: MIT License
Description: Cryptography lesson on cyclic groups

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

  • Zn\mathbb{Z}_n is addition modulo nn.
  • Zn\mathbb{Z}_n^* is multiplication modulo nn on elements coprime to nn.
  • The multiplicative part of GF(pk)GF(p^k).
  • Elliptic curve groups.

Multiplicative or additive notation

When we talk about a generic group GG 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,+)(G,+)

  • The identity is 0
  • The inverse of aa is a-a
  • na=a+a+a++antimesna = \underbrace{a+a+a+\cdots+a}_{n\,times}.
  • The DLP: Solve for nn in the equation: na=bna = b.

Multiplicative or additive notation

When we talk about a generic group GG 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,)(G,\cdot)

  • The identity is 1
  • The inverse of aa is a1a^{-1}
  • an=aaaantimesa^n = \underbrace{a\cdot a \cdot a \cdots a}_{n\,times}.
  • The DLP: Solve for nn in the equation: an=ba^n = b.

The order of an element

Given aa in GG, the order of aa is the smallest positive integer kk such that ak=1a^k = 1.

G = Zmod(397) g = G.random_element() g
198
g.multiplicative_order()
44
for k in range(g.multiplicative_order()+1): print("g^{:2} = {:3}".format(k,g^k))
g^ 0 = 1 g^ 1 = 198 g^ 2 = 298 g^ 3 = 248 g^ 4 = 273 g^ 5 = 62 g^ 6 = 366 g^ 7 = 214 g^ 8 = 290 g^ 9 = 252 g^10 = 271 g^11 = 63 g^12 = 167 g^13 = 115 g^14 = 141 g^15 = 128 g^16 = 333 g^17 = 32 g^18 = 381 g^19 = 8 g^20 = 393 g^21 = 2 g^22 = 396 g^23 = 199 g^24 = 99 g^25 = 149 g^26 = 124 g^27 = 335 g^28 = 31 g^29 = 183 g^30 = 107 g^31 = 145 g^32 = 126 g^33 = 334 g^34 = 230 g^35 = 282 g^36 = 256 g^37 = 269 g^38 = 64 g^39 = 365 g^40 = 16 g^41 = 389 g^42 = 4 g^43 = 395 g^44 = 1
## The order of g is the size of the set it can generate len(set([g^k for k in range(G.order())]))
44
euler_phi(397)/44
9
## The order of g divides |G| euler_phi(397)%g.multiplicative_order()
0

Cyclic groups

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

In other words some single element generates GG.

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

Theorem

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

## Empirical check: r = randint(0,2193821983798217) p = next_prime(r) G = Zmod(p) G.multiplicative_group_is_cyclic()
True
## Not true for all composite numbers: Zmod(8).multiplicative_group_is_cyclic()
False
def show_orders(n): """Print the orders of the elements of Z_n^*""" print("The multiplicative orders of the elements of Z_{}".format(n)) for g in Zmod(n): if gcd(g,n) != 1: continue print("the order of {} is {}".format(g,g.multiplicative_order())) show_orders(19)
The multiplicative orders of the elements of Z_19 the order of 1 is 1 the order of 2 is 18 the order of 3 is 18 the order of 4 is 9 the order of 5 is 9 the order of 6 is 9 the order of 7 is 3 the order of 8 is 6 the order of 9 is 9 the order of 10 is 18 the order of 11 is 3 the order of 12 is 6 the order of 13 is 18 the order of 14 is 18 the order of 15 is 18 the order of 16 is 9 the order of 17 is 9 the order of 18 is 2

Theorem

For every element gg of a finite group GG, the order of gg divides G|G|.

Proof:

Let gGg \in G be given:

aGa=aGga=gGaGa\displaystyle \prod_{a \in G} a = \prod_{a \in G} ga = g^{|G|} \prod_{a\in G} a

Therefore

1=gG1 = g^{|G|}

This implies that the order of gg divides G|G|.

It also generalizes FLT to finite groups.

Theorem

Let GG be a finite cyclic group. Then

  1. The number of primitive elements of GG is φ(G)\varphi(|G|).
  2. If G|G| is prime, then all elements a1a \neq 1 in GG are primitive.
p = next_prime(293847) G = Zmod(p) generators = [g for g in G if g != 0 and g.multiplicative_order()==p-1] len(generators) == euler_phi(p-1)
True

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

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

# Any element is a generator of the additive group Z_p n=7 r = randint(1,7) for g in range(1,7): print((g*r)%n)
4 1 5 2 6 3

Subgroups

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

Example of a subgroup

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

Check closure:

Let 7j7^j and 7k7^k be two powers of 7 mod nn for integers j,kj,k.

Then

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

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

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 Zn\mathbb{Z}_n^*) and so we get the following theorem of group theory:

Theorem: Cyclic subgroup theorem

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

Proof:

In our subgroup example, replace Zn\mathbb{Z}_n^* with GG and 77 with aa.

Enumerating all cyclic subgroups

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

Here is an example of that happening.

## Enumerate all cyclic subgroups of Z_n^* n = 16 G = Zmod(n) print("Working modulo {}".format(n)) for a in range(n): if gcd(a,n) != 1: continue print("The subgroup generated by {} is:".format(a)) subgroup = [power_mod(a,k,n) for k in range(G(a).multiplicative_order())] print(sorted(subgroup))
Working modulo 16 The subgroup generated by 1 is: [1] The subgroup generated by 3 is: [1, 3, 9, 11] The subgroup generated by 5 is: [1, 5, 9, 13] The subgroup generated by 7 is: [1, 7] The subgroup generated by 9 is: [1, 9] The subgroup generated by 11 is: [1, 3, 9, 11] The subgroup generated by 13 is: [1, 5, 9, 13] The subgroup generated by 15 is: [1, 15]

Observation

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

Also observe that some distinct subgroups have the same cardinality.

An example of this is H={1,9}H=\{1,9\} and K={1,15}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=16n=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!

Z16\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.

## Enumerate all cyclic subgroups of Z_n^* n = 23 G = Zmod(n) print("Working modulo {}".format(n)) for a in range(n): if gcd(a,n) != 1: continue print("The subgroup generated by {} is:".format(a)) subgroup = [power_mod(a,k,n) for k in range(G(a).multiplicative_order())] print(sorted(subgroup))
Working modulo 23 The subgroup generated by 1 is: [1] The subgroup generated by 2 is: [1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18] The subgroup generated by 3 is: [1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18] The subgroup generated by 4 is: [1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18] The subgroup generated by 5 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22] The subgroup generated by 6 is: [1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18] The subgroup generated by 7 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22] The subgroup generated by 8 is: [1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18] The subgroup generated by 9 is: [1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18] The subgroup generated by 10 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22] The subgroup generated by 11 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22] The subgroup generated by 12 is: [1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18] The subgroup generated by 13 is: [1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18] The subgroup generated by 14 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22] The subgroup generated by 15 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22] The subgroup generated by 16 is: [1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18] The subgroup generated by 17 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22] The subgroup generated by 18 is: [1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18] The subgroup generated by 19 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22] The subgroup generated by 20 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22] The subgroup generated by 21 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22] The subgroup generated by 22 is: [1, 22]

Thinking about subgroups

In the above example we saw that most subgroups of Z23\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 231=2223-1 = 22.

But 2323 is a safe prime because 22=21122=2\cdot11 (p1p-1 is twice a prime).

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

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

## Enumerate all cyclic subgroups of Z_n^* n = 37 G = Zmod(n) print("Working modulo {}".format(n)) for a in range(n): if gcd(a,n) != 1: continue print("The subgroup generated by {} is:".format(a)) subgroup = [power_mod(a,k,n) for k in range(G(a).multiplicative_order())] print(sorted(subgroup))
Working modulo 37 The subgroup generated by 1 is: [1] The subgroup generated by 2 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] The subgroup generated by 3 is: [1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 36] The subgroup generated by 4 is: [1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 36] The subgroup generated by 5 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] The subgroup generated by 6 is: [1, 6, 31, 36] The subgroup generated by 7 is: [1, 7, 9, 10, 12, 16, 26, 33, 34] The subgroup generated by 8 is: [1, 6, 8, 10, 11, 14, 23, 26, 27, 29, 31, 36] The subgroup generated by 9 is: [1, 7, 9, 10, 12, 16, 26, 33, 34] The subgroup generated by 10 is: [1, 10, 26] The subgroup generated by 11 is: [1, 10, 11, 26, 27, 36] The subgroup generated by 12 is: [1, 7, 9, 10, 12, 16, 26, 33, 34] The subgroup generated by 13 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] The subgroup generated by 14 is: [1, 6, 8, 10, 11, 14, 23, 26, 27, 29, 31, 36] The subgroup generated by 15 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] The subgroup generated by 16 is: [1, 7, 9, 10, 12, 16, 26, 33, 34] The subgroup generated by 17 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] The subgroup generated by 18 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] The subgroup generated by 19 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] The subgroup generated by 20 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] The subgroup generated by 21 is: [1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 36] The subgroup generated by 22 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] The subgroup generated by 23 is: [1, 6, 8, 10, 11, 14, 23, 26, 27, 29, 31, 36] The subgroup generated by 24 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] The subgroup generated by 25 is: [1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 36] The subgroup generated by 26 is: [1, 10, 26] The subgroup generated by 27 is: [1, 10, 11, 26, 27, 36] The subgroup generated by 28 is: [1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 36] The subgroup generated by 29 is: [1, 6, 8, 10, 11, 14, 23, 26, 27, 29, 31, 36] The subgroup generated by 30 is: [1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 36] The subgroup generated by 31 is: [1, 6, 31, 36] The subgroup generated by 32 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] The subgroup generated by 33 is: [1, 7, 9, 10, 12, 16, 26, 33, 34] The subgroup generated by 34 is: [1, 7, 9, 10, 12, 16, 26, 33, 34] The subgroup generated by 35 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] The subgroup generated by 36 is: [1, 36]

Thinking about subgroups

In the case of p=37p=37, p1=36p-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 GG and HH are not cyclic:

Theorem (Lagrange's Theorem)

Let HH be a subgroup of GG. Then H|H| divides G|G|.

Proof sketch

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

Cyclic Subgroup Theorem:

Let GG be a finite cyclic group of order nn and let α\alpha be a generator of GG.

Then for every integer kk that divides nn there exists exactly one cyclic subgroup HH of GG of order kk.

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

HH consists exactly of the elements aGa \in G that satisfy ak=1a^k = 1.

There are no other subgroups.

## Sage example p = 101 G = Zmod(p) alpha = G.multiplicative_generator() alpha
2
divisors(p-1)
[1, 2, 4, 5, 10, 20, 25, 50, 100]
for k in divisors(p-1): generator = alpha^((p-1)//k) subgroup = [generator^j for j in range(generator.multiplicative_order())] print("The following subgroup has generator = {} = alpha^{} (n={} and k={})".format(generator,(p-1)//k,p-1,k)) print(sorted(subgroup))
The following subgroup has generator = 1 = alpha^100 (n=100 and k=1) [1] The following subgroup has generator = 100 = alpha^50 (n=100 and k=2) [1, 100] The following subgroup has generator = 10 = alpha^25 (n=100 and k=4) [1, 10, 91, 100] The following subgroup has generator = 95 = alpha^20 (n=100 and k=5) [1, 36, 84, 87, 95] The following subgroup has generator = 14 = alpha^10 (n=100 and k=10) [1, 6, 14, 17, 36, 65, 84, 87, 95, 100] The following subgroup has generator = 32 = alpha^5 (n=100 and k=20) [1, 6, 10, 14, 17, 32, 36, 39, 41, 44, 57, 60, 62, 65, 69, 84, 87, 91, 95, 100] The following subgroup has generator = 16 = alpha^4 (n=100 and k=25) [1, 5, 16, 19, 24, 25, 31, 36, 37, 52, 54, 56, 58, 68, 71, 78, 79, 80, 81, 84, 87, 88, 92, 95, 97] The following subgroup has generator = 4 = alpha^2 (n=100 and k=50) [1, 4, 5, 6, 9, 13, 14, 16, 17, 19, 20, 21, 22, 23, 24, 25, 30, 31, 33, 36, 37, 43, 45, 47, 49, 52, 54, 56, 58, 64, 65, 68, 70, 71, 76, 77, 78, 79, 80, 81, 82, 84, 85, 87, 88, 92, 95, 96, 97, 100] The following subgroup has generator = 2 = alpha^1 (n=100 and k=100) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]

Safe primes again

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

Recall that pp is safe if p1=2qp-1 = 2q where qq is prime.

You can see from the definition that the only divisors of p1p-1 are 1, 2, qq, and p1p-1.

Let's see an example.

def next_safe_prime(n): n = next_prime(n) while True: if is_prime((n-1)//2): break n = next_prime(n+1) print(n,factor(n-1)) return n next_safe_prime(100)
(103, 2 * 3 * 17) (107, 2 * 53) 107
p = 107 G = Zmod(p) alpha = G.multiplicative_generator() alpha
2
divisors(p-1)
[1, 2, 53, 106]
for k in divisors(p-1): generator = alpha^((p-1)//k) subgroup = [generator^j for j in range(generator.multiplicative_order())] print("The following subgroup has generator = {} = alpha^{} (n={} and k={})".format(generator,(p-1)//k,p-1,k)) print(sorted(subgroup))
The following subgroup has generator = 1 = alpha^106 (n=106 and k=1) [1] The following subgroup has generator = 106 = alpha^53 (n=106 and k=2) [1, 106] The following subgroup has generator = 4 = alpha^2 (n=106 and k=53) [1, 3, 4, 9, 10, 11, 12, 13, 14, 16, 19, 23, 25, 27, 29, 30, 33, 34, 35, 36, 37, 39, 40, 41, 42, 44, 47, 48, 49, 52, 53, 56, 57, 61, 62, 64, 69, 75, 76, 79, 81, 83, 85, 86, 87, 89, 90, 92, 99, 100, 101, 102, 105] The following subgroup has generator = 2 = alpha^1 (n=106 and k=106) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106]

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 qq is only one less than pp, so even if the base is in the subgroup of size qq, this is okay.

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

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

And since pp is prime this is only true for α=p1\alpha = p-1.

It's similarly easy to see if the order of α\alpha is qq.

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.

[email protected]:~/.ssh$ openssl dhparam -out dh.pem 512
Generating DH parameters, 512 bit long safe prime, generator 2
This is going to take a long time
......................................................+......................+........++*++*++*++*++*
[email protected]:~/.ssh$ openssl dhparam -text -in dh.pem
    DH Parameters: (512 bit)
        prime:
            00:e2:e8:54:d3:75:f1:0a:2d:90:c1:5d:54:82:1e:
            b5:75:f7:23:06:41:7c:d3:d9:23:9c:39:b7:ae:fb:
            a0:eb:9d:be:93:da:65:0a:ea:13:84:49:eb:04:11:
            ad:dc:dc:62:41:2a:aa:92:bb:52:02:a0:37:14:0b:
            cc:fa:2d:36:43
        generator: 2 (0x2)
-----BEGIN DH PARAMETERS-----
MEYCQQDi6FTTdfEKLZDBXVSCHrV19yMGQXzT2SOcObeu+6Drnb6T2mUK6hOESesE
Ea3c3GJBKqqSu1ICoDcUC8z6LTZDAgEC
-----END DH PARAMETERS-----
p = """00:e2:e8:54:d3:75:f1:0a:2d:90:c1:5d:54:82:1e: b5:75:f7:23:06:41:7c:d3:d9:23:9c:39:b7:ae:fb: a0:eb:9d:be:93:da:65:0a:ea:13:84:49:eb:04:11: ad:dc:dc:62:41:2a:aa:92:bb:52:02:a0:37:14:0b: cc:fa:2d:36:43""" p = p.replace(':','').replace('\n','').replace('\t','').replace(' ','') p = int(p,16) p
11884112392174931525551803878284316468547743675014443360835956479033078578449820213217260145091693859837332463855747972651088419742292198211998500015388227L
is_prime(p)
True
q = (p-1)//2 q
5942056196087465762775901939142158234273871837507221680417978239516539289224910106608630072545846929918666231927873986325544209871146099105999250007694113
is_prime(q)
True
G=Zmod(p) alpha = G(2) alpha^(q)
11884112392174931525551803878284316468547743675014443360835956479033078578449820213217260145091693859837332463855747972651088419742292198211998500015388226

Safe prime

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

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

But in that case we would have observed αq=1\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 GG with the group operation \circ and cardinality nn.

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

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

β=αααxtimes=αx\beta = \underbrace{\alpha\circ \alpha \circ \cdots \circ \alpha}_{x\, times} = \alpha^x

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 Zp\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 Zp\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 Zp\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.

### Below we use Sage to investigate an elliptic curve E with 10 elements. ### We show that (0:7:1) is a generator. ### Note that elliptic curve groups use additive notation.
E=EllipticCurve(GF(11),[2,5]) E
Elliptic Curve defined by y^2 = x^3 + 2*x + 5 over Finite Field of size 11
E.cardinality()
10
g = E.an_element() g
(0 : 7 : 1)
2*g
(9 : 9 : 1)
3*g
(3 : 7 : 1)
4*g
(8 : 4 : 1)
5*g
(4 : 0 : 1)
6*g
(8 : 7 : 1)
7*g
(3 : 4 : 1)
8*g
(9 : 2 : 1)
9*g
(0 : 4 : 1)
10*g
(0 : 1 : 0)

Cyclic group theorem applied to elliptic curves...

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

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

for g in E: print("The order of {} is {}".format(g,g.order()))
The order of (0 : 1 : 0) is 1 The order of (0 : 4 : 1) is 10 The order of (0 : 7 : 1) is 10 The order of (3 : 4 : 1) is 10 The order of (3 : 7 : 1) is 10 The order of (4 : 0 : 1) is 2 The order of (8 : 4 : 1) is 5 The order of (8 : 7 : 1) is 5 The order of (9 : 2 : 1) is 5 The order of (9 : 9 : 1) is 5
euler_phi(10)
4
alpha = E.an_element() for k in divisors(10): generator = (10//k)*alpha subgroup = [j*generator for j in range(generator.order())] print("The following subgroup has generator = {} = {}*alpha (n={} and k={})".format(generator,(10//k),10,k)) print(sorted(subgroup))
The following subgroup has generator = (0 : 1 : 0) = 10*alpha (n=10 and k=1) [(0 : 1 : 0)] The following subgroup has generator = (4 : 0 : 1) = 5*alpha (n=10 and k=2) [(0 : 1 : 0), (4 : 0 : 1)] The following subgroup has generator = (9 : 9 : 1) = 2*alpha (n=10 and k=5) [(0 : 1 : 0), (8 : 4 : 1), (8 : 7 : 1), (9 : 2 : 1), (9 : 9 : 1)] The following subgroup has generator = (0 : 7 : 1) = 1*alpha (n=10 and k=10) [(0 : 1 : 0), (0 : 4 : 1), (0 : 7 : 1), (3 : 4 : 1), (3 : 7 : 1), (4 : 0 : 1), (8 : 4 : 1), (8 : 7 : 1), (9 : 2 : 1), (9 : 9 : 1)]

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

It turns out Galois Fields are cyclic. paper

n = 256 G = GF(n,'x') alpha = [f for f in G if f != 0 and f.multiplicative_order()==n-1][0] ## Get a generator print("alpha = {}, alpha.order() = {}".format(alpha,alpha.multiplicative_order())) for k in divisors((n-1)): generator = alpha^((n-1)//k) subgroup = [generator^j for j in range(generator.multiplicative_order())] print("The following subgroup has generator = {} = alpha^{} (|G|={} and k={})".format(generator,((n-1)//k),(n-1),k)) print(sorted(subgroup))
alpha = x, alpha.order() = 255 The following subgroup has generator = 1 = alpha^255 (|G|=255 and k=1) [1] The following subgroup has generator = x^7 + x^6 + x^4 + x^2 + x = alpha^85 (|G|=255 and k=3) [1, x^7 + x^6 + x^4 + x^2 + x, x^7 + x^6 + x^4 + x^2 + x + 1] The following subgroup has generator = x^3 + x = alpha^51 (|G|=255 and k=5) [1, x^3 + x, x^6 + x^2, x^7 + x^4 + x, x^7 + x^6 + x^4 + x^3 + x^2 + 1] The following subgroup has generator = x^7 + x^4 + x^3 = alpha^17 (|G|=255 and k=15) [1, x^3 + x, x^3 + x + 1, x^6 + x^2, x^6 + x^2 + 1, x^6 + x^3 + x^2 + x, x^6 + x^3 + x^2 + x + 1, x^7 + x^4 + x, x^7 + x^4 + x + 1, x^7 + x^4 + x^3, x^7 + x^4 + x^3 + 1, x^7 + x^6 + x^4 + x^2 + x, x^7 + x^6 + x^4 + x^2 + x + 1, x^7 + x^6 + x^4 + x^3 + x^2, x^7 + x^6 + x^4 + x^3 + x^2 + 1] The following subgroup has generator = x^5 + x^2 + x = alpha^15 (|G|=255 and k=17) [1, x^3 + x^2 + x + 1, x^4 + x^3 + x, x^5 + x^2, x^5 + x^2 + x, x^5 + x^3 + x^2, x^5 + x^4 + x^3 + x + 1, x^6 + x^4 + x^2 + 1, x^6 + x^4 + x^3 + 1, x^6 + x^5, x^6 + x^5 + x^2, x^7 + x^4 + 1, x^7 + x^4 + x^2 + x, x^7 + x^5 + x^3 + 1, x^7 + x^5 + x^4 + x^3 + 1, x^7 + x^6 + 1, x^7 + x^6 + x^4 + x^3 + x^2 + x + 1] The following subgroup has generator = x^5 = alpha^5 (|G|=255 and k=51) [1, x + 1, x^2 + 1, x^3 + x^2 + x + 1, x^4 + 1, x^4 + x^3 + x, x^4 + x^3 + x^2, x^5, x^5 + x^2, x^5 + x^2 + x, x^5 + x^3 + x^2, x^5 + x^3 + x^2 + x, x^5 + x^4 + x + 1, x^5 + x^4 + x^2 + x + 1, x^5 + x^4 + x^3 + x + 1, x^6 + x^3 + x^2 + 1, x^6 + x^4 + x^2 + 1, x^6 + x^4 + x^3 + 1, x^6 + x^4 + x^3 + x^2 + x, x^6 + x^5, x^6 + x^5 + x^2, x^6 + x^5 + x^2 + x + 1, x^6 + x^5 + x^3 + x, x^6 + x^5 + x^3 + x^2, x^6 + x^5 + x^4 + x, x^6 + x^5 + x^4 + x^2, x^6 + x^5 + x^4 + x^3 + x^2, x^7 + x^2, x^7 + x^4 + 1, x^7 + x^4 + x^2 + x, x^7 + x^4 + x^3 + x^2, x^7 + x^5, x^7 + x^5 + x^2 + x + 1, x^7 + x^5 + x^3 + 1, x^7 + x^5 + x^3 + x^2, x^7 + x^5 + x^3 + x^2 + x, x^7 + x^5 + x^4 + x^2, x^7 + x^5 + x^4 + x^3 + 1, x^7 + x^5 + x^4 + x^3 + x^2 + x, x^7 + x^6 + 1, x^7 + x^6 + x^4 + x^2 + x, x^7 + x^6 + x^4 + x^2 + x + 1, x^7 + x^6 + x^4 + x^3 + x^2 + x + 1, x^7 + x^6 + x^5 + x, x^7 + x^6 + x^5 + x^2 + x, x^7 + x^6 + x^5 + x^3 + 1, x^7 + x^6 + x^5 + x^3 + x + 1, x^7 + x^6 + x^5 + x^3 + x^2 + x + 1, x^7 + x^6 + x^5 + x^4 + x^2, x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + 1, x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1] The following subgroup has generator = x^3 = alpha^3 (|G|=255 and k=85) [1, x^2 + x + 1, x^3, x^3 + x, x^3 + x^2, x^3 + x^2 + x + 1, x^4 + x^2 + 1, x^4 + x^2 + x + 1, x^4 + x^3 + x, x^5 + 1, x^5 + x^2, x^5 + x^2 + 1, x^5 + x^2 + x, x^5 + x^2 + x + 1, x^5 + x^3 + 1, x^5 + x^3 + x^2, x^5 + x^3 + x^2 + 1, x^5 + x^3 + x^2 + x + 1, x^5 + x^4 + x^2 + 1, x^5 + x^4 + x^2 + x, x^5 + x^4 + x^3, x^5 + x^4 + x^3 + x, x^5 + x^4 + x^3 + x + 1, x^5 + x^4 + x^3 + x^2 + 1, x^5 + x^4 + x^3 + x^2 + x, x^6, x^6 + x^2, x^6 + x^2 + x, x^6 + x^4, x^6 + x^4 + x^2 + 1, x^6 + x^4 + x^2 + x, x^6 + x^4 + x^2 + x + 1, x^6 + x^4 + x^3 + 1, x^6 + x^5, x^6 + x^5 + 1, x^6 + x^5 + x^2, x^6 + x^5 + x^2 + 1, x^6 + x^5 + x^2 + x, x^6 + x^5 + x^3 + x + 1, x^6 + x^5 + x^3 + x^2 + x, x^6 + x^5 + x^4 + x + 1, x^6 + x^5 + x^4 + x^2 + 1, x^6 + x^5 + x^4 + x^3, x^6 + x^5 + x^4 + x^3 + x^2 + 1, x^6 + x^5 + x^4 + x^3 + x^2 + x + 1, x^7 + x, x^7 + x^2 + x, x^7 + x^3 + x, x^7 + x^3 + x + 1, x^7 + x^3 + x^2 + x + 1, x^7 + x^4 + 1, x^7 + x^4 + x, x^7 + x^4 + x^2 + x, x^7 + x^5 + 1, x^7 + x^5 + x^2 + x, x^7 + x^5 + x^3, x^7 + x^5 + x^3 + 1, x^7 + x^5 + x^3 + x^2 + 1, x^7 + x^5 + x^4 + x + 1, x^7 + x^5 + x^4 + x^2 + 1, x^7 + x^5 + x^4 + x^2 + x, x^7 + x^5 + x^4 + x^3, x^7 + x^5 + x^4 + x^3 + 1, x^7 + x^5 + x^4 + x^3 + x, x^7 + x^5 + x^4 + x^3 + x^2 + x + 1, x^7 + x^6 + 1, x^7 + x^6 + x + 1, x^7 + x^6 + x^2, x^7 + x^6 + x^2 + 1, x^7 + x^6 + x^3 + x^2 + 1, x^7 + x^6 + x^3 + x^2 + x, x^7 + x^6 + x^3 + x^2 + x + 1, x^7 + x^6 + x^4, x^7 + x^6 + x^4 + x^3 + 1, x^7 + x^6 + x^4 + x^3 + x + 1, x^7 + x^6 + x^4 + x^3 + x^2 + 1, x^7 + x^6 + x^4 + x^3 + x^2 + x + 1, x^7 + x^6 + x^5 + x^2, x^7 + x^6 + x^5 + x^2 + x + 1, x^7 + x^6 + x^5 + x^3 + x^2 + 1, x^7 + x^6 + x^5 + x^4 + 1, x^7 + x^6 + x^5 + x^4 + x, x^7 + x^6 + x^5 + x^4 + x^2 + 1, x^7 + x^6 + x^5 + x^4 + x^3 + x + 1, x^7 + x^6 + x^5 + x^4 + x^3 + x^2] The following subgroup has generator = x = alpha^1 (|G|=255 and k=255) [1, x, x + 1, x^2, x^2 + 1, x^2 + x, x^2 + x + 1, x^3, x^3 + 1, x^3 + x, x^3 + x + 1, x^3 + x^2, x^3 + x^2 + 1, x^3 + x^2 + x, x^3 + x^2 + x + 1, x^4, x^4 + 1, x^4 + x, x^4 + x + 1, x^4 + x^2, x^4 + x^2 + 1, x^4 + x^2 + x, x^4 + x^2 + x + 1, x^4 + x^3, x^4 + x^3 + 1, x^4 + x^3 + x, x^4 + x^3 + x + 1, x^4 + x^3 + x^2, x^4 + x^3 + x^2 + 1, x^4 + x^3 + x^2 + x, x^4 + x^3 + x^2 + x + 1, x^5, x^5 + 1, x^5 + x, x^5 + x + 1, x^5 + x^2, x^5 + x^2 + 1, x^5 + x^2 + x, x^5 + x^2 + x + 1, x^5 + x^3, x^5 + x^3 + 1, x^5 + x^3 + x, x^5 + x^3 + x + 1, x^5 + x^3 + x^2, x^5 + x^3 + x^2 + 1, x^5 + x^3 + x^2 + x, x^5 + x^3 + x^2 + x + 1, x^5 + x^4, x^5 + x^4 + 1, x^5 + x^4 + x, x^5 + x^4 + x + 1, x^5 + x^4 + x^2, x^5 + x^4 + x^2 + 1, x^5 + x^4 + x^2 + x, x^5 + x^4 + x^2 + x + 1, x^5 + x^4 + x^3, x^5 + x^4 + x^3 + 1, x^5 + x^4 + x^3 + x, x^5 + x^4 + x^3 + x + 1, x^5 + x^4 + x^3 + x^2, x^5 + x^4 + x^3 + x^2 + 1, x^5 + x^4 + x^3 + x^2 + x, x^5 + x^4 + x^3 + x^2 + x + 1, x^6, x^6 + 1, x^6 + x, x^6 + x + 1, x^6 + x^2, x^6 + x^2 + 1, x^6 + x^2 + x, x^6 + x^2 + x + 1, x^6 + x^3, x^6 + x^3 + 1, x^6 + x^3 + x, x^6 + x^3 + x + 1, x^6 + x^3 + x^2, x^6 + x^3 + x^2 + 1, x^6 + x^3 + x^2 + x, x^6 + x^3 + x^2 + x + 1, x^6 + x^4, x^6 + x^4 + 1, x^6 + x^4 + x, x^6 + x^4 + x + 1, x^6 + x^4 + x^2, x^6 + x^4 + x^2 + 1, x^6 + x^4 + x^2 + x, x^6 + x^4 + x^2 + x + 1, x^6 + x^4 + x^3, x^6 + x^4 + x^3 + 1, x^6 + x^4 + x^3 + x, x^6 + x^4 + x^3 + x + 1, x^6 + x^4 + x^3 + x^2, x^6 + x^4 + x^3 + x^2 + 1, x^6 + x^4 + x^3 + x^2 + x, x^6 + x^4 + x^3 + x^2 + x + 1, x^6 + x^5, x^6 + x^5 + 1, x^6 + x^5 + x, x^6 + x^5 + x + 1, x^6 + x^5 + x^2, x^6 + x^5 + x^2 + 1, x^6 + x^5 + x^2 + x, x^6 + x^5 + x^2 + x + 1, x^6 + x^5 + x^3, x^6 + x^5 + x^3 + 1, x^6 + x^5 + x^3 + x, x^6 + x^5 + x^3 + x + 1, x^6 + x^5 + x^3 + x^2, x^6 + x^5 + x^3 + x^2 + 1, x^6 + x^5 + x^3 + x^2 + x, x^6 + x^5 + x^3 + x^2 + x + 1, x^6 + x^5 + x^4, x^6 + x^5 + x^4 + 1, x^6 + x^5 + x^4 + x, x^6 + x^5 + x^4 + x + 1, x^6 + x^5 + x^4 + x^2, x^6 + x^5 + x^4 + x^2 + 1, x^6 + x^5 + x^4 + x^2 + x, x^6 + x^5 + x^4 + x^2 + x + 1, x^6 + x^5 + x^4 + x^3, x^6 + x^5 + x^4 + x^3 + 1, x^6 + x^5 + x^4 + x^3 + x, x^6 + x^5 + x^4 + x^3 + x + 1, x^6 + x^5 + x^4 + x^3 + x^2, x^6 + x^5 + x^4 + x^3 + x^2 + 1, x^6 + x^5 + x^4 + x^3 + x^2 + x, x^6 + x^5 + x^4 + x^3 + x^2 + x + 1, x^7, x^7 + 1, x^7 + x, x^7 + x + 1, x^7 + x^2, x^7 + x^2 + 1, x^7 + x^2 + x, x^7 + x^2 + x + 1, x^7 + x^3, x^7 + x^3 + 1, x^7 + x^3 + x, x^7 + x^3 + x + 1, x^7 + x^3 + x^2, x^7 + x^3 + x^2 + 1, x^7 + x^3 + x^2 + x, x^7 + x^3 + x^2 + x + 1, x^7 + x^4, x^7 + x^4 + 1, x^7 + x^4 + x, x^7 + x^4 + x + 1, x^7 + x^4 + x^2, x^7 + x^4 + x^2 + 1, x^7 + x^4 + x^2 + x, x^7 + x^4 + x^2 + x + 1, x^7 + x^4 + x^3, x^7 + x^4 + x^3 + 1, x^7 + x^4 + x^3 + x, x^7 + x^4 + x^3 + x + 1, x^7 + x^4 + x^3 + x^2, x^7 + x^4 + x^3 + x^2 + 1, x^7 + x^4 + x^3 + x^2 + x, x^7 + x^4 + x^3 + x^2 + x + 1, x^7 + x^5, x^7 + x^5 + 1, x^7 + x^5 + x, x^7 + x^5 + x + 1, x^7 + x^5 + x^2, x^7 + x^5 + x^2 + 1, x^7 + x^5 + x^2 + x, x^7 + x^5 + x^2 + x + 1, x^7 + x^5 + x^3, x^7 + x^5 + x^3 + 1, x^7 + x^5 + x^3 + x, x^7 + x^5 + x^3 + x + 1, x^7 + x^5 + x^3 + x^2, x^7 + x^5 + x^3 + x^2 + 1, x^7 + x^5 + x^3 + x^2 + x, x^7 + x^5 + x^3 + x^2 + x + 1, x^7 + x^5 + x^4, x^7 + x^5 + x^4 + 1, x^7 + x^5 + x^4 + x, x^7 + x^5 + x^4 + x + 1, x^7 + x^5 + x^4 + x^2, x^7 + x^5 + x^4 + x^2 + 1, x^7 + x^5 + x^4 + x^2 + x, x^7 + x^5 + x^4 + x^2 + x + 1, x^7 + x^5 + x^4 + x^3, x^7 + x^5 + x^4 + x^3 + 1, x^7 + x^5 + x^4 + x^3 + x, x^7 + x^5 + x^4 + x^3 + x + 1, x^7 + x^5 + x^4 + x^3 + x^2, x^7 + x^5 + x^4 + x^3 + x^2 + 1, x^7 + x^5 + x^4 + x^3 + x^2 + x, x^7 + x^5 + x^4 + x^3 + x^2 + x + 1, x^7 + x^6, x^7 + x^6 + 1, x^7 + x^6 + x, x^7 + x^6 + x + 1, x^7 + x^6 + x^2, x^7 + x^6 + x^2 + 1, x^7 + x^6 + x^2 + x, x^7 + x^6 + x^2 + x + 1, x^7 + x^6 + x^3, x^7 + x^6 + x^3 + 1, x^7 + x^6 + x^3 + x, x^7 + x^6 + x^3 + x + 1, x^7 + x^6 + x^3 + x^2, x^7 + x^6 + x^3 + x^2 + 1, x^7 + x^6 + x^3 + x^2 + x, x^7 + x^6 + x^3 + x^2 + x + 1, x^7 + x^6 + x^4, x^7 + x^6 + x^4 + 1, x^7 + x^6 + x^4 + x, x^7 + x^6 + x^4 + x + 1, x^7 + x^6 + x^4 + x^2, x^7 + x^6 + x^4 + x^2 + 1, x^7 + x^6 + x^4 + x^2 + x, x^7 + x^6 + x^4 + x^2 + x + 1, x^7 + x^6 + x^4 + x^3, x^7 + x^6 + x^4 + x^3 + 1, x^7 + x^6 + x^4 + x^3 + x, x^7 + x^6 + x^4 + x^3 + x + 1, x^7 + x^6 + x^4 + x^3 + x^2, x^7 + x^6 + x^4 + x^3 + x^2 + 1, x^7 + x^6 + x^4 + x^3 + x^2 + x, x^7 + x^6 + x^4 + x^3 + x^2 + x + 1, x^7 + x^6 + x^5, x^7 + x^6 + x^5 + 1, x^7 + x^6 + x^5 + x, x^7 + x^6 + x^5 + x + 1, x^7 + x^6 + x^5 + x^2, x^7 + x^6 + x^5 + x^2 + 1, x^7 + x^6 + x^5 + x^2 + x, x^7 + x^6 + x^5 + x^2 + x + 1, x^7 + x^6 + x^5 + x^3, x^7 + x^6 + x^5 + x^3 + 1, x^7 + x^6 + x^5 + x^3 + x, x^7 + x^6 + x^5 + x^3 + x + 1, x^7 + x^6 + x^5 + x^3 + x^2, x^7 + x^6 + x^5 + x^3 + x^2 + 1, x^7 + x^6 + x^5 + x^3 + x^2 + x, x^7 + x^6 + x^5 + x^3 + x^2 + x + 1, x^7 + x^6 + x^5 + x^4, x^7 + x^6 + x^5 + x^4 + 1, x^7 + x^6 + x^5 + x^4 + x, x^7 + x^6 + x^5 + x^4 + x + 1, x^7 + x^6 + x^5 + x^4 + x^2, x^7 + x^6 + x^5 + x^4 + x^2 + 1, x^7 + x^6 + x^5 + x^4 + x^2 + x, x^7 + x^6 + x^5 + x^4 + x^2 + x + 1, x^7 + x^6 + x^5 + x^4 + x^3, x^7 + x^6 + x^5 + x^4 + x^3 + 1, x^7 + x^6 + x^5 + x^4 + x^3 + x, x^7 + x^6 + x^5 + x^4 + x^3 + x + 1, x^7 + x^6 + x^5 + x^4 + x^3 + x^2, x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + 1, x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x, x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1]