Last month a team completed a multi-year effort to factor a 768-bit number. The number was one from an old RSA Challenge list. A 22 page paper was written on the subject. The team consisted of Thorsten Kleinjung and associates. This is a record for factoring integers. Their conclusion is that 768-bit RSA numbers are no longer recommend for encryption.
Let us put this into perspective. 10 years ago a team factored a 512-bit number. Factoring a 768-bit number is a few thousand times more difficult then that. Factoring a 1024-bit number will be around a thousand times more difficult than factoring a 768-bit one. The researchers estimate that 1024-bit number factorization will occur some time in the next decade. However it won’t occur as soon as the next 5 years.
The techniques used in the factorization involved heavy math. But one idea they used was that of a sieve. They report that sieving is easy. Conducting work in parallel does create some challenges. Clients must do a lot of communication with servers. Trouble arises when one machine or a network connection goes down.
A square root step significantly reduced the solution space. Many large primes were generated to help the factorization process. Some steps required a terabyte of memory. They ran their jobs on up to 80 different machines. In total the factorization took 10^20 computations. The techniques were chosen using some experience and a lot of luck.
I am amazed at the multi-year commitment by the team to complete the factorization. However this does not mean I no longer trusting 768-bit encryption. Congrats to the Kleinjung team. This is good stuff.
