Factoring Feat: Largest Special Hard-to-Factor Number Yields its Secrets

May 25, 2007

After 11 months of "strenuous calculation," computers from three international institutions realized the prime factors of a 307-digit number—"special" because it's close to a power of 2. The breakthrough, which was made on March 6, may signal trouble for information security techniques that rely on 1024-bit encryption, particularly the RSA scheme, in which information is encrypted using a large composite number created by multiplying two large prime numbers, each about 150 digits in size.

Computers at the École Polytechnique Fédérale de Lausanne (EPFL), the University of Bonn, and Japan's NTT used the "special number field sieve," developed by cryptology professor Arjen Lenstra (now at EPFL) and others in the late 1980s, to crack (2¹⁰³⁹ – 1). In those days, this kind of calculation seemed inconceivable.

However, today's more powerful computers have altered the reality. "We have come up with better ways to map the algorithm onto the architecture," Lenstra said, "and we take better advantage of cache behavior."

What this means is that information security professionals—their gold standard is the near impossibility of factoring huge composite numbers—may have to think twice about the encryption techniques they employ.

For the moment, 1024-bit encryption remains secure. It's much more difficult to factor a number made up of two large primes than it is to factor a large number that has a special mathematical form. Last time, it took Lenstra and others nine years to go from factoring a 155-digit special number to a more general 155-digit number. Now that a special 307-digit special number has been cracked, larger, more general numbers may eventually be in range.

Source: École Polytechnique Fédérale de Lausanne, May 21, 2007