Clock ticking on 1024-bit encryption safety

Researchers have discovered the prime factors of a 307-digit number

A team of boffins at the University of Lausanne, the University of Bonn and NTT DoCoMo in Japan have discovered the prime factors of a 307-digit number.

Factoring such huge numbers is extremely difficult, which is why encryption companies use them to protect data.

RSA, for example, uses a large composite number, usually 1,024 bits in size, created by multiplying two roughly 150-digit prime numbers as keys.

Because there is a vast supply of large prime numbers, it is easy to come up with unique keys. Information encrypted this way is secure because no one has ever been able to factor these huge numbers. At least not yet.

"This is the largest 'special' hard-to-factor number factored to date," said Arjen Lenstra, professor of cryptology at the University of Lausanne.

The professor believes that this now answers the question of whether 1,024-bit encryption is dead. "The answer is an unqualified yes," he said.

The standard is still secure, because it is much more difficult to factor a number made up of two huge prime numbers than it is to factor a number like this one that has a special mathematical form. But the clock is definitely ticking.

"Last time, it took nine years for us to generalise from a special to a non-special hard-to-factor number [155 digits]. I will not make predictions, but let us just say that it might be a good idea to stay tuned," explained Professor Lenstra.

The team spent 11 months completing the task, which took the equivalent of 100 years of computer run time.

The researchers used a technique called a 'special number field sieve', developed in the 1980s by Lenstra (then at Bellcore), along with his brother Hendrik (then a professor at UC Berkeley), English mathematician John Pollard and Mark Manasse from DEC.