6. Discrete Logs, Diffie-Hellman Key Exchange, and the ElGamal Cryptosystem

6.1. The Discrete Log Problem

6.1.1. Logarithms

Remember how logarithms work: if you are asked was is \(\log_{\color{red} 2}({\color{blue} 4})\), what you are being asked is what power of \({\color{red} 2}\) gives us \({\color{blue} 4}\)? In other words, the answer is the value of \(x\) such that \({\color{red} 2}^x = {\color{blue} 4}\). In this case, the answer is easy: since \({\color{red} 2}^2 = {\color{blue} 4}\), we have that \(\boxed{\log_2(4) = 2}\).

That is essentially all that there is to logs. On the other hand, it clearly is harder than computing powers. If I asked you what is \(5^3\), you simply compute it directly: \(5^3 = 5 \cdot 5 \cdot 5 = 125\). But if I ask you what is \(\log_5(125)\), you do not compute it directly: you solve \(5^x = 125\) for \(x\). (And this solution is \(\log_5(125)\), which is \(3\) in this case.)

This is similar to how to compute square roots. To compute, say, \(\sqrt{9}\) we do not do (in general) perform a direct computation, but solve the equation \(x^2 = 9\), for which the non-negative solution will be our answer.

6.1.2. Discrete Logs

Now suppose we have some elements \(a, g \in \mathbb{Z}/m\mathbb{Z}\). One might ask if there is some power \(k\) such that \(a = g^k\). Note that is the same question that the logarithm asks: what is the power of \(g\) that gives us \(a\). Hence, if \(g^k = a\), we write, similar to real numbers, that \(k = \log_g(a)\).

For real numbers we know that if the base \(b\) of the log is positive and different from \(1\), and \(a\) is positive, then \(\log_b(a)\) exists, meaning, there is indeed some unique power of \(b\) that gives \(a\). This questions is a bit harder to answer for logs in \(\mathbb{Z}/m\mathbb{Z}\). For instance, in \(\mathbb{Z}/8\mathbb{Z}\), no power of \(2\) can give you \(3\). There are few ways to check that this is indeed true, but let’s do it computationally with Sage.

To do so, we can simply start computing the powers \(2^0\), \(2^1\), \(2^2\), etc., in \(\mathbb{Z}/8\mathbb{Z}\). First, how many times do we have to compute these powers? In other words, is there a way to know when we can stop computing these and be sure that no positive integer power will ever give us \(3\)?

If we get a repetition, then the values of the powers will start repeating themselves (in the same order). After all, if \(2^k = 2^l\), then

\[2^{k+r} = 2^r \cdot 2^k = 2^r \cdot 2^l = 2^{l+r},\]

for any positive integer \(r\).

So, if we get a repetition before getting \(3\), we will never get \(3\).

So, let’s check:

Mod(2, 8)^2

4

Mod(2, 8)^3

0

Mod(2, 8)^4

0

Ah, since we got \(0\) again, we know that from now on you we will only get zeros, and we can stop. No power of \(2\) will ever give us \(3\) in \(\mathbb{Z}/8\mathbb{Z}\). The powers can only give us \(1\) (power \(0\)), \(2\) (power \(1\)), \(4\) (power \(2\)), and \(0\) (any power \(3\) or larger). So, in this case we say that \(\log_2(3)\) (in \(\mathbb{Z}/8\mathbb{Z}\)) does not exist.

As another example, we can see, still in \(\mathbb{Z}/8\mathbb{Z}\), that \(\log_3(5)\) does not exist, i.e., there is no power of \(3\) that gives \(5\):

Mod(3, 8)^2

1

Ah, we already have a repetition since \(3^0 = 1\), \(3^1=3\), and \(3^2 = 1\). So, we know that the powers will just repeat, giving \(1\), \(3\), \(1\), \(3\), … In fact, if \(n\) is even, we get \(3^n = 1\), and if odd we get \(3^n = 3\), due to this pattern.

On the other hand, sometimes the discrete log does exist! A simple one, still in \(\mathbb{Z}/8\mathbb{Z}\), is \(\log_3(1)\): we have that \(3^0 = 1\), so \(\log_3(1) = 0\).

But wait! We also have that \(3^2 = 1\). In fact, any positive even integer power of \(3\) would give \(1\), as we’ve just seen. So, which one of these powers is \(\log_3(1)\)? Let’s postpone the answer for a little while, but we will come back to this issue later.

6.1.2.1. Terminology

We call a log in \(\mathbb{Z}/m\mathbb{Z}\) a discrete log, as the result is a subset of the integers, not the real numbers. The integers are called discrete because its separated from each other by gaps in the real line. Conversely, the real numbers are continuous, since there are not gaps between real numbers (in the real line) that is not filled by real numbers.

More generally, a discrete log is any kind of log (meaning, situations where we are asking for powers) where the results are integers. We will mostly work for discrete logs in \(\mathbb{Z}/m\mathbb{Z}\), although later we will talk about discrete logs in elliptic curves.

6.1.2.2. Properties

The discrete log has similar properties to the regular log:

Property 6.1 (Discrete Log Properties)

1. If \(\log_g(a)\) and \(\log_g(b)\) both exist, then \(\log_g(ab)\) also exists and \(\boxed{\log_g(ab) = \log_g(a) + \log_g(b)}\).

2. If \(\log_g(a)\) exists and \(k\) is a positive integer, then \(\log_g(a^k)\) also exists and \(\boxed{\log_g(a^k) = k \cdot \log_g(a)}\).

6.1.3. Computing the Discrete Log

Again, when trying to compute a discrete log, we are not sure in principle, if it exists or not. But, there is one case when are sure that it does. If \(g\) is a primitive root of \(\mathbb{Z}/p\mathbb{Z}\), where \(p\) is prime, and \(a\) is a unit, then we know that \(\log_g(a)\) exists, since every unit is a power of \(g\).

Moreover, in this case, the question of how we properly define the discrete log, since multiple powers of \(g\) can give \(a\), is to think of the exponent, and so the values of the discrete log, in \(\mathbb{Z}/(p-1)\mathbb{Z}\). This works, since, as we’ve seen before, we have that \(|g| = \varphi(p) = p-1\) and hence we can consider the exponents of \(g\) modulo \(p-1\). (More generally, if \(g\) is not primitive root, we consider exponents, and so the values of the discrete log, in \(\mathbb{Z}/|g|\mathbb{Z}\).)

Note that with the usual log (with real numbers), we have numerical methods that allow us to compute these logs fairly quickly. But discrete log, although similar in concept, is very different. If you look at consecutive powers of a single primitive root \(g\) in \(\mathbb{Z}/p\mathbb{Z}\), they seem to just bounce randomly, making it difficult to predict the value, and hence difficult to compute discrete logs.

For instance, in \(\mathbb{Z}/31\mathbb{Z}\), we have that \(17\) is a primitive root. Here are the powers of \(17\), in order:

Table 6.1 Powers of \(17\) in \(\mathbb{Z}/31\mathbb{Z}\)

\(k\)	\(17^k\)		\(k\)	\(17^k\)		\(k\)	\(17^k\)
0	1		10	25		20	5
1	17		11	22		21	23
2	10		12	2		22	19
3	15		13	3		23	13
4	7		14	20		24	4
5	26		15	30		25	6
6	8		16	14		26	9
7	12		17	21		27	29
8	18		18	16		28	28
9	27		19	24		29	11

As you can see, the powers do not seem to follow any pattern.

list_plot([power_mod(17, x, 31) for x in range(30)])

Therefore, at this point the only method we see to compute the discrete log is brute force: to compute \(\log_g(a)\), we start computing powers of \(g\), i.e., \(g^0\), \(g^1\), \(g^2\), etc., until we either get \(a\) or get a repeated power, in which case the log does not exist. This make this computation extremely time consuming if \(|g|\) is a really large number, and as we will soon see, we can use this difficulty to create a cryptosystem that is difficult to break.

Definition 6.1 (The Discrete Log Problem (DLP))

We call the (computationally intensive) problem of computing a discrete log \(\log_g(a)\), i.e., finding a power \(x\) (in \(\mathbb{Z}/|g|\mathbb{Z}\)) such that \(g^x = a\) in \(\mathbb{Z}/m\mathbb{Z}\), the discrete log problem (DLP).

6.2. Cryptosystems

A Cryptosystem is a set of algorithms used in the transmission of private messages.

As we’ve mentioned before, the usual scenario is when Bob wants to send Alice some secret message so that even if their enemy Eve intercepts the message, she will not be able to read its content.

This means that Bob needs a way to encode the message and Alice needs a way to decode Bob’s encoded message, and the decoding process must difficult enough that, without some secret knowledge, Eve should not be able to discover the decoding method.

Formally, we write that if \(m\) is the plain/unencrypted message, then Bob uses some encoding key, say \(e\), to create a function \(E_e\), called the encryption function, which depends on the key \(e\), so that \(E_e(m)\) produces the encrypted message.

Alice then uses a decoding key \(d\) (which will depend on the encoding key \(e\)) to produce a decryption function \(D_d\) that can recover an encrypted message, i.e., such that \(D_d(E_e(m)) = m\).

In our example of the Caesar Cipher, the encryption key \(e\) was the table that would permute the letters of the alphabet, and the encryption function would use the table \(e\) to replace the letters. The decoding key \(d\) was the inverse table of \(e\), and the decoding function would use this reversed table to replace the letters based on this new table \(d\).

6.3. Symmetric versus Asymmetric Cryptosystems

In our Caesar Cipher example, as mentioned before, knowledge of the encryption table/key \(e\) would automatically tell Eve what the decryption key \(d\) should be. This is an example of what we call a symmetric cryptosystem: the same key allows for both encrypting and decrypting messages.

But again, this raises the problem of how will Alice and Bob exchange the encryption/decryption key. A better method would be to have an asymmetric cryptosystem, i.e., one in which Alice can provide publicly an encoding key to Bob (or anyone else who might want to send her a message), but keep secret her decoding key, with the obvious assumption that is hard to obtain the decoding key from the publicly available decoding key. In this situation the encoding key is called the public-key and the decoding key is called the private key. For this reason, these asymmetric cryptosystems are also called public-key cryptosystems.

Of course, the real question is how to create such a system. Most of the naive methods one can come up with will be symmetric. But before we do that, let’s see if we can find a safe way to exchange a secret key for a symmetric cryptosystem.

6.4. The Diffie-Hellman Key Exchange

If you have a symmetric cryptosystem, you are faced with the problem of sharing the encryption/decryption key. Whitfield Diffie and Martin Hellman proposed in 1976 a clever method to do so, based on the discrete log problem (DLP). Here is how it goes:

The Diffie-Hellman Key Exchange:

1. A trusted party publishes:

   • a large prime \(p\) and

   • an element \(g\) of \(\mathbb{F}_p^{\times}\) of large prime order \(q\). (The order \(q\) is also public.)

2. Alice chooses a secret integer \(a\), and Bob chooses a secret integer \(b\).

3. Alice computes \(A = g^a\) and publicly sends the result \(A\) to Bob. (So, \(A\) is known, but not the exponent \(a\) to produce it.) Similarly, Bob computes \(B = g^b\) and publicly sends the result \(B\) to Alice.

4. Alice computes \(B^a\) and Bob computes \(A^b\). These values are equal and that is their shared key.

Note that \(A^b = (g^a)^b = g^{ab}\) and \(B^a = (g^b)^a = g^{ba} = g^{ab}\), and that’s why \(A^b = B^a\). This element of \(\mathbb{F}_p^{\times}\) is their shared key.

Eve, Alice and Bob’s enemy, will know \(p\), \(g\), \(q\), \(A\), and \(B\), since these are all public, but will not know \(a\) and \(b\). Only Alice knows \(a\) and only Bob knows \(b\). Now Alice and Bob can, somehow, use their shared key to produce they key for a symmetric cryptosystem.

Note

The numbers involved are very large in general, so one would have to compute very large powers of \(g\). So, you can see how the Fast Powering Algorithm.

We will discuss the security of this method below.

6.4.1. Finding \(q\) and \(g\)

How would one find the \(g\), with large order \(q\) in \(\mathbb{F}_p^{\times}\)? Let’s first think about its order, which we called \(q\). We want it to be as large as possible. As we’ve seen in a previous proposition, we know that \(|g| = q \mid \varphi(p)=p-1\). Since \(p\) is odd, being a prime different from \(2\), the largest that \(q\) could be is if \(p-1 = 2q\). So, to find the pair \(p\) and \(q\), we look for a \(p\) of the desired size, and check if \((p-1)/2\) is also prime. If so, \(q = (p-1)/2\) works.

We can do that relatively easy with Sage for primes of reasonable size:

%%time

# let's find a 64-bit prime
lower_bound = 2^63
upper_bound = 2^64 - 1

while True:
    p = random_prime(upper_bound, lbound=lower_bound)
    q = (p - 1) // 2
    if is_prime(q):
        break

print(f"We can take {p = } and {q = }.")

We can take p = 18156127522675026527 and q = 9078063761337513263.
CPU times: user 264 µs, sys: 0 ns, total: 264 µs
Wall time: 264 µs

Here is some details about the system used for this computation:

!inxi --system --cpu --memory

System:
  Host: dell7010 Kernel: 6.17.8-1-siduction-amd64 arch: x86_64 bits: 64
  Desktop: KDE Plasma v: 6.5.3 Distro: siduction 22.1.2 Masters_of_War -
    kde - (202303220911)
Memory:
  System RAM: total: 128 GiB available: 125.51 GiB used: 22.23 GiB (17.7%)
  Array-1: capacity: 128 GiB slots: 4 modules: 4 EC: None
  Device-1: DIMM1 type: DDR5 size: 32 GiB speed: spec: 4800 MT/s
    actual: 3600 MT/s
  Device-2: DIMM2 type: DDR5 size: 32 GiB speed: spec: 4800 MT/s
    actual: 3600 MT/s
  Device-3: DIMM3 type: DDR5 size: 32 GiB speed: spec: 4800 MT/s
    actual: 3600 MT/s
  Device-4: DIMM4 type: DDR5 size: 32 GiB speed: spec: 4800 MT/s
    actual: 3600 MT/s

CPU:
  Info: 24-core model: 13th Gen Intel Core i9-13900 bits: 64 type: MCP cache:
    L2: 32 MiB
  Speed (MHz): avg: 800 min/max: 800/5300:5600:4200 cores: 1: 800 2: 800
    3: 800 4: 800 5: 800 6: 800 7: 800 8: 800 9: 800 10: 800 11: 800 12: 800
    13: 800 14: 800 15: 800 16: 800 17: 800 18: 800 19: 800 20: 800 21: 800
    22: 800 23: 800 24: 800

Now, how do we find \(g\), and element of \(\mathbb{F}_p^{\times}\) of order \(q\)?

If we take a random element of \(a\) of \(\mathbb{F}_p^{\times}\), we know that \(|a| \mid p-1 = 2q\). Since \(q\) is prime, the only possible orders for \(a\) are \(1\) (and only the element \(1\) of \(\mathbb{F}_p^{\times}\) has order \(1\)), \(2\) (and one can show that the only \(-1 = p - 1\) has order \(2\) in \(\mathbb{F}_p^{\times}\)), \(q\), or \(2q\).

Now, we can compute \(a^2\). If we get \(1\), then \(a\) is either \(1\) or \(p-1\), and we try a different random \(a\). But if \(a^2 \neq 1\), then, either \(|a| = q\) or \(|a|=2q\).

If \(|a|=q\), then, by the Order of a Power Proposition from a previous chapter, we have that

\[|a^2| = \frac{q}{\gcd(q, 2)} = \frac{q}{1} = q,\]

since \(q\) is odd.

If \(|a|=2q\), then, by the same result, we have that

\[|a^2| = \frac{2q}{\gcd(2q, 2)} = \frac{2q}{2} = q.\]

Hence, in either case \(a^2\) gives us an element of order \(q\).

So, we have, when \(p = 2q + 1\), with \(p\) and \(q\) primes, to find an element of order \(q\) we simply take an random element \(a\) between \(2\) and \(p-2\), and square it, i.e., we take \(g = a^2\).

More generally, when we do not necessarily have that \(q = (p-1)/2\), but simply a prime number dividing \(p-1\), we have:

Proposition 6.1 (Finding \(g\))

Given primes \(p\) and \(q\), with \(q\) dividing \(p-1\), and a random element \(a \in \mathbb{F}_p^{\times}\), then the probability that \(a^{\frac{p-1}{q}}\) has order \(q\) is \((q-1)/q\). (If \(q\) is large, this probability is quite high!)

Homework

In your homework you will implement this general method of finding \(g\) of order \(q\) and check the statement about the probability above.

6.4.2. Example

Let’s do a quick example. First, let’s use a prime \(p\) between \(100{,}000\) and \(200{,}000\), such that \((p-1)/2\) is also prime. (This size is too small for it to safe, but will illustrate the process.)

while True:
    p = next_prime(randint(10^5, 2*10^5))
    q = (p-1) // 2
    if is_prime(q):
        break

print(f"We have {p = }, and {q = }.")

We have p = 103043, and q = 51521.

We also need some element \(g\) in \(\mathbb{F}_p^{\times}\) of order \(q\).

g = Mod(randint(2, p-2), p)^2
g

89374

Let’s check its order:

g.multiplicative_order() == q

True

Now Alice takes a random \(a\) between \(2\) and \(q - 1\):

a = randint(2, q - 1)
a

6186

And Bob takes and random \(b\) in the same range:

b = randint(2, q - 1)
b

29166

Alice computes \(A = g^a\):

A = g^a
A

19674

And Bob computes \(B = g^b\):

B = g^b
B

102305

So, now Alice sends Bob \(A\), i.e., , and Bob sends Alice \(B\), i.e., , while keeping \(a\) and \(b\) for themselves.

Then, Alice computes \(B^a\), with \(B\) from Bob and her private key \(a\):

B^a

60527

And Bob computes \(A^b\), with \(A\) from Alice and his private key \(b\):

A^b

60527

As you can see, it is the same number, the same as \(g^{ab}\):

g^(a * b)

60527

6.4.3. Finding the Shared Key

How could Eve find the shared key \(g^{ab}\) without knowing \(a\) and \(b\)? In other words, how can she solve the Diffie-Hellman Problem:

Definition 6.2 (Diffie-Hellman Problem)

We call the Diffie-Hellman Problem the problem of being able to break the Diffie-Hellman key exchange, namely: given a prime \(p\), \(g \in \mathbb{F}_p^{\times}\), and \(A=g^a\) and \(B=g^b\) (without knowing \(a\) and \(b\) themselves), find \(g^{ab}\).

If she can solve the discrete log problem, then she can solve the Diffie-Hellman problem: Eve computes \(\log_g(A)\), which is just \(a\), and then, as Alice does, gets the shared key as \(B^a\).

It is not known if the converse is true, namely, if one can solve the Diffie-Hellman problem, then somehow one can also solve the discrete log problem.

6.4.4. Security Considerations

Is the Diffie-Hellman Key Exchange secure in general? If \(p\) (from \(\mathbb{F}_p^{\times}\)) and \(q = |g|\) are large enough, and \(a\) and \(b\) are randomly generated number between \(2\) and \(q-1\) (and therefore likely quite large as well), it is believed to be secure, because the discrete log and Diffie-Hellman problems are believed to be difficult to solve.

Note

In general we want \(p\) to have at least \(2048\) bits, i.e., we want \(p \geq 2^{2047}\) (noting that \(2^{2047}\) has \(617\) digits), and if possible have the prime \(q\) to be simply \((p-1)/2\), the largest possible order of an element in \(\mathbb{F}_p^{\times}\). This would mean that \(q\) would be a \(2047\)-bit prime.

Choosing \(a\) and \(b\) randomly is also strongly encouraged, as to avoid numbers that are easier to guess, like birth dates, phone numbers, addresses, etc.

But why is the discrete log and Diffie-Hellman problems believed to be safe? Mostly because those are mathematical problems that mathematicians, including some of the most capable individuals one can expect to find, have been trying to solve for a relatively long time. Moreover, as researchers, mathematicians would most likely publish any solution they find, instead of secretly keeping the solution to themselves.

But note that we have no guarantee that some very clever individual will come up with an ingenious solution tomorrow. Or that this individual, or nation, will not be tempted to keep the solution secret for personal, financial, or military gains. But basing security of cryptosystems in long standing mathematical problems is the best idea we have so far.

Also note that if the order of the element \(g\) were not prime, then we can compute \(|A| = |g^a|\) and if \(|A| \neq |g|\), which is possible when \(|g|\) is not prime, then by the Order of a Power Proposition (from a previous chapter), we know that

\[|A| = \frac{|g|}{\gcd(|g|, a)} \qquad \Longrightarrow \qquad \gcd(|g|, a) = \frac{|g|}{|A|},\]

and hence, since \(|g|\) is known, we can find \(\gcd(|g|, a)\), a divisor of \(a\), giving us some information about Alice’s private key \(a\). In particular, one can try to guess it by trying multiples of this found GCD.

Even more importantly, if \(|g|\) is not prime, there are methods that increase the efficiency of computing the discrete log \(\log_g(A)\) (as above), making the key exchange considerably less secure! (This will be discussed in the chapter Improvements on Computations of Discrete Logs.)

6.4.5. Public Setup

A great advantage of a public setup step, as step 1 of the Diffie-Hellman Key Exchange is that we can copy the setup (i.e., the \(p\), \(g\), and \(q\)) from some organization using the depend on its security, like the National Security Agency or some large online retailer, like Amazon, as they have certainly devoted considerable resources to make sure that their setup is secure.

6.5. The ElGamal Public-Key Cryptosystem

The Diffie-Hellman key exchange allows us to have a shared key with each one can set up some public-key cryptosystem (based on this key). But how can one actually do it? Taher ElGamal in 1985 introduce the ElGamal Cryptosystem based on Diffie-Hellman.

Note

The ElGamal cryptosystem was not the first public-key cryptosystem. The RSA Cryptosystem was introduce in 1977, one year after the introduction of the Diffie-Hellman key exchange, but, unlike ElGamal, it does not use it. We will introduce the RSA cryptosystem in a later chapter.

We will now describe the cryptosystem, but observe that, for now, we will assume that the message to be exchanged between Bob and Alice is a number. We describe how to deal with text below.

6.5.1. Steps for ElGamal Encryption

1. Set up: Choose and publish large prime \(p\) and element \(g \in \mathbb{F}_p^{\times}\) of large prime order.

2. Key Creation: Alice chooses a private key \(a \in \{2, 3, \ldots, p-2\}\) and publishes \(A = g^a\) (in \(\mathbb{F}_p^{\times}\)).

3. Encryption: To encrypt the message \(m\) (a number between \(1\) and \(p-1\)), Bob chooses a random ephemeral key (i.e., a random key to be discarded after a single use) \(k\) in \(\mathbb{F}_p^{\times}\), computes \(c_1 = g^k\), and \(c_2=mA^k\) (both in \(\mathbb{F}_p^{\times}\)), and sends the pair \((c_1, c_2)\) to Alice. (This pair is the encrypted message.)

4. Decryption: To decrypt \((c_1, c_2)\) sent by Bob, Alice, using her private key \(a\), computes \((c_1^a)^{-1} \cdot c_2\) (in \(\mathbb{F}_p\)). This last expression is equal to the message \(m\).

Let’s check that this process works. We have

\[\begin{split}\begin{align*} (c_1^a)^{-1} \cdot c_2 &= {\left({\left(g^k\right)}^a\right)}^{-1} \cdot m A^k && \text{(since $c_1 = g^k$, and $c_2=mA^k$)}\\ &= {\left(g^{ak}\right)}^{-1} \cdot m A^k\\ &= {\left({\left(g^a\right)}^k\right)}^{-1} \cdot m A^k \\ &= {\left(A^k\right)}^{-1} \cdot m A^k && \text{(since $g^a = A$)}\\ &= m \cdot (A^k)^{-1} A^k \\ &= m. \end{align*}\end{split}\]

Note

Note that inside this process we have an Diffie-Hellman key exchange: Alice has \(A = g^a\) and Bob has \(g^k\), with the shared key being \(A^k = g^{ak}\), which Alice uses for decryption when she computes \(c_1^a\).

6.5.2. Example

6.5.2.1. Set Up

We can use the same \(p\) and \(g\) we’ve used for Diffie-Hellman above (or one can repeat the same steps, of copy the set up from a trusted source):

print(f"We will use {p = } and {g = }.")

We will use p = 103043 and g = 89374.

6.5.2.2. Private/Public Keys

Alice can just choose her private key \(a\) as a random number:

a = randint(2, p - 2)
print(f"Alice will use {a = }.")

Alice will use a = 63359.

Finally, Alice publishes \(A=g^a\):

A = g^a

6.5.2.3. Encryption

Now, suppose that Bob wants to send Alice the last four digits of his Social Security Number, say \(m = 1234\).

Note

Note that the size of \(p\), in principle, restricts the size of numbers that Bob can send Alice, as it needs to be between \(0\) and \(p-1\). But we will see how to deal with this restriction later.

m = Mod(1234, p)

Now, Bob chooses his random ephemeral key \(k\) (to be used only once):

k = randint(2, p - 2)

Then, computes \(c_1\) and \(c_2\) and gets the encrypted message \((c_1, c_2)\):

c1 = g^k
c2 = m * A^k
encrypted_message = (c1, c2)

encrypted_message

(19974, 15400)

Bob then sends \((c_1, c_2)\) to Alice.

6.5.2.4. Decryption

Alice receives \((c_1, c_2)\) and decrypts with the formula \((c_1^a)^{-1} \cdot c_2\) as above. We should get the original message \(m = 1234\) as the result:

c1, c2 = encrypted_message  # Alice reads c1 and c2 from encrypted message received
(c1^a)^(-1) * c2

1234

Homework

As usual, you will implement these steps more generally in your homework.

6.5.3. Security Considerations

Again, as for the Diffie-Hellman key exchange, we need the order of \(g\) to be prime, and again, the best possible scenario is when \(|g| = (p-1)/2\) and prime.

The fact that \(g\) has prime order is essential, as there are faster methods to compute discrete logs when it is not.

Also note that in the encryption process, Bob should use an ephemeral private key \(k\), meaning that he should randomly generate a new key for each message. This increases security as if somehow Eve knows that some message \(m\) was encrypted and \((c_1, c_2)\) was the encrypted message, then she can decrypt any other encrypted message. Say that Bob encrypts another message \(m'\) using \(k\) again, and resulting on the encrypted message \((c_1', c_2')\), then Eve can find the new secret message \(m'\) by computing \(m \cdot c_2'/c_2\), since:

\[\begin{split}\begin{align*} m \cdot \frac{c_2'}{c_2} &= m \cdot \frac{m' \cdot A^k}{m \cdot A^k} && \text{(since using $k$ again)} \\ &= m \cdot \frac{m'}{m} \\ &= m'. \end{align*}\end{split}\]

6.6. A Note on Quantum Computers

It is important to note that there are theoretical methods, based on Shor’s Algorithm, to efficiently compute discrete log with quantum computers. This would effectively make ElGamal cryptosystem unsafe!

Although there have been some progress in the area and some “small” quantum computers already exist, they still have very limited capability. There is debate on how feasible it is to scale these to more capable computers, with a wild range of estimates for how long it will take for these to become a threat to cryptosystems currently in use. As an anecdote (with no value for a scientific debate), the author has been hearing the quantum computers will be fast enough to break the current cryptosystems “in the next five years” for almost twenty years. Maybe that is now true (or maybe even sooner!), but maybe some will keep repeating that statements for the next twenty years.

It should be noted that the threat is not simply because these quantum computers would much faster than our current ones, but that their architecture allows some problems to be solved a lot more efficiently, and the discrete log problem would be one those.

Therefore there is current research on quantum cryptography and post-quantum (or quantum-safe) cryptography, i.e., the search for new cryptosystems that could remain safe after quantum computers become powerful enough to threat the current methods. For example, one current candidate for quantum-safe methods is lattice based cryptography.

The problem with these new methods is that most of them are based in newer mathematical and computational problems, which have not stood the test of several years of mathematicians and computer scientists trying to solve them, making their security less certain. Moreover, the switch to new encryption methods would be very costly to industry and governments, so these new methods are not currently being implemented in scale.

Important

None of the publick-key encryption methods discussed in this book is quantum-safe! Only the Advanced Encryption Standard (AES) covered here is quantum-safe, but it is not a public-key cryptosystem (the same key is used for both encryption and decryption), and therefore is usually used along with one for key exchange.

Even then, we believe that the ideas introduced here work as a good introduction to the ideas of cryptography in general, independent of the particular methods.

6.7. Encrypting Text and Large Numbers

6.8. Converting Text

The ElGamal cryptosystem, as well as others we will learn, encode numbers. But in practice, we often need to encode text. Therefore, we need a way to convert text to numbers and vice-versa. One way is to again use the corresponding ASCII value of a character.

Table 6.2 ASCII Table

Decimal Value	Character		Decimal Value	Character		Decimal Value	Character		Decimal Value	Character
0	NUL (null)		32	SPACE		64	@		96	`
1	SOH (start of heading)		33	!		65	A		97	a
2	STX (start of text)		34	“		66	B		98	b
3	ETX (end of text)		35	#		67	C		99	c
4	EOT (end of transmission)		36	$		68	D		100	d
5	ENQ (enquiry)		37	%		69	E		101	e
6	ACK (acknowledge)		38	&		70	F		102	f
7	BEL (bell)		39	‘		71	G		103	g
8	BS (backspace)		40	(		72	H		104	h
9	TAB (horizontal tab)		41	)		73	I		105	i
10	LF (NL line feed, new line)		42	*		74	J		106	j
11	VT (vertical tab)		43	+		75	K		107	k
12	FF (NP form feed, new page)		44	,		76	L		108	l
13	CR (carriage return)		45	-		77	M		109	m
14	SO (shift out)		46	.		78	N		110	n
15	SI (shift in)		47	/		79	O		111	o
16	DLE (data link escape)		48	0		80	P		112	p
17	DC1 (device control 1)		49	1		81	Q		113	q
18	DC2 (device control 2)		50	2		82	R		114	r
19	DC3 (device control 3)		51	3		83	S		115	s
20	DC4 (device control 4)		52	4		84	T		116	t
21	NAK (negative acknowledge)		53	5		85	U		117	u
22	SYN (synchronous idle)		54	6		86	V		118	v
23	ETB (end of trans. block)		55	7		87	W		119	w
24	CAN (cancel)		56	8		88	X		120	x
25	EM (end of medium)		57	9		89	Y		121	y
26	SUB (substitute)		58	:		90	Z		122	z
27	ESC (escape)		59	;		91	[		123	{
28	FS (file separator)		60	<		92	\		124
29	GS (group separator)		61	=		93	]		125	}
30	RS (record separator)		62	>		94	^		126	~
31	US (unit separator)		63	?		95	_		127	DEL

Remember that Python/Sage has functions for conversions:

• ord: takes a character (as a string) and returns the ASCII value of a character;

• chr: takes a numerical value (integer between 0 and 127) and return the character corresponding to that value in ASCII.

6.8.1. Example

As an example, say you want to convert the text cat to a number to encode. Each character in a number between \(0\) and \(127\), as we can see from the table. We have:

ord('c'), ord('a'), ord('t')

(99, 97, 116)

We now need to put these individual numbers together into a single number in a unique and reversible way. One idea is to use the numbers obtained to build a number in base \(128\):

m = 99 + 97 * 128 + 116 * 128^2
m

1913059

We can then use ElGamal (or another cryptosystem) to encode this number!

Now when Alice decodes the encoded number, she will get this \(m\) back and needs to recover the text from it. For that, she looks at its digits in base \(128\), and use these digits to get the characters back:

v = 1913059.digits(base=128)
v

[99, 97, 116]

Then, she converts the “digits” (numbers between \(0\) and \(127\)) back to characters using chr:

chr(99) + chr(97) + chr(116)

'cat'

6.8.2. Smaller Base

This works fine, but for longer text the corresponding number might get very large. One can make them considerably smaller by working in base \(26\), since we have only \(26\) letters. (We could work in base \(27\), if we wanted to keep spaces as well, but let’s keep it simple here). So, we can convert any text we need to encode to lower case (with the string method .lower()), remove all characters but lower case letters, and then subtract \(97\) (the ASCII value of a) from the ASCII value of each character left. Then, we put them together in base \(26\). For example, for the word cat again:

ord('c') - 97, ord('a') - 97, ord('t') - 97

(2, 0, 19)

We put it in base \(26\):

m = 2 + 0 * 26 + 19 * 26^2
m

12846

Again, we can encrypt this number and Alice can decode in a similar way, but remembering to add \(97\) to the digits in base \(26\) to get the characters back:

v = 12846.digits(base=26)
v

[2, 0, 19]

Then, she converts the “digits” (numbers between \(0\) and \(127\)) back to characters using chr:

chr(2 + 97) + chr(0 + 97) + chr(19 + 97)

'cat'

6.8.3. Functions

Now, let’s write these conversions as functions. We will have a parameter small that allow us to choose base \(26\) (with small=True) or base \(128\) (with small=False).

Now, let’s make these into functions:

def string2number(string, small=True):
    """
    Converts a string to its numerical representation in either base 26 (lowercase letters only) or
    in base 128 (using full ASCII characters).

    INPUT:
      * string: string to be converted to a number;
      * small: if True, use base 26, if False, use base 128.

    OUTPUT:
    An intger obtained by using the numerical values of the characters as digits in the corresponding
    base.
    """
    # find appropriate base
    # difference is the value to be subtracted of the ASCII value
    if small:
        base = 26
        difference = 97
        # lower case only in base 26
        string = string.lower()
    else:
        base = 128
        difference = 0

    res = 0  # final result
    factor = 1  # power of the base
    for char in string:  # we can loop over a string!
        digit = ord(char) - difference  # digit
        # skip the rest if base 26 and character is invalid
        if small and (digit < 0 or digit > 25):
            continue
        res += digit * factor
        factor *= base
    return res

Now decoding:

def number2string(number, small=True):
    """
    Converts a number to its string representation in either base 26 (lowercase letters only) or
    in base 128 (using full ASCII characters).

    INPUT:
      * number: integer to be converted to a string;
      * small: if True, use base 26, if False, use base 128.

    OUTPUT:
    A string obtained by using the digits in the corresponding base as the numerical values for the characters.
    """
    res = ""
    if small:
        base = 26
        difference = 97
    else:
        base = 128
        difference = 0

    return "".join(chr(x + difference) for x in number.digits(base))

So, if we want to convert “Luis is the best professor ever!”, we do:

string2number("Luis is the best professor ever!")

4069000240540552872126375355100619523

To recover the original:

number2string(4069000240540552872126375355100619523)

'luisisthebestprofessorever'

Or, using full ASCII:

string2number("Luis is the best professor ever!", small=False)

7139509106217299707736390611080077508851787183905427399303772142284

number2string(7139509106217299707736390611080077508851787183905427399303772142284, small=False)

'Luis is the best professor ever!'

6.9. Encrypting Large Numbers

In the ElGamal cryptosystem, and others we will soon learn, the numbers to be encrypted are in \(\mathbb{Z}/m\mathbb{Z}\) for some modulus \(m\). A problem arises when we try to convert a number larger than this \(m\), as we cannot distinguish in \(\mathbb{Z}/m\mathbb{Z}\) a number \(n\) from \(n + km\) for any integer \(k\).

For instance, let’s say that we want to encrypt Luis is the best professor ever! using \(p = 24{,}778{,}948{,}499\) (for \(\mathbb{F}_p\)). Then, as we can see from the values above, even using base \(26\), the numerical values for this message are too large! (This prime is way too small to be safe for encryption, but it illustrates the point.)

So if were working modulo this \(p\), the numerical value would be changed when reducing modulo \(p\):

p = 24778948499
n = string2number("Luis is the best professor ever!")
print(f"The original number is {n}, but modulo p it is {n % p}.")

The original number is 4069000240540552872126375355100619523, but modulo p it is 21385918090.

In \(\mathbb{F}_p\) the original number would be lost, and we would only have its reduction. But decoding this reduction gives us gibberish:

number2string(n % p)

'enfuyfrc'

How do we fix this issue when the number we are trying to encrypt is larger than the modulus? We break the number in smaller parts and encrypt each part!

We do that by writing the number in the base \(m\), where \(m\) is the modulus!

v = n.digits(base=p)
v

[21385918090, 12473413431, 20840107311, 267447]

We must encrypt each one of those digits separately, using ElGamal (or whichever) cryptosystem. Bob then sends a tuple of messages, the digits of the original encrypted, and then Alice decrypts each one individually and put them back together using base \(m\).

base = p
res = sum(digit * base^i for i, digit in enumerate(v))
res, number2string(res)

(4069000240540552872126375355100619523, 'luisisthebestprofessorever')

Or, computing consecutive powers more efficiently:

base = p
res = 0
factor = 1
for digit in v:
    res += digit * factor
    factor *= base
res, number2string(res)

(4069000240540552872126375355100619523, 'luisisthebestprofessorever')

(In this case the last method is not strictly necessary, as the numbers are small, but it is good to get used thinking on the best general way to perform a computation.)