PuTTY semi-bug puttygen-keys-one-bit-short

Home | FAQ | Feedback | Licence | Updates | Mirrors | Keys | Links | Team
Download: Stable · Snapshot | Docs | Changes | Wishlist

summary: RSA keys generated by PuTTYgen could be one bit too short
class: semi-bug: This might or might not be a bug, depending on your precise definition of what a bug is.
difficulty: fun: Just needs tuits, and not many of them.
priority: low: We aren't sure whether to fix this or not.
absent-in: 0.70
present-in: 0.71
fixed-in: 582284fa6c27dc30484789a803ab968beea2a5a3 (0.72)

When PuTTYgen is asked to generate an RSA key with a 2n-bit modulus, it does it by generating two n-bit primes and multiplying them together. (Adjusted appropriately if the requested length is odd.)

Implemented naïvely, this technique could generate either a (2n−1)-bit modulus or a 2n-bit one, because if each input prime is between 1/2 and 1 times 2n, then their product could be anywhere between 1/4 and 1 times 22n, and the bottom half of that range gives a key modulus one bit smaller than the user asked for.

Cryptographically, this is perfectly harmless (there's no significant difference in ease of factoring between a 2048- and 2047-bit key). But people often used to complain, so in 0.63 we introduced a check that would control the initial few bits of the primes just enough to guarantee their product was at least 1/2 × 22n.

Just before the 0.71 release, that checking code was rewritten to improve it in minor ways, and was not quite adequately tested, which reintroduced the bug where keys can be one bit short. In 0.72, that's now fixed again.


If you want to comment on this web site, see the Feedback page.
Audit trail for this semi-bug.
(last revision of this bug record was at 2019-07-20 07:44:55 +0100)