CryptoBook
Search…
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.
For example in AES128
K=M=C={0,1}128\mathcal{K} = \mathcal{M} = \mathcal{C} = \{0, 1\}^{128}
since the input, output and key spaces are 128 bits. We also have the encryption and decryption operations:
Enc:K×MCDec:K×CMEnc: \mathcal{K} \times \mathcal{M} \to \mathcal{C} \\ Dec: \mathcal{K} \times \mathcal{C} \to \mathcal{M}
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 set
GG
paired with a binary operation
:G×GG\cdot:G\times G\to G
is 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 element
    eGe\in G
    such that
    ae=ea=aa\cdot e=e\cdot a=a
    for all
    aGa\in G
    Inverse: For all elements
    aGa\in G
    , there exists some
    bGb\in G
    such that
    ba=ab=eb\cdot a=a\cdot b=e
    . We usually denote
    bb
    as
    a1a^{-1}
For
nZn\in\mathbb Z
,
ana^n
means
aaan times\underbrace{a\cdot a\dots{}\cdot a}_{n\text{ times}}
when
n>0n>0
and
(an)1\left(a^{-n}\right)^{-1}
when
n<0n<0
. For
n=0n=0
,
an=ea^n=e
.
If
ab=baab=ba
, then
\cdot
is commutative and the group is called abelian. We often denote the group operation by
++
instead of
\cdot
and we typically use
nana
instead 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.
    \checkmark
    Modular addition is associative
    3.
    \checkmark
    0+aa+0amodn00 + a \equiv a + 0 \equiv a \bmod n \Rightarrow 0
    is the identity element
    4.
    \checkmark
    aZ/nZ\forall a \in \mathbb{Z}/ n\mathbb{Z}
    we take
    namodnn - a \bmod n
    to 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.
1
Z5 = Zmod(5) # Technically it's a ring but we'll use the addition here
2
print(Z5.list())
3
# [0, 1, 2, 3, 4]
4
5
print(Z5.addition_table(names = 'elements'))
6
# + 0 1 2 3 4
7
# +----------
8
# 0| 0 1 2 3 4
9
# 1| 1 2 3 4 0
10
# 2| 2 3 4 0 1
11
# 3| 3 4 0 1 2
12
# 4| 4 0 1 2 3
13
14
a, b = Z5(14), Z5(3)
15
print(a, b)
16
# 4 3
17
print(a + b)
18
# 2
19
print(a + 0)
20
# 4
21
print(a + (5 - a))
22
# 0
23
Copied!
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
nn
that 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.
1
n = 11
2
Zn = Zmod(n)
3
a, b = Zn(5), Zn(7)
4
print(n - (a + b))
5
# 10
6
print((n - a) + (n - b))
7
# 10
Copied!

Orders

In abstract algebra we have two notions of order: Group order and element order
Group order
The order of a group
GG
is 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|
1
Z12 = Zmod(12) # Residues modulo 12
2
print(Z12.order()) # The additive order
3
# 12
4
a, b= Z12(6), Z12(3)
5
print(a.order(), b.order())
6
# 2 4
7
print(a.order() * a)
8
# 0
9
10
print(ZZ.order()) # The integers under addition is a group of infinite order
11
# +Infinity
Copied!
We said our messages lay in some group
M\mathcal{M}
. The order of this group
M|\mathcal{M}|
is the number of possible messages that we can have. For
M={0,1}128\mathcal{M} = \{0,1\}^{128}
we have
M=2128|\mathcal{M}| = 2^{128}
possible messages.
Let
mMm \in \mathcal{M}
be some message. The order of
mm
means how many different messages we can generate by applying the group operation on
mm

Subgroups

Definition
Let
(G,)(G, \cdot)
be a group. We say
HH
is 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
    HH
    are 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
GG
be a group,
gGg \in G
an 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
GG
generated by an element
gg
.
Why do we care about subgroups? We praise the fact that some problems are hard because the numbers we use are huge and exhaustive space searches are too hard in practice.
Suppose we have a big secret values space
GG
and we use an element
gg
to generate them.
If an element
gGg \in G
with a small order
nn
is used then it can generate only
nn
possible values and if
nn
is small enough an attacker can do a brute force attack.
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.
1
p = 101 # prime
2
Zp = Zmod(p)
3
H_list = Zp.multiplicative_subgroups() # Sage can get the subgroup generators for us
4
print(H_list)
5
# ((2,), (4,), (16,), (32,), (14,), (95,), (10,), (100,), ())
6
7
g1 = H_list[3][0] # Weak generator
8
print(g1, g1.multiplicative_order())
9
# 32 20
10
11
g2 = Zp(3) # Strong generator
12
print(g2, g2.multiplicative_order())
13
# 3 100
14
15
16
## Consider the following functions
17
def brute_force(g, p, secret_value):
18
"""
19
Brute forces a secret value, returns number of attempts
20
"""
21
for i in range(p-1):
22
t = pow(g, i, p)
23
if t == secret_value:
24
break
25
return i
26
27
def mean_attempts(g, p, num_keys):
28
"""
29
Tries `num_keys` times to brute force and
30
returns the mean of the number of attempts
31
"""
32
total_attempts = 0
33
for _ in range(num_keys):
34
k = random.randint(1, p-1)
35
sv = pow(g, k, p) # sv = secret value
36
total_attempts += brute_force(g, p, sv)
37
return 1. * total_attempts / num_keys
38
39
## Let's try with our generators
40
print(mean_attempts(g1, p, 100)) # Weak generator
41
# 9.850
42
print(mean_attempts(g2, p, 100)) # Strong generator
43
# 49.200
44
Copied!

Examples

// subgroups, quotient groups
// cyclic groups
Last modified 5mo ago