# Breaking RSA

### RSA Challenges

On March 18, 1991, RSA laboratories began the RSA Factoring Challenge by offering cash prizes to anyone who could factor one of the “challenge numbers”. There were eight challenge numbers ranging in size from 576 bits to 2048 bits, and each number was the product of two large primes. The challenge served as away to ” learn about the actual difficulty of factoring large numbers of the type used in RSA keys” and to “track the state of the art in factoring”.

RSA Laboratories also suggests that RSA users who in charge of securing high-value information (such as banks) might use the challenge to decide on an appropriate key size (if RSA-768 has just been broken, you probably want to choose a key that is considerably larger than 768 bits)

RSA-100, which is 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 if you’re curious, was factored on April 1, 1991, only fourteen days after the challenge was issued. The solver, Arjen K Lenstra, was a Dutch mathematician interested in cryptography and specifically integer factorization. He used a quadratic sieve algorithm to do the factorization, a technique that was developed in 1981. However, the seive

The largest RSA challenge number that has been factored is RSA-768, which was factored in 2009 by hundreds of computers over a two year period. It is worthwhile to note that although an instance of 768-bit RSA has been broken, it was not computationally efficient to do so. So as long as the information you’re trying to protect is worth less than two years of computation on hundreds of computers, you should be fine to use RSA-768.

### Side-channel attacks

No efficient method has been found for factoring arbitrarily large numbers, so most attacks on RSA are what are called “side-channel attacks”. A side-channel attack tries to exploit the physical implementation of a cryptosystem, instead of the underlying mathematics. Going back to the notion of Shannon’s perfect security, it is sometimes possible for physical effects of encryption (power, sound) to give away information about the message or the key.

### Quantum Computing

Shor’s algorithm is a factorization method invented in 1994 by mathematician Peter Shor that runs in polynomial time – but only on what is known as a quantum computer. A quantum computer uses qubits (quantum bits) to store data, and uses quantum phenomena to perform operations on those qubits. As of right now, quantum computing is only a reality on the small scale (with a very small number of qubits), but if large-scale quantum computing is realized, factoring will no longer be a computationally infeasible problem, and cryptography based on the hardness of factoring (like RSA) will become insecure.

Shor’s algorithm solves the factoring problem by reducing it to another type of problem, the ordering problem, solving the ordering problem, and then using that result to find the solution to the original factoring problem.

Shor’s algorithm is efficient because the Fourier transform is extremely efficient on a quantum computer. On a normal computer, the Fourier transform takes $O(n2^n)$ time, while on a quantum computer the operation can be performed in $O(n^2)$ time.

Some small demonstrations of Shor’s algorithm on very small numbers of qubits have been performed, notably by IBM in 2001, when they factored 15 in to 5 and 3 using quantum computing. However, we are still quite a ways off from factoring any large RSA numbers.