Polynomial RSA Key

If primes for an RSA private key are generated with a faulty random number generation logic that includes long zero-byte patterns, this leads to a key that can be represented as a polynomial. RSA's security relies on the difficulty of factoring integers. For polynomials, efficient factoring algorithms are known, which makes such keys easy to break.

Such bugs can, for example, result from casting small random values to larger integer types.

badkeys distinguishes two known variations. One affects SSH host keys generated by vulnerable versions of the software CompleteFTP (before version 26.1.0). The other — with a different width of zero-byte patterns — was generated by an unknown implementation. It is currently identified by the placeholder name "nautilus" and appears in various certificates logged by Certificate Transparency, most of them for hosts from Yahoo or Verizon, and in some self-signed certificates in Internet-wide scans.

Other variations have been occasionally seen and are also detected.

• Factoring "short-sleeve" RSA keys with polynomials (Keegan Ryan, Trail of Bits)
• Discussion about an affected WebPKI certificate on Mozilla's dev-sec-policy list