RSA

RSA

2. Attack

2.4. Textbook RSA

when p and q is known, because it is used in textbooks.

2.9. Fermat Factorization

Even though it is a classic way to factorize public keys, there are real-world cases.

CVE-2022-26320 https://nvd.nist.gov/vuln/detail/CVE-2022-26320

Infineon Technologies is an infamous semiconductor company located in Germany. They developed lots of security devices such as HSM. Chips from Infineon can easily be found in security critical devices like ECUs in automotives.

In October 2017, CVE-2017-15361 was discovered. Because of the vulnerability, the public key in the Infineon Trusted Platform Module(TPM) can be factored. The team who discovered the vulnerability named the vulnerability "Return of Coppersmith’s Attack". Affected devices of the vulnerability includes ChromeOS, BitLocker with TPM, and Yubikey 4.

CVE Record: CVE-2017-15361
The Return of Coppersmith’s Attack: Practical Factorization of Widely Used RSA Moduli: https://crocs.fi.muni.cz/_media/public/papers/nemec_roca_ccs17_preprint.pdf
Reconstructing ROCA: A case study of how quickly an attack can be developed from a limited disclosure, The cr.yp.to blog. https://blog.cr.yp.to/20171105-infineon.html
RSA 암호화 알고리즘에서 인수분해 취약점 발견, 보안뉴스. https://www.boannews.com/media/view.asp?idx=57541

GnuPG

1. Basic Algorithm

2. Attack

2.1. When p or q is leaked

2.2. when phi is leaked

2.3. when d is leaked

2.4. Textbook RSA

2.5. Pollard’s Rho

2.6. Pollard p-1 Algorithm

2.7. Chosen Ciphertext Attack

2.8. Cycling Attack

2.9. Fermat Factorization

2.10. Weiner’s Attack

2.11. Hastard Attack

2.12. Dixon’s Factorization

2.13. Coppersmith’s Attack

2.13.1. ROCA Return of Coppersmith’s Attack

3. RSACtfTools

4. Python Cryptodome

5. Ruby OpenSSL

6. Reference

7. See Also