by Dan Moren
Some encryption keys could use “trapdoored” prime numbers
A really fascinating (if a bit technical) piece from Ars Technica’s Dan Goodin on a way that encryption keys could be seeded with prime numbers that make them easier to crack:
Since the early 1990s, researchers have known that certain composite integers are especially susceptible to being factored by NFS. They also know that primes with certain properties allow for easier computation of discrete logarithms. This special set of primes can be broken much more quickly than regular primes using NFS. For some 25 years, researchers believed the trapdoored primes weren’t a threat because they were easy to spot. The new research provided novel insights into the special number field sieve that proved these assumptions wrong.
In short, there are a few things going on here. One is that the 1024-bit key length that’s in wide use and presumed to require an unreasonable amount of time to compromise could in fact require only about a tenth of the time that was previously thought. There’s also the question of the provenance of the random numbers used to generate encryption keys–some suspect that the NSA may have had a hand in some of the sources that are often used, seeding them with these “trapdoored” prime numbers.
The best alternative currently seems to be trying to move as much encryption as possible to 2048- or 4096-bit keys, which–at least for the present–require much, much longer to crack.