Incorrectly Generated RSA Keys: How I Learned To Stop Worrying And Recover Lost Plaintexts.

This article focuses on the problem of recovering plaintexts encrypted with incorrectly generated RSA keys, specifically when the public exponent \( e \) is not relatively prime to \(\varphi(N) = (p-1)(q-1)\), causing the decryption exponent to be undefined. Such incorrectly generated keys, which occurred due to a software bug in a prerelease version of Windows 10, result in ciphertexts that cannot be decrypted by standard means. The paper analyzes the mathematical structure underlying this failure and presents an \( O(e) \)-time algorithm to recover a small set of candidate plaintexts, leveraging the knowledge of the prime factors \( p \) and \( q \) and the properties of common RSA padding schemes—PKCS1 v1.5 and Optimal Asymmetric Encryption Padding (OAEP)—to narrow down or uniquely identify the original plaintext. The work includes a practical Python implementation of the recovery algorithm and discusses implications for cryptographic testing, emphasizing the importance of thorough validation in randomized cryptographic functions to prevent rare but impactful bugs.