Authors: Ariana, Zademn Reviewed by:
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 and .
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.
A setpaired with a binary operation is a group if the following requirements hold:
Closure: For all - Applying the operation keeps the element in the set
Associativity: For all
Identity: There exists an elementsuch that for all
Inverse: For all elements , there exists some such that . We usually denoteas
For , means when and when . For , .
If , then is commutative and the group is called abelian. We often denote the group operation by instead of and we typically use instead of .
The identity element of a group is also denoted with or just if only one groups is present
Examples of groups
Integers modulo (remainders) under modular addition . Let's look if the group axioms are satisfied
. Because of the modulo reduction
Modular addition is associative
is the identity element
we take to be the inverse of . We check that
Therefore we can conclude that the integers mod with the modular addition form a group.
Z5 = Zmod(5) # Technically it's a ring but we'll use the addition hereprint(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 3a, b = Z5(14), Z5(3)print(a, b)# 4 3print(a + b)# 2print(a + 0)# 4print(a + (5 - a))# 0
Example of non-groups
is not a group because we can find the element that doesn't have an inverse for the identity . is not a group because we can find elements that don't have an inverse for the identity
Is a group? If yes why? If not, are there values for that make it a group?
sɹosᴉʌᴉp uoɯɯoɔ puɐ sǝɯᴉɹd ʇnoqɐ ʞuᴉɥ┴ :ʇuᴉH
The identity of a group is unique
The inverse of every element is unique
. The inverse of the inverse of the element is the element itself
n = 11Zn = Zmod(n)a, b = Zn(5), Zn(7)print(n - (a + b))# 10print((n - a) + (n - b))# 10
In abstract algebra we have two notions of order: Group order and element order
The order of a group is the number of the elements in that group. Notation:
The order of an element is the smallest integer such that . If such a number doesn't exist we say the element has order . Notation:
Z12 = Zmod(12) # Residues modulo 12print(Z12.order()) # The additive order# 12a, b= Z12(6), Z12(3)print(a.order(), b.order())# 2 4print(a.order() * a)# 0print(ZZ.order()) # The integers under addition is a group of infinite order# +Infinity
Let be a group. We say is a subgroup of if is a subset of and forms a group. Notation:
The identity of is also in
The inverses of the elements in are found in
How to check ? Let's look at a 2 step test
Closed under operation:
Closed under inverses:
Let be a group,an element and . Consider the following set:
This set paired the group operation form a subgroup of generated by an element .
For now, trust us that if given a prime , a value and we compute for a secret , finding is a hard problem. We will tell you why a bit later.
p = 101 # primeZp = Zmod(p)H_list = Zp.multiplicative_subgroups() # Sage can get the subgroup generators for usprint(H_list)# ((2,), (4,), (16,), (32,), (14,), (95,), (10,), (100,), ())g1 = H_list # Weak generatorprint(g1, g1.multiplicative_order())# 32 20g2 = Zp(3) # Strong generatorprint(g2, g2.multiplicative_order())# 3 100## Consider the following functionsdef 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:breakreturn idef mean_attempts(g, p, num_keys):"""Tries `num_keys` times to brute force andreturns the mean of the number of attempts"""total_attempts = 0for _ in range(num_keys):k = random.randint(1, p-1)sv = pow(g, k, p) # sv = secret valuetotal_attempts += brute_force(g, p, sv)return 1. * total_attempts / num_keys## Let's try with our generatorsprint(mean_attempts(g1, p, 100)) # Weak generator# 9.850print(mean_attempts(g2, p, 100)) # Strong generator# 49.200
// subgroups, quotient groups
// cyclic groups