CryptoBook
  • CryptoBook
  • Book Plan
  • Style Guide
    • Sample Page
  • Contributors
  • Fundamentals
    • Mathematical Notation
    • Division and Greatest common divisor
      • Euclidean Algorithm
    • Modular Arithmetic
      • Theorems of Wilson, Euler, and Fermat
        • Fermat's Little Theorem in Detail
        • Euler's Theorem in Detail
      • Quadratic Residues
    • Continued Fractions
  • Number Theory
  • Ideals
  • Polynomials With Shared Roots
  • Integer Factorization
    • Pollard rho
    • Sieves
  • Abstract algebra
    • Groups
      • Another take on groups
      • Discrete Log Problem
    • Rings
    • Fields
    • Polynomials
  • Elliptic Curves
    • Untitled
  • Lattices
    • Introduction
    • LLL reduction
      • Gram-Schmidt Orthogonalization
      • Lagrange's algorithm
      • LLL reduction
    • Lattice reduction
      • Minkowski reduced
      • HKZ reduced
      • LLL reduced
    • Applications
      • Coppersmith algorithm
      • Extensions of Coppersmith algorithm
    • Hard lattice problems
    • Lattices of interest
    • Cryptographic lattice problems
      • Short integer solutions (SIS)
      • Learning with errors (LWE)
      • Ring-LWE
      • NTRU
    • Interactive fun
    • Resources and notations
  • Asymmetric Cryptography
  • RSA
    • Proof of correctness
    • RSA application
    • Low Private Component Attacks
      • Wiener's Attack
      • Boneh-Durfee Attack
    • Common Modulus Attack
    • Recovering the Modulus
  • Diffie-Hellman
    • MITM
  • Elliptic Curve Cryptography
  • Symmetric Cryptography
    • Encryption
    • The One Time Pad
    • AES
      • Rijndael Finite Field
      • Round Transformations
  • Hashes
    • Introduction / overview
    • The Birthday paradox / attack
  • Isogeny Based Cryptography
    • Introduction to Isogeny Cryptography
    • Isogenies
    • Isogeny and Ramanujan Graphs
  • Appendices
    • Sets and Functions
    • Probability Theory
Powered by GitBook
On this page
  • Introduction
  • Definition
  • Proprieties
  • Orders
  • Subgroups
  • Generators
  • Examples

Was this helpful?

Export as PDF
  1. Abstract algebra

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}M,K and C\mathcal{C}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}K=M=C={0,1}128since the input, output and key spaces are 128 bits. We also have the encryption and decryption operations: Enc:K×M→CDec:K×C→MEnc: \mathcal{K} \times \mathcal{M} \to \mathcal{C} \\ Dec: \mathcal{K} \times \mathcal{C} \to \mathcal{M}Enc:K×M→CDec:K×C→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 setGGGpaired with a binary operation ⋅:G×G→G\cdot:G\times G\to G⋅:G×G→Gis a group if the following requirements hold:

  • Closure: For all a,b∈G: a, b \in G: \ a,b∈G:  a⋅b∈Ga\cdot b \in Ga⋅b∈G - Applying the operation keeps the element in the set

  • Associativity: For all a,b,c∈G:a, b, c \in G: a,b,c∈G: (a⋅b)⋅c=a⋅(b⋅c)(a \cdot b) \cdot c=a\cdot (b\cdot c)(a⋅b)⋅c=a⋅(b⋅c)

  • Identity: There exists an elemente∈Ge\in Ge∈Gsuch that a⋅e=e⋅a=aa\cdot e=e\cdot a=aa⋅e=e⋅a=afor all a∈Ga\in Ga∈G

  • Inverse: For all elements a∈Ga\in Ga∈G, there exists some b∈Gb\in Gb∈Gsuch that b⋅a=a⋅b=eb\cdot a=a\cdot b=eb⋅a=a⋅b=e. We usually denotebbbas a−1a^{-1}a−1

For n∈Zn\in\mathbb Zn∈Z, ana^nanmeans a⋅a…⋅a⏟n times\underbrace{a\cdot a\dots{}\cdot a}_{n\text{ times}}n timesa⋅a…⋅a​​when n>0n>0n>0and (a−n)−1\left(a^{-n}\right)^{-1}(a−n)−1when n<0n<0n<0. For n=0n=0n=0, an=ea^n=ean=e.

If ab=baab=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 nananainstead of ana^nan.

Remark

  • The identity element of a group GGG is also denoted with 1G1_G1G​ or just 111 if only one groups is present

Examples of groups

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

  1. ✓\checkmark✓ ∀a,b∈Z/nZ let c≡a+b mod n\forall a, b \in \mathbb{Z}/ n\mathbb{Z} \text{ let } c \equiv a + b \bmod n∀a,b∈Z/nZ let c≡a+bmodn. Because of the modulo reduction c<n⇒c∈Z/nZc < n \Rightarrow c \in \mathbb{Z}/ n\mathbb{Z} c<n⇒c∈Z/nZ

  2. ✓\checkmark✓Modular addition is associative

  3. ✓\checkmark ✓0+a≡a+0≡a mod n⇒00 + a \equiv a + 0 \equiv a \bmod n \Rightarrow 00+a≡a+0≡amodn⇒0 is the identity element

  4. ✓\checkmark✓∀a∈Z/nZ\forall a \in \mathbb{Z}/ n\mathbb{Z} ∀a∈Z/nZwe take n−a mod nn - a \bmod nn−amodnto be the inverse of aaa. We check that

    a+n−a≡n≡0 mod na + n - a \equiv n \equiv 0 \bmod na+n−a≡n≡0modn

    n−a+a≡n≡0 mod nn - a + a \equiv n \equiv 0 \bmod nn−a+a≡n≡0modn

Therefore we can conclude that the integers mod nnn 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)(Q,⋅) is not a group because we can find the element 000 that doesn't have an inverse for the identity 111. (Z,⋅)(\mathbb{Z}, \cdot)(Z,⋅)is not a group because we can find elements that don't have an inverse for the identity 111

Exercise

Is (Z/nZ∖{0},⋅)(\mathbb{Z} / n \mathbb{Z} \smallsetminus \{0\}, \cdot)(Z/nZ∖{0},⋅)a group? If yes why? If not, are there values for nnnthat 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∈G :(a−1)−1=ga \in G \ : \left(a^{-1} \right) ^{-1} = ga∈G :(a−1)−1=g. The inverse of the inverse of the element is the element itself

  4. ∀a,b∈G:\forall a, b \in G: ∀a,b∈G: (ab)−1=b−1a−1(ab)^{-1} = b^{-1}a^{-1}(ab)−1=b−1a−1

    Proof: (ab)(b−1a−1)=a(bb−1)a−1=aa−1=e.(ab)(b^{−1}a^{−1}) =a(bb^{−1})a^{−1}=aa^{−1}= e.(ab)(b−1a−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 GGGis the number of the elements in that group. Notation: ∣G∣|G|∣G∣

Element order

The order of an element a∈Ga \in Ga∈G is the smallest integer nnn such that an=1Ga^n = 1_Gan=1G​. If such a number nnn doesn't exist we say the element has order ∞\infty∞. Notation: ∣a∣|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

We said our messages lay in some group M\mathcal{M}M. The order of this group ∣M∣|\mathcal{M}|∣M∣ is the number of possible messages that we can have. For M={0,1}128\mathcal{M} = \{0,1\}^{128}M={0,1}128we have ∣M∣=2128|\mathcal{M}| = 2^{128}∣M∣=2128 possible messages.

Let m∈Mm \in \mathcal{M}m∈Mbe some message. The order of mmm means how many different messages we can generate by applying the group operation on mmm

Subgroups

Definition

Let (G,⋅)(G, \cdot)(G,⋅) be a group. We say HHHis a subgroup of GGG if HHH is a subset of GGG and (H,⋅)(H, \cdot)(H,⋅)forms a group. Notation: H≤GH \leq GH≤G

Proprieties

  1. The identity of GGG is also in H:H: H:1H=1G1_H = 1_G1H​=1G​

  2. The inverses of the elements in HHHare found in HHH

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

  1. Closed under operation: ∀a,b∈H→ab∈H\forall a, b \in H \to ab \in H∀a,b∈H→ab∈H

  2. Closed under inverses: ∀a∈H→a−1∈H\forall a \in H \to a^{-1} \in H∀a∈H→a−1∈H

Generators

Let GGGbe a group,g∈Gg \in Gg∈Gan element and ∣g∣=n|g| = n∣g∣=n. Consider the following set:

{1,g,g2,...,gn−1}=denoted⟨g⟩.\{1, g, g^2, ..., g^{n-1}\} \overset{\text{denoted}}{=} \langle g\rangle.{1,g,g2,...,gn−1}=denoted⟨g⟩.

This set paired the group operation form a subgroup of GGGgenerated by an element ggg.

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 GGGand we use an element gggto generate them.

If an elementg∈Gg \in Gg∈Gwith a small order nnn is used then it can generate only nnn possible values and if nnn is small enough an attacker can do a brute force attack.

Example

For now, trust us that if given a prime ppp, a value g∈Z/pZg \in \mathbb{Z} / p \mathbb{Z}g∈Z/pZ and we compute y=gx mod py = g^x \bmod py=gxmodp for a secret xxx, finding xxx 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

PreviousSievesNextAnother take on groups

Last updated 4 years ago

Was this helpful?