3
$\begingroup$

Is there any use for Fermat's Factorization Method in the world of cryptography? I see that several algorithms are based on it, such as the quadratic sieve and general number field sieve. I understand that Fermat's can be very fast if the factors are close to the square root. Generally RSA moduli have factors that are far enough apart to be resistant to Fermat's.

Are there any real-world examples of when Fermat's Method would be used?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

There is a recent instance (March 14th 2022) of the breaking of RSA public keys which were generated carelessly (full report here). Apparently that version of the software is no longer used.

Cryptographic keys generated with older software now owned by technology company Rambus are weak enough to be broken instantly using commodity hardware, a researcher reported on Monday. This revelation is part of an investigation that also uncovered a handful of weak keys in the wild.

the vulnerable SafeZone library doesn't sufficiently randomize the two prime numbers it used to generate RSA keys. (These keys can be used to secure Web traffic, shells, and other online connections.) Instead, after the SafeZone tool selects one prime number, it chooses a prime in close proximity as the second one needed to form the key.

Edit: Here are some more links Fermat attack site: https://fermatattack.secvuln.info/

Code: https://github.com/badkeys/badkeys

Script which checks this and other vulnerabilities: https://badkeys.info/

Improve this answer
$\endgroup$
1
  • $\begingroup$ Did they release a code? Do you know about it? $\endgroup$
    – kelalaka
    Oct 15, 2022 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.