Factorization and cryptography
Until a few decades ago, number theory, namely the study of prime numbers, factorization and other features of the integers, was widely regarded as the epitome of pure mathematics, completely divorced from considerations of practical utility. This sentiment was expressed most memorably by British mathematician G.H. Hardy (best known for mentoring Ramanujan and results on the Riemann Zeta function), who wrote in his book A Mathematician’s Apology (1941),
I have never done anything “useful”. No discovery of mine has made, or is likely to make, directly or indirectly, for good or ill, the least difference to the amenity of the world.
It did not turn out that way. Today number theory is a centerpiece of our digital economy. In particular, integer factorization and other number theory-related techniques are key to modern cryptography, which is used numerous times each day by a typical person, say to purchase items on an e-commerce site, to reserve theatre seats, or even to merely authenticate one’s subscription on a news or social media site. In fact, it is hard to think of any topic of mathematics that is more deeply connected to the day-to-day life of a typical person than number theory.
Mathematics of RSA cryptography
The RSA cryptosystem, named for the authors Ron Rivest, Adi Shamir and Leonard Adleman, is one of the most widely used cryptosystems today. It is based on the observation that given large positive integers $e, d, m$ and $n$ such that $(m^e)^d \equiv m$ mod $n$, then even if one knows $e, m$ and $n$, it is typically very difficult to compute $d$. This leads to a public key cryptosystem: a public key can be used to encrypt messages, but a secret private key is required to decrypt them.
Here is a very brief overview of how the scheme works (see this Wikipedia article for additional details):
- Choose two distinct large primes $p$ and $q$ (typically 100 digits or more in length). These are normally generated by a pseudorandom number generator and then tested for primality using one of several well-known primality tests.
- Compute $n = p q$, which is then released publicly.
- Compute $\lambda(n)$, where $\lambda$ is the Carmichael totient function. In this application, since $p$ and $q$ are primes, $\lambda(n) =$ lcm $(p-1, q-1)$, where lcm means least common multiple. The numbers $p, q$ and $\lambda(n)$ are kept private.
- Choose an integer $e$ coprime to $\lambda (n)$ in the range $1 \lt e \lt \lambda(n)$. Typically $e = 2^{16} + 1 = 65537$.
- Compute $d = e^{-1}$ mod $\lambda(n)$, i.e., the multiplicative inverse of $e$ in the ring of integers modulo $\lambda(n)$, using the extended Euclidean algorithm. The number $d$ is kept private.
- To encrypt a message or message segment represented as a large integer $m$, calculate $M = m^e$ mod $n$ using the public exponent $e$. To decrypt the resulting cypher text $M$, calculate $m = M^d$ mod $n$ using the private key $d$. Exponentiation modulo a large integer can be performed very rapidly by means of the binary algorithm for exponentiation modulo $n$.
Factoring large integers
The RSA scheme is based on the difficulty of factoring large numbers. If one could factor $n = pq$ to obtain $p$ and $q$, then one could immediately find $\lambda(n) =$ lcm $(p – 1, q – 1)$ and thus could calculate the decryption key $d = e^{-1}$ mod $\lambda(n)$.
So how hard is factoring large numbers? Shortly after the RSA scheme was first announced in 1977, the authors challenged Scientific American readers to decrypt a 129-digit cyphertext, with a posted award of US$100. Rivest had estimated, given known integer factorization schemes at the time, that factoring a 129-digit integer would require 40 quadrillion years on the fastest available computers.
In the wake of the RSA scheme announcement, several new integer factorization algorithms were found, some of which were found to be significantly faster than the existing known algorithms. In April 1994, the original RSA secret message was finally decrypted, using one of these new schemes, by means of a consortium of 1600 computers from 600 volunteers worldwide. The secret text was “The Magic Words are Squeamish Ossifrage.”
Some of the current state-of-the-art integer factorization algorithms are the following:
- Continued fraction factorization.
- Quadratic sieve factorization.
- Pollard’s rho algorithm.
- General number field sieve factorization.
See this Wikipedia article for an overview of integer factorization algorithms.
Latest factorization achievement
The RSA cryptosystem is now supported by RSA Security, which was founded by Rivest, Shamir and Adleman in 1982 to commercialize RSA and a number of other related cryptographic systems. From 1991 to 2007, RSA Security offered the RSA challenge problems in integer factorization, with cash prizes of various sizes for successful solution. Beyond the lure of cash prizes (which are no longer offered) these challenge problems have become benchmarks for progress in the field. As of the current date (December 2019), 20 of the 54 challenges have been factored.
The most recent achievement (December 2019) was the solution of RSA-240, namely the factorization of the 795-bit (240-digit) integer
$12462036678171878406583504460810659043482037465167880575481878888328966680118821$ $08550360395702725087475098647684384586210548655379702539305718912176843182863628$ $46948405301614416430468066875699415246993185704183030512549594371372159029236099$ $= 50943595228583991455505102358084371413264838202411147318666029652182120646974670$$ $$0620316443478873837606252372049619334517$ × $24462420883831815056781313902400289665380209257893140145204122133655847709517815$$ $$5258218897735030590669041302045908071447.$
This factorization required 900 core-years of computation, using a number field sieve algorithm. Additional details are given at this announcement.
Are your bank accounts and e-commerce transactions safe?
Current e-commerce standards employing the RSA scheme, for example, are based on 1024-bit and 2048-bit integers. Given that the current state-of-the-art is factorization of a 795-bit integer, it appears that systems currently in use are still safe, although most observers in the field recommend that 2048-bit integers should quickly become the universal standard.
On the other hand, a new breakthrough in factorization research could quickly change the situation. Such breakthroughs have occurred before, as mentioned above, and there is no reason to believe that any of the current factorization methods are the best possible. The only real security here is that the problem of integer factorization is so basic, and has been studied in such great depth by so many mathematicians and computer scientists worldwide, that any still-undiscovered method must require a great deal of mathematical sophistication and difficult-to-develop software.
Along this line, blockchain technology is also founded on integer-factorization-based cryptography. Thus we must accept the disquieting possibility that a major breakthrough in factorization could jeopardize billions of dollars, euros, pounds, yen and yuan held in Bitcoin accounts and other cryptocurrencies.
Does the rise of quantum computing change the score?
In 1994, American mathematician Peter Shor published a paper describing an algorithm (now called Shor’s algorithm), that permits a quantum computer to perform large integer factorization, provided it has enough working “qubits.” In recent years, as researchers have been developing ever-more-capable quantum computers, some have dreamed of a quantum computer potentially becoming a super-efficient factorization engine, one potentially far more powerful for this purpose than any conventional computer system.
However, the development of truly practical quantum computer hardware has proven to be a daunting technical challenge. Among other things, current prototype systems typically involve cryogenic tanks cooled very close to absolute zero, namely -273.15 degrees Celsius or -459.67 degrees Fahrenheit. To date, such computers have only been able to perform a few fairly simple demonstration tasks, although the Canadian firm D-Wave claims several more sophisticated successes.
In a previous Math Scholar blog, we discussed a recent announcement by Google researchers that they had finally achieved “quantum supremacy” — i.e., that they had demonstrated an application running on a quantum computer that solves a problem faster than any present-day conventional computer. Within a few days, however, IBM released a paper arguing that the Google demonstration was flawed, because, among other things, the conventional computer run that they compared with did not take full advantage of large storage systems available on present-day supercomputers. See this Math Scholar blog for details.
The latest news here is that IBM researchers have developed a new scheme to factor numbers on a quantum computer, and have used it to factor the integer $1099551473989 = 1048589$ x $1048601$. This is a remarkable advance — the previous record for factoring integers on a quantum computer was for factoring $4088459 = 2017$ x $2027$. But compared with the 240-digit integer recently factored by conventional computers (see above), it is nothing. So quantum computer factorization still has a VERY long ways to go.
Some researchers argue that truly practical quantum computing is still far in the future. Mikhail Dyakonov, for instance, wrote:
All these problems, as well as a few others I’ve not mentioned here, raise serious doubts about the future of quantum computing. There is a tremendous gap between the rudimentary but very hard experiments that have been carried out with a few qubits and the extremely developed quantum-computing theory, which relies on manipulating thousands to millions of qubits to calculate anything useful. That gap is not likely to be closed anytime soon.
So don’t cash out your Bitcoins just yet. But stay tuned — a new breakthrough may be just around the corner.