14. Quadratic Sieve and Index Calculus#
In this chapter we introduce two of the more effective (and mathematically sophisticated) tools for attacks at the ElGamal and RSA Cryptosystems.
14.1. The Quadratic Sieve#
We will focus again on the problem of factorization, more specifically, factoring \(N = p q\), where \(p\) and \(q\) are large, distinct primes. With the difference of squares Factorization method, the hard part was the Relation Building, i.e., finding \(a_1, a_2, \ldots , a_r > \sqrt{N}\), for \(r\) sufficiently large, such the \(c_i\)’s, defined as the reduction modulo \(N\) of \(a_i^2\), are all \(B\)-smooth for some relatively small \(B\).
In this section we introduce the Quadratic Sieve, which is an efficient algorithm for relation building. When used with the difference of squares factorization method, it is the best known algorithm to factor \(N = pq\) with \(N < 2^{350}\).
Note
The number \(2^{350}\) is huge! The estimated number of atoms in the know universe is about \(2^{272}\). We would need to double this number \(78\) times to get \(2^{350}\).
Note
For \(N > 2^{350}\), the Number Field Sieve is more efficient, but beyond the scope of these notes.
14.1.1. Sieving \(B\)-Smooth Numbers#
Let’s start with a simple and intuitive way of finding \(B\)-smooth numbers in a list of consecutive integers:
Algorithm 14.1 (Sieving \(B\)-Smooth Numbers)
Given a list of numbers \(2, 3, 4, \ldots , n\) and some \(B > 0\), the following procedure finds the \(B\)-smooth numbers in the list. We refer to the “number in position \(k\)” in the list following Sage/Python’s convention: \(2\) is position \(0\), \(3\) in position \(1\), etc. So, initially, the number \(k\) is in position \(k-2\).
Initialize \(p \leftarrow 2\) and a new list as a copy of the original.
While \(p < B\):
Set \(i \leftarrow 1\):
While \(p^i < n\):
Set \(j \leftarrow p^i - 2\).
While \(j \leq n-2\):
Divide the number in position \(j\) of the new list by \(p\).
Set \(j \leftarrow j + p^i\)
Set \(i \leftarrow i + 1\).
Set \(p\) as the next element on the new list different from \(1\).
Return the elements from the original list in the positions where we have \(1\)’s in the new list.
Here is an example for finding \(3\)-smooth numbers up to \(19\).
We start \(p = 2\) and divide all multiples of \(2\) by \(2\):
Now, we divide all numbers in positions corresponding to multiples of \(2^2\) by \(2\):
Now, we divide all numbers in positions corresponding to multiples of \(2^3\) by \(2\):
Now, we divide all numbers in positions corresponding to multiples of \(2^4\) by \(2\):
Since \(2^5 = 32 > 19\), we set \(p\) to the next element on the list different from \(1\), so \(3\) in this case:
We then repeat the process for \(p=3\), dividing terms in positions corresponding to \(3\), and then \(3^2\), by \(3\):
Now, the next \(p\) would be the next number different from \(1\), so \(5\), but \(5 > B = 3\), so we stop, and return the numbers from the original list (top row) corresponding to \(1\)’s in the new one (bottom row):
Therefore, the \(3\)-smooth numbers less than or equal to \(19\) are: \(2, 3, 4, 6, 8, 9, 12, 16, 18\).
14.1.1.1. Implementation#
Here is an implementation of the algorithm above:
def b_smooth_sieve(n, B):
"""
Given and upper bound n and some B, finds all B-smooth numbers between 2 and n.
INPUTS:
n: integer greater than one; check number from 2 to n for B-smoothness.
B: positive integer (or float) used for smoothness.
OUTPUT:
A list containing all B-smooth numbers between 2 and n (inclusive).
"""
numbers = list(range(2, n + 1))
p = 2 # first prime
index = 0 # position of current prime
while p <= B:
# divide entries by all possible powers of p
i = 1
while p^i <= n:
for j in range(p^i - 2, n - 1, p^i):
numbers[j] = numbers[j] // p
i += 1
# go to next prime (next element different from 1 in the list)
index += 1
while numbers[index] == 1:
index += 1
p = numbers[index]
# select numbers where we obtained 1
return [i for i in range(2, n + 1) if numbers[i - 2] == 1]
Let’s check our work above:
b_smooth_sieve(19, 3)
[2, 3, 4, 6, 8, 9, 12, 16, 18]
And for all \(5\)-smooth numbers less than or equal to \(100\):
b_smooth_sieve(100, 5)
[2,
3,
4,
5,
6,
8,
9,
10,
12,
15,
16,
18,
20,
24,
25,
27,
30,
32,
36,
40,
45,
48,
50,
54,
60,
64,
72,
75,
80,
81,
90,
96,
100]
14.1.2. Relation Building#
The method above works for consecutive numbers. But in our application, we need to find \(a\)’s, with \(a > \sqrt{N}\), such that the reduction modulo \(N\) of \(a^2\) are \(B\)-smooth. Hence, we need to adapt our previous method.
We define the function \(F(t) = t^2 - N\) (so \(t\) is a variable and \(N = pq\) the number we are trying to factor). Then, if \(\sqrt{N} < a < \sqrt{2N}\), we have that \(0 < F(a) < N\), and hence \(F(a)\) is its own reduction modulo \(N\) and congruent to \(a^2\) modulo \(N\), i.e., \(F(a)\) is the corresponding \(c\). Note that we had to restrict the size of \(a\), but it helps avoid reducing \(a^2\) modulo \(N\): no long division, we just subtract \(N\).
Therefore, we go through the list starting at \(a = \lfloor \sqrt{N} \rfloor + 1\) up to some upper bound \(b < \sqrt{2N}\) and find the \(B\)-smooth numbers in the list \(F(a), F(a+1), F(a+2) , \ldots, F(b)\). Note that since \(N\) is very large, we have that \(\sqrt{2N} - \sqrt{N}\) (about the largest length for our list) is about \(0.41 \sqrt{N}\) and still quite larger, which should be enough to find a sufficient number of \(B\)-smooth numbers for the difference of squares algorithm.
Before we describe the actual process, we need the following definition:
Definition 14.1 (Factor Base)
Given \(B>0\), the factor base of \(B\) is the set of primes less than or equal to \(B\).
To find \(B\)-smooth number in \(F(a), F(a+1), \ldots , F(b)\), for each \(p\) in the factor base of \(B\), we look for \(t \in \{ a, a+1 , a+2, \ldots , b \}\) such that
This means that \(N\) is a square modulo \(p\). Fortunately, we have seen how to do this, for instance, we can use Quadratic Reciprocity. If \(N\) is not square modulo \(p\), we move to the next prime.
Note that if \(p \mid N\), then we found a prime factor and are done. So, let’s assume that \(p \nmid N\). Then, if \(N\) is a square modulo \(p\), we get either two square roots, when \(p\) is odd, or one, two, or four, when \(p=2\). If \(c\) is a square root of \(N\), i.e., \(c^2 \equiv N \pmod{p}\), then \(F(c), F(c + p), F(c + 2p), \ldots\) are all divisible by \(p\) (i.e., congruent to \(0\) modulo \(p\)). Then, as with consecutive numbers, we sieve through the list by dividing each every \(p\) terms of our list by \(p\). More precisely, if \(c_p\) is the smallest integer in \(a, a+1, a+2, \ldots, b\) such that \(c_p \equiv c \pmod{p}\), then we divide \(F(c_p), F(c_p+p), F(c_p + 2p) \ldots\) by \(p\).
But we need to also divide the terms that are divisible by higher powers of \(p\). For that, we can use Hensel’s Lemma (i.e., Theorem 13.5 and Theorem 13.6) to solve
14.1.3. Algorithm#
Here is the algorithm for relation building:
Algorithm 14.2 (Relation Building)
Given an integer \(N\) (to be eventually factored), \(B>0\), and an upped bound \(b\) between \(\sqrt{N}\) and \(\sqrt{2N}\), we will produce two lists:
A list of integers between \(\lfloor \sqrt{N} \rfloor + 1\) and \(b\) such that their squares reduced modulo \(N\) are \(B\)-smooth (the “\(a_i\)’s”) and
the list of their squares reduced modulo \(N\) (the “\(c_i\)’s”).
We obtain these lists as follows:
Initialize:
set
list_awith elements from \(\lfloor \sqrt{N} \rfloor + 1\) to the given \(b\) (inclusive);set
list_cwith entries as \(a^2 - N\) for \(a\)’s inlist_acreate a copy of
list_c, saysieve_list.
Loop over primes \(p\) less than or equal to the given \(B\):
If \(N\) is not a square modulo \(p\), skip the rest of this loop (and go to the next prime).
Set \(n \leftarrow 1\).
Until we manually break out, do:
Compute all square roots of \(N\) modulo \(p^n\).
For each one of the roots:
Find (if possible) the index, say \(i\), in
sieve_listfor the first entry that is congruent to the root modulo \(p^n\).While \(i\) is less than the length of
sieve_list, divide the entry ofsieve_listat index \(i\) by \(p\) and set \(i \leftarrow i + p^n\).
If no root had a match in the list, break this loop (and go to the next prime).
Set \(n \leftarrow n + 1\).
Return the elements of
list_acorresponding to entries insieve_listwith \(1\)’s and, similarly, the elements oflist_ccorresponding to entries insieve_listwith \(1\)’s.
Important
We know how to find square roots modulo \(p\) or verify if there is no such root. But when finding square roots modulo \(p^2\), \(p^3\), etc., we should use Hensel’s Lemma: when we have a square root modulo \(p^k\) (from the previous step), we can use it to easily find a square root modulo \(p^{k+1}\). Also, remember that we only need one root, as the others are easy to find:
If \(p\) is odd and \(r\) is one square root modulo \(p^n\), then the other is \(p^n - r\).
If \(p=2\):
There is a single square root modulo \(2\).
If \(r\) is a square root modulo \(r\), then the other is \(r + 2\).
If \(r\) is a square root modulo \(2^n\), for \(n \geq 3\), then the others are \(2^n - a\), \(2^n - a - 2^{n-1}\), \(a + 2^{n-1}\).
14.1.4. Example#
Let’s illustrate the process with an example: let \(N = 1073\). Then, \(a = \lfloor \sqrt{1073} \rfloor + 1 = 33\). Let’s use \(b = 46 < \sqrt{2 \cdot 1073}\). So, we computer \(F(33), F(34), F(35), \ldots , F(46)\):
N = 1073
a = floor(sqrt(N)) + 1
b = ceil(sqrt(2 * N)) - 1
def F(t):
return t^2 - N
[F(x) for x in range(a, b + 1)]
[16, 83, 152, 223, 296, 371, 448, 527, 608, 691, 776, 863, 952, 1043]
In the tables below, the first row will always be the elements in the original list (the \(a_i\)’s), and below are the corresponding squares modulo \(N\).
Let’s find all \(19\)-smooth numbers in the second row \(F(33), F(34), \ldots, F(46)\).
We start with \(p=2\). Since \(N\) is odd, we have that \(F(t)\) is even whenever \(t\) is odd. Or, we have that the square root of \(N\) modulo \(2\) is \(1\), so any \(t \equiv 1 \pmod{2}\) is such that \(F(t) \equiv 0 \pmod{2}\) and can be divided by \(2\). Moreover that is the only square root modulo \(2\).
Now, we see if \(N\) has a square root modulo \(4\). But \(N \equiv 1 \pmod{4}\), so we have two square roots modulo \(4\): \(t \equiv 1, 3 \pmod{4}\). We have that \(33 \equiv 1 \pmod{4}\) and \(35 \equiv 3 \pmod{4}\). We now divide \(F(33), F(37), F(41), \ldots , F(45)\) and \(F(35), F(39), F(43), \ldots F(43)\) by \(2\):
Moving on to \(2^3\), we have that \(N \equiv 1 \pmod{8}\), so we have \(4\) square roots modulo \(8\): \(1\), \(3\), \(5\), and \(7\). This means that again, we can divide every other element of the list of \(F(t)\)’s by \(2\):
Modulo \(2^4 = 16\) we also know that we have \(4\) square roots, since \(N \equiv 1 \pmod{8}\). Now we apply Hensel’s Lemma to compute these. We find them to be \(1\), \(7\), \(9\), \(15\).
The first element in \(\{ 33, 34, 35, \ldots, 46 \}\) congruent to \(1\) modulo \(16\) is \(33\). Since \(33 + 16 > 46\), we only divide the number corresponding to \(F(33)\) by \(2\).
The first element in \(\{ 33, 34, 35, \ldots, 46 \}\) congruent to \(7\) modulo \(16\) is \(39\). Since \(39 + 16 > 46\), we only divide the number corresponding to \(F(39)\) by \(2\).
The first element in \(\{ 33, 34, 35, \ldots, 46 \}\) congruent to \(9\) modulo \(16\) is \(41\). Since \(41 + 16 > 46\), we only divide the number corresponding to \(F(41)\) by \(2\).
There is no element in \(\{ 33, 34, 35, \ldots, 46 \}\) congruent to \(15\) modulo \(16\), so there is no other element to divide by \(2\).
The square roots of \(N\) modulo \(2^5 = 32\) (using Hensel’s Lemma again) are \(7\), \(9\), \(23\), \(25\). In \( \{ 33, 34, \ldots, 46 \}\), only \(39 \equiv 7 \pmod{32}\) and \(41 \equiv 9 \pmod{32}\), so we can divide the corresponding numbers by \(2\):
The square roots modulo \(2^6 = 64\) are \(7\), \(25\), \(39\), and \(57\). This only gives \(39\) in our list, so we divide the corresponding number by \(2\):
The square roots modulo \(2^7 = 128\) are \(7\), \(57\), \(71\), and \(121\), but no number in our list is congruent to any of these modulo \(128\), so we move on to the next prime, \(p=3\).
We have that \(N \equiv 2 \pmod{3}\), and hence not a square. So, we move to \(p=5\). But \(N \equiv 3 \pmod{5}\), also not a square. We then try \(7\), and \(N \equiv 2 \pmod{7}\), which is a square! The square roots are \(3\) and \(4\). The numbers in our list which are congruent to \(3\) modulo \(7\) are \(38\) and \(45\), and the ones congruent to \(4\) are \(39\) and \(46\). We divide the corresponding numbers in our list by \(7\):
Now, using Hensel’s Lemma, we have that \(17\) and \(32\) are square roots modulo \(7^2 = 49\), but we have no elements in our list congruent to those, so we move to the next prime, \(p = 11\). But \(N\) is not a square modulo \(11\), nor modulo \(13\), but it is modulo \(17\). The square roots modulo \(17\) are \(6\) and \(11\). The only elements congruent to \(6\) modulo \(17\) in our list is \(40\) and the only one congruent to \(11\) is \(45\). We divide the corresponding numbers:
The square roots modulo \(17^2\) are \(28\) and \(261\), but neither has representatives in our list. So, we move on to our next, and last, prime, \(p=19\). \(N\) is a square modulo \(19\), with roots \(3\) and \(16\). This gives only \(41\) and \(35\), and we divide the corresponding elements in our list by \(19\):
The square roots of \(N\) modulo \(19^2\) are \(60\) and \(301\), but no element in our list is congruent to either of those modulo \(19^2\). Hence, we are done and to find the the list of \(a\)’s which are such that the reduction modulo \(N\) of \(a^2\) are \(19\)-smooth, we take the numbers corresponding to the numbers ending with \(1\):
Hence, we have the following \(a\)’s: \(33, 35, 39, 41, 45\); and their corresponding \(19\)-smooth \(c\)’s (their squares reduced modulo \(N\)): \(16, 152, 448, 608, 952\):
We can now do the process of elimination. In this case, for instance, we have:
We then compute
And indeed, \(29\) is a factor of \(1073\):
divmod(1073, 29)
(37, 0)
So, we’ve factored \(1073\) as \(29 \cdot 37\).
Homework
You will implement the algorithm in your homework.
14.2. Index Calculus#
Here we introduce the most efficient method to solve the Discrete Log Problem (in the context we introduced here):
Definition 14.2 (The Discrete Log Problem)
We call the (computationally intensive) problem of computing a discrete log \(\log_g(a)\), i.e., finding a power \(x\) (in \(\mathbb{Z}/|a|\mathbb{Z}\)) such that \(g^x = a\) in \(\mathbb{Z}/m\mathbb{Z}\), the discrete log problem (DLP).
As in the context of the ElGamal cryptosystem, we take the modulus \(m\) to be a prime \(p\). On the other hand, we will take the base \(g\) to be a primitive root in \(\mathbb{F}_p\). Suppose we want then to compute \(\log_g(h)\), i.e., find a power \(x\) such that \(g^x = h\) in \(\mathbb{F}_p\). In this case, we can assume that \(x\) (i.e., \(\log_g(h)\)) is in \(\mathbb{Z}/(p-1)\mathbb{Z}\).
14.2.1. General Computation#
The idea is the following: let \(B\) be a positive number and \(\ell_1, \ell_2, \ldots , \ell_n\) be all primes less than or equal to \(B\). Then, we solve (with a method to be described below):
Then, we compute \(h \cdot g^{-k}\) (in \(\mathbb{F}_p\)) for \(k=0, 1, 2, \ldots\) until the result is \(B\)-smooth. This has to eventually happen, since these values will run over all elements of \(\mathbb{F}_p^{\times}\). So, we have:
for some positive integers \(r_1, r_2, \ldots , r_n\).
Taking \(\log_g\) on the left-side, we get
while the log of the right-side is
Putting these last two equations together, we get:
On the left we have what we want to compute, while on the right all terms are known!
14.2.1.1. Example#
Let’s illustrate the process with a concrete example: we take \(p = 32051\).
p = 32051
is_prime(p)
True
We have that \(g = 10\) is a primitive element:
g = Mod(10, p)
g.multiplicative_order() == p - 1
True
Let’s then find the discrete log base \(g = 10\) of \(h = 1205\) in \(\mathbb{F}_{32051}\).
h = Mod(1205, p)
We will use \(B = 19\) with our method. Let’s save the corresponding primes in the primes list.
B = 19
B_primes = prime_range(B + 1)
B_primes
[2, 3, 5, 7, 11, 13, 17, 19]
Our first steps is to compute \(\log_g(\ell)\) for all primes \(\ell \leq B\). We will learn below how to do that in an efficient way, but here we will simply use Sage’s discrete_log function. (You will do the same in your homework!)
logs_B = [discrete_log(Mod(l, p), g) for l in B_primes]
logs_B
[22975, 28220, 9076, 15394, 27232, 19677, 6533, 903]
Now, we first check if \(h\) is \(B\)-smooth.
Important
We should not use factor to check if a number n is \(B\)-smooth. The proper way would be
n == prod(p^valuation(n, p) for p in primes(B + 1))
On the other hand, in the present case, we not only need to determine if numbers are \(B\)-smooth, but also need the corresponding prime factorization. Therefore, we save the exponents (i.e., the valuation(n, p)) in a list to obtain the corresponding factorization in the \(B\)-smooth case.
element = ZZ(h) # convert to an integer
exponents = [valuation(element, l) for l in B_primes] # exponents
element == prod(l^r for l, r in zip(B_primes, exponents)) # is it B-smooth?
False
So, \(h\) is not \(B\)-smooth. We then try \(h \cdot g^{-1}\):
g_inv = g^(-1) # compute it only once!
element = ZZ(h * g_inv)
exponents = [valuation(element, l) for l in B_primes]
element == prod(l^r for l, r in zip(B_primes, exponents))
False
Since it is not \(B\)-smooth, we try \(h \cdot g^{-2}\):
element = ZZ(element * g_inv)
exponents = [valuation(element, l) for l in B_primes]
element == prod(l^r for l, r in zip(B_primes, exponents))
False
We keep trying \(h \cdot g^{-3}, h \cdot g^{-4}, \ldots\) until we find a \(B\)-smooth one:
element = ZZ(element * g_inv) # i = -3
exponents = [valuation(element, l) for l in B_primes]
element == prod(l^r for l, r in zip(B_primes, exponents))
False
element = ZZ(element * g_inv) # i = -4
exponents = [valuation(element, l) for l in B_primes]
element == prod(l^r for l, r in zip(B_primes, exponents))
False
element = ZZ(element * g_inv) # i = -5
exponents = [valuation(element, l) for l in B_primes]
element == prod(l^r for l, r in zip(B_primes, exponents))
True
Ah, so \(h \cdot g^{-5}\) is \(B\)-smooth. According to (14.1), we have that the discrete log \(\log_g(h)\) is:
disc_log = (5 + sum(r * log_l for r, log_l in zip(exponents, logs_B))) % (p - 1)
disc_log
15754
And we can double check it with Sage:
g^disc_log == h
True
Homework
You will implement this algorithm in your homework.
14.2.2. Discrete Logs of Small Primes#
So, how can we efficiently compute \(\log_g(\ell_1), \log_g(\ell_2), \ldots, \log_g(\ell_n)\)?
The idea is to choose some random exponents \(a \in \mathbb{Z}/(p-1)\mathbb{Z}\) and compute \(g^{a}\). If the result is \(B\)-smooth, we save it in a list, if not, we discard it and try another random \(a\). We repeat this process until we have enough \(B\)-smooth powers of \(g\). We need at least \(\pi(B)\) (i.e., the number of primes less than or equal to \(B\), which we denoted by \(n\) here) distinct powers of \(g\).
So, assume that we have exponents \(a_1, a_2, \ldots, a_m\) (for some \(m \geq n = \pi(B)\)), with \(g^{a_i}\) \(B\)-smooth, say:
Taking \(\log_g\), we obtain
Note that all the \(a_i\)’s and \(r_{i,j}\)’s are known, and we are trying to find the \(\log_g(\ell_j)\)’s. These should be then the solution of the system
with \(x_j\) found being \(\log_g(\ell_j)\). So, we just need to solve this system!
14.2.2.1. Example#
Let’s see how to produce the matrix and vector associated to this system in Sage.
Let’s take \(p=331\) and find a primitive root \(g\):
p = 331
F = FiniteField(p)
g = F.primitive_element()
Let’s take \(h = 200\) (in \(\mathbb{F}_{331}\)).
h = F(200)
First, let’s create a list of primes less than \(B = 30\):
list_l = prime_range(30)
list_l
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Now, let’s save the length of this list (which \(\pi(30)\), with our previous notation):
pi_B = len(list_l)
Now, we need to find \(\pi(B)\) different \(a\)’s such that \(g^a\) is \(B\)-smooth. For each one of these, we save as a row of our matrix the exponents of the prime decomposition of \(g^a\) for each of the primes in our list list_l. (Since \(g^a\) is \(B\)-smooth, this list contains all the primes in the factorization of \(g^a\).)
Let’s initialize some variables:
used_as = set() # set of used a's, to avoid repeating!
coef_matrix = [] # matrix of coefficients
va = [] # vector with the a's
Let’s add elements:
while len(va) < pi_B: # need pi_B elements
a = randint(1, p - 1) # a to try
# make sure it hasn't been used:
while a in used_as:
a = randint(1, p - 1) # try another
used_as.add(a) # add this a to our set
gi = ZZ(g^a) # our power of g
# we might need the valuations more than once:
# - to check if gi is B-smooth, and
# - if B-smooth, to get the row of the matrix
# if gives the exponents of each prime in list_l in the factorization of gi
valuations = [valuation(gi, l) for l in list_l]
if gi == prod(l^val for l, val in zip(list_l, valuations)): # is gi B-smooth?
# if so
va.append(a)
coef_matrix.append([val % (p - 1) for val in valuations])
Now coef_matrix should be the list of rows for our matrix:
coef_matrix
[[0, 0, 2, 1, 0, 0, 0, 0, 0, 0],
[0, 2, 0, 0, 0, 0, 1, 0, 0, 0],
[0, 3, 0, 1, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 1, 0, 0, 0, 0, 1, 0],
[2, 0, 0, 2, 0, 0, 0, 0, 0, 0],
[2, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 0, 1, 0, 0, 0, 0, 0],
[3, 0, 0, 0, 0, 0, 0, 1, 0, 0],
[2, 1, 2, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 1, 0, 1, 0, 0, 0, 0]]
And va should be the list that gives the necessary vector:
va
[223, 186, 84, 167, 74, 183, 165, 47, 55, 227]
We can check if it worked. Let’s compute the list of the discrete logs (which is what this matrix and vector would allow us to compute) directly using Sage:
list_dl = [discrete_log(F(l), g) for l in list_l]
list_dl
[121, 1, 236, 81, 137, 145, 184, 14, 295, 271]
If our work is correct, multiplying the matrix given by coef_matrix by the vector of discrete logs, it would give our vector va:
MM = matrix(Zmod(p - 1), coef_matrix)
xx = vector(Zmod(p - 1), list_dl)
aa = vector(Zmod(p - 1), va)
MM * xx == aa
True
It works!
Homework
In your homework you will write the code to obtain the matrix of coefficients of the system above. This basically means a list containing the rows of the system (which is itself another list). But you will not implement the solution of the system.
But there is a problem: the coefficients (since they are all exponents) are in \(\mathbb{Z}/(p-1)\mathbb{Z}\), which is not a field (like the real numbers or \(\mathbb{F}_p\)), so solving the system is not as straight forward. But it still can be done, and here is the (vague) idea on how to do it:
For each prime factor \(q\) of \(p-1\), we solve the system modulo \(q\) (i.e., in the field \(\mathbb{F}_q\), where our methods for solving systems work well).
If \(q^s\) is the largest power of \(q\) dividing \(p-1\), then we “lift” the solution we’ve found (modulo \(q\)) to a solution modulo \(q^s\). (The method to do this is similar to Theorem 13.5 or Theorem 13.6.)
We use the Chinese Remainder Theorem to “patch” these solutions to a solution modulo \(p-1\). More precisely, if \(p-1 = q_1^{s_1} q_2^{s_2} \cdots q_t^{s_t}\), and if we’ve obtained \(x_i \equiv b_{i,j} \pmod{q_j^{s_j}}\) for \(j = 1, 2, \ldots, t\), solving
(with the Chinese Remainder Theorem) we obtain the solution \(\log_g(\ell_i)\) (in \(\mathbb{Z}/(p-1)\mathbb{Z}\)).
Important
Constructing the matrix of coefficients is time consuming! So, with ElGamal we want \(p-1\) to not have small prime factors other than \(2\), to make this process as difficult as possible. Again, the ideal is to have \((p-1)/2\) to be prime.
14.2.3. Adapting it to Break the ElGamal Cryptosystem#
In the ElGamal cryptosystem, instead of taking the base of the discrete log to be a primitive root, we take it to be an element of large prime order, say \(q\). The process above needs \(g\) to be a primitive element, so we can find \(\log_g(\ell_i)\) for \(i\). (If \(g\) is not a primitive root, these discrete logs might not exist!) But we can easily adapt our method to this situation.
If \(|g_1| = q\) and we want to compute \(\log_{g_1}(h)\), we first find a primitive root \(g\). In the most common case, when \(q = (p-1)/2\), we have a special method, which was part of Homework 3: it suffices to try random elements in \(\mathbb{F}_p^{\times}\) different from \(1\) and \(-1\) until we have one whose the \(q\)-th power is not \(1\). This element will be a primitive root. Since there is a \(50\%\) change that this random element will be a primitive root, this process should take only a few tries.
Then, using the index calculus method, we compute \(\log_g(g_1)\) and \(\log_g(h)\). Then, we have that \(\log_{g_1}(h) = \log_g(h) / \log_g(g_1)\). This is just the change of base formula for logs, but we can verify it directly:
Note
One can generalize the discrete log and ElGamal cryptosystem by replacing \(\mathbb{F}_p^{\times}\) with an arbitrary group. (We will do this in a later chapter.) While our previous methods for computing the discrete log (e.g., Shanks Baby-Step/Giant-Step, Pohlig-Hellman) generalize for arbitrary groups, this index calculus algorithm (introduced here) does not. Since it is the faster than the previous methods, to make ElGamal more secure, one can use different groups instead of \(\mathbb{F}_p^{\times}\).