Encryption researchers are close to cracking the 1024-bit RSA encryption algorithm after demonstrating that a 307-bit Mersenne number could be broken down into primes. According to the scientists, the breakthrough will lead to changes in the way data is encrypted.
The researchers from the Ecoles Polytechniques Federales de Lausanne, the University of Bonn, and Japanese telco NTT in breaking down the huge number 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 (21039-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 for 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.
