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

When generating primes p and q for an RSA key, the algorithm specifies that if p 1 and q 1 must be relatively prime to the public exponent e. If this is not done, then the decryption exponent is not well defined. However, what if a software bug allows the generation of public parameters N and e of an RSA key with this property and then it is subsequently used for encryption? Though this may seem like a purely academic question, a software bug in a preview release of the Windows 10 operating system makes this question of more than purely theoretical. Without a well defined decryption exponent, plaintexts encrypted to such keys will be undecryptable thus potentially losing user data, a serious software defect. Though the decryption exponent is no longer well defined, it is in fact possible to recover the a small number of potential plaintexts, if the prime factors p and q of the public modulus N are known. This paper presents an analysis of what steps fail in the RSA algorithm and derives a plaintext recovery algorithm. The runtime of this algorithm is O(e) making it practical to use, and it has been implemented in python.