Groups

Authors: Ariana, Zademn Reviewed by:

Introduction

Modern cryptography is based on the assumption that some problems are hard (unfeasable to solve). Since the we do not have infinite computational power and storage we usually work with finite messages, keys and ciphertexts and we say they lay in some finite sets M,K\mathcal{M}, \mathcal{K} and C\mathcal{C}.

Furthermore, to get a ciphertext we usually perform some operations with the message and the key.

The study of sets, and different types of operations on them is the target of abstract algebra. In this chapter we will learn the underlying building blocks of cryptosystems and some of the hard problems that the cryptosystems are based on.

Definition

A setGGpaired with a binary operation :G×GG\cdot:G\times G\to Gis a group if the following requirements hold:

  • Closure: For all a,bG: a, b \in G: \ abGa\cdot b \in G - Applying the operation keeps the element in the set

  • Associativity: For all a,b,cG:a, b, c \in G: (ab)c=a(bc)(a \cdot b) \cdot c=a\cdot (b\cdot c)

  • Identity: There exists an elementeGe\in Gsuch that ae=ea=aa\cdot e=e\cdot a=afor all aGa\in G

  • Inverse: For all elements aGa\in G, there exists some bGb\in Gsuch that ba=ab=eb\cdot a=a\cdot b=e. We usually denotebbas a1a^{-1}

For nZn\in\mathbb Z, ana^nmeans aaan times\underbrace{a\cdot a\dots{}\cdot a}_{n\text{ times}}when n>0n>0and (an)1\left(a^{-n}\right)^{-1}when n<0n<0. For n=0n=0, an=ea^n=e.

If ab=baab=ba, then \cdotis commutative and the group is called abelian. We often denote the group operation by ++instead of \cdotand we typically use nanainstead of ana^n.

Remark

  • The identity element of a group GG is also denoted with 1G1_G or just 11 if only one groups is present

Examples of groups

Integers modulo nn (remainders) under modular addition =(Z/nZ,+)= (\mathbb{Z} / n \mathbb{Z}, +). Z/nZ={0,1,...,n1}\mathbb{Z} / n \mathbb{Z} = \{0, 1, ..., n -1\} Let's look if the group axioms are satisfied

  1. \checkmark a,bZ/nZ let ca+bmodn\forall a, b \in \mathbb{Z}/ n\mathbb{Z} \text{ let } c \equiv a + b \bmod n. Because of the modulo reduction c<ncZ/nZc < n \Rightarrow c \in \mathbb{Z}/ n\mathbb{Z}

  2. \checkmarkModular addition is associative

  3. \checkmark 0+aa+0amodn00 + a \equiv a + 0 \equiv a \bmod n \Rightarrow 0 is the identity element

  4. \checkmarkaZ/nZ\forall a \in \mathbb{Z}/ n\mathbb{Z} we take namodnn - a \bmod nto be the inverse of aa. We check that

    a+nan0modna + n - a \equiv n \equiv 0 \bmod n

    na+an0modnn - a + a \equiv n \equiv 0 \bmod n

Therefore we can conclude that the integers mod nn with the modular addition form a group.

Z5 = Zmod(5) # Technically it's a ring but we'll use the addition here
print(Z5.list())
# [0, 1, 2, 3, 4]

print(Z5.addition_table(names = 'elements'))
# +  0 1 2 3 4
#  +----------
# 0| 0 1 2 3 4
# 1| 1 2 3 4 0
# 2| 2 3 4 0 1
# 3| 3 4 0 1 2
# 4| 4 0 1 2 3

a, b = Z5(14), Z5(3)
print(a, b)
# 4 3
print(a + b)
# 2
print(a + 0)
# 4
print(a + (5 - a))
# 0

Example of non-groups

(Q,)(\mathbb{Q}, \cdot) is not a group because we can find the element 00 that doesn't have an inverse for the identity 11. (Z,)(\mathbb{Z}, \cdot)is not a group because we can find elements that don't have an inverse for the identity 11

Exercise

Is (Z/nZ{0},)(\mathbb{Z} / n \mathbb{Z} \smallsetminus \{0\}, \cdot)a group? If yes why? If not, are there values for nnthat make it a group?

sɹosᴉʌᴉp uoɯɯoɔ puɐ sǝɯᴉɹd ʇnoqɐ ʞuᴉɥ┴ :ʇuᴉH

Proprieties

  1. The identity of a group is unique

  2. The inverse of every element is unique

  3. \forall aG :(a1)1=ga \in G \ : \left(a^{-1} \right) ^{-1} = g. The inverse of the inverse of the element is the element itself

  4. a,bG:\forall a, b \in G: (ab)1=b1a1(ab)^{-1} = b^{-1}a^{-1}

    Proof: (ab)(b1a1)=a(bb1)a1=aa1=e.(ab)(b^{−1}a^{−1}) =a(bb^{−1})a^{−1}=aa^{−1}= e.

n = 11
Zn = Zmod(n)
a, b = Zn(5), Zn(7)
print(n - (a + b))
# 10
print((n - a) + (n - b))
# 10

Orders

In abstract algebra we have two notions of order: Group order and element order

Group order

The order of a group GGis the number of the elements in that group. Notation: G|G|

Element order

The order of an element aGa \in G is the smallest integer nn such that an=1Ga^n = 1_G. If such a number nn doesn't exist we say the element has order \infty. Notation: a|a|

Z12 = Zmod(12) # Residues modulo 12
print(Z12.order()) # The additive order 
# 12
a, b= Z12(6), Z12(3)
print(a.order(), b.order())
# 2 4
print(a.order() * a)
# 0

print(ZZ.order()) # The integers under addition is a group of infinite order
# +Infinity

Subgroups

Definition

Let (G,)(G, \cdot) be a group. We say HHis a subgroup of GG if HH is a subset of GG and (H,)(H, \cdot)forms a group. Notation: HGH \leq G

Proprieties

  1. The identity of GG is also in H:H: 1H=1G1_H = 1_G

  2. The inverses of the elements in HHare found in HH

How to check HGH \leq G? Let's look at a 2 step test

  1. Closed under operation: a,bHabH\forall a, b \in H \to ab \in H

  2. Closed under inverses: aHa1H\forall a \in H \to a^{-1} \in H

Generators

Let GGbe a group,gGg \in Gan element and g=n|g| = n. Consider the following set:

{1,g,g2,...,gn1}=denotedg.\{1, g, g^2, ..., g^{n-1}\} \overset{\text{denoted}}{=} \langle g\rangle.

This set paired the group operation form a subgroup of GGgenerated by an element gg.

Example

For now, trust us that if given a prime pp, a value gZ/pZg \in \mathbb{Z} / p \mathbb{Z} and we compute y=gxmodpy = g^x \bmod p for a secret xx, finding xx is a hard problem. We will tell you why a bit later.

p = 101 # prime
Zp = Zmod(p) 
H_list = Zp.multiplicative_subgroups() # Sage can get the subgroup generators for us
print(H_list)
# ((2,), (4,), (16,), (32,), (14,), (95,), (10,), (100,), ())

g1 = H_list[3][0] # Weak generator
print(g1, g1.multiplicative_order())
# 32 20

g2 = Zp(3) # Strong generator
print(g2, g2.multiplicative_order())
# 3 100


## Consider the following functions
def brute_force(g, p, secret_value):
    """
    Brute forces a secret value, returns number of attempts
    """
    for i in range(p-1):
        t = pow(g, i, p)
        if t == secret_value:
            break
    return i
    
def mean_attempts(g, p, num_keys):
    """
    Tries `num_keys` times to brute force and 
    returns the mean of the number of attempts
    """
    total_attempts = 0
    for _ in range(num_keys):
        k = random.randint(1, p-1)
        sv = pow(g, k, p) # sv = secret value
        total_attempts += brute_force(g, p, sv)
    return 1. * total_attempts / num_keys
    
## Let's try with our generators
print(mean_attempts(g1, p, 100)) # Weak generator
# 9.850
print(mean_attempts(g2, p, 100)) # Strong generator
# 49.200

Examples

// subgroups, quotient groups

// cyclic groups

Last updated

Was this helpful?