CryptoBook

Search…

Fundamentals

Number Theory

Elliptic Curves

Lattices

Asymmetric Cryptography

Symmetric Cryptography

Isogeny Based Cryptography

Appendices

Powered By GitBook

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**

$\mathcal{M}, \mathcal{K}$

and $\mathcal{C}$

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

For example in AES128

$\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: \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**group** if the following requirements hold:

$G$

paired with a binary operation $\cdot:G\times G\to G$

is a $a, b \in G: \$

$a\cdot b \in G$

- Applying the operation keeps the element in the set$a, b, c \in G:$

$(a \cdot b) \cdot c=a\cdot (b\cdot c)$

$e\in G$

such that $a\cdot e=e\cdot a=a$

for all $a\in G$

$a\in G$

, there exists some $b\in G$

such that $b\cdot a=a\cdot b=e$

. We usually denote$b$

as $a^{-1}$

For

$n\in\mathbb Z$

, $a^n$

means $\underbrace{a\cdot a\dots{}\cdot a}_{n\text{ times}}$

when $n>0$

and $\left(a^{-n}\right)^{-1}$

when $n<0$

. For $n=0$

, $a^n=e$

.If **commutative** and the group is called **abelian**. We often denote the group operation by

$ab=ba$

, then $\cdot$

is $+$

instead of $\cdot$

and we typically use $na$

instead of $a^n$

.The identity element of a group

$G$

is also denoted with $1_G$

or just $1$

if only one groups is presentIntegers modulo

$n$

(remainders) under modular addition $= (\mathbb{Z} / n \mathbb{Z}, +)$

.
$\mathbb{Z} / n \mathbb{Z} = \{0, 1, ..., n -1\}$

Let's look if the group axioms are satisfied1.

$\checkmark$

$\forall a, b \in \mathbb{Z}/ n\mathbb{Z} \text{ let } c \equiv a + b \bmod n$

.
Because of the modulo reduction $c < n \Rightarrow c \in \mathbb{Z}/ n\mathbb{Z}$

2.

$\checkmark$

Modular addition is associative3.

$\checkmark$

$0 + a \equiv a + 0 \equiv a \bmod n \Rightarrow 0$

is the identity element4.

$\checkmark$

$\forall a \in \mathbb{Z}/ n\mathbb{Z}$

we take $n - a \bmod n$

to be the inverse of $a$

. We check that$a + n - a \equiv n \equiv 0 \bmod n$

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

Therefore we can conclude that the integers mod

$n$

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!

$(\mathbb{Q}, \cdot)$

is not a group because we can find the element $0$

that doesn't have an inverse for the identity $1$

.
$(\mathbb{Z}, \cdot)$

is not a group because we can find elements that don't have an inverse for the identity $1$

Is

$(\mathbb{Z} / n \mathbb{Z} \smallsetminus \{0\}, \cdot)$

a group? If yes why? If not, are there values for $n$

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$

$a \in G \ : \left(a^{-1} \right) ^{-1} = g$

. The inverse of the inverse of the element is the element itself4.

$\forall a, b \in G:$

$(ab)^{-1} = b^{-1}a^{-1}$

$(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

The order of a group **number of the elements** in that group. Notation:

$G$

is the $|G|$

The order of an element **smallest integer **

$a \in G$

is the $n$

such that $a^n = 1_G$

. If such a number $n$

doesn't exist we say the element has order $\infty$

. Notation: $|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

$\mathcal{M}$

. The order of this group $|\mathcal{M}|$

is the number of possible messages that we can have. For $\mathcal{M} = \{0,1\}^{128}$

we have $|\mathcal{M}| = 2^{128}$

possible messages.Let **different** messages we can generate by applying the group operation on

$m \in \mathcal{M}$

be some message. The order of $m$

means how many $m$

Subgroups

Let

$(G, \cdot)$

be a group. We say $H$

is a subgroup of $G$

if $H$

is a subset of $G$

and $(H, \cdot)$

forms a group.
Notation: $H \leq G$

1.

The identity of

$G$

is also in $H:$

$1_H = 1_G$

2.

The inverses of the elements in

$H$

are found in $H$

$H \leq G$

1.

Closed under operation:

$\forall a, b \in H \to ab \in H$

2.

Closed under inverses:

$\forall a \in H \to a^{-1} \in H$

Generators

Let

$G$

be a group,$g \in G$

an element and $|g| = n$

. Consider the following set:$\{1, g, g^2, ..., g^{n-1}\} \overset{\text{denoted}}{=} \langle g\rangle.$

This set paired the group operation form a subgroup of

$G$

generated by an element $g$

. 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

$G$

and we use an element $g$

to generate them.If an element

$g \in G$

with a small order $n$

is used then it can generate only $n$

possible values and if $n$

is small enough an attacker can do a brute force attack.For now, trust us that if given a prime

$p$

, a value $g \in \mathbb{Z} / p \mathbb{Z}$

and we compute $y = g^x \bmod p$

for a secret $x$

, finding $x$

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

Export as PDF

Copy link