4. Modern Cryptography

  1. 4.1. Interlude: Primes
  2. 4.2. Interlude: Euler’s Phi Function
  3. 4.3. Interlude: Binary Exponentiation
  4. 4.4. Interlude: Primality Testing
  5. 4.5. RSA
  6. 4.6. Interlude: Order
  7. 4.7. Elgamal
  8. 4.8. Diffie-Hellman
  9. 4.9. Interlude: Elliptic Curves Over the Reals
  10. 4.10. Interlude: Elliptic Curves Mod a Prime
  11. 4.11. Elliptic Curve Diffie-Hellman
  12. 4.12. Interlude: Quadratic Residues
  13. 4.13. Elliptic Curve Elgamal

4.1. Interlude: Primes

Here is a definition that you may have seen before:

Definition A positive integer \(p \geq 2\) is prime if its only positive divisors are 1 and itself. An integer \(n \geq 2\) that is not prime is called composite.

For example, 5 is prime since 1 and 5 are its only divisors. 4, on the other hand, is not prime, since 2 is a divisor of 4 (in addition to 1 and 4).

Exercise The “twin prime conjecture” is a famous open problem which says that there are infinitely many “twin primes,” ie, pairs of primes that are 2 apart. For example, 3 and 5 are twin primes, as are 5 and 7, or 11 and 13. Give five more examples of twin primes.

Exercise There is a version of the twin prime conjecture which says that every even integer can be written as the difference of consecutive primes in infinitely many ways. For example, we have: \[ 6 = 29 - 23 = 137 - 131 = 599 - 593 = \cdots \] Express the integer 10 as the difference of two consecutive primes in five different ways.

Exercise Explain why any composite integer \(n \geq 2\) must have a prime factor \(p\) such that \(p \leq \sqrt{n}\). Then use this fact to determine whether or not 701 is prime.

Ubiquity of Primes

There is a very important sense in which primes are “ubiquitous” — namely, that every positive integer \(n \geq 2\) can be written (uniquely!) as a product of primes. For example, \(18 = 2 \cdot 3^2\), and both 2 and 3 are prime. An expression of an integer \(n \geq 2\) as a product of primes is called a prime factorization of \(n\).

Fundamental Theorem of Arithmetic Any positive integer \(n \geq 2\) has a unique prime factorization. In other words, there exists an expression \[ n = p_1^{e_1} \cdots p_r^{e_r} \] where \(p_1, \dotsc, p_r\) are primes and \(e_1, \dotsc, e_r\) are positive integers, and this expression is unique up to reordering the indices.

For example, \(60 = 2^2 \cdot 3^1 \cdot 5^1\) is a prime factorization of 60. It is the only one: we could instead write \(60 = 5^1 \cdot 2^2 \cdot 3^1\), but besides this kind of reordering of the factors, there is nothing else.

Exercise Find the prime factorizations of 1231 and of 1232.

Exercise

  1. Find all prime factors of \(50!\). (Just a list of the prime factors is sufficient; you don’t need to find the exponents of the prime factorization for this part.)

  2. Find the prime factorization of \(10!\).

  3. Find the prime factorization of \(11!/2^8\).

The fundamental theorem of arithmetic is likely deeply ingrained in your mathematical intuition, but it is in fact a “theorem” — it is something that can and should be proved. The proof makes use of some of the machinery we’ve already seen, so let’s prove it!

Proof of the fundamental theorem of arithmetic. The existence statement is a great example of a proof by “strong induction.” We start by noticing that 2 is prime, so it is its own prime factorization. Now suppose that \(n \geq 2\) and that every integer \(m\) such that \(2 \leq m < n\) has a prime factorization. If \(n\) itself is prime, it is again its own prime factorization and we are done. If \(n\) is composite, by definition it has a divisor \(m\) such that \(2 \leq a < n\). This means that \(n/a = b\) is an integer with \(2 \leq b < n\) as well. By assumption, both \(a\) and \(b\) have prime factorizations; since \(n = ab\), multiplying those prime factorizations together gives us a prime factorization of \(n\).

For the uniqueness statement, suppose for a contradiction that there is an integer greater than or equal to 2 that can be written as a product of primes in two different ways. But then there must be a smallest such integer; let’s call that integer \(n\). By assumption, we have \(n = p_1 \cdots p_t = q_1 \cdots q_u\). Since \(p_1\) divides the left-hand side, it must also divide the right hand side. We must have \(\gcd(p_1, q_i) = 1\) or \(p_1\), but it cannot be equal to 1 for all \(i\) by Euclid’s lemma. Thus there exists some \(i\) such that \(\gcd(p_1, q_i) = p_1\), which means that \(p_1\) divides \(q_i\). Since \(q_i\) is also prime, we must have \(p_1 = q_i\), so then we can cancel \(p_1 = q_i\) from both sides to see that \(p_2 \cdots p_t = q_1 \cdots q_{i-1} q_{i+1} \cdots q_u\). But now we have two distinct prime factorizations of a number that’s strictly smaller than \(n\), which is a contradiction! \(\Box\)

Proof Exercise Suppose \(a\) and \(b\) are positive integers. Let \(p_1, \dotsc, p_r\) be a list of distinct primes that contains every prime factor of both \(a\) and \(b\).

  1. Explain why there exist non-negative integers \(e_1, \dotsc, e_r, f_1, \dotsc, f_r\) such that \(a = p_1^{e_1} \cdots p_r^{e_r}\) and \(b = p_1^{f_1} \cdots p_r^{f_r}\).

  2. Show that \(\gcd(a, b) = p_1^{\min\{e_1, f_1\}} \cdots p_r^{\min\{e_r, f_r\}}\).

Proof Exercise It is a fact that there are infinitely many prime numbers. Prove this by contradiction in two different ways:

  1. Suppose there are only finitely many primes \(p_1, \dotsc, p_n\), and then consider \(a = p_1 \cdots p_n + 1\). Find a contradiction.

  2. Suppose there are only finitely many primes and let \(n\) be an integer that’s greater than all of them. Then consider \(a = n!+1\). Find a contradiction.

Scarcity of Primes

Having made the observation that primes are “ubiquitous,” we now turn to two important senses in which primes are “scarce.” The first sense is a literal sense: as a proportion of all integers, very few integers end up being prime!

SageCell Here is a SageCell to convince you that primes are scarce. Hit “Run.” What you see is a plot of a function \(f\) where, for any real number \(x \geq 2\), the corresponding \(y\)-value \(f(x)\) is the proportion of integers less than or equal to \(x\) that are prime, for any real number \(x \geq 2\). Notice how, in the long run, very few numbers are actually prime! Try changing the upper endpoint 1000 and investigate how the graph changes.

Let me also just mention in passing that the scarcity of primes we see in the plot above is formalized by the statement of “Prime number theorem,” which is a difficult but landmark theorem in analytic number theory.

Difficulty of Factoring

The second sense in which primes are “scarce” is that prime factorizations are extremely difficult to actually calculate, even for moderately large numbers.

The naive way to find a prime factorization is to just start going through to see what’s a factor. Let’s say, for example, that we want to factor 75. We check first that 2 does not divide 75. We then see that 3 does divide 75, and we’re left with 25. Now 3 no longer divides 25. 4 also does not divide 25 (which we anyway knew since we already saw that 2 didn’t divide 75), but 5 does divide 25, so we divide again and we’re left with 5. And 5 divides itself again, which leaves a 1 in the end and we can stop. This procedure tells us that \[ 75 = 3^1 \cdot 5^2. \] As you might imagine, this procedure gets extremely slow as the number gets larger — or more specifically, as the prime factors of the number get larger.

Computational number theorists have worked out lots of deep, sophisticated, and clever techniques (which we do not have time to discuss this quarter) to speed this process up, but no one has yet found a factorization algorithm for classical computers that is substantially better than the naive method we just described. If you’ve seen some computational complexity theory, you might know what it means to say that there is no known factorization algorithm which is polynomial in the number of digits in the input.

SageCell Here is a SageCell to convince you that prime factorization is difficult. The Sage function factor will factor integers. It tries to use as much sophisticated math as possible to make this as fast as possible. It’s certainly much faster than a human being, but it starts becoming infeasibly slow as the size of the prime factors of the numbers grow. Hit Run to see Sage factor a number with several “small” prime factors.

Then try factoring:

98451812256345345465436565462354534524552443341112317013333179953

Sage will take a long time to get back to you, but it should get back to you eventually; be patient. Then try adding or subtracting digits to the number on your own whim to see what happens! Do you see patterns in when Sage returns an answer quickly, or when Sage seems to struggle?

We’ll see below that the difficulty of factoring can be leveraged to build modern cryptosystems that are in widespread use today.

Incidentally, you may have noticed two things in the discussion above. First, we said only that no substantially better algorithm is known, not that there is no such algorithm. We do not have a proof that prime factorization cannot be done “quickly” (ie, in polynomial time), and it is an open problem in mathematics and/or theoretical computer science to prove this. (Or to disprove it, but given how much time and money people have put into trying to find a quick factorization algorithm, this seems unlikely…!)

The second thing you may have noticed is the phrase “classical computers.” In fact, we do know efficient factorization algorithms for quantum computers! Quantum computing hardware has not yet caught up to our theoretical knowledge, so our modern cryptosystems are still safe for now, but this state of affairs won’t last for much longer. We will soon need new cryptosystems that are secure against quantum computers.

The difficulty of factoring suggests that the function \(\mu\), which takes as input two prime numbers \(p\) and \(q\) and outputs the product \[ \mu(p, q) = pq \] is our first example of a one-way function. It’s very easy to compute the product of two primes; but, if the primes are large, it’ll be very hard to invert this function (ie, to find the prime factors of some given number that has two large prime factors). This is the one-way function on which RSA is based, as we will see soon. But first, we need to develop still more theory.

4.2. Interlude: Euler’s Phi Function

Here’s an idea that we’ve already seen before:

Definition For a positive integer \(n\), let \(\phi(n)\) denote the number of integers \(r\) with \(0 \leq r < n\) and \(\gcd(n, r) = 1\). The function \(n \mapsto \phi(n)\) is called Euler’s phi function (or Euler’s totient function).

For example, when we were counting that there are 312 affine encryption functions available in English, part of the process involved counting the number of numbers relatively prime to 26, and we found that it was 12. We can now say this more succinctly by saying \(\phi(26) = 12\).

Exercise Compute \(\phi(12), \phi(13), \phi(14)\), and \(\phi(15)\).

Exercise Explain why, in a language that uses an alphabet with \(n\) letters, the number of distinct affine encryption functions is \(n\phi(n)\).

Important Exercise Suppose \(p\) is prime.

  1. Explain why \(\phi(p) = p-1\).
  2. Explain why \(\phi(p^e) = p^e - p^{e-1} = p^{e-1}(p-1)\) for any \(e \geq 1\).

In fact, there is a nice formula for \(\phi(n)\) in terms of the prime factorization of \(n\), which we now describe. First, let us record the following property.

Multiplicativity of Euler’s Phi Function If \(\gcd(a, b) = 1\), then \(\phi(ab) = \phi(a)\phi(b)\).

Proof sketch. Observe that \(\gcd(r, ab) = 1\) if and only if \(\gcd(r, a) = 1\) and \(\gcd(r, b) = 1\). Let’s arrange the numbers 0 through \(ab-1\) in a grid as follows. \[ \begin{matrix} 0 & 1 & 2 & \cdots & b-1 \\ b & b+1 & b+2 & \cdots & 2b-1 \\ 2b & 2b+1 & 2b+2 & \cdots & 3b-1 \\ (a-1)b & (a-1)b + 1 & (a-1)b + 2 & \cdots & ab-1 \end{matrix} \] All of the numbers in a given column are congruent mod \(b\), so if if one of these numbers is relatively prime with \(b\), then every number in that column must also be relatively prime with \(b\). Thus there are \(\phi(b)\) columns that are relatively prime with \(b\), and it is sufficient to show that each of those columns has \(\phi(a)\) entries which are relatively prime with \(a\).

The entries in the \(r\)th column are of the form \(sb + r\) for \(s\) varying between 0 and \(a-1\). Since \(\gcd(a, b) = 1\), every congruence class mod \(a\) is represented exactly once in each column. We know that \(\phi(a)\) of the congruence classes mod \(a\) are relatively prime to \(a\), so we are done. \(\Box\)

Proof Exercise Fill in the details in the above proof sketch. In particular, explain how the Affine Cipher Lemma plays into the ideas discussed in the second paragraph of the sketch above.

This brings us to the promised formula.

Formula for Euler’s Phi Function Suppose \(n = p_1^{e_1} \cdots p_r^{e_r}\) is the prime factorization of \(n\). Then \[ \phi(n) = p_1^{e_1-1} (p_1-1) \cdots p_r^{e_r-1}(p_r - 1). \]

Proof Exercise Prove the formula for Euler’s phi function using the multiplicativity property and the calculation of \(\phi(p^e)\).

Exercise Use the formula for Euler’s phi function to calculate \(\phi(n)\) for each of the following values of \(n\).

  1. \(n = 20 = 2^2 \cdot 5\)
  2. \(n = 25 = 5^2\)
  3. \(n = 30 = 2 \cdot 3 \cdot 5\)
  4. \(n = 35 = 5 \cdot 7\)
  5. \(n = 40 = 2^3 \cdot 5\)

Exercise Explain why \(\phi(n)\) is always even when \(n \geq 3\).

Exercise Explain why we can also write \[\phi(n) = n \prod_{p \mid n} \left( 1 - \frac{1}{p} \right). \]

SageCell Sage can work with Euler’s phi function as well. Try it!

We can now calculate Euler’s phi function, but the reason this number is important is because of the following very important theorem.

Euler’s Theorem Suppose \(n\) is a positive integer and \(a\) is another integer with \(\gcd(a, n) = 1\). Then \[ a^{\phi(n)} \equiv 1 \pmod{n}. \]

Proof sketch. Let \(r_1, \dotsc, r_{\phi(n)}\) be the integers between 0 and \(n-1\) which are relatively prime to \(n\). Since \(\gcd(a, n) = 1\), the integers \(ar_1, \dotsc, ar_{\phi(n)}\) represent the same congruence classes, but maybe in a different order. Since multiplication of integers is commutative, we have \[ r_1 \cdots r_{\phi(n)} \equiv (ar_1) \cdots (ar_{\phi(n)}) = a^{\phi(n)} r_1 \cdots r_{\phi(n)} \pmod{n}. \] We can now multiply mod \(n\) by \(r_{\phi(n)}^{-1}\), and \(r_{\phi(n)-1}^{-1}\), and so forth, all the way down to \(r_1^{-1}\) to conclude that \[ 1 \equiv a^{\phi(n)} \pmod{n}, \] which is what we wanted to show. \(\Box\)

Proof Exercise Fill in the details in the above proof sketch.

Let’s consider an example. Notice that \(20 = 2^2 \cdot 5\), so \[ \phi(20) = 2^1(2-1) \cdot 5^0 (5-1) = 8. \] This means that \(a^{\phi(20)} = a^8 \equiv 1 \bmod{20}\) for any \(a\) that is relatively prime to 20. For example, consider \(a = 3\). We do in fact have \(\gcd(3, 20) = 1\), and we can check explicitly using the Modular Arithmetic Theorem that: \[ \begin{aligned} 3^2 &= 9 \\ 3^4 &= (3^2)^2 \equiv 9^2 = 81 \equiv 1 \pmod{20} \\ 3^8 &= (3^4)^2 \equiv 1^2 = 1 \pmod{20}. \end{aligned} \] We can also use this Euler’s theorem to compute very very large powers of some number. Suppose, for example, that we want to compute \(7^{20232023} \bmod{20}\). Notice that \(20232000\) is divisible by 8, so we have \[ 20232023 = 20232000 + 23 \equiv 23 \equiv 7 \bmod{8}. \] In other words, this means that \(20232023 = 8q + 7\) for some integer \(q \geq 0\). We then have \[ 7^{20232023} = 7^{8q + 7} = (7^8)^q 7^7 \equiv 1^q 7^7 = 7^7 \pmod{20}. \] So now we just have to compute \(7^7 \bmod{20}\), which we can do as follows: \[ \begin{aligned} 7^2 &= 49 \equiv 9 \bmod{20} \\ 7^4 &= (7^2)^2 \equiv 9^2 = 81 \equiv 1 \bmod{20} \\ 7^7 &= 7^4 \cdot 7^2 \cdot 7 \equiv 1 \cdot 9 \cdot 7 = 63 \equiv 3 \bmod{20} \end{aligned} \] We thus have \(7^{20232023} \bmod{20} = 3\).

Notice that we were able to do this remainder calculation without having to actually compute \(7^{20232023}\). This is an important observation, because we’ll see below that RSA will require us to do similar remainder calculations even when the numbers are so large that it is completely infeasible for computers to actually calculate out the result of the exponentiation. We’ll discuss this point in more detail in the following section.

Meanwhile, here are some exercises to practice with Euler’s theorem!

Exercise Use Euler’s theorem to show that 51 divides \(10^{32n+9} - 7\) for any integer \(n \geq 0\).

Exercise Find the units digit of \(3^{100}\) using Euler’s theorem.

Exercise Fix a prime number \(p\). There are two versions of “Fermat’s little theorem.”

  1. If \(a\) is an integer that is not divisible by \(p\), then \(a^{p-1} \equiv 1 \pmod{p}\).
  2. For any integer \(a\), we have \(a^p \equiv a \pmod{p}\).

Explain how to derive both of these statements from Euler’s theorem. You may find it helpful to first derive statement (a), and then use that to derive statement (b).

4.3. Interlude: Binary Exponentiation

With Euler’s theorem in hand, we can now compute large powers in modular arithmetic very quickly. We saw this briefly above, but let’s now explain the process systematically. Suppose we have a positive integer \(n\) and an integer \(a\) with \(\gcd(a, n) = 1\), and that we want to compute \(a^m \bmod{n}\) for some large number \(m\).

The first step is to calculate \(r = m \bmod{\phi(n)}\). Indeed, if we do this, then we have \(m = \phi(n)q + r\), so \[ a^m = a^{\phi(n)q + r} = (a^{\phi(n)})^q a^r \equiv 1^q a^r = a^r \pmod{n} \] using Euler’s Theorem (and the Modular Arithmetic Theorem). This immediately reduces the power we have to compute substantially.

We can then compute \(a^r \bmod{n}\) using a technique called “binary exponentiation.” The idea is fairly straightforward in examples, though it can becomes hard to understand in the abstract, so let’s start by considering an example.

Suppose we find that \(r = 25\). How can we compute \(a^r \bmod{n}\)? One naive thing we could do is multiply \(a\) by itself mod \(n\) repeatedly; this would require 25 multiplications mod \(n\). Here’s another idea. Let’s start squaring repeatedly:

If we square again, we’ll go past \(r = 25\), so we’ll stop there. We now want to figure out how to find \(a^{25}\) using the powers of \(a\) we’ve already computed. Notice that \(25 = 16 + 8 + 1\), so \[ a^{25} = a^{16+8+1} = a^{16} a^8 a^1, \] and we already know \(a^{16}, a^8\), and \(a\) mod \(n\), so we can compute \(a^{25} \bmod{n}\) by multiplying these three values together mod \(n\). Notice that this required only 6 multiplications total — much less than the 25 of the naive method!

Let’s see this entire process in action before describing the binary exponentiation part in the abstract. Suppose we want to compute \[ 3^{4398391} \bmod{80}. \] We first compute \(\phi(80) = 32\), and that \(4398391 \equiv 23 \bmod{32}\). Thus \(3^{4398391} \equiv 3^{23} \bmod{80}\) by Euler’s Theorem. We now use binary exponentiation: \[ \begin{aligned} 3^2 &= 9 \\ 3^4 &= (3^2)^2 = 9^2 = 81 \equiv 1 \bmod{80} \\ 3^8 &= (3^4)^2 \equiv 1^2 = 1 \bmod{80} \\ 3^{16} &= (3^8)^2 \equiv 1^2 = 1 \bmod{80} \\ 3^{23} &= 3^{16 + 4 + 2 + 1} = 3^{16} 3^4 3^2 3 \equiv 1 \cdot 1 \cdot 9 \cdot 3 = 27 \bmod{80} \end{aligned} \]

Exercise Compute \(3^{293423948903859017} \bmod{50}\).

The “repeated squaring and then multiplying together” part of this process is very closely related to finding binary representations of integers. Here is the definition:

Definition Let \(r\) be a non-negative integer. The binary representation of \(r\) is a string \(b_k \cdots b_1 b_0\) where each \(b_i\) is either 0 or 1, and where \[ r = b_0 + b_1 2 + b_2 2^2 + \cdots + b_k 2^k. \] The number \(b_i\) is called the \(i\)th bit of \(r\). We call \(b_0\) the rightmost bit and \(b_k\) the leftmost bit.

For example, the binary representation of 25 is 11001 because \[ 1 + 0 \cdot 2 + 0 \cdot 2^2 + 1 \cdot 2^3 + 1 \cdot 2^4 = 1 + 8 + 16 = 25. \] It is not clear at all from the definition how to find this binary representation, but here is the algorithm for doing this!

Algorithm for Finding Binary Representations Let \(r\) be a non-negative integer. To find the binary representation of \(r\), divide \(r\) by 2, and then divide the quotient by 2, and then divide that quotient by 2, and so forth, until you hit a quotient of 0. The remainders of these divisions are the binary representation, with the last remainder corresponding to the leftmost bit.

For example, suppose we want to calculate the binary representation of 193. We divide 193 by 2, and then repeatedly divide the quotient by 2: \[ \begin{aligned} 193 &= 96 \cdot 2 + 1 \\ 96 &= 48 \cdot 2 + 0 \\ 48 &= 24 \cdot 2 + 0 \\ 24 &= 12 \cdot 2 + 0 \\ 12 &= 6 \cdot 2 + 0 \\ 6 &= 3 \cdot 2 + 0 \\ 3 &= 1 \cdot 2 + 1 \\ 1 &= 0 \cdot 2 + 1 \end{aligned} \] We’ve now hit a quotient of 0, so we stop dividing. The binary representation is the sequence of remainders we found, with the leftmost bit being the last remainder we found and the rightmost bit being the first remainder we found. In other words, the binary representation of 193 is 11000001.

There’s a technical remark worth making here for those who are interested in computation. The above process is an “algorithm,” but it’s an algorithm that only human beings really have to perform…! A computer doesn’t have to go through the above process to find the binary representation, because a computer will already know the binary representation of any integer: binary representations are how computers talk about integers!

Exercise Find binary representations of the following integers.

  1. 37
  2. 123
  3. 290
  4. 300

Exercise Why must the rightmost bit in the binary representation of an even number must be 0?

Exercise If an integer is divisible by 8, what can you say about its binary representation?

Proof Exercise Prove that the output of the above algorithm is in fact the binary representation of \(r\).

We can now state the general fact about binary exponentiation we described in the context of examples above:

Binary Exponentiation Lemma Let \(n\) be a positive integer, and let \(b_k \cdots b_1 b_0\) be the binary representation of a non-negative integer \(r\). To compute \(a^r \bmod{n}\) for some integer \(a\), first compute \(a^{2^i} \bmod{n}\) for \(i = 0, \dotsc, k\) by repeated squaring. Then, to get \(a^r\), multiply together all of the \(a^{2^i}\) where \(b_i = 1\). In other words, \[ a^r \equiv \prod_{b_i = 1} a^{2^i} \pmod{n}. \]

Proof Exercise Prove the above lemma.

Exercise Show that the number of multiplications mod \(n\) that are required to compute \(a^r \bmod{n}\) with binary exponentiation is at most \(2\log_2(r)\).

SageCell Sage performs the algorithm we’ve described in this section when you ask it to compute remainders of high powers. For example, the following code computes \(3^{4398391} \bmod{80}\) using this procedure of Euler’s Theorem followed by binary exponentiation.
SageCell Sage can compute binary representations for you as follows. Note that the output will be prefixed with 0b to indicate that what follows is a binary representation.

Exercise A binary representation is also called a base 2 representation. What is a base 3 representation, and how do we compute it? How about base 4 representations?

Exercise Read about hexadecimal representations of integers, and then explain what’s going on in your own words.

4.4. Interlude: Primality Testing

We have one more theoretical ingredient to discuss for now: how can we quickly figure out if a number is prime? Remember that factoring is computationally expensive, so it’s not a good idea to try to figure out that a number is prime by factoring it!

It turns out that there are a number of fast strategies for testing primality. Here we’ll discuss one called the Miller-Rabin test. To explain how the this test works, we need to establish some theoretical preliminary results.

Lemma If \(n\) is prime, the only solutions to \(x^2 \equiv 1 \pmod{n}\) are \(x \equiv \pm 1 \pmod{n}\).

Proof. Observe that \(x^2 \equiv 1 \pmod{n}\) implies \[0 \equiv x^2 - 1 = (x-1)(x+1) \pmod{n}, \] which means that \(n\) divides \((x-1)(x+1)\). Since \(n\) is prime, Euclid’s lemma implies that \(n\) divides either \(x-1\) or \(x+1\), which means we have either \(x-1 \equiv 0 \pmod{n}\) or \(x+1 \equiv 0 \pmod{n}\). In other words, we have either \(x \equiv 1 \pmod{n}\) or \(x \equiv -1 \pmod{n}\), respectively. \(\Box\)

Miller-Rabin Lemma Suppose \(n\) is a positive odd integer and write \(n-1 = 2^s d\) for some positive integer \(s\) and an odd number \(d\). Suppose \(a\) is an integer between 1 and \(n-1\). If \(n\) is prime, then one of the following congruence relations must hold true: \[ \begin{aligned} a^d &\equiv 1 \pmod{n} \\ a^d &\equiv -1 \pmod{n} \\ a^{2d} &\equiv -1 \pmod{n} \\ a^{2^2d} &\equiv -1 \pmod{n} \\ &\,\vdots \\ a^{2^{s-1}d} &\equiv -1 \pmod{n} \end{aligned} \]

Proof. Since \(1 \leq a \leq n-1\) and \(n\) is prime, we have \(\gcd(a, n) = 1\). Thus, by Euler’s Theorem, we know that \(a^{n-1} = a^{2^s d} \equiv 1 \pmod{n}\). This means that \(x_1 = a^{2^{s-1}d}\) is satisfies \[ x^2_1 = (a^{2^{s-1}d})^2 = a^{2^s d} \equiv 1 \pmod{n}, \] so by the previous lemma, we must have either \(x_1 \equiv -1 \pmod{n}\), in which case we’re done, or else \(x_1 \equiv 1 \pmod{n}\). In the latter case, we can repeat the same argument with \(x_1\) replaced by \(x_2 = a^{2^{s-2}d}\), and so on, all the way down to \(x_s = a^d\). \(\Box\)

Let’s see what this lemma is saying in an example. Consider \(n = 41\), which is prime. We then have \(n-1 = 40 = 2^3 \cdot 5\). In other words, we can take \(s = 3\) and \(d = 5\) in the above lemma. Suppose we fix some integer \(a = 17\). Since \(s = 3\), we have 4 congruences in our list, and one of them should then be true, so let’s check which one! We first compute \(17^5 \equiv 27 \pmod{41}\) using binary exponentiation (as described in the previous section). This is not \(\pm 1\), so the first two congruence in the list fail. We then have \[ 17^{2 \cdot 5} = (17^5)^2 \equiv 27^2 \equiv 32 \bmod{41} \] so the third congruence also fails. But then we have \[ 17^{2^2 \cdot 5} = (17^{2 \cdot 5})^2 \equiv 32^2 \equiv 40 \equiv -1 \pmod{41} \] so the last congruence is in fact true!

Exercise

For each of the following integers \(n\), find the integers \(s\) and \(d\) such that \(n-1 = 2^s d\), where \(d\) odd.

  1. 43
  2. 49
  3. 65

The Miller-Rabin Lemma leads us to the following definition:

Definition Suppose \(n\) is a positive odd integer and write \(n-1 = 2^s d\) for some positive integer \(s\) and an odd number \(d\). Suppose \(a\) is an integer between 1 and \(n-1\). We say that \(n\) is a strong probable prime to base \(a\) if one of the following congruences is true: \[ \begin{aligned} a^d &\equiv 1 \pmod{n} \\ a^d &\equiv -1 \pmod{n} \\ a^{2d} &\equiv -1 \pmod{n} \\ a^{2^2d} &\equiv -1 \pmod{n} \\ &\,\vdots \\ a^{2^{s-1}d} &\equiv -1 \pmod{n} \end{aligned} \] If \(n\) is not a strong probable prime to base \(a\), then \(a\) is called a witness for the compositness of \(n\), or a Miller-Rabin witness for \(n\).

Using this definition, the Miller-Rabin Lemma can be restated as saying simply that “every prime number is a strong probable prime to any base.” This is equivalent to the contrapositive, ie, the statement that “if \(n\) is not a strong probable prime to some base \(a\), then \(n\) must be composite.”

Consider, for example, \(n = 25\). Of course, this number is small enough that we can see right away that it is not actually prime! But let’s see what’s going on with this notion of strong probable primes. Observe that \(n-1 = 24 = 2^3 \cdot 3\), so we have \(s = 3\) and \(d = 3\). Suppose first that we choose a base of \(a = 7\). Then \[ \begin{aligned} 7^3 &\equiv 18 \pmod{25} \\ 7^{2 \cdot 3} &= (7^3)^2 \equiv 18^2 \equiv 24 \equiv -1 \pmod{25} \end{aligned} \] so this says that 25 is a strong probable prime to base 7. If we instead choose \(a = 2\), then we have \[ \begin{aligned} 2^3 &= 8 \\ 2^{2 \cdot 3} &= (2^3)^2 = 8^2 \equiv 64 \equiv 14 \pmod{25} \\ 2^{2^2 \cdot 3} &= (2^{2 \cdot 3})^2 \equiv 14^2 \equiv 21 \pmod{25} \end{aligned} \] Thus \(n\) is not a strong probable prime to base 2, and 2 is a witness to the compositeness of 25.

Exercise

  1. Check that 49 is a strong probable prime to base 18. Check also that 2 is a witness to the compositeness of 49.
  2. Check that \(221\) is a strong probable prime to the base 174. Check also that 2 is a witness for the compositeness of 221.
SageCell Here is some Sage code for a function called is_strong_probable_prime that checks if a number \(n\) is a strong probable prime to some base \(a\). At the very end, we call is_strong_probable_prime(25, 7) to check if 25 is a strong probable prime to the base 7. It should return True. Hit “Run” to check! Then try changing \(n\) and \(a\) and experimenting.

Exercise Explain why any positive odd integer \(n\) is always a strong probable prime to base 1, and also to base \(n-1\).

The idea now is as follows. If \(n\) is composite, the most of the possible choices of base \(2 \leq a \leq n-2\) will in fact be witnesses for the compositeness of \(n\). This means that, if we try several such bases and none of them turn out to be a witness for compositness, we can be quite sure that \(n\) is in fact prime!

Sage Exercise Write some code that plots, for each positive odd composite integer \(n\) up to 10000, the percentage of bases \(2 \leq a \leq n-2\) such that \(n\) is a strong probable prime to base \(a\). (You should find that no more than 25% of bases have this property.)

We’ve just described the Miller-Rabin primality test:

Miller-Rabin Primality Test Suppose \(n\) is a positive integer. If \(n\) is 2, output True. Otherwise, if \(n\) is even, output False. Otherwise, repeat the following step some fixed pre-determined number of times:

If we reach the end without having output False, then output True.

If we do \(k\) repetitions, the probability of a false positive is less than \(4^{-k}\). This gets small very quickly! For example, if we do just 10 repetitions, the probability of a false positive is about one in a million!

Exercise Perform the Miller-Rabin primality test by hand for each of the following numbers:

  1. 13
  2. 15
  3. 9

Sage Exercise Write some code that implements the Miller-Rabin primality test. It should be a function that takes as input a positive integer \(n \geq 2\) and a number of iterations \(k\), and then perform at most \(k\) iterations as described above, returning either True or False at the end. Feel free to use the is_strong_probable_prime function defined in the SageCell above.

If you don’t like the idea of a probabilistic algorithm, you may be interested in reading about the AKS Primality Test, which is a fully deterministic algorithm that runs in polynomial time (ie, polynomial in the number of digits in the input). Note, though, that the AKS primality test often runs much slower than the Miller-Rabin test…! If you like, you can also read about deterministic variants of the Miller-Rabin test.

The upshot is that we can quickly check if a number is prime without having to factor it. This also gives us an algorithm for generating large prime numbers: basically, just keep generating random numbers until we find one that’s prime!

Algorithm for Generating Large Primes Let \(r\) be a positive integer. To generate an \(r\)-bit prime, run the following steps:

Exercise The first step of the algorithm above requires you to pick a random odd integer between \(2^{r-1}\) and \(2^r - 1\). How would you go about ensuring that the number you pick is odd and that every odd number between \(2^{r-1}\) and \(2^r - 1\) is equally likely? Hint. It might be helpful to think about binary representations.

SageCell Sage has functionality to generate a random prime using the function random_prime. The algorithm it uses is very close to what’s described above, though the primality test is not exactly the Miller-Rabin test (it instead uses the Baillie-PSW primality test, which is a probabilistic primality test that involves some of the same ideas). By default, it generates a random prime between 2 and the input number:
If you want to generate a random prime between something bigger than 2, you have to tell it as follows:
Sage is using a probabilistic test, so it isn’t guaranteed that the number will actually be prime: it’s just very likely to be prime! If you want Sage to verify that the number is actually prime, you can do that too:

4.5. RSA

RSA is a cryptosystem named after Ron Rivest, Adi Shamir, and Leonard Adleman, who publicly described the algorithm in 1977. The GCHQ mathematician Clifford Cocks developed an equivalent system back in 1973, but his work was not declassified until 1997.

Let’s start by discussing how RSA works. We’ll then talk about why it works, and finally about why it’s secure (or at least, probably secure for now).

How to Convert Text Messages to Numbers

We first need a preliminary discussion about how to convert text messages into integers, since RSA only allows us to transfer integers. A variety of methods could be employed to make this happen, but one simple idea is for her to encode a message in the usual way (remove all non-alphabet characters and capitalize everything), and regard the resulting string as a number in base 26.

Suppose, for example, that Alice’s message is HIBOB. Under the usual letter-to-number correspondence (A is 0, B is 1, etc), these numbers correspond to the numbers 7, 8, 1, 14, 1 (in that order). We can then construct the integer \[ 1 \cdot 26^0 + 14 \cdot 26^1 + 1 \cdot 26^2 + 8 \cdot 26^3 + 7 \cdot 26^4 = 3340481. \] This is an integer representation of the message HIBOB in the sense that there is a straightforward algorithm to recover the plaintext: we use the same algorithm that we used to write a number in binary, but now we divide repeatedly by 26 instead. \[ \begin{aligned} 3340481 &= 128480 \cdot 26 + 1 \\ 128480 &= 4941 \cdot 26 + 14 \\ 4941 &= 190 \cdot 26 + 1 \\ 190 &= 7 \cdot 26 + 8 \\ 7 &= 0 \cdot 26 + 7 \end{aligned} \] We then look at the sequence of remainders, starting from the bottom (ie, 7, 8, 1, 14, 1), and associate to each of these remainders the corresponding letters to get back to the plaintext: HIBOB.

Exercise

  1. Find the integer representation of the text GAIA.
  2. Find the text corresponding to the integer 245405438.
SageCell Here is a SageCell that implements the above described integer representations of text, and also the reverse.

Exercise Let’s say you wanted to preserve spaces in your message. How would you modify the above method of associating an integer to text to make this happen?

Exercise There’s a problem with the base 26 encoding/decoding scheme described above! Specifically, the problem arises with words like APPLE or AARDVARK.

  1. What is the problem?
  2. How would you go about modifying this scheme to avoid this problem? (There are many possible solutions, including “do nothing”…! What’s your favorite solution, and why?)

How RSA Works

Bob starts off by picking two distinct large primes \(p\) and \(q\). He computes \(n = pq\) and \(\phi(n) = (p-1)(q-1)\). He picks a random integer \(d\) between 0 and \(\phi(n)\) such that \(\gcd(d, \phi(n)) = 1\). He then computes \(e \equiv d^{-1} \pmod{\phi(n)}\) (eg, using the extended Euclidean algorithm). He then publishes the pair \((n, e)\) for the world to see; this is his public encryption key. He keeps the remaining numbers private.

Suppose Alice has a secret integer \(m\) between 0 and \(n-1\) that she wants to send to Bob. She encrypts \(m\) by computing \(c = m^e \bmod{n}\), and this is the ciphertext that she sends to Bob.

When Bob receives \(c\), he computes \(c^d \bmod{n}\). As it turns out, this must be \(m\), so he has received Alice’s message!

Exercise Suppose Bob picks the primes \(p = 3\) and \(q = 5\). These are not even remotely large enough primes to be secure, but it’s useful to work through small examples to understand the generality described above. We have \(n = pq = 15\) and \(\phi(n) = (p-1)(q-1) = 8\). Suppose Bob further chooses \(d = 3\) (which is in fact relatively prime to 8).

  1. What is Bob’s public encryption key?
  2. Suppose Alice wants to send Bob the message \(m = 7\). What is the ciphertext \(c\) that Alice sends Bob?
  3. Check that, if Alice sends the ciphertext \(c\) corresponding to \(m = 7\) to Bob, that Bob actually recovers the original plaintext.
  4. Suppose Alice sends the ciphertext \(c = 2\) to Bob. What is the corresponding plaintext?

Exercise Let’s now take Eve’s perspective to see why choosing large primes is crucial. Suppose Bob’s RSA public key is \((35, 7)\) and Alice has just sent Bob the ciphertext \(c = 17\). What is Bob’s decryption key? What is Alice’s plaintext message?

Exercise

  1. Suppose Bob’s public key has \(n = 3233\). What is the maximum integer \(n\) such that Alice can send Bob any message of length \(n\)?

  2. Suppose Bob wants to be able to receive any message with 100 characters. How big does \(n\) have to be?

SageCell Here are two SageCells that together implement RSA.

The first cell generates RSA keys. You will input a number of bits; it will then generate two primes with that many bits in their binary representation, multiply them together to get \(n\), and then generate \(d\) and \(e\) as described above. The larger you choose the number of bits, the more secure the key is. Remember that \((n, e)\) is the public key, and that \(d\) must be kept secret.

The next cell implements the encryption and decryption. It defaults to using a key that was generated using the above SageCell with 100-bit primes. Encryption does not require you to enter a value for d, but decryption does.

Why RSA Works

RSA Theorem Suppose \(p, q\) are distinct primes and \(n = pq\), that \(d\) is an integer with \(1 \leq d \leq \phi(n)\) and \(\gcd(d, \phi(n)) = 1\), and that \(e \equiv d^{-1} \pmod{\phi(n)}\). If \(0 \leq m \leq n-1\) and \(c = m^e \bmod{n}\), then \[ c^d \bmod{n} = m. \]

Proof. Observe that \(de \equiv 1 \pmod{\phi(n)}\), so there exists an integer \(k\) such that \(de = 1 + k\phi(n)\) and we have \[ c^d \equiv (m^e)^d = m^{ed} = m^{1 + k\phi(n)} \pmod{n}. \] Since \(0 \leq m < n\), it is therefore sufficient for us to show that \(m^{1 + k\phi(n)} \equiv m \pmod{n}\).

There are two cases. The first case is when \(\gcd(m, n) = 1\). Then Euler’s theorem says that \(m^{\phi(n)} \equiv 1 \pmod{n}\), so \[ \begin{aligned} m^{1 + k\phi(n)} = m \cdot (m^{\phi(n)})^k \equiv m \cdot 1^k = m \pmod{n}, \end{aligned} \] which is what we wanted to show.

The second case is when \(\gcd(m, n) \neq 1\). Since \(n = pq\) and \(0 \leq m < n\), it must be that \(\gcd(m, n) = p\) or \(\gcd(m, n) = q\). Without loss of generality, suppose \(\gcd(m, n) = p\). This means that \(m = xp\) for some integer \(x\) and also that \(m\) is not divisible by \(q\). Euler’s theorem tells us that \(m^{q-1} \equiv 1 \pmod{q}\), so \[ m^{k\phi(n)} = m^{k(p-1)(q-1)} = (m^{q-1})^{k(p-1)} \equiv 1^{k(p-1)} = 1 \pmod{q} \] so there exists an integer \(h\) such that \(m^{k\phi(n)} = 1 + hq\). Then \[ m^{1 + k\phi(n)} = m(1 + hq) = m + hmq = m + hxpq = m + hxn \equiv m \pmod{n}, \] which again is what we wanted to show! \(\Box\)

Proof Exercise Show that the RSA theorem continues to hold when \(n\) is a product of arbitrarily many distinct primes (ie, not just 2 distinct primes).

Exercise Give an example to show that the RSA theorem does not hold when \(n\) is not a product of two distinct primes.

Hints. In other words, you want to find an integer \(n\), and an integer \(d\) which is relatively prime to \(\phi(n)\) with inverse \(e\), and an integer \(m\) with \(0 \leq m \leq n-1\) such that \((m^e)^d \not\equiv m \pmod{n}\). The RSA theorem tells us that \(n\) cannot be a product of two distinct primes, and in fact if you did the above proof exercise, you know that it cannot be a product of any number of distinct primes, which means the prime factorization of \(n\) must contain at least one exponent that’s bigger than 1. Pick your favorite such value of \(n\). Then use Euler’s theorem to rule out many possibilities for \(m\)

Exercise Suppose \(n\) is a product of two distinct primes, that \(e\) is invertible mod \(\phi(n)\), and that \(c\) is an \(e\)th power mod \(n\). Show that \(c\) has a unique \(e\)th root mod \(n\).

Why RSA is Probably Secure (for now…)

If Eve is eavesdropping on Alice and Bob’s communication, she knows Bob’s public key \((n, e)\) and she sees Alice’s ciphertext \(c\). She knows that \(c\) is the \(e\)th power mod \(n\) of Alice’s original message \(m\), so the security of RSA relies on the presumed difficulty of the following problem:

Discrete Root Problem Suppose you are given positive integers \(n\), \(e\), and \(c\), and you know further that:

Find the unique \(e\)th root of \(c\) mod \(n\), ie, the unique integer \(m\) such that \(0 \leq m \leq n-1\) such that \(m^e \equiv c \bmod{n}\).

Most likely, there is no fast way of doing this — except for the way that Bob uses, which requires some secret knowledge! Bob needs to know the decryption exponent \(d\), which is an inverse of \(e\) mod \(\phi(n)\), and knowing that would seem to require knowing \(\phi(n)\).1 The following lemma shows that knowledge of \(\phi(n)\) is actually equivalent to a knowledge of a factorization of \(n\), which is believed to be hard to find quickly!

Lemma Suppose \(p, q\) are distinct primes and \(n = pq\). If Eve knows \(n\) and can quickly calculate \(\phi(n)\), then she can also quickly find \(p\) and \(q\).

Proof. Observe that \[ \phi(n) = (p-1)(q-1) = pq - p - q + 1 = n - p - q + 1, \] which means that \[ n+1-\phi(n) = p + q, \] which means that \[ (x-p)(x-q) = x^2 - (p+q)x + pq = x^2 - (n+1-\phi(n))x + n. \] In other words, \(p\) and \(q\) are the two roots of the quadratic polynomial \(x^2 - (n+1-\phi(n))x + n\), so if Eve knows how to quickly find \(\phi(n)\), she can then just apply the quadratic formula to this polynomial to factor \(n\) and find \(p\) and \(q\). \(\Box\)

Exercise Suppose \(p\) and \(q\) are distinct primes and \(n = pq\). Use the quadratic formula to write down an explicit formula for \(p\) and \(q\) in terms of \(n\) and \(\phi(n)\).

In other words, the lemma tells us that, since it is believed that there is no fast factoring algorithm for classical (ie, non-quantum) computers, this tells us that Eve probably does not have a quick way of finding the decryption exponent \(d\) in the same way that Bob does.

Exercise Bob’s public key is \((n, e)\) where \[ \begin{aligned} n &= 717426848223284193177165144369883618288687316631460708260937 \\ e &= 31883625115837871682689851305708348256252087949589953972423. \end{aligned} \] Unfortunately for Bob, he has chosen his public key to be too small: this \(n\) is small enough that it can be factored by modern computers in a few seconds! Eve has just intercepted the ciphertext \[ c = 35831783079824311094981278118129411294275821240128031455119 \] that Alice was trying to send to Bob. Find the plaintext (as text, not just as a number).

Exercise Do one (or more!) of the following:

  1. Play the role of Bob: Generate a RSA public key for yourself using the RSA SageCells and post it to our class stream on Zulip.
  2. Play the role of Alice: Watch for a classmate who has posted their RSA public key to Zulip. Send them a secret message by encrypting it with their public key using the RSA SageCells.
  3. Play the role of Eve: Watch for RSA ciphertext being exchanged by some pair of your classmates on Zulip. See if you can figure out what the plaintext is!

Exercise Bob chooses a large and secure RSA key. Suppose that Alice encodes each letter in her message as an integer 0–25 and then encrypts each of these integers individually using Bob’s public key (instead of encoding her entire message using the base-26 encoding scheme described above). She then sends that entire sequence of ciphertexts over to Bob.

Explain why this is very insecure. In other words, suppose Eve intercepts the sequence of ciphertexts (each corresponding to a single letter in her message) that Alice sends to Bob. Explain how Eve will be able to recover Alice’s message even if the modulus of Bob’s RSA public key is too large to be factored.

4.6. Interlude: Order

Here is a basic definition that we will need in order to describe our next cryptosystems.

Definition Fix a positive integer \(n\). If \(a\) is an integer with \(\gcd(a, n) = 1\), the order of \(a\) mod \(n\), denoted \(\mathrm{ord}_n(a)\), is the smallest positive integer \(k\) such that \(a^k \equiv 1 \pmod{n}\).

For example, suppose \(n = 7\) and \(a = 2\). We then compute: \[ \begin{aligned} 2^2 &= 4 \pmod{7} \\ 2^3 &= 8 \equiv 1 \pmod{7} \end{aligned} \] Thus 3 is the smallest positive exponent such that raising 2 to that power gives us something congruent to 1 mod 7, which means that \(\mathrm{ord}_7(2) = 3\).

Order Lemmas

Note that \(\phi(7) = 6\), and \(\mathrm{ord}_7(2) = 3\) happens to be a divisor of 6. This is no coincidence!

First Lemma About Orders Fix a positive integer \(n\) and an integer \(a\) with \(\gcd(a, n) = 1\). If \(m\) is an integer with \(a^m \equiv 1 \pmod{n}\), then \(\mathrm{ord}_n(a)\) divides \(m\). In particular, \(\mathrm{ord}_n(a)\) divides \(\phi(n)\).

Proof. Let \(k = \mathrm{ord}_n(a)\). By Euclid’s Division Lemma, we can write \(m = kq + r\) where \(0 \leq r < k\). Then \[ 1 \equiv a^m = a^{kq + r} = (a^k)^q a^r \equiv 1^q \cdot a^r = a^r \pmod{n}. \] If \(r\) was nonzero, it would be a positive exponent strictly smaller than \(k\) which gives a number congruent to 1 mod \(n\), which contradicts the definition of \(\mathrm{ord}(a)\). Thus it must be that \(r = 0\), ie, that \(k\) divides \(m\).

By Euler’s theorem, we know that \(a^{\phi(n)} \equiv 1 \pmod{n}\). By what we have just shown, we therefore know that \(\mathrm{ord}_n(a)\) divides \(\phi(n)\). \(\Box\)

The First Order Lemma makes it a bit easier to compute the order of an element. Suppose, for example, that we are interested in \(n = 7\) and \(a = 3\). The lemma guarantees that \(\mathrm{ord}_7(3)\) must be a divisor of \(\phi(7) = 6\), so it can only be 1, 2, 3, or 6. We check: \[ \begin{aligned} 3^1 &\not\equiv 1 \pmod{7} \\ 3^2 &= 9 \equiv 2 \not\equiv 1 \pmod{7} \\ 3^3 &= 27 \equiv 6 \not\equiv 1 \pmod{7} \end{aligned} \] Thus \(\mathrm{ord}_7(3)\) cannot be 1, 2, or 3, so we know that it must be 6.

Exercise Calculate the following orders.

  1. \(\mathrm{ord}_5(2)\)
  2. \(\mathrm{ord}_9(4)\)
  3. \(\mathrm{ord}_{10}(3)\)
  4. \(\mathrm{ord}_{11}(7)\)
  5. \(\mathrm{ord}_{13}(1)\)

Second Lemma About Orders Fix a positive integer \(n\) and an integer \(a\) with \(\gcd(a, n) = 1\) and let \(k = \mathrm{ord}_n(a)\). Then \(a^i \equiv a^j \pmod{n}\) if and only if \(i \equiv j \pmod{k}\). In particular, the numbers \(a^0, a^1, a^2, a^3, \dotsc, a^{k-1}\) are all incongruent mod \(n\).

Proof. First suppose that \(i \equiv j \pmod{k}\). Then there exists an integer \(q\) such that \(i = kq + j\), so \[ a^i = a^{kq + j} = (a^k)^q a^j \equiv 1^q a^j = a^j \pmod{n} \] since \(a^k \equiv 1 \pmod{n}\). Conversely, suppose \(a^i \equiv a^j \pmod{n}\) and assume without loss of generality that \(i \geq j\). By multiplying both sides by \(a^{-1}\) mod \(n\) a total of \(j\) times, we find that \(a^{i-j} \equiv 1 \pmod{n}\), so the First Lemma About Orders tells us that \(k\) divides \(i - j\). In other words, \(i \equiv j \pmod{k}\).

For the final assertion, note that \(0, 1, 2, \dotsc, k-1\) are all incongruent mod \(k\), so \(a^0, a^1, a^2, \dotsc, a^{k-1}\) must all be incongruent mod \(n\). \(\Box\)

SageCell Sage can find orders mod \(n\). The following computes \(\mathrm{ord}_5(2)\), for example.

Proof Exercise

  1. If \(m\) is an integer and \(p\) is an odd prime divisor of \(m^4 + 1\), show that \(p \equiv 1 \pmod{8}\). Hint. First show carefully that \(m\) has order 8 mod \(p\).
  2. Show that there are infinitely many primes that are congruent to 1 mod 8. Hint. Suppose for a contradiction that there are only finitely many such primes \(p_1, \dotsc, p_r\) and then apply the part (a) to the integer \(n = (2p_1 \cdots p_r)^4 + 1\).

Primitive Roots and Discrete Logarithms

The First Lemma About Orders tells us that \(\phi(n)\) is the largest possible order mod \(n\) that any integer could have, since the order must always be a divisor of \(\phi(n)\). The situation when this maximum is achived gets a special name:

Definition Fix an integer \(n \geq 2\). An integer \(g\) with \(\gcd(g, n) = 1\) and \(\mathrm{ord}_n(g) = \phi(n)\) is called a primitive root mod \(n\).

For example, we saw above that \(\mathrm{ord}_7(3) = 6 = \phi(7)\), so 3 is a primitive root mod 7.

The Second Lemma About Orders tells us that \(3^0, 3^1, 3^2, 3^3, 3^4, 3^5\) are all incongruent mod 7, but there are only 6 nonzero congruence classes mod 7, so the fact that all of the nonzero congruence classes mod 7 must be represented among the integers \(3^0, 3^1, 3^2, 3^3, 3^4, 3^5\). Let’s check this explicitly: \[ \begin{aligned} 3^0 &\equiv 1 \pmod{7} \\ 3^1 &\equiv 3 \pmod{7} \\ 3^2 &\equiv 2 \pmod{7} \\ 3^3 &\equiv 6 \pmod{7} \\ 3^4 &\equiv 4 \pmod{7} \\ 3^5 &\equiv 5 \pmod{7} \end{aligned} \] All of the nonzero remainders mod 7 appear in this list. This generalizes:

Existence of Discrete Logarithms Lemma Fix an integer \(n \geq 2\) and suppose \(g\) is a primitive root mod \(n\). If \(\gcd(a, n) = 1\), then there exists a unique integer \(k\) such that \(0 \leq k \leq \phi(n)\) and \(g^k \equiv a \pmod{n}\). This integer \(k\) is called the discrete log base \(g\) of \(a\) mod \(n\) and is denoted \(\log_g(a \bmod{n})\).

Our calculations above show that the discrete log base 3 of 6 mod 7 is 3, because \(3^3 \equiv 6 \pmod{7}\).

Exercise For each of the following, determine whether or not the proposed value of \(g\) is actually a primitive root mod \(n\).

  1. \(n = 11, g = 2\)
  2. \(n = 11, g = 3\)
  3. \(n = 11, g = 4\)

Exercise For each of the following values of \(n\), find all of the primitive roots mod \(n\).

  1. \(n = 5\)
  2. \(n = 7\)
  3. \(n = 11\)

Exercise For each of the following, find the discrete log base \(g\) of \(a\) mod \(n\).

  1. \(n = 7, g = 3, a = 5\)
  2. \(n = 5, g = 2, a = 4\)
  3. \(n = 11, g = 2, a = 3\)

Exercise Explain in your own words why the Second Lemma About Orders immediately implies the Existence of Discrete Logarithms Lemma.

SageCell Sage can find discrete logarithms. It is of course much faster than trying to find discrete logarithms by hand, but it is important to note for what’s coming next that finding discrete logarithms seems to be an inherently hard problem: there is no fast way of doing it, and Sage will struggle as soon as the numbers get moderately large, just as Sage struggles with finding prime factorizations for moderately large numbers. Here is the syntax for finding \(\log_3(6 \bmod{7})\).

Exercise Suppose \(p \geq 3\) is prime and \(g\) is a primitive root mod \(p\). Explain why \[\log_g(-1 \bmod{p}) = \frac{p-1}{2}. \]

Exercise Suppose \(p \geq 3\) is prime and \(g\) is a primitive root mod \(p\). Explain why \[ 1 + g + g^2 + \cdots + g^{p-1} \equiv 0 \pmod{p}. \]

Existence of Primitive Roots

We haven’t yet shown that primitive roots always exist, and in fact, it is not true that primitive roots always exist. Here is the statement:

Primitive Root Theorem Fix an integer \(n \geq 2\). Then there exists a primitive root mod \(n\) if and only if \(n = 2, 4, p^k\), or \(2p^k\) for an odd prime \(p\) and a positive integer \(k\). In particular, there always exists a primitive root mod a prime.

Proving this theorem would require a somewhat lengthy tangent, so I will omit it.

Exercise Verify explicitly (ie, without using the Primitive Root Theorem) that there is no primitive root mod 8. In other words, verify that none of the integers 1, 3, 5, or 7 have order \(\phi(8) = 4\) mod 8.

Exercise Use the Primitive Root Theorem to find the 5 smallest integers \(n \geq 2\) such that there does not exist a primitive root mod \(n\).

Proof Exercise Do one of the following:

  1. (Harder) Prove the Primitive Root Theorem yourself.
  2. (Easier) Read through a proof of the Primitive Root Theorem. (For example, see section 2.5 in Stein’s “Elementary Number Theory,” or sections 8.2–3 in Burton’s “Elementary Number Theory,” or find another reference you like!) Then summarize the proof strategy that you read about in your own words.
SageCell The Sage function primitive_root returns the smallest primitive root for the input argument. For example:

Sage Exercise Find the proportion of primes \(p < 1000\) such that 2 is a primitive root mod \(p\).

Sage Exercise Find a prime \(p\) such that the smallest primitive root mod \(p\) is \(g = 37\).

4.7. Elgamal

The Elgamal cryptosystem is a public-key cryptosystem like RSA, named after the Egyptian cryptographer Taher Elgamal.

How Elgamal Works

The process begins by Bob choosing a public key. He picks a prime number \(p\) and a primitive root \(g\) of \(p\). He chooses a random integer \(x\) with \(0 \leq x < p-1\). This is his private key. He then computes \(h = g^x \bmod{p}\) and his public key is the triple \((p, g, h)\).

Suppose now that Alice wants to send Bob a message. She first encodes her message as an integer \(m\) between 0 and \(p-1\). For example, we can use the same “base 26” strategy that we employed for RSA above. She then chooses a random integer \(y\) between 0 and \(p-1\) called the “ephemeral key.” Alice will have to choose a different ephemeral key for every message she sends, but Bob does not have to know the value of this key beforehand! Alice computes \(s = h^y \bmod{p}\), \(c_1 = g^y \bmod{p}\), and \(c_2 = ms \pmod{p}\). Note that she can compute \(s\) and \(c_1\) quickly using binary exponentiation! The pair \((c_1, c_2)\) is the ciphertext that she sends to Bob.

To decrypt the ciphertext \((c_1, c_2)\), Bob first computes \(c_1^x \bmod{p}\). Bob can do this quickly using binary exponentiation. Observe that \[ c_1^x \equiv (g^y)^x = g^{xy} = (g^x)^y \equiv h^y \equiv s \bmod{p}. \] In other words, Bob has now found the same value of \(s\) that Alice had, even though he does not know the value of the ephemeral key \(y\). He then computes an inverse mod \(p\) of \(c_1^x\) using the extended euclidean algorithm (which is also very efficient). He then computes the product \[ c_2 (c_1^x)^{-1} \equiv c_2 s^{-1} \equiv (ms)s^{-1} \equiv m \cdot 1 = m, \pmod{p} \] and he has recovered Alice’s message \(m\).

For example, suppose Bob picks the prime \(p = 4115549\), and \(g = 2\) is his primitive root. He then picks a random integer \(x = 2634326\). He can then compute \(h = g^x \bmod{p}\) quickly using binary exponentiation (eg, using the power_mod function in Sage); he finds \(h = 1149114\), so the triple \((4115549, 2, 1149114)\) is his public key. He must keep \(x = 2634326\) secret.

Now suppose that Alice wants to send Bob the message Hi Bob. As we did earlier in the RSA section, she can convert this to the integer \(m = 3340481\). She chooses an ephemeral key, say \(y = 2775147\). She keeps this value of \(y\) secret. She computes \(s = h^y \bmod{p}\) using binary exponentiation and finds \(s = 962840\). This \(s\) too, she keeps secret. She also computes \(c_1 = g^y \bmod{p}\) using binary exponentiation and finds \(c_1 = 621674\), and finally she computes \(c_2 = ms \bmod{p}\) and finds \(c_2 = 1911501\). The pair \((c_1, c_2) = (621674, 1911501)\) is then the ciphertext that she sends Bob.

Bob receives the pair \((c_1, c_2) = (621674, 1911501)\). He computes \(c_1^x \bmod{p}\) using binary exponentiation and finds that it is \(962840\), which is the same value that Alice had found for \(s\). He computes an inverse mod \(p\) (eg, using the Sage function inverse_mod) and finds \(s^{-1} \equiv 2329074 \bmod{p = 4115549}\). He then computes \[ c_2 s^{-1} \bmod{p} = 3340481, \] and he finally converts this back to the text HIBOB.

Exercise Suppose Bob picks the prime \(p = 29\) and the primitive root \(g = 2\).

  1. Suppose Bob picks \(x = 3\). What is his public key?
  2. Suppose Alice wants to send Bob the plaintext integer \(m = 7\). What is the corresponding ciphertext pair if the ephemeral key she chooses is \(y = 11\)?
  3. Suppose Bob receives the ciphertext pair \((3, 9)\) from Alice. What is the plaintext integer \(m\)?

Exercise If Bob wants to be able to receive messages with \(r = 10\) characters, how large must he choose \(p\) to be? What if \(r = 100\)? \(r = 1000\)?

Sage Exercise Write a pair of SageCells analogous to the RSA SageCells: one should generate an Elgamal key, and the second should perform Elgamal encryption and decryption.

Why Elgamal is Probably Secure (for now…)

There are at least two strategies that Eve might employ to recover the plaintext \(m\) from the ciphertext \((c_1, c_2)\). She might try to find Bob’s decryption key \(x\) so that she can follow Bob’s decryption strategy, but to do this, she needs to find the discrete log base \(g\) of \(h\) mod \(p\). Alternatively, she might try to find Alice’s ephemeral key \(y\) (because she can then compute \(h^y\), and then \((h^y)^{-1} \equiv s^{-1} \pmod{p}\), and then \(c_2(h^y)^{-1} \equiv (ms)s^{-1} \equiv m \pmod{p}\)), but then she needs to find the discrete log base \(g\) of \(c_1\) mod \(p\).

In other words, it would seem that in either case, Eve needs to find a discrete log base \(g\) mod \(p\). The security of the Elgamal cryptosystem thus relies on the presumed difficulty of the following problem:

Discrete Logarithm Problem Suppose you are given a prime \(p\), a primitive root \(g\) mod \(p\), and an integer \(a\) not divisible by \(p\). Find the discrete log base \(g\) of \(a\) mod \(p\). In other words, find the unique integer \(k\) such that \(0 \leq k \leq p-1\) such that \(g^k \equiv a \pmod{p}\).

As \(p\) gets large, this problem seems to get intractible for classical computers. The naive method to solving this problem would be to try all the possible values of \(k\) from 1 up to \(p-1\), but this is at least linear in \(p\), which means it is at least exponential in the number of digits of \(p\). There are slightly faster algorithms than this, and these faster methods are implemented by Sage for its discrete log functionality, but they are not faster by much (more precisely, there is no known algorithm that accomplishes this task that is polynomial in the number of digits of \(p\)).

Sage Exercise Read about Shank’s Baby-Step Giant-Step Algorithm for computing discrete logarithms. Then implement the algorithm yourself.

Sage Exercise Read about Pollard’s Kangaroo Algorithm (also called “Pollard’s Lambda Algorithm”) for computing discrete logarithms. Then implement the algorithm yourself.

4.8. Diffie-Hellman

The Diffie-Hellman key exchange is not quite a cryptosystem for exchanging messages; it is a protocol that allows Alice and Bob to share a secret, but neither has full control over the content of the shared secret. Nonetheless, the shared secret can then be used as the key for a symmetric key cipher like a one-time pad.

The procedure is named after Whitfield Diffie and Martin Hellman, who published the protocol in 1976. The GCHQ mathematician Malcolm Williamson had developed the same protocol back in 1974, but his work was only declassified in 1997.

The procedure is as follows. Alice and Bob publicly agree to fix a prime \(p\) and a primitive root \(g\) mod \(p\). Alice then chooses a secret integer \(0 \leq a < p-1\) and sends Bob \(x = g^a \bmod{p}\). She can compute this value quickly using binary exponentiation. Bob similarly chooses a secret integer \(0 \leq b < p-1\) and sends Alice \(y = g^b \bmod{p}\). Alice computes \(s = y^a \bmod{p}\), and Bob computes \(s = x^b \bmod{p}\). The two values of \(s\) that Alice and Bob compute are the same, because \[ y^a \equiv (g^b)^a = g^{ab} = (g^a)^b \equiv x^b \pmod{p}. \] Thus Alice and Bob now share a secret, \(s\). Notice that neither has full control over the shared secret, so this cannot be regarded as Alice or Bob sending a message to the other.

Exercise Suppose Alice and Bob agree to use \(p = 11\) and \(g = 2\). Alice chooses the integer \(a = 3\). She receives the integer \(y = 5\) from Bob. What is her shared secret \(s\) with Bob?

Exercise Explain how the base-26 representation of Alice and Bob’s shared secret \(s\) can be used as a key for a one-time pad.

Exercise Explain why the presumed difficulty finding discrete logarithms implies the security of the Diffie-Hellman key exchange.

Exercise Do one (or both!) of the following:

  1. Play the role of Alice and Bob: Pick a friend in the class and perform a Diffie-Hellman key exchange with them. Do your communications in our class stream on Zulip so that everyone can see the values of \(p, g, x, y\) that you share between the two of you, but make sure to keep \(a\) and \(b\) secret.
  2. Play the role of Eve: Watch for some pair of classmates performing Diffie-Hellman on Zulip, and then see if you can figure out their shared secret!

Exercise Explain how the Diffie-Hellman process of producing a “shared secret” also appears as a part of the Elgamal cryptosystem.

There are many other cryptographic protocols besides the Diffie-Hellman key exchange which involve the presumed difficulty of the discrete log problem and which are not strictly about exchanging messages. Here are some examples:

Sage Exercise Read about one of the protocols listed above, and then implement it!

4.9. Interlude: Elliptic Curves Over the Reals

We’ll start with a discussion of elliptic curves over the real numbers in order to develop some geometric intuition about elliptic curves.

Definition A Weierstrass equation over the real numbers is an equation in \(x\) and \(y\) of the form \[ y^2 = x^3 + ax + b \] where \(a, b\) are fixed real numbers. The discriminant of the equation is \[ \Delta = -16(4a^3 + 27b^2) \] and the equation is singular when \(\Delta = 0\). Otherwise, the equation is said to be nonsingular.

Here is a theorem that is useful to keep in mind, but we omit a proof because it will not be important for us in cryptography:

Theorem The Weierstrass equation \(y^2 = x^3 + ax + b\) is nonsingular if and only if the cubic equation \(x^3 + ax + b = 0\) has no repeated roots in the complex numbers.

Given a Weierstrass equation, we can make a plot of the points \((x, y)\) in the plane that satisfy that equation. Here is a SageCell that makes these plots for you; make sure to play with it before moving forward!

SageCell / Exercise This SageCell makes plots of curves defined by Weierstrass equations. It defaults to \(y^2 = x^3 - 1\). The view box defaults to the range \(-3 \leq x, y \leq 3\), but you can change the 3 using the ``View’’ input box. The cell tells you whether the curve is singular or not, and then makes plots. Use the SageCell to look at plots of the following curves:

  1. \(y^2 = x^3 + b\) for \(b = 0, -1, -2, -3, \dotsc, -6\)
  2. \(y^2 = x^3 + ax\) for \(a = -6, -5, \dotsc, 0, 1, \dotsc, 6\)
  3. \(y^2 = x^3 + ax + \sqrt{4/27}\) for \(a = -0.5, -0.8, -0.9, -0.99, -1, -1.01, -1.1, -1.2, -1.5\)

Note that you can enter expressions like sqrt(4/27) in the input box for b.

What you should have found by playing with the above SageCell is that the set of points satisfying a nonsingular Weierstrass equation always roughly has one of the following shapes:

These curves have a lot of important geometry. To get started, observe that they are symmetric about the \(x\)-axis, ie, they have vertical symmetry. Stated formally, if \((x, y)\) is a point satisfying \(y^2 = x^3 + ax + b\), then its reflection \((x, -y)\) across the \(x\)-axis is also a point satisfying the same equation! If \(P = (x, y)\) is a point on a curve defined by a Weierstrass equation, we define \(-P\) to be this reflection \((x, -y)\). (Careful: we only invert the \(y\)-coordinate of \(P\) to get \(-P\), not both coordinates!)

Here is the second property: if I pick any two points on the curve, the unique line that passes through those two points will have a unique “other” point of intersection with the curve. Well, almost…! But we will get to this almost soon. First, here is an example:

Consider the Weierstrass equation \[ y^2 = x^3 + 17. \] It is nonsingular because \[ \Delta = -16(4 \cdot 0^3 + 27 \cdot 17^2) = -16 \cdot 27 \cdot 17^2 \neq 0. \] Consider the points \(P = (-2, 3)\) and \(Q = (-1, 4)\). Both of these lie on the curve, as you should verify:

Exercise Check that \(P = (-2, 3)\) and \(Q = (-1, 4)\) are both on the curve defined by \(y^2 = x^3 + 17\).

There is a unique “secant” line that passes through these two points. We can calculate its slope using the usual rise-over-run formula as \[ m = \frac{4 - 3}{-1 - (-2)} = \frac{1}{1} = 1 \] and then we can find the equation of the secant line itself using point-slope form: \[ \begin{aligned} y - 4 &= 1 \cdot (x - (-1)) \\ y &= x + 5 \end{aligned} \] Let’s now think about intersecting this secant line with the curve. This will consist of all \((x, y)\) which satisfy both \(y = x + 5\) and also \(y^2 = x^3 + 17\), so if we substitute the first equation in the second, we see that we must have \[ \begin{aligned} (x+5)^2 &= x^3 + 17 \\ x^2 + 10x + 25 &= x^3 + 17 \\ x^3 - x^2 - 10x - 8 &= 0 \end{aligned} \] We now have to solve a cubic equation, which isn’t easy in general, but here’s the trick: we already know that \(x = -2\) and \(x = -1\) must be solutions to this equation! After all, we know that \(P = (-2, 3)\) and \(Q = (-1, 4)\) are on the curve and on the line, and the \(x\)-coodinates of these points are precisely \(-2\) and \(-1\). This means that \((x+2)(x+1) = x^2 + 3x + 2\) must divide \(x^3 - x^2 - 10x - 8\), and we can use polynomial long division to find the quotient.

Exercise Use polynomial long division to divide \(x^3 - x^2 - 10x - 8\) by \(x^2 + 3x + 2\) and check that the quotient is \(x-4\) and the remainder is 0.

The upshot is that \(x^3 - x^2 - 10x - 8 = (x+2)(x+1)(x-4)\), so the third solution to the cubic equation \(x^3 - x^2 - 10x - 8 = 0\) is \(x = 4\). If we plug \(x = 4\) into the equation of the line, we find the point \(R = (4, 9)\). We already know by construction that this point \(R\) must satisfy the Weierstrass equation too, but you should check this:

Exercise Check that \(R = (4, 9)\) is on the curve defined \(y^2 = x^3 + 17\).

Here is the picture of what we’ve just done:

As indicated in the picture, we will define \(P+Q\) to be the negative of this third point of intersection. Be careful: this process is much more complicated than simply adding the \(x\) and \(y\) coordinates of the two points! You should do the following exercise before proceeding:

Exercise

  1. Let \(S = (2, 5)\). Check that \(S\) is on the same curve \(y^2 = x^3 + 17\).
  2. What is the third point of the intersection on between the curve \(y^2 = x^3 + 17\) and the secant line connecting \(Q = (-1, 4)\) and \(S\)?
  3. What is \(Q + S\)?
  4. With \(P = (-2, 3)\) and \(R = (4, 9)\) on \(y^2 = x^3 + 17\) as above, what is \(P + R\)?

Let’s now return to the “almost” we mentioned above. In fact, this “almost” actually encompassed two caveats that we need to discuss.

The first caveat has to do with the case when the two points we start with are the same point. Consider again the situation \(P = (-2, 3)\). How can we make sense of \(P + P\), or \(2P\)? The very first step involves finding the equation of the secant line that passes through \(P\) and \(P\), but there isn’t a unique such line…!

But, if you think back to your calculus classes, you might remember that: if you think about the secant lines through two points on a curve, and take the limit as one of the two points approaches the other, what you wind up with is the tangent line! So we’ll use this. In other words, to define \(P + P\), we’ll go through the same process that we did above, but we’ll use the tangent line of the curve at \(P\).

Let’s work this out. To find the slope of the tangent line, we use implicit differentiation on the equation \(y^2 = x^3 + 17\). We get \[ 2y \frac{dy}{dx} = 3x^2 \] and then we plug in \(P = (x, y) = (-2, 3)\) to get \[ \begin{aligned} 2 \cdot 3 \cdot \left.\frac{dy}{dx}\right|_P &= 3(-2)^2 \\ \left.\frac{dy}{dx}\right|_P &= 2 \end{aligned} \] We then find the equation of the tangent line again using point-slope form like we did above: \[ \begin{aligned} y - 3 &= 2(x - (-2)) \\ y &= 2x + 7 \end{aligned} \] We now want to intersect this point with the curve, so we again substitute \(y = 2x+7\) into \(y^2 = x^3 + 17\) like we did above: \[ \begin{aligned} (2x+7)^2 &= x^3 + 17 \\ 4x^2 + 28x + 49 &= x^3 + 17 \\ x^3 - 4x^2 - 28x - 32 &= 0 \end{aligned} \] We again have a cubic equation to factor. Last time, we knew two factors of the cubic because we knew two points on the intersection. This time, we only know one point of the intersection, but we know that the line is tangent to the curve at \(P\), so the \(x\)-coordinate of \(P\), ie \(x = -2\), must be a double root of this cubic! This means that the cubic must be divisible by \((x-(-2))^2 = x^2 + 4x + 4\), and we can again use polynomial long division to find the “third” point of intersection.

Exercise Use polynomial long division to divide \(x^3 - 4x^2 - 28x - 32\) by \(x^2 + 4x + 4\) and check that the quotient is \(x-8\) and the remainder is 0.

This means that the third point of intersection has \(x\)-coordinate 8, so its \(y\)-coordinate is \(2 \cdot 8 + 7 = 23\). We then reflect this point across the \(x\)-axis and find that \(2P = (8, -23)\). Here is a picture of what we have just done:

Note that the curve looks different from the previous picture only because of the scale on the axes; it is the same curve.

Exercise On the same curve \(y^2 = x^3 + 17\), calculate the following.

  1. \(2Q\), where \(Q = (-1, 4)\).
  2. \(2S\), where \(S = (2, 5)\).

This brings us to the second caveat that was encompassed by our “almost.” There is one situation when the line passing through two points (either the secant line through two distinct points or the tangent line at a single point) does not have a third point of intersection with the curve. This will happen precisely when the line ends up being vertical! This should be clear from the geometry, but you should verify it algebraically:

Exercise Verify algebraically that the secant line passing through \((-2, 3)\) and \((-2, -3)\) is vertical, and that this line has no other point of intersection with the curve \(y^2 = x^3 + 17\).

We deal with this by fiat. We declare that there is a point, denoted \(O\) and called the point at infinity, which is a point on the curve defined by \(y^2 = x^3 + 17\) and is also a point on every vertical line in the plane. It is its own negative. Thus, if we’re trying to “add” two points and encounter the situation where a secant or tangent line is vertical, we declare the sum to be \(O\).

Exercise Based on our definition of \(O\) as being “point on the curve defined by \(y^2 = x^3 + 17\) and also a point on every vertical line in the plane,” explain why it makes sense to assert that \(P + O = P\) for \(P = (-2, 3)\) – or, in fact, for any point \(P\) on the curve.

Having worked through this extended example, we can now make some formal statements.

Definition-Theorem Fix a nonsingular Weiertrass equation \(y^2 = x^3 + ax + b\). The elliptic curve \(E\) defined by this equation is the set of points \((x, y)\) satisfying this equation, together with a point at infinity denoted \(O\) and assumed by fiat to:

Given any \(P \in E\), we define \(-P\) to be the reflection of \(P\) across the \(x\)-axis. Given any two points \(P, Q \in E\), there is a unique secant or tangent line passing through \(P\) and \(Q\), and this line has a unique third point of intersection with the curve; we define \(P+Q\) to be the negative of this third point of intersection. Then:

If you’ve taken some abstract algebra, you’ll probably recognize that the above is saying that \(E\) is an “abelian group” — but don’t worry about this if you don’t know what this means.

Exercise Explain geometrically why the commutativity, identity, and inverses properties above hold.

Note. It is also possible to explain geometrically why the associativity property holds, but this is much much harder.

Exercise What do you think goes wrong if we start with a singular Weierstrass equation instead?

It is also useful to generalize the calculations we did above and derive the following general formulas:

Elliptic Curve Addition Formula Theorem Suppose \(P = (x_1, y_1)\) and \(Q = (x_2, y_2)\) are both points on the curve \(y^2 = x^3 + ax + b\). Define \[ \lambda = \begin{cases} \dfrac{y_2 - y_1}{x_2 - x_1} & \text{if } P \neq Q \\ \dfrac{3x_1^2 + a}{2y_1} & \text{if } P = Q \end{cases} \] If \(\lambda\) is defined (ie, if the denominator above is nonzero), set \[ \begin{aligned} \nu &= y_1 - \lambda x_1 \\ x_3 &= \lambda^2 - x_1 - x_2 \\ y_3 &= \lambda x_3 + \nu \end{aligned} \] Then \(P + Q = (x_3, -y_3)\).

Proof Exercise Prove the Elliptic Curve Addition Formula Theorem. Hint. The line passing through \(P\) and \(Q\) is \(y = \lambda x + \nu\).

Harder Proof Exercise Use the Elliptic Curve Addition Formula Theorem to prove algebraically that the associativity property holds, ie, that \((P + Q) + R = P + (Q + R)\) for all \(P, Q, R \in E\).

Let’s conclude our discussion of elliptic curves over the reals with one more concrete example. This is another highly recommended exercise!

Exercise Consider the Weierstrass equation \(y^2 = x^3 - 2x\).

  1. Verify that this equation is nonsingular. Let \(E\) be the corresponding elliptic curve.
  2. Verify that \(P = (0, 0)\) is on the curve. What is \(2P\)?
  3. Verify that \(Q = (-1, 1)\) is on the curve. What is \(2Q\)?
  4. What is \(P + Q\)?
  5. What is \(3Q\)?
  6. What is \(4Q\)?
  7. What is \(5Q\)?

We can compute multiples of a point by using the same idea as binary exponentiaton — except that maybe it’s better to call it “binary multiplication” in this situation. Consider \(P = (-2, 3)\) on the elliptic curve defined by \(y^2 = x^3 + 17\) again. Let’s say that we want to compute \(6P\), ie, the sum of \(P\) with itself 6 times. The idea is to double repeatedly: \[ \begin{aligned} P &= (-2, 3) \\ 2P &= (8, -23) \\ 4P &= 2(2P) = \left(\frac{752}{529}, -\frac{54239}{12167}\right) \end{aligned} \] We then put these together: \[ 6P = 4P + 2P = \left(\frac{752}{529}, -\frac{54239}{12167}\right) + (8, -23) = \left( -\frac{4471631}{3027600}, -\frac{19554357097}{5268024000} \right). \]

We also make the following definition of order.

Definition Suppose \(P\) is a point on an elliptic curve \(E\). The order of \(P\), denoted \(\mathrm{ord}_E(P)\), is the smallest positive integer \(n\) such that \(nP = O\), if such an integer exists. Otherwise, the order of \(P\) is \(\infty\).

Exercise Let \(E\) be the elliptic curve defined by the Weierstrass equation \(y^2 = x^3 - 4x\). Find the order of the following points.

  1. \(P = (-2, 0)\).
  2. \(Q = (0, 0)\).
  3. \(P + Q\).

Exercise Let \(E\) be the elliptic curve defined by the Weierstrass equation \(y^2 = x^3 + 5805x - 285714\). Verify that \(P = (327, 6048)\) is a point on this curve, and then find its order by hand.

Note. This might be a little tedious, but it’s good practice! It’s also not that horrendous: the answer is somewhere between 5 and 10 ☺

SageCell Here is some Sage code to create an elliptic curve. Specifically, this code sets E to be the elliptic curve corresponding to the equation \(y^2 = x^3 + 17 = x^3 + 0 \cdot x + 17\). We then define P the be the point \((-2, 3)\) on the curve E and Q to be the point \((-1, 4)\), and then have Sage compute the sum for us!

A note about the format of the output: the point that we’ve been calling \(O\) is denoted by Sage as (0 : 1 : 0), and the point that we’d call \((x, y)\) is what Sage would denote by (x : y : 1). There are really good reasons for doing this (these are what are called “projective coordinates” for the points), but we don’t need to get into this. If you like, you can also specify points on the curve in projective coordinates by writing things like P = E(-2, 3, 1).

We can also get Sage to compute multiples for us:

Note that the QQ in the above tells Sage to do exact arithmetic with fractions, instead of using floating point decimal approximations. If you don’t care about doing exact arithmetic, you can replace the QQ with RR instead.

4.10. Interlude: Elliptic Curves Mod a Prime

We now fix a prime \(p\). For technical reasons that not worth lingering on for our cryptographic purposes, we should assume \(p \neq 2, 3\), ie, that \(p \geq 5\). (In applications to cryptography, \(p\) will anyway be very very large!)

We start with adapting our definitions above as follows.

Definition A Weierstrass equation \(y^2 = x^3 + ax + b\) is integral if \(a\) and \(b\) are integers. We then say that the equation is singular mod \(p\) if \(\Delta \equiv 0 \pmod{p}\). Otherwise, it is nonsingular mod \(p\).

Consider, for example, the Weierstrass equation \(y^2 = x^3 + 17\). It is integral since \(a = 0\) and \(b = 17\) are integers. We calculated earlier that \[ \Delta = -16 \cdot 27 \cdot 17^2. \] The only primes this is divisible by are 2, 3, and 17. Thus the equation \(y^2 = x^3 + 17\) is singular mod \(p = 17\), but nonsingular otherwise (recall that we are anyway ruling out \(p = 2, 3\)).

Exercise For each of the following integral Weierstrass equations, find all primes \(p \geq 5\) such that the equation is singular mod \(p\).

  1. \(y^2 = x^3 - 2x\)
  2. \(y^2 = x^3 + x + 1\)
  3. \(y^2 = x^3 - 1\)

When we have an integral Weierstrass equation \(y^2 = x^3 + ax + b\), we can consider its “solutions mod \(p\).” By this we mean integers \((x, y)\) such that \(y^2 \equiv x^3 + ax + b \pmod{p}\). For example, suppose \(p = 7\) and consider the Weierstrass equation \(y^2 = x^3 + 17\). Then \((1, 2)\) is a solution to the equation mod \(p\) because \[ y^2 = 2^2 = 4 \equiv 18 = 1^3 + 17 = x^3 + 17 \pmod{7}. \] Let’s define that, if \(x, y, x', y'\) are all integers, then \((x, y) \equiv (x', y') \pmod{p}\) means that \(x \equiv x' \pmod{p}\) and \(y \equiv y' \pmod{p}\). Notice that, if \((x, y)\) is a solution mod \(p\) of \(y^2 = x^3 + ax + b\), then so is any pair of integers that is congruent mod \(p\). In the example above, observe that \((1, 9)\) or \((8, 2)\) or \((-6, 9)\) are all congruent mod 7 to \((1,2)\), and they are all also solutions mod 7 to \(y^2 = x^3 + 17\). We’ll typically only consider solutions \((x, y)\) where \(0 \leq x, y < p\), in order to avoid having to list off all of the congruent solutions.

It doesn’t really make sense to visualize (congruence classes of) solutions to Weierstrass equations mod \(p\) in the same way that we visualized solutions over the real numbers. Nonetheless, we can take the formulas that we derived using the geometry we discussed above (eg, the Elliptic Curve Addition Formula Theorem), and use the same formulas to make sense of elliptic curves mod \(p\). These formulas look very strange in isolation, but it is important to remember where they come from: they come from the same geometry involving secant and tangent lines that we discussed above! If you understand that geometry, you can do all of the same calculations “mod \(p\)” and derive the formulas that appear below.

Definition-Theorem Suppose \(y^2 = x^3 + ax + b\) is an integral Weierstrass equation which is nonsingular mod \(p\). The corresponding elliptic curve mod \(p\) is the set \(E\) of solutions mod \(p\) to the equation, together with an extra point at infinity called \(O\).

Suppose \(P \in E\). We define \(-P\) as follows:

Then \(-P\) is in fact an element of \(E\).

Moreover, suppose \(P, Q \in E\). We define \(P + Q\) as follows:

Then:

Let’s do an example. Consider again \(p = 7\) and the Weierstrass equation \(y^2 = x^3 + 17 \equiv x^3 + 3 \pmod{7}\). We’ve already seen that \(P = (1, 2)\) is a solution to this equation. You should verify for yourself that \(Q = (3, 4)\) is also a solution to this equation. Let’s think about computing \(P + Q\) in “two” ways (but, as you’ll see, they’re both really the same thing).

The first way is just to go through the above formulas carefully. Notice that \(P \neq Q\) and \(x_2 - x_1 = 3 - 1 = 2\) is invertible mod 7 because \(\gcd(2, 7) = 1\). Its inverse is 4 (which we can compute by eyeballing since the numbers are small enough in this case, but in general we would use the extended euclidean algorithm). Thus \[ \begin{aligned} \lambda &= (y_2 - y_1)(x_2 - x_1)^{-1} \bmod{p} \\ &= (4 - 2)(3 - 1)^{-1} \bmod{7} \\ &= 2 \cdot 4 \bmod{7} = 1. \end{aligned} \] Then \[ \begin{aligned} \nu &= y_1 - \lambda x_1 \bmod{p} \\ &= 2 - 1 \cdot 1 \bmod{7} = 1 \\ x_3 &= \lambda^2 - x_1 - x_2 \bmod{p} \\ &= 1^2 - 1 - 3 \bmod{7} = 4 \\ y_3 &= \lambda x_3 + \nu \bmod{p} \\ &= 1 \cdot 4 + 1 \bmod{7} = 5 \end{aligned} \] Thus \(R = (4, 5)\) and \(P + Q = -R = (4, -5 \bmod{7}) = (4, 2)\).

The second way (which, again, is really the same way!) is to remember the geometry that underlies these formulas and use that geometry to guide your calculations; you just have to remember to do your calculations “mod 7” instead. We’re trying to add two distinct points, so the first step is to find the line that passes through those points. We compute the slope of that line as rise-over-run, ie, as \((y_2 - y_1)/(x_2 - x_1)\) — but we have to do this calculation “mod 7,” so instead of dividing, we’ll multiply by a modular inverse. In other words, we really compute \[ (4 - 2)(3 - 1)^{-1} = 2 \cdot 2^{-1} \equiv 2 \cdot 4 = 8 \equiv 1 \pmod{7}. \] Notice that this is the same as the value of \(\lambda\) that we computed above. The next step is to use point-slope form to find the equation of the secant line: we now know it has slope 1, and it passes through \((1, 2)\), so its equation should be \(y - 2 = 1(x - 1)\), or \(y = x + 1\). Notice that this \(y\)-intercept matches what we computed for \(\nu\) above. We next want to intersect this secant line with the curve. We substitute \(y = x + 1\) into \(y^2 = x^3 + 3\) and get \[ \begin{aligned} (x+1)^2 &= x^3 + 3 \\ x^2 + 2x + 1 &= x^3 + 3 \\ x^3 - x^2 - 2x + 2 &= 0 \end{aligned} \] We now need to find the roots of this cubic mod 7. We know that 1 and 3 are roots, so \((x-1)(x-3) = x^2 - 4x + 3\) must divide this cubic.

Exercise Do polynomial long division “mod 7” to divide \(x^3 - x^2 - 2x + 2\) by \(x^2 - 4x + 3\). You should find a quotient of \(x-4\) with remainder 0.

The fact that the quotient is \(x-4\) tells us that the third point of intersection of the secant line with the curve has \(x\)-coordinate 4, so its \(y\)-coordinate must be \(y = x + 1 = 4 + 1 = 5\). This gives us the same point \(R = (4, 5)\) that we found earlier, and then we “reflect” across the \(x\)-axis to get \[ P + Q = (1, 2) + (3, 4) = (4, -5 \bmod{7}) = (4, 2), \] just as we did before.

Exercise Consider \(p = 7\) and \(y^2 = x^3 + 17\) again. Compute the following:

  1. \((1, 2) + (1, 2)\).
  2. \((1, 2) + (1, 5)\).
  3. \((2, 2) + (3, 3)\).
  4. \((2, 2) + (2, 2)\).
  5. \((2, 2) + O\).
  6. \(O + O\).

Again, we can quickly compute large multiples of a point using the same “binary multiplication” idea.

Exercise Consider \(p = 7\) and \(y^2 = x^3 + 17\) again. Let \(P = (1, 2)\) and use “binary multiplication” to compute \(11P\).

We can also make the following definition of order.

Definition Suppose \(P\) is a point on an elliptic curve \(E\) mod \(p\). The order of \(P\), denoted \(\mathrm{ord}_E(P)\), is the smallest positive integer \(n\) such that \(nP = O\).

Unlike in the real case, we don’t need to worry about infinite order anymore:

Group Theory Exercise Explain why, if \(E\) is an elliptic curve mod \(p\), then it must be that \(\mathrm{ord}_E(P)\) is finite for any \(E \in P\).

We also have the analogs of the First and Second Lemmas about Orders in this case:

First Lemma About Orders for Elliptic Curves Let \(E\) be an elliptic curve mod \(p\) and suppose \(P \in E\). If \(mP = O\), then \(\mathrm{ord}_E(P)\) divides \(m\).

Second Lemma About Orders for Elliptic Curves Let \(E\) be an elliptic curve mod \(p\) and suppose \(P \in E\). Let \(k = \mathrm{ord}_E(P)\). Then \(iP \equiv jP \pmod{p}\) if and only if \(i \equiv j \pmod{k}\). In particular, the points \(O, P, 2P, 3P, \dotsc, (k-1)P\) are all incongruent mod \(p\).

If you haven’t seen any group theory, you can just take these lemmas for granted. But if you have studied some group theory, I highly encourage you to work through the following exercise:

Group Theory Exercise Prove the First and Second Lemmas about Orders for elliptic curves.

Here are some concrete examples:

Exercise Consider \(p = 5\) and \(y^2 = x^3 + 17\). Verify that the following points are on the elliptic curve, and then calculate their orders.

  1. \((2, 0)\)
  2. \((3, 2)\)
  3. \((3, 3)\)
  4. \((4, 1)\)

Exercise Consider \(p = 7\) and \(y^2 = x^3 + 17\). Show that \(P = (1, 2)\) has order 13.

SageCell Here is some Sage code to create an elliptic curve mod \(p\). Specifically, this code sets E to be the elliptic curve mod \(p = 7\) corresponding to the equation \(y^2 = x^3 + 17 = x^3 + 0 \cdot x + 17\). The GF(7) is what tells Sage that you want to work mod 7. We then call points() to see a complete list of all the (congruence classes of) points on the elliptic curve. Hit “Run,” and then read below to understand more about the output:

Again, you will see points in projective coordinates when you do this. For example, we saw above that \((1, 2)\) is a solution to \(y^2 = x^3 + 17\) mod 7, and Sage lists (1 : 2 : 1), which refers to the same point.

If you already know a point \((x, y)\) on the elliptic curve, you can tell Sage to treat it as a point on the elliptic curve by prefixing it with the name of the curve. The following code defines P to be the point \((1, 2)\).
You can now easily get Sage to perform addition on an elliptic curve for you! The following computes \((1, 2) + (3, 4)\), the same calculation we did earlier. Hit “Run” to make sure that Sage agrees that the answer is the point \((4, 2)\).
We can also get Sage to calculate orders for us, as follows:
SageCell Earlier, I said that “it doesn’t really make sense to visualize (congruence classes of) solutions to Weierstrass equations mod \(p\) in the same way that we visualized solutions over the real numbers.” You could make a plot of all of the points on the curve, but you get very weird pictures: it doesn’t look anything like a “curve” and it doesn’t make any sense to draw secant or tangent lines this. You can get Sage to make these types of pictures for you as follows, but I don’t recommend thinking too much about these pictures. They’re next to meaningless…

Having developed all of this theory, we can now state the basic problem that underlies elliptic curve cryptography. You should compare it with the discrete logarithm problem that we discussed above:

Elliptic Curve Discrete Logarithm Problem Suppose you are given a prime \(p\), an elliptic curve \(E\) mod \(p\), and a point \(P \in E\). Suppose further that \(Q \in E\) is known to be a multiple of \(P\). Find the discrete logarithm base \(P\) of \(Q\), ie, the unique integer \(k\) such that \(0 \leq k < \mathrm{ord}_E(P)\) such that \(Q = mP\).

The naive method for doing this is to just try all the values of \(k\) starting from \(k = 0\) all the way up to \(k = \mathrm{ord}_E(P) - 1\), but if \(\mathrm{ord}_E(P)\) is very large, this will be very slow! There are slightly faster methods than this that work in general. There are also substantially faster methods that work in special cases. But we do not know of anything that is substantially faster in general, which means that by choosing \(p, E, P\) judiciously, we can make the Elliptic Curve Discrete Logarithm Problem intractable for an adversary. This intractability can then be used for cryptographic purposes, in much the same way that the intractibility of the usual Discrete Logarithm Problem can be.

The National Institute of Standards and Technology (NIST) just published (on February 3rd, 2023) a document describing which elliptic curves are currently thought to be safe to use for cryptography; you can browse this document here.

SageCell Sage can find discrete logarithms for elliptic curves as well. Here is the syntax for finding the integer \(m\) such that \((5, 3) = m(1, 2)\).

4.11. Elliptic Curve Diffie-Hellman

Let’s start with the elliptic curve variant of the Diffie-Hellman key exchange. Alice and Bob publicly agree to fix a prime \(p\), an elliptic curve \(E\) mod \(p\) (specified by integers \(a, b\) such that the Weierstrass equation \(y^2 = x^3 + ax + b\) is nonsingular mod \(p\)), and a point \(P \in E\). To ensure security, we need for \(\mathrm{ord}_P(E)\) to be large. The data \((p, E, P)\) is all shared publicly.

Alice then chooses a secret integer \(0 \leq k_a < \mathrm{ord}_E(P)\) and sends Bob \(Q_a = k_a P\). She can compute this value quickly using binary multiplication. Bob similarly chooses a secret integer \(0 \leq k_b < \mathrm{ord}_E(P)\) and sends Alice \(Q_b = k_b P\). Alice computes \(R = k_a Q_b\), and Bob computes \(R = k_b Q_a \bmod{p}\). The two values of \(R\) that Alice and Bob compute are the same, because \[ k_aQ_b \equiv k_a(k_bP) = k_ak_bP = k_b(k_aP) = k_bQ_a. \] Thus Alice and Bob now share a secret point \(R\) on the elliptic curve.

Exercise Suppose Alice and Bob publicly agree to use the elliptic curve \(y^2 = x^3 + 17\) mod \(p = 7\) and the point \(P = (1, 2)\).

  1. Suppose Alice picks the number \(k_a = 4\). What is the message \(Q_a\) that she sends Bob?
  2. Suppose Alice receivces the point \(Q_b = (5, 3)\) from Bob. What is her shared secret with Bob?

Exercise Explain why the presumed difficulty of finding elliptic curve discrete logarithms implies the security of the elliptic curve Diffie-Hellman key exchange.

Exercise Suppose Alice and Bob publicly agree to use the elliptic curve \(y^2 = x^3 + 17\) mod \(p = 7\) and the point \(P = (1, 2)\). This point has order 13, which is too small to be secure. Suppose Eve intercepts Alice and Bob’s message: she sees that Alice sent Bob \(Q_a = (3, 3)\) and that Bob sent Alice \(Q_b = (6, 4)\). What is Alice and Bob’s shared secret?

Exercise Do one (or both!) of the following:

  1. Play the role of Alice and Bob: Pick a friend in the class and perform an elliptic curve Diffie-Hellman key exchange with them. Do your communications in our class stream on Zulip so that everyone can see the values of \(p, E, P, Q_a, Q_b\) that you share between the two of you, but make sure to keep \(a\) and \(b\) secret.
  2. Play the role of Eve: Watch for some pair of classmates performing elliptic curve Diffie-Hellman on Zulip, and then see if you can figure out their shared secret!

Sage Exercise Write some code that for performing an elliptic curve Diffie-Hellman key exchange.

4.12. Interlude: Quadratic Residues

A familiar feature of the real numbers is that some numbers do not have square roots (namely, the negatives). The same thing happens when you work mod an integer. For example, let \(n = 5\). We know that integer is congruent to 0, 1, 2, 3, or 4 mod 5. This means that any square must be congruent to \(0^2 = 0, 1^2 = 1, 2^2 = 4, 3^2 \equiv 4 \pmod{5}\), or \(4^2 \equiv 1 \pmod{5}\). In other words, only 0, 1, or 4 have square roots mod 5 — and 2 and 3 do not!

Definition Fix a positive integer \(n\). We say that an integer \(a\) is a quadratic residue mod \(n\) if it has a square root mod \(n\), ie, if there exists an integer \(x\) such that \(x^2 \equiv a \pmod{n}\).

Exercise Find all quadratic residues mod the following integers:

  1. \(n = 3\)
  2. \(n = 7\)
  3. \(n = 11\)

We’ll see below that it will be useful to quickly determine whether an integer \(a\) is a quadratic residue mod a prime \(p \geq 3\). It turns out that there is a good way to do this! Let us first introduce the following notation:

Definition Let \(p \geq 3\) be prime. For any integer \(a\), define the Legendre symbol \((a/p)\) by \[ \left( \frac{a}{p} \right) = \begin{cases} 0 & \text{if } a \equiv 0 \pmod{p} \\ 1 & \text{if $a \not\equiv 0 \pmod{p}$ and $a$ is a quadratic residue mod $p$} \\ -1 & \text{if $a \not\equiv 0 \pmod{p}$ and $a$ is not a quadratic residue mod $p$} \end{cases} \]

For example, we saw above that 4 is a quadratic residue mod 5, so \[ \left( \frac{4}{5} \right) = 1 \] and we saw that 2 is not a quadratic residue mod 5, so \[ \left( \frac{2}{5} \right) = -1. \] We can now rephrase our goal: we would like a quick way of computing Legendre symbols. This is provided to us by combining binary exponentiation with the following:

Euler’s Criterion Let \(p \geq 3\) be prime. For any integer \(a\), \[ \left( \frac{a}{p} \right) \equiv a^{(p-1)/2} \pmod{p}. \]

Proof. There are three cases to consider:

  1. \(a \equiv 0 \pmod{p}\);
  2. \(a \not\equiv 0 \pmod{p}\) and \(a\) is a quadratic residue mod \(p\); and
  3. \(a \not\equiv 0 \pmod{p}\) and \(a\) is not a quadratic residue mod \(p\).

In case (1), the statement we’re trying to prove is clear since both sides of the congruence are 0 mod \(p\). In case (2), there exists an integer \(x\) such that \(x^2 \equiv a \pmod{p}\). Since \(p\) does not divide \(a\), it also does not divide \(x^2\), so it cannot divide \(x\) either by Euclid’s Lemma. Thus \(\gcd(x, p) = 1\), and Euler’s Theorem implies that \[ a^{(p-1)/2} \equiv (x^2)^{(p-1)/2} = x^{p-1} = x^{\phi(p)} \equiv 1 = \left( \frac{a}{p} \right) \pmod{p}. \]

Now consider case (3). The idea is to calculate \((p-1)!\) mod \(p\) in two different ways, by “pairing off” the numbers in two different ways. The first way is to pair them off into pairs \(x, y\) where \(xy \equiv 1 \pmod{p}\). There are 2 “degenerate” pairs where \(x = y\), namely, \(x = y = 1\) and \(x = y = p-1\) (cf. Lemma 4.4.1), but the remaining numbers \(2, \dotsc, p-2\) are all paired off with a different number in the same range and the product of each of those “nondegenerate” pairs is 1, so the Modular Arithmetic Theorem implies that \[ (p-1)! = 1 \cdot 2 \cdot 3 \cdots (p-3) (p-2) (p-1) \equiv 1 \cdot (p-1) \equiv -1 \pmod{p}. \] (This fact is sometimes called Wilson’s Theorem.) On the other hand, we can also pair the numbers off into pairs \(x, y\) where \(xy \equiv a \pmod{p}\). Since we are in case (3) and \(a\) is not a quadratic residue mod \(p\), we know that there is no solution to this congruence where \(x = y\), ie, there are no “degenerate” pairs in this case. There are \((p-1)/2\) pairs, and the product of each pair is \(a\), so the Modular Arithmetic Theorem again guarantees that \[ (p-1)! = 1 \cdot 2 \cdots (p-2) \cdot (p-1) \equiv a^{(p-1)/2} \equiv{p}. \] Thus we have \[ a^{(p-1)/2} \equiv (p-1)! \equiv -1 = \left( \frac{a}{p} \right) \pmod{p} \] and we are done. \(\Box\)

Proof Exercise Here is a fact we tacitly made use of twice in the above proof. Suppose \(p\) is prime and \(a\) is an integer that is not divisible by \(p\). For any integer \(1 \leq x \leq p-1\), there is a unique integer \(1 \leq y \leq p-1\) such that \(xy \equiv a \pmod{p}\).

  1. Prove this fact.
  2. Find the two places in the above proof where this fact was used.

Euler’s Criterion means that we have an efficient algorithm for determining whether something is a quadratic residue: we simply use binary exponentiation to compute \(a^{(p-1)/2} \bmod{p}\) and we can read off the answer! For example, suppose we want to know if \(a = 37\) is a quadratic residue mod \(p = 97\). We have \((p-1)/2 = 96/2 = 48\), so we compute \(a^{(p-1)/2} = 37^{48} \bmod{97}\) using binary exponentiation, and we find that it is \(96 \equiv -1 \pmod{97}\). Euler’s Criterion says that \[ \left( \frac{37}{97} \right) \equiv 37^{(97-1)/2} = 37^{48} \equiv -1 \pmod{97}, \] which means that 37 is not a quadratic residue mod 97.

Exercise Use Euler’s Criterion to determine whether or not the following integers \(a\) are quadratic residues mod \(p = 19\).

  1. \(a = 3\)
  2. \(a = 5\)
  3. \(a = 11\)

Harder Proof Exercise Suppose \(p \geq 3\) is prime.

  1. Show that there are exactly \((p+1)/2\) quadratic residues mod \(p\).
  2. Conclude that, if \(p\) is large, then the probability that a randomly chosen integer in \([0, p)\) happens to be a quadratic residue is approximately 50%.
SageCell Sage can compute Legendre symbols using the kronecker_symbol function:
When the Legendre symbol is not \(-1\), Sage can also compute a modular square root:

Random Exercise What does Sage output for Mod(k, n).sqrt() when \(k\) is not a quadratic residue mod \(n\)? If you know what the words “splitting field” and “finite field” mean, can you explain this behavior in terms of these words?

There is a lot more that can be said about quadratic residues, though this will be roughly enough for our purposes. If you are interested in reading more, you should look up the Tonelli-Shanks algorithm for computing square roots mod \(p\). You might also read more about Jacobi symbols, Kronecker symbols, and quadratic reciprocity.

4.13. Elliptic Curve Elgamal

There is also a variant of the Elgamal cryptosystem using elliptic curves that can be used to exchange messages, but there is a nontrivial encoding step. To make Elgamal work with elliptic curves, we first need a way to encode a plaintext message as a point on an elliptic curve \(E\) mod \(p\).

There is a probabilistic algorithm for doing this. The rough idea is that we can try to encode plaintext as the \(x\)-coordinate of a point, but note that not every integer will occur as the \(x\)-coordinate of a point on an elliptic curve mod \(p\)! Specifically, if \(E\) is given by \(y^2 = x^3 + ax + b\) and if \(P = (x, y)\) is a point on the curve, then the \(x\)-coordinate must have the property that \(x^3 + ax + b\) is a quadratic residue mod \(p\).

Entire Process

Let us start by describing the Elgamal process in its entirety and in the abstract.

Suppose that Bob would like to be able to receive messages of length \(N\). Bob will fix a positive integer \(s\). We will see that, the larger that Bob chooses this integer, the higher the probability that encoding will succeed. Bob will then choose a prime \(p > s26^N\), and an elliptic curve \(E\) mod \(p\) (defined by integers \(a, b\) such that the integral Weierstrass equation \(y^2 = x^3 + ax + b\) is nonsingular mod \(p\)), and a point \(P \in E\). He computes \(\mathrm{ord}_E(P)\). Then Bob chooses a secret integer \(0 \leq k < \mathrm{ord}_E(P)\) to serve as his private key. He computes \(Q = kP\), and this value is part of his public key. In other words, Bob will share all of the data \((s, E, P, \mathrm{ord}_E(P), Q)\) publicly, and keep only the integer \(k\) secret.

Suppose now that Alice wants to send Bob a message. She first converts her message into an integer \(m\) using the same base 26 idea we used for RSA. She will then iterate through values of \(r = 0, 1, 2, \cdots, s-1\) until she finds the first value of \(x = sm + r\) such that \[ \left( \frac{x^3 + ax + b}{p} \right) \neq -1. \] Note that that the maximum possible value of \(m\) is \(26^N - 1\), so \[ x = sm + r < s(26^N-1) + s = s26^N < p, \] since Bob chose \(p\) to be larger than \(s26^N\). There is a roughly 1/2 chance that an integer in \([0, p)\) is not a quadratic residue mod \(p\), and here we are iterating through \(s\) integers in the range \([0, p)\), so there is a \(1/2^s\) chance that \(x^3 + ax + b\) is not a quadratic residue for any of the \(s\) possible values of \(x = sm + r\). If none of the \(s\) integers are quadratic residues, encoding fails — but if Bob chose \(s\) to be even moderately large, encoding failure is very unlikely! If encoding does fail, Alice can just modify her message slightly (rephrase slightly? add a nonsense letter?) and try encoding again. Once Alice is able to find a value of \(x\) such that \(x^3 + ax + b\) is a quadratic residue mod \(p\), then there is a integer \(y\) such that \(y^2 \equiv x^3 + ax + b \pmod{p}\), so the point \(M = (x, y)\) is on \(E\). This will be the encoding of her plaintext message.

This is not yet the ciphertext, but at this point she can encrypt the encoded message using a process very similar to the Elgamal cryptosystem we discussed earlier. Alice chooses an “ephemeral key” \(h\) such that \(0 \leq h < \mathrm{ord}_E(P)\). She computes \(S = hQ\), \(R_1 = hP\), and \(R_2 = M + S\). The pair \((R_1, R_2)\) is the ciphertext that she sends to Bob.

To decrypt the ciphertext \((R_1, R_2)\), Bob uses his private key \(k\) to compute \(S = kR_1\). Observe that \[ kR_1 = k(hP) = khP = h(kP) = hQ, \] so Bob has found the same value of \(S\) that Alice had, even though he does not know the value of the ephemeral key \(h\). He can then compute \(-S\) by negating the \(y\)-coordinate, and he then calculates \[ R_2 - S = R_2 + (-S) = (M + S) + (-S) = M + (S + (-S)) = M + O = M. \] He has thus recovered Alice’s encoded plaintext!

Finally, Bob just needs to decode \(M\). If \(M = (x, y)\), he can extract the first coordinate \(x\). The quotient when he divides this by \(s\) is the integer \(m\) that represents the message in base 26, so he then finishes off by converting back to text using the same process we used for RSA above.

Whew!

Encoding and Decoding

Here are some exercises to help you understand the above process by breaking it down and working with some pieces. First up are the encoding and decoding parts of the process (careful: not the encryption and decryption yet).

Exercise Suppose Bob’s public key has \(s = 2, p = 97, a = 31\), and \(b = 20\). The elliptic curve \(E\) is then the one given by \(y^2 = x^3 + 31x + 20\) mod \(p = 97\).

  1. What is the encoding of the plaintext message B? Follow the process above to find the corresponding point \(M \in E\).
  2. Show that encoding fails for the letter K.
  3. Follow the process described above to find the plaintext message that results from decoding the point \((25, 30) \in E\).

Exercise Suppose Bob’s public key has \(p = 9393107\) and \(s = 3\).

  1. What is the maximum length for messages that Bob can receive?
  2. What is the probability of encoding failure?

Exercise Bob would like to be able to receive messages of length \(N = 50\) with an encoding failure rate of at most \(0.1%\). What is the smallest prime \(p\) that he can use for his public key?

Hint. You should probably use Sage to help you do this calculation, and if you do, you might find it helpful to use the function next_prime, which tells you the smallest prime number greater than the input.

SageCell Here is a SageCell that implements the encoding step described above. Note that it will output the point \(M \in E\) with three coordinates where the third coordinate will always be 1 (for technical reasons); this is the same as what you observed in the previous elliptic curve SageCells, except that here commas are used to separate the three numbers instead of colons.
Here is another SageCell that implements the decoding step.

Exercise Describe in your own words what goes wrong if Alice tries to encode a message that is too long (based on what Bob chose for his values of \(p\) and \(s\)). You might find it helpful to experiment with the above SageCells.

Encryption and Decryption

Here is an example of the encryption and decryption process in a small example and using Sage. I encourage you to follow along and type things into a SageCell yourself as you read through this example (or you can do the calculations by hand, though this might get a little tiring even in this small example).

When generating his elliptic curve Elgamal public key, Bob chooses the elliptic curve \(E\) defined by \(y^2 = x^3 + 3x + 4\) mod \(p = 7\) and the point \(P = (5, 5) \in E\).

E = EllipticCurve(GF(7), [3, 4])
P = E(5, 5)

By running P.order(), we find that \(\mathrm{ord}_E(P) = 10\). Suppose Bob chooses the secret integer \(k = 3\). By typing 3*P into Sage, he finds that \(Q = kP = 3 \cdot (5, 5) = (2, 5)\). All parts of this calculation except the value of \(k = 3\) are made public; \(k\) is his private decryption key.

Now suppose Alice wants to send Bob a message. She sets up her Sage session by pulling the following information from Bob’s public key.

E = EllipticCurve(GF(7), [3, 4])
P = E(5, 5)
order = 10
Q = E(2, 5)

Suppose that, following the encryption process described above, her encoded message is the point \(M = (0, 5)\). She chooses an ephemeral key between \(0\) and \(\mathrm{ord}_E(P) = 10\), say \(h = 4\). She must keep this value of \(h\) secret. She computes \(R_1 = hP\) by typing \(4 * P\) into Sage and finds \(R_1 = (0, 2)\). She then computes \(R_2 = M + S = M + hQ\) by typing E(0, 5) + 4*Q into Sage and finds \(R_2 = (1, 6)\). The pair \((R_1, R_2) = ((0, 2), (1, 6))\) is the ciphertext that she sends to Bob.

Let’s now go backwards and check that Bob is able to recover Alice’s message. He computes \(M = R_2 - kR_1\) by typing E(1, 6) - 3*E(0, 2) and finds \(M = (0, 5)\), which was Alice’s encoded message!

Exercise When generating his elliptic curve Elgamal public key, Bob chooses the elliptic curve \(E\) defined by \(y^2 = x^3 - 3x + 3\) mod \(p = 11\) and the point \(P = (10, 7) \in E\).

  1. What is \(\mathrm{ord}_E(P)\)?
  2. Suppose Bob chooses \(k = 4\). What is the value of \(Q = kP\)?
  3. Alice encodes some message to produce the point \(M = (1, 1) \in E\). She also generates the ephemeral key \(h = 2\). What is the ciphertext \((R_1, R_2)\) that she sends to Bob?
  4. Check that if Bob decrypts the ciphertext \((R_1, R_2)\) that he receives from Alice, he does in fact recover \(M = (1, 1)\).
  5. Bob receives the message \(((6, 5), (10, 4))\) from Alice. What is the encoded plaintext point \(M \in E\)?

Exercise Suppose Bob’s elliptic curve Elgamal public key is as follows: \[ \begin{aligned} s &= 10 \\ p &= 965840826414842165347088832781 \\ E &: y^2 = x^3 + 2x + 1 \\ P &= (537016992844572701251197286080, 809430503509725487398100177667) \\ \mathrm{ord}_E(P) &= 965840826414840286830465288570 \\ Q &= (636209278006637725237624425202, 310653932799215077905485882454) \end{aligned} \]

  1. What is the probability that encoding fails?
  2. Alice wants to send Bob the message I have turned into a cat. What is the ciphertext she sends Bob?

Exercise Suppose Bob’s elliptic curve Elgamal public key is as follows: \[ \begin{aligned} s &= 10 \\ p &= 884300930387974803998998733399 \\ E &: y^2 = x^3 + 2x + 1 \\ P &= (361652577940189312498172547614, 514746227051815551959384860286) \\ \mathrm{ord}_E(P) &= 884300930387974691696035383315 \\ Q &= (882188314538809138823874338820, 772608417660306453415686049932) \end{aligned} \] His private key is \[ k = 587487808581088164390024475576. \] He receives the following ciphertext \((R_1, R_2)\) from Alice. \[ \begin{aligned} R_1 &= (779503153810704949581662586128, 391600280839951295424353453750) \\ R_2 &= (590367533102870068877884575138, 460366500620283882415563572675) \end{aligned} \] What is the plaintext (as text, rather than as an encoded point)?

Exercise Suppose Bob’s elliptic curve Elgamal public key is as follows: \[ \begin{aligned} s &= 10 \\ p &= 34159136004208027161199 \\ E &: y^2 = x^3 + 2x + 1 \\ P &= (5205000772914715415725, 20236812690413582503099 \\ \mathrm{ord}_E(P) &= 34159136004127088328131 \\ Q &= (25509677592482725856096, 823756708348136845691) \end{aligned} \] Unfortunately, his public key is not large enough to be secure! What is his private decryption key \(k\)?

SageCell Here is a SageCell that implements Elgamal encryption. When you hit “Run,” you’ll see the following input boxes:

The SageCell will then compute the corresponding ciphertext pair \((R_1, R_2)\) that Alice sends to Bob and display it in the Output box. Again, each point \(R_1, R_2\) will be represented by three coordinates; the point \(O\) will be represented by (0, 1, 0), and a point \((x, y)\) will be represented by (x, y, 1). Again, this is the same format for points that you are familiar with from the earlier elliptic curve SageCells, except that we use commas instead of colons to separate the numbers.

Note that the encryption generates a random ephemeral key, so you’ll see different ciphertexts every time you run this SageCell even if all of the input fields are exactly the same!

The next SageCell implements decryption. You’ll see a lot of the same fields as above, except now:

The Output is the corresponding plaintext.

Exercise Do one (or more!) of the following:

  1. Play the role of Bob: Choose an elliptic curve Elgamal public key for yourself and post it to our class stream on Zulip.
  2. Play the role of Alice: Watch for a classmate who has posted their elliptic curve Elgamal public key to Zulip, and send them a secret message.
  3. Play the role of Eve: Watch for an elliptic curve Elgamal ciphertext being exchanged by some pair of your classmates on Zulip, and see if you can figure out what the plaintext is.