Editing RSA cryptosystem (section)

===Integer factorization and the RSA problem===
{{See also|RSA Factoring Challenge|Integer factorization records|Shor's algorithm|}}
The security of the RSA cryptosystem is based on two mathematical problems: the problem of [[integer factorization|factoring large numbers]] and the [[RSA problem]]. Full decryption of an RSA ciphertext is thought to be infeasible on the assumption that both of these problems are [[computational hardness assumption|hard]], i.e., no efficient algorithm exists for solving them. Providing security against ''partial'' decryption may require the addition of a secure [[padding (cryptography)|padding scheme]].<ref>{{cite book |first=Edmond K. |last=Machie |url=https://books.google.com/books?id=AK5MySZbbuMC&pg=PA167 |title=Network security traceback attack and react in the United States Department of Defense network |date=29 March 2013 |pages=167 |publisher=Trafford |isbn=978-1466985742}}</ref>

The [[RSA problem]] is defined as the task of taking {{mvar|e}}th roots modulo a composite {{mvar|n}}: recovering a value {{mvar|m}} such that {{math|''c'' ≡ ''m''<sup>''e''</sup> (mod ''n'')}}, where {{math|(''n'', ''e'')}} is an RSA public key, and {{mvar|c}} is an RSA ciphertext. Currently the most promising approach to solving the RSA problem is to factor the modulus {{mvar|n}}. With the ability to recover prime factors, an attacker can compute the secret exponent {{mvar|d}} from a public key {{math|(''n'', ''e'')}}, then decrypt {{mvar|c}} using the standard procedure. To accomplish this, an attacker factors {{mvar|n}} into {{mvar|p}} and {{mvar|q}}, and computes {{math|lcm(''p'' − 1, ''q'' − 1)}} that allows the determination of {{mvar|d}} from {{mvar|e}}. No polynomial-time method for factoring large integers on a classical computer has yet been found, but it has not been proven that none exists; see [[integer factorization]] for a discussion of this problem.

The first RSA-512 factorization in 1999 used hundreds of computers and required the equivalent of 8,400 MIPS years, over an elapsed time of about seven months.<ref>{{Cite web |url=https://www.iacr.org/archive/eurocrypt2000/1807/18070001-new.pdf |title=Factorization of a 512-bit RSA Modulus |date=2000 |first=Arjen |last=Lenstra |collaboration=Group |publisher=Eurocrypt }}</ref> By 2009, Benjamin Moody could factor an 512-bit RSA key in 73 days using only public software (GGNFS) and his desktop computer (a dual-core [[Athlon64]] with a 1,900&nbsp;MHz CPU). Just less than 5&nbsp;gigabytes of disk storage was required and about 2.5&nbsp;gigabytes of RAM for the sieving process.

Rivest, Shamir, and Adleman noted<ref name="rsa" /> that Miller has shown that – assuming the truth of the [[Generalized Riemann hypothesis|extended Riemann hypothesis]] – finding {{mvar|d}} from {{mvar|n}} and {{mvar|e}} is as hard as factoring {{mvar|n}} into {{mvar|p}} and {{mvar|q}} (up to a polynomial time difference).<ref>{{cite conference |url=https://www.cs.cmu.edu/~glmiller/Publications/Papers/Mi75.pdf |first=Gary L. |last=Miller |title=Riemann's Hypothesis and Tests for Primality |book-title=Proceedings of Seventh Annual ACM Symposium on Theory of Computing |year=1975 |pages=234–239}}</ref> However, Rivest, Shamir, and Adleman noted, in section IX/D of their paper, that they had not found a proof that inverting RSA is as hard as factoring.

{{As of|2020}}, the largest publicly known factored [[RSA number]] had 829&nbsp;bits (250 decimal digits, [[RSA-250]]).<ref>{{cite web |title=Factorization of RSA-250 |date=2020-02-28 |first=Paul |last=Zimmermann |publisher=Cado-nfs-discuss |url=https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2020-February/001166.html |access-date=2020-07-12 |archive-date=2020-02-28 |archive-url=https://web.archive.org/web/20200228234716/https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2020-February/001166.html |url-status=dead }}</ref> Its factorization, by a state-of-the-art distributed implementation, took about 2,700 CPU-years. In practice, RSA keys are typically 1024 to 4096 bits long. In 2003, [[RSA Security]] estimated that 1024-bit keys were likely to become crackable by 2010.<ref name="twirl">{{cite web |url=http://emc.com/emc-plus/rsa-labs/historical/twirl-and-rsa-key-size.htm|title=TWIRL and RSA Key Size |publisher=[[RSA Security|RSA Laboratories]] |archive-url=https://web.archive.org/web/20170417095741/https://www.emc.com/emc-plus/rsa-labs/historical/twirl-and-rsa-key-size.htm |archive-date=2017-04-17 |url-status=dead |access-date=2017-11-24 |first=Burt |last=Kaliski |date=May 6, 2003 |df=ymd-all}}</ref> As of 2020, it is not known whether such keys can be cracked, but minimum recommendations have moved to at least 2048&nbsp;bits.<ref name="keymanagement">{{cite web |url=http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-57Pt3r1.pdf |title=NIST Special Publication 800-57 Part 3 Revision 1: Recommendation for Key Management: Application-Specific Key Management Guidance |date=2015-01-22 |page=12 |access-date=2017-11-24 |publisher=[[National Institute of Standards and Technology]] |doi=10.6028/NIST.SP.800-57pt3r1 |first1=Elaine |last1=Barker |first2=Quynh |last2=Dang}}</ref> It is generally presumed that RSA is secure if {{mvar|n}} is sufficiently large, outside of quantum computing.

If {{mvar|n}} is 300&nbsp;[[bit]]s or shorter, it can be factored in a few hours on a [[personal computer]], using software already freely available. Keys of 512&nbsp;bits have been shown to be practically breakable in 1999, when [[RSA-155]] was factored by using several hundred computers, and these are now factored in a few weeks using common hardware. Exploits using 512-bit code-signing certificates that may have been factored were reported in 2011.<ref>{{cite web |url=https://blog.fox-it.com/2011/11/21/rsa-512-certificates-abused-in-the-wild/ |title=RSA-512 certificates abused in-the-wild |website=Fox-IT International blog |date=November 21, 2011 |first=Michael |last=Sandee}}</ref> A theoretical hardware device named [[TWIRL]], described by Shamir and Tromer in 2003, called into question the security of 1024-bit keys.<ref name="twirl" />

In 1994, [[Peter Shor]] showed that a [[quantum computer]] – if one could ever be practically created for the purpose – would be able to factor in [[polynomial time]], breaking RSA; see [[Shor's algorithm]].