Password Problems - All the members of my old team had their own development schemas. We were give the schema password so we could make changes as we saw fit. These schemas w...
Factoring a 768-bit RSA Number
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.