Given any groupGand elementsa,bsuch that an=b, the problem of solving fornis known as the disctete log problem (DLP). In sage, this can be done for general groups by calling discrete_log
Discrete log over
Typically, one considers the discrete log problem in , i.e. the multiplicative group of integers. Explicitly, the problem asks forgiven . This can be done by calling b.log(a) in sage:
This section is devoted to helping the reader understand which functions are called when for this specific instance of DLP.
Whenis composite and not a prime power, discrete_log() will be used, which uses generic algorithms to solve DLP (e.g. Pohlig-Hellman and baby-step giant-step).
When is a prime, Pari znlog will be used, which uses a linear sieve index calculus method, suitable for .
When , SageMath will fall back on the generic implementation discrete_log()which can be slow. However, Pari znlog can handle this as well, again using the linear sieve index calculus method. To call this within SageMath we can use either of the following (the first option being a tiny bit faster than the second)
Example
Given a small prime, we can compare the Pari method with the Sage defaults
We can also solve this problem with even larger primes in a very short time
Discrete log over
// elliptic curve discrete log functions
sage: G = DihedralGroup(99)
sage: g = G.random_element()
sage: discrete_log(g^9,g) # note that if the order of g is less than 9 we would get 9 mod g.order()
9
Another take on groups
// Visual
// Symmetries
// Permutations
(Z/nZ)β
(Z/nZ)β
modΒ n
x
ax=b(modn)
n
n=p
p<1050βΌ2166
n=pk
E(k)
sage: R = Integers(99)
sage: a = R(4)
sage: b = a^9
sage: b.log(a)
9
x = int(pari(f"znlog({int(b)},Mod({int(a)},{int(n)}))"))
x = gp.znlog(b, gp.Mod(a, n))
p = getPrime(36)
n = p^2
K = Zmod(n)
a = K.multiplicative_generator()
b = a^123456789
time int(pari(f"znlog({int(b)},Mod({int(a)},{int(n)}))"))
# CPU times: user 879 Β΅s, sys: 22 Β΅s, total: 901 Β΅s
# Wall time: 904 Β΅s
# 123456789
time b.log(a)
# CPU times: user 458 ms, sys: 17 ms, total: 475 ms
# Wall time: 478 ms
# 123456789
time discrete_log(b,a)
# CPU times: user 512 ms, sys: 24.5 ms, total: 537 ms
# Wall time: 541 ms
# 123456789
p = getPrime(100)
n = p^2
K = Zmod(n)
a = K.multiplicative_generator()
b = a^123456789
time int(pari(f"znlog({int(b)},Mod({int(a)},{int(n)}))"))
# CPU times: user 8.08 s, sys: 82.2 ms, total: 8.16 s
# Wall time: 8.22 s
# 123456789
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 setsM,K and C.
Furthermore, to get a ciphertext we usually perform some operations with the message and the key.
For example in AES128 since the input, output and key spaces are 128 bits. We also have the encryption and decryption operations:
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 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 , 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 .
Remark
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
Therefore we can conclude that the integers mod with the modular addition form a group.
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
Exercise
Is a group? If yes why? If not, are there values for that make it a group?
. The inverse of the inverse of the element is the element itself
Orders
In abstract algebra we have two notions of order: Group order and element order
Group order
The order of a group is the number of the elements in that group. Notation:
Element order
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:
We said our messages lay in some group . The order of this group is the number of possible messages that we can have. For we have possible messages.
Let be some message. The order of means how many different messages we can generate by applying the group operation on
Subgroups
Definition
Let be a group. We say is a subgroup of if is a subset of and forms a group.
Notation:
Proprieties
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:
Generators
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 .
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 and we use an element to generate them.
If an elementwith a small order is used then it can generate only possible values and if
Example
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.
Examples
// subgroups, quotient groups
// cyclic groups
for all
Inverse: For all elements aβG, there exists some bβGsuch that bβ a=aβ b=e. We usually denotebas aβ1
ββaβZ/nZwe take nβamodnto be the inverse of a. We check that
a+nβaβ‘nβ‘0modn
nβa+aβ‘nβ‘0modn
βa,bβG:(ab)β1=bβ1aβ1
Proof: (ab)(bβ1aβ1)=a(bbβ1)aβ1=aaβ1=e.
is small enough an attacker can do a brute force attack.
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
n = 11
Zn = Zmod(n)
a, b = Zn(5), Zn(7)
print(n - (a + b))
# 10
print((n - a) + (n - b))
# 10
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
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
