{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,31]],"date-time":"2025-08-31T23:29:07Z","timestamp":1756682947826},"reference-count":12,"publisher":"Oxford University Press (OUP)","issue":"6","license":[{"start":{"date-parts":[[2023,1,22]],"date-time":"2023-01-22T00:00:00Z","timestamp":1674345600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,6,19]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>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.<\/jats:p>","DOI":"10.1093\/comjnl\/bxac199","type":"journal-article","created":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T11:18:12Z","timestamp":1674645492000},"page":"1342-1349","source":"Crossref","is-referenced-by-count":2,"title":["Incorrectly Generated RSA Keys: How I Learned To Stop Worrying And Recover Lost Plaintexts"],"prefix":"10.1093","volume":"66","author":[{"given":"Daniel","family":"Shumow","sequence":"first","affiliation":[{"name":"Microsoft Research , Redmond, WA 98052 , USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2023,1,22]]},"reference":[{"key":"2023062312053513200_ref1","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1145\/359340.359342","article-title":"A method for obtaining digital signatures and public key signatures","volume":"21","author":"Rivest","year":"1978","journal-title":"Comm. ACM"},{"key":"2023062312053513200_ref2","article-title":"Elementary Number Theory","volume-title":"International Series in Pure and Applied Mathematics","author":"Burton","year":"1998"},{"key":"2023062312053513200_ref3","volume-title":"Prime Numbers A Computational Perspective","author":"Crandall","year":"2000"},{"key":"2023062312053513200_ref4","volume-title":"PKCS #1: RSA Encryption Version 1.5. RFC 2313","author":"Kaliski","year":"1998"},{"key":"2023062312053513200_ref5","volume-title":"PKCS #1: RSA Cryptography Specifications Version 2.0. RFC 2437","author":"Kaliski","year":"1998"},{"key":"2023062312053513200_ref6","first-page":"92","article-title":"Optimal Asymmetric Encryption \u2013 How to Encrypt with RSA","volume-title":"Eurocrypt","author":"Bellare","year":"1994"},{"key":"2023062312053513200_ref7","first-page":"260","article-title":"RSA-OAEP is Secure Under the RSA Assumption","volume-title":"Advances in Cryptology\u2013CRYPTO","author":"Fujisaki","year":"2001"},{"key":"2023062312053513200_ref8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BFb0055716","article-title":"Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1","volume-title":"Advances in Cryptology \u2013 CRYPTO","author":"Bleichenbacher","year":"1998"},{"key":"2023062312053513200_ref9","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1137\/0218012","article-title":"The knowledge complexity of interactive proof systems","volume":"18","author":"Goldwasser","year":"1989","journal-title":"SIAM J. Comput."},{"key":"2023062312053513200_ref10","volume-title":"Bug in CNG RSA Key generation?","author":"Graff","year":"2019"},{"key":"2023062312053513200_ref11","volume-title":"microsoft\/SymCrypt: Cryptographic Library","year":"2018"},{"key":"2023062312053513200_ref12","volume-title":"1804 - cryptoapi: SymCrypt Modular Inverse Algorithm - Project Zero","author":"Ormandy","year":"2019"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/6\/1342\/50684636\/bxac199.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/6\/1342\/50684636\/bxac199.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,23]],"date-time":"2023-06-23T12:06:48Z","timestamp":1687522008000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/66\/6\/1342\/6995423"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,22]]},"references-count":12,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2023,1,22]]},"published-print":{"date-parts":[[2023,6,19]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxac199","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023,6]]},"published":{"date-parts":[[2023,1,22]]}}}