Researchers close to breaking 1024-bit RSA encryption

 

Gallery

By Rene Millman

Posted on 25 May 2007 at 12:18

The 1024-bit RSA encryption algorithm is close to being cracked, after encryption researchers demonstrate that a 307-bit Mersenne number can be broken down into primes. The breakthrough will lead to changes in the way data is encrypted, according to the scientists.

The researchers - from the Ecoles Polytechniques Federales de Lausanne, the University of Bonn, and Japanese telco NTT - also broke a new record for discovering the prime factors of the number in 11 months.

The cracking of the number was achieved using the special number field sieve method developed by cryptology professor Arjen Lenstra, his brother Hendrik, then a professor at UC Berkeley, English mathematician John Pollard and Mark Manasse from DEC in the late eighties. The method factored the number (2¹⁰³⁹-1) using around 100 years of computing time to crack it.

The researchers said that identifying large prime numbers was the easy bit. Factoring, or breaking a number down into its prime components, is extremely difficult.

RSA encryption, named after the three individuals who devised the technique (Ronald Rivest, Adi Shamir and Leonard Adleman), takes advantage of this difficulty. Using the RSA method, information is encrypted using a large composite number, usually 1024 bits in size, created by multiplying together two 150 digit prime numbers. As the person who knows these two numbers, the 'keys', they can read the message.

And as there is a limitless supply of large prime numbers, it is easy to produce unique keys. The researchers said that information encrypted this way is secure, because 'no one has ever been able to factor these huge numbers, at least not yet.'

Lenstra said that increased computing power meant that while the feat would have been unthinkable back in the 1990 when he first applied number theory and distributed computing to the task of breaking factoring records, he and his team are now very close to cracking 1024-bit encryption.

'Last time, it took nine years for us to generalise from a special to a non-special hard-to factor number (155 digits). I won't make predictions, but let's just say it might be a good idea to stay tuned,' said Lenstra.