# Factoring "short-sleeve" RSA keys with polynomials

DevFeed: [Factoring "short-sleeve" RSA keys with polynomials](<https://devfeed.tech/articles/factoring-short-sleeve-rsa-keys-with-polynomials-7653.md>)

Original publisher: [Read original article](<https://blog.trailofbits.com/2026/06/12/factoring-short-sleeve-rsa-keys-with-polynomials/>)

Author: "Keegan Ryan"

Published: 2026-06-12T11:00:00Z

Content type: article

Language: en

Sources: [The Trail of Bits Blog](<https://devfeed.tech/sources/the-trail-of-bits-blog.md>), [The Trail of Bits Blog](<https://devfeed.tech/sources/the-trail-of-bits-blog-2.md>)

Topics: [Vulnerabilities](<https://devfeed.tech/topics/vulnerabilities.md>), [Certificate Transparency](<https://devfeed.tech/topics/certificate-transparency.md>), [TLS (Transport Layer Security)](<https://devfeed.tech/topics/tls.md>), [ssh](<https://devfeed.tech/topics/ssh.md>), [Open Source](<https://devfeed.tech/topics/open-source.md>), [Code](<https://devfeed.tech/topics/code.md>)

Tags: [attacks](<https://devfeed.tech/tags/attacks.md>), [bug](<https://devfeed.tech/tags/bug.md>), [certificate-transparency](<https://devfeed.tech/tags/certificate-transparency.md>), [code](<https://devfeed.tech/tags/code.md>), [cryptography](<https://devfeed.tech/tags/cryptography.md>), [exploits](<https://devfeed.tech/tags/exploits.md>), [internet](<https://devfeed.tech/tags/internet.md>), [open-source](<https://devfeed.tech/tags/open-source.md>), [software](<https://devfeed.tech/tags/software.md>), [ssh](<https://devfeed.tech/tags/ssh.md>), [tls](<https://devfeed.tech/tags/tls.md>), [vulnerabilities](<https://devfeed.tech/tags/vulnerabilities.md>)

## AI overview

Researchers found hundreds of weak RSA and DSA keys whose structured zero-bit patterns made them quickly factorable with a polynomial-based cryptanalytic technique. They linked many of the keys to a type mismatch in older CompleteFTP big-integer code and recovered 603 RSA private keys and 74 DSA keys from internet scans.

## Source excerpt

What happens when the bits of an RSA private key are heavily biased toward 0 instead of being randomly generated? The public key's bits could be biased enough for us to detect these incorrectly generated keys in the wild. Together with Hanno Böck of the badkeys project, we found hundreds of unique keys that not only have this property, but can be quickly factored. We also found the bug that led to many of these keys and analyzed historical data to track the issue over time. Surprisingly, the pattern of 0 bits is often highly structured, allowing us to develop a powerful polynomial-based cryptanalytic technique that exploits the pattern. Figure 1: Two patterns of RSA moduli with repeated blocks of 0 bits seen in real-world examples. These "short-sleeve" keys, named for how the 0 bits don't fully cover the limbs of the big integers, largely fell into two patterns. Pattern 1 remains unexplained, but we traced pattern 2 to a type mismatch in big-integer code from old versions of the CompleteFTP file transfer software. The CompleteFTP bug also generated vulnerable short-sleeve DSA keys, and we recovered 603 unique RSA private keys and 74 DSA keys from internet scans. If you used CompleteFTP to generate host keys between December 2016 and December 2023, CompleteFTP has released a tool to check whether your keys need to be regenerated. How we found the weak keys The badkeys project is an open-source service that checks public keys for known vulnerabilities. While developing this tool, Hanno collected a massive number of real-world keys from public sources, including Certificate Transparency logs, internet-wide TLS and SSH scans, PGP keys, and many others. By searching this dataset for unexpectedly sparse RSA moduli, we uncovered a large number of keys in the wild with the patterns in Figure 1. Both patterns include several regularly spaced blocks of all zeros interleaved with seemingly random data. Pattern 1 appears in CT logs for certificates issued to several large organ