Fermat Attack

In 1643 Pierre de Fermat developed a factorization algorithm. The algorithm allows efficiently calculating the prime factors of a composite number that is the product of two "close" primes.

The RSA encryption and signature algorithm relies on the fact that factorization of large numbers is a hard problem. The RSA public key contains a composite number (usually called N) that is the product of two primes (usually called p and q).

If RSA keys are generated with "close" primes then RSA can be broken with Fermat's factorization algorithm.

During the development of badkeys.info such vulnerabilities have been discovered in printers by Canon and Fujifilm and in an underlying cryptographic module by Rambus.

More Information the Fermat Attack and our findings