768 bit RSA key broken in two and a half years

A new record has been set demonstrating the vulnerability of 786 bit RSA keys using the public key algorithm.

The RSA algorithm (Rivest Shamir Adleman) is a public key system used for confidential information exchanges. In this schema, the keys used to encrypt and decrypt the data are not the same, meaning that the sender and receiver don’t use the same key.

On Thursday, an international team of mathematicians and computer encryption researchers announced that they reached the end (last December) of a calculation which took two and a half years to compute. The aim of these calculations was to break the 768 bit RSA key, in the same way that the 663 bit key was broken four years earlier. This is a record in this field, with the consequences being that 768 bit RSA keys are now "obsolete" meaning that they will have a lot fewer uses in future.

To find the prime numbers which make up this 232 digit key, a large scale calculation was conducted through the use of a distributed network calculator. The French INRIA (Institut national de recherche en informatique et en automatique – National computer research institute) which participated in the project indicated that they occupied the equivalent of 1700 processor cores for a year, through 425 quad-core PC’s.

The INRIA is now just waiting for the conclusions to play out: "Users basing their work on 768 bit RSA keys (or less) should change for another solution. All encryption systems based on such undersized keys, including digital transactions (electronic commerce), banking smartcards or other systems, should avoid these solutions as they are poorly adapted."

The French National computer systems security agency recommends using keys that are at least 2048 bits.