The simplest difficult task

Privacy & Cookies: This site uses cookies. By continuing to use this website, you agree to their use.
To find out more, including how to control cookies, see here: Cookie Policy

Most of us have heard of the RSA algorithm and how it’s very useful for cryptography. In order to crack it we need to be able to factor large numbers, but experience has told us that the problem of factorisation, while very simple to describe, is very difficult to do in practice. Yet there exists a problem that, though it might sound even simpler, is just as difficult.

Basic arithmetic

We all know how to add or multiply two numbers. In particular, we can multiply a number by itself, which we call
`squaring’. In other words, if I give you a number, say 127, then I’m sure you will be able to tell me, possibly after some time, that its square is 16,129. Piece of cake.

But consider now the inverse problem: suppose I gave you the number 33,124. Can you tell me what number this is the square of? In other words, what is the square root of 33,124? The answer, of course, is $\sqrt{33,124}$ (or $-\sqrt{33,124}$, but we’ll get back to this point later). However, this feels a bit like cheating, so let’s suppose that I want a more explicit answer, without the square root. This might not make much sense in general—for example, what answer more explicit than $\sqrt{2}$ could I possibly expect? So let’s make a deal: if I ask you for a square root of a number, I will make sure that the answer is an integer $n$. Now, how to approach this problem?

A rather naive method would be to just take the numbers below, say, 1000 and square them all to look for a hit. This will, of course, take a horrendous amount of time, especially with larger numbers. But consider the following method: we first try taking some number that we expect to be about the size of $n$. Let’s start with 200. We find that $200^2$ is larger than 33,124. So this is a miss—our square root $n$ is not 200. But we get to know a bit more: $n$ is strictly less than 200. So let’s try a smaller number, say 170. Then $170^2<33\text{,}124$, so $n$ is larger than $170$. We can now try some number between $170$ and $200$ to find some tighter bounds for $n$. After five or six more such guesses, we will finally find out that $n=182$. Maybe this isn’t the most effective method, but it’s still better than trying all $181$ smaller numbers!

At this point, let’s note a very important thing: to find the solution we made use of the structure of the integers, which was not required in the statement of the problem. To be more precise, we used the ordering of the integers in order to learn something about $n$ given only $n^2$. This suggests that the problem might become harder if we consider it in a system that doesn’t have this structure.

Modular arithmetic

A simple example of a system that has multiplication (and addition, for that matter) is the set of integers modulo some natural number $N>1$. In modular arithmetic, we say that every two integers $a, b$ are the same if they differ by a multiple of $N$. More precisely, we say that $a$ and $b$ are congruent modulo $N$, written $a\equiv b\pmod{N\,}$, if and only if the number $a-b$ is a (possibly negative) multiple of $N$. We can identify numbers modulo $N$ with the possible remainders when dividing by $N$, ie with the numbers $\{0,1,\dots,N-1\}$. Now we can state the problem we wish to consider: given the integers $y$ and $N$, find an integer $x$ such that $x^2\equiv y\pmod{N\,}$.

For example, let’s say that $y=2$ and $N=7$. Then you can see that $3^2\equiv 2\pmod{7}$, so 3 is a valid, though not unique, answer to our problem. On the other hand, if I gave you $y=2$ and $N=5$, you will eventually realise that there is no solution. Like before, I won’t give you such numbers. Although the question of determining the existence of square roots is very interesting in itself, here we will restrict ourselves to finding the square roots under the assumption that they exist.

As with many things in mathematics, this problem simplifies quite a bit when we consider prime numbers, so let’s assume for now that $N$ is a prime number $p$. If $p=2$, then every number is its own square, which is a rather boring case, so we will suppose that $p$ is odd.

We only know that $y\equiv x^{2}$ modulo $p$, and we somehow want to extract the value of $x$ from it, so we want to get rid of the square. We can try exponentiating $y$ further. Since we don’t know how to take arbitrary powers of numbers modulo $p$, the exponent has to be an integer. This wouldn’t work if we were solving $y=x^{2}$ in the integers: $y^{k}$ will always be bigger than $x$ for $k>1$. But in modular arithmetic we have at least one tool that makes this idea feasible: Fermat’s little theorem, which states that $x^{p}\equiv x\pmod p$. We would therefore like to try and raise $y$ to the power $p/2$, but sadly $p/2$ is not an integer. The closest integers are $(p-1)/2$ and $(p+1)/2$, but taking $y$ to these powers gives us

$$y^{(p-1)/2}\equiv (x^{2})^{(p-1)/2}\equiv x^{p-1}\equiv 1\pmod p,$$
$$y^{(p+1)/2}\equiv (x^{2})^{(p+1)/2}\equiv x^{p+1}\equiv x^{p-1}\cdot x^{2}\equiv x^{2}\equiv y\pmod p.$$
This doesn’t seem to be of much help… but wait! Since $y^{(p+1)/2}$ is $y$, then $y^{(p+1)/4}$ squared will be $y$—provided that $(p+1)/4$ is an integer, which is equivalent to saying that $p+1\equiv 0\pmod 4$, or $p\equiv 3\pmod 4$. Moreover, this gives rise to a rather fast algorithm—the (possibly large) exponent $(p+1)/4$ might make you think that we are bound to make $(p+1)/4$ multiplications, but thankfully modular exponentiation can be made very effective using so-called repeated squaring. So we have figured out a way to find square roots in, essentially, half of the cases! Is there a way to find square roots in the remaining half: modulo primes $p\equiv 1\pmod 4$?

Indeed there is! A beautiful algorithm was discovered sort-of independently by Alberto Tonelli in 1891 and Daniel Shanks

in 1973, with the explanation that Shanks’ “tardiness in learning of these historical references was because [he] had lent Volume 1 of Dickson’s History [of the Theory of Numbers] to a friend and it was never returned”. The algorithm lets us find square roots modulo primes $p$ that are equal to 1 modulo 4 almost as quickly as the one described above. It has one drawback though: in order to use it, we need to find a number that is not a perfect square modulo $p$. It might sound easy enough: it can be shown that half of the numbers indivisible by $p$ are not squares, which suggests that a randomised search could be efficient (testing whether a number is a square modulo a prime can be done quickly using a concept called Euler’s criterion). Trial and error is the best nonrandom (ie deterministic) algorithm we have, so its computation time depends on the size of the smallest non-square. Very surprisingly, the only useful bounds on it have to be proven under the assumption of very complicated number-theoretic conjectures like the generalised Riemann hypothesis! Given that, we won’t pursue this problem further, but we highly recommend that interested readers look up the Tonelli–Shanks algorithm.

Factorisation

There is certainly a lot more to be said about square roots modulo prime numbers, but given that we have already found some rather efficient algorithms, we will now move on to finding square roots modulo composite (non-prime) numbers.

First, let’s try working with a prime power, say $N=p^e$. There is a very useful result known as Hensel’s lemma which lets us “lift” a root of a polynomial in $p^e$ to a root in $p^{e+1}$. The idea is the following: if we know that $x^{2}\equiv y\pmod{p^e}$, we can write $x^{2}=y+ap^e$. Now we consider numbers of the form $x+bp^e$ and we hope that one of them will give us a root in $p^{e+1}$. If we square them, we get $x^{2}+2bxp^e+b^{2}p^{2e}\equiv y+(a+2bx)p^e\pmod{p^{e+1}}$. Now it’s a matter of choosing $b$ such that $a+2bx$ is divisible by $p$. This will give us a desired solution as long as $p$ does not divide $y$ and $p\neq 2$. It is a rather instructive exercise to consider what happens in the remaining cases.

Things get a lot more interesting when $N$ has more prime factors, say $N=p_1^{e_1}… p_k^{e_k}$. First, using the above method, we can find square roots $x_i$ of $y$ modulo $p_i^{e_i}$ for each $i$. A theorem evocatively known as the Chinese remainder theorem then states that there is a number $x$ satisfying, for all $i$, $x\equiv x_i\pmod{p_i^{e_i}}$. If we look at $x^{2}$, we find, for each $i$,
\begin{align*}
x^{2}\equiv x_i^{2}\equiv y\pmod{p_i^{e_i}},
\end{align*}
from which it follows that $x^{2}\equiv y\pmod{N\,}$. This looks nice and all, but note that we have used, in a very essential way, the factorisation of $N$, which, as we know, is a very difficult problem. Maybe there is a way to find square roots modulo $N$ without needing to factor $N$?

And here is the point we’ve been building towards: finding square roots modulo composite numbers is just as difficult as factorisation. To see why this is true, we need to find a way of finding nontrivial factors of $N$ provided an algorithm for finding square roots modulo $N$. First, we may assume that $N$ is odd and is not a perfect power, otherwise factoring it is moderately easy. If this holds, then we can write $N$ as a product $PQ$ of two relatively prime odd numbers (two numbers that have no common factors). Now suppose that $y\not\equiv 0\pmod{N\,}$ has a square root $x$ (we don’t care what this square root is, we just assume it exists). If $y$ and $N$ have a common factor, then this common factor will be a nontrivial divisor of $N$ and we have factored $N$. Now assume that $y, N$ are relatively prime. Clearly, $-x$ is also a square root of $y$, but the cool bit is that there will be more square roots.

How can we use such additional square roots to factor $N$? Suppose $x_1,x_2$ are two roots of $y$ modulo $N$ such that $x_1\not\equiv x_2,x_1\not\equiv -x_2\pmod{N\,}$. Since $x_1^2\equiv y\equiv x_2^2\pmod{N\,}$, $N$ must divide $x_1^2-x_2^2=(x_1-x_2)(x_1+x_2)$. But, from our definition of $x_1$ and $x_2$, $N$ divides neither factor on the right, so $N$ and $x_1-x_2$ (as well as $N$ and $x_1 + x_2$) must have their highest common factor strictly between $1$ and $N$, which lets us find a nontrivial factor of $N$ using the Euclidean algorithm! This idea underlies all modern factorisation algorithms, including Shor’s quantum version.

Only one question remains: how can we use our square root finding algorithm to generate two distinct roots of a number? The answer is incredibly simple: take a number $y$ that we already know a square root of, and hope that the algorithm gives you a different root. We knew which square root we squared to get $y$, but the algorithm doesn’t know which of the (at least) four square roots we used. So by choosing a number randomly, squaring it and asking our algorithm for a square root, we have at least a 50% chance of finding another square root, thereby letting us factor $N$.

Cryptography

This discussion tells us that finding the square of a number is easy, but finding a square root modulo $N$ is hard, unless we know the factorisation of $N$. These observations were made by Rabin in 1979, when he realised that they could be used to construct an extremely simple public-key cryptographic system, nowadays known as the Rabin cryptosystem.

As is usual in cryptography, we will describe this technique using a scenario in which Alice wants to send a secret message to Bob, but this message has to pass through a public channel. First Bob chooses two large primes $p,q$ that are congruent to $3\pmod 4$. In practice, these numbers will be tens of digits long. He will keep these primes secret, but he will make $N=pq$ public. Afterwards, Alice takes her secret message and encodes it as a number $m$, which we assume is smaller than $N$ and relatively prime to it, and computes the remainder of $m^2$ when dividing by $N$, calling it $M$. $M$ is the encrypted message that can now be sent to Bob. Since Bob knows $p$ and $q$, he can find square roots of $M$ modulo these primes by computing $M^{(p+1)/4}\pmod p,M^{(q+1)/4}\pmod q$ (this is why we assumed that  $p,q$ are $3\pmod 4$), and finally, using the Chinese remainder theorem, we can combine these square roots to get a square root modulo $pq=N$. At this point we are almost done. The only remaining question is, how do we know that this square root is $m$? And here is the issue: we don’t.

Ambiguity

Earlier, we established that $M$ will have at least four distinct roots modulo $N$. Actually, we can show that it has precisely four roots. If $m$ were a message that could reasonably be distinguished from a random string of characters, eg if it were a sentence written in English and then encoded as Ascii, there would be a high chance that Bob will be able to figure out which of the roots is Alice’s message. However, in general, there is a very small, but unfortunately nonzero, chance that two of these roots will encode equally valid messages, for example if we are trying to send a large numerical value. Of course, Alice hasn’t provided enough information to let Bob unambiguously find out what the message is. But maybe Alice can provide some additional information that will enable Bob to identify the message? If so, can she do this in a way that will not make it easier to break the algorithm?

Let’s write the four roots of $M$ as $m$, $N-m$, $x$ and $N-x$, where $x\equiv -m\pmod p$ and $x\equiv m\pmod q$. We can easily remove half of the ambiguity: note that precisely one of $m$ and $p-m$ is odd; and precisely one of $x$ and $p-x$ is odd number. Therefore if Alice specifies“my message is odd”, Bob will be able to remove half of all the possibilities, and at the same time Alice won’t make it any easier to find the square roots. Specifying whether the message lies in $\{m,p-m\}$ or $\{x,p-x\}$ is more difficult. The simplest way to solve this problem is to use the Jacobi symbol $\big(\frac{a}{b}\big)$, where $a$ and $b$ are integers, and $b$ is positive and odd. We won’t need its most general definition, but we need to use the following facts: $\big(\frac{a}{b}\big)$ is $\pm 1$ if $a,b$ are relatively prime; for primes $p\equiv 3\pmod 4$, we have $\big(\frac{-a}{p}\big)=-\big(\frac{a}{p}\big)$ and $\big(\frac{a}{pq}\big)=\big(\frac{a}{p}\big)\big(\frac{a}{q}\big)$; if $a\equiv a’\pmod b$ then $\big(\frac{a}{b}\big)=\big(\frac{a’}{b}\big)$; and finally, $\big(\frac{a}{b}\big)$ can be efficiently calculated even if we can’t factor $a$ or $b$, thanks to so-called quadratic reciprocity. In particular, we find that

\begin{align*}
\bigg(\frac{m}{N}\bigg)=\bigg(\frac{m}{p}\bigg)\bigg(\frac{m}{q}\bigg)=\left(\bigg(-\frac{-m}{p}\bigg)\right)\left(-\bigg(\frac{-m}{q}\bigg)\right)=\bigg(\frac{-m}{p}\bigg)\bigg(\frac{-m}{q}\bigg)=\bigg(\frac{-m}{N}\bigg)=\bigg(\frac{N-m}{N}\bigg)
\end{align*}
and similarly $\big(\frac{x}{N}\big)=\big(\frac{N-x}{N}\big)$; but
\begin{align*}
\bigg(\frac{x}{N}\bigg)=\bigg(\frac{x}{p}\bigg)\bigg(\frac{x}{q}\bigg)=\bigg(\frac{-m}{p}\bigg)\bigg(\frac{m}{q}\bigg)=-\bigg(\frac{m}{p}\bigg)\bigg(\frac{m}{q}\bigg)=-\bigg(\frac{m}{N}\bigg).
\end{align*}

So Alice can specify in which of $\{m,p-m\}$ or $\{x,p-x\}$ her message lies using the value of $\big(\frac{m}{N}\big)$, it being different to that of $\big(\frac{x}{N}\big)$! And again, this won’t help anyone find the square roots.

Therefore, we can uniquely specify which is the correct square root out of four possibilities using precisely two bits of information.

Comparison with RSA

At the beginning, I intentionally made a not-so-precise statement that in order to crack RSA, we need to factor large numbers. This isn’t false, but it isn’t known to be true either—what we actually need is to be able to find the $e$-th roots modulo $N$; but in the case of RSA, the root is known to be unique. This is known as the RSA problem. As opposed to the above square root finding problem, the RSA problem is not known to be equivalent to factorising, so it is consistent with our current knowledge that the RSA problem might be solved without an efficient factorisation algorithm. Rabin’s

cryptosystem is known to be secure, provided we believe factorisation is hard. Beyond that, apart from the disambiguation of roots, Rabin’s cryptosystem is conceptually simpler to the RSA cryptosystem, since it only requires us to square numbers and find square roots. Also, encoding messages is about as simple as is conceivable, and the generation of public and private keys ($N$ and $p, q$ respectively) is very simple as well. In RSA, the generation of keys requires the further step of finding suitable exponents that we later use, and the encryption exponent is bound to be larger than $2$.

As for decryption, in RSA the decryption exponent can be pretty much any number between 3 and $(p-1)(q-1)$, so it is usually much larger than the exponents used in Rabin’s system. The fact that we have to do two exponentiations and then later use the Chinese remainder theorem makes the decryption take roughly the same amount of time in the two systems.

However, the disambiguation issue is what has decided which of the two algorithms became dominant for so many years. The need to compute the Jacobi systems introduces an additional level of complexity to the algorithms, which isn’t worth the implementation effort. Although finding square roots is provably as hard as factorisation, in practice what matters is the algorithms we know, and no RSA-breaking algorithm is more efficient than factorisation.

Regardless, both of these algorithms are quickly becoming obsolete: elliptic curve cryptography provides us with more secure systems using smaller private and public keys. But that’s a story for another time…