Editing RSA cryptosystem (section)

==Security and practical considerations==

===Using the Chinese remainder algorithm===
For efficiency, many popular crypto libraries (such as [[OpenSSL]], [[Java (programming language)|Java]] and [[.NET Framework|.NET]]) use for decryption and signing the following optimization based on the [[Chinese remainder theorem]].<ref>{{cite web |title=OpenSSL bn_s390x.c |url=https://github.com/openssl/openssl/blob/422a13fb5cd668cdc4c1eebce8accb4d25c3d8eb/crypto/bn/bn_s390x.c#L70 |website=Github |access-date=2 August 2024}}</ref>{{fact|date=December 2023}} The following values are precomputed and stored as part of the private key:
* <math>p</math> and <math>q</math>{{snd}} the primes from the key generation,
* <math>d_P = d \pmod{p - 1},</math>
* <math>d_Q = d \pmod{q - 1},</math>
* <math>q_\text{inv} = q^{-1} \pmod{p}.</math>

These values allow the recipient to compute the exponentiation {{math|1=''m'' = ''c''<sup>''d''</sup> (mod ''pq'')}} more efficiently as follows:
{{indent|5}}<math>m_1 = c^{d_P} \pmod{p}</math>,
{{indent|5}}<math>m_2 = c^{d_Q} \pmod{q}</math>,
{{indent|5}}<math>h = q_\text{inv}(m_1 - m_2) \pmod{p}</math>,{{efn|If <math>m_1 < m_2</math>, then some{{clarify|date=June 2020}} libraries compute {{mvar|h}} as <math>q_\text{inv}\left[\left(m_1 + \left\lceil \frac{q}{p} \right\rceil p\right) - m_2\right] \pmod{p}</math>.}}
{{indent|5}}<math>m = m_2 + hq</math>.

This is more efficient than computing [[exponentiation by squaring]], even though two modular exponentiations have to be computed. The reason is that these two modular exponentiations both use a smaller exponent and a smaller modulus.

===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]].

===Faulty key generation===
{{more citations needed|section|date=October 2017}}
{{See also|Coppersmith's attack|Wiener's attack}}

Finding the large primes {{mvar|p}} and {{mvar|q}} is usually done by testing random numbers of the correct size with probabilistic [[primality test]]s that quickly eliminate virtually all of the nonprimes.

The numbers {{mvar|p}} and {{mvar|q}} should not be "too close", lest the [[Fermat factorization]] for {{mvar|n}} be successful. If {{math|''p'' − ''q''}} is less than {{math|2''n''<sup>1/4</sup>}} ({{math|1=''n'' = ''p''⋅''q''}}, which even for "small" 1024-bit values of {{mvar|n}} is {{val|3|e=77}}), solving for {{mvar|p}} and {{mvar|q}} is trivial. Furthermore, if either {{math|''p'' − 1}} or {{math|''q'' − 1}} has only small prime factors, {{mvar|n}} can be factored quickly by [[Pollard's p − 1 algorithm|Pollard's ''p'' − 1 algorithm]], and hence such values of {{mvar|p}} or {{mvar|q}} should be discarded.

It is important that the private exponent {{mvar|d}} be large enough. Michael J. Wiener showed that if {{mvar|p}} is between {{mvar|q}} and {{math|2''q''}} (which is quite typical) and {{math|''d'' &lt; ''n''<sup>1/4</sup>/3}}, then {{mvar|d}} can be computed efficiently from {{mvar|n}} and&nbsp;{{mvar|e}}.<ref name="wiener">{{Cite journal | title=Cryptanalysis of short RSA secret exponents | first1=Michael J. | last1=Wiener | journal=IEEE Transactions on Information Theory | volume=36 | issue=3 | pages=553–558 | date=May 1990 | doi=10.1109/18.54902 | s2cid=7120331 |url=http://www.cits.rub.de/imperia/md/content/may/krypto2ss08/shortsecretexponents.pdf }}</ref>

There is no known attack against small public exponents such as {{math|1=''e'' = 3}}, provided that the proper padding is used. [[Coppersmith's attack]] has many applications in attacking RSA specifically if the public exponent {{mvar|e}} is small and if the encrypted message is short and not padded. [[65537]] is a commonly used value for&nbsp;{{mvar|e}}; this value can be regarded as a compromise between avoiding potential small-exponent attacks and still allowing efficient encryptions (or signature verification). The NIST Special Publication on Computer Security (SP&nbsp;800-78 Rev.&nbsp;1 of August 2007) does not allow public exponents {{mvar|e}} smaller than 65537, but does not state a reason for this restriction.

In October 2017, a team of researchers from [[Masaryk University]] announced the [[ROCA vulnerability]], which affects RSA keys generated by an algorithm embodied in a library from [[Infineon]] known as RSALib. A large number of [[smart card]]s and [[trusted platform module]]s (TPM) were shown to be affected. Vulnerable RSA keys are easily identified using a test program the team released.<ref name=nemecsys>{{cite conference |url=https://crocs.fi.muni.cz/_media/public/papers/nemec_roca_ccs17_preprint.pdf |title=The Return of Coppersmith's Attack: Practical Factorization of Widely Used RSA Moduli |first1=Matus |last1=Nemec |first2=Marek |last2=Sys |first3=Petr |last3=Svenda |first4=Dusan |last4=Klinec |first5=Vashek |last5=Matyas |date=November 2017 |doi=10.1145/3133956.3133969 |book-title=Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security |series=CCS '17}}</ref>

===Importance of strong random number generation===
A cryptographically strong [[random number generator]], which has been properly seeded with adequate entropy, must be used to generate the primes {{mvar|p}} and {{mvar|q}}. An analysis comparing millions of public keys gathered from the Internet was carried out in early 2012 by [[Arjen Klaas Lenstra|Arjen K.&nbsp;Lenstra]], James P.&nbsp;Hughes, Maxime Augier, Joppe W.&nbsp;Bos, Thorsten Kleinjung and Christophe Wachter. They were able to factor 0.2% of the keys using only Euclid's algorithm.<ref>{{cite web|title=Flaw Found in an Online Encryption Method |url=https://www.nytimes.com/2012/02/15/technology/researchers-find-flaw-in-an-online-encryption-method.html |newspaper=[[The New York Times]] |date=February 14, 2012 |first=John |last=Markoff }}</ref><ref>{{cite web |title=Ron was wrong, Whit is right |url=http://eprint.iacr.org/2012/064.pdf |year=2012 |last1=Lenstra |first1=Arjen K. |last2=Hughes |first2=James P. |last3=Augier |first3=Maxime |last4=Bos |first4=Joppe W. |last5=Kleinjung |first5=Thorsten |last6=Wachter |first6=Christophe }}</ref>{{self published inline|date=December 2023|reason=This paper is not from a journal and may not have been peer-reviewed}}

They exploited a weakness unique to cryptosystems based on integer factorization. If {{math|1=''n'' = ''pq''}} is one public key, and {{math|1=''n''′ = ''p''′''q''′}} is another, then if by chance {{math|1=''p'' = ''p''′}} (but {{mvar|q}} is not equal to {{mvar|q}}'), then a simple computation of {{math|1=gcd(''n'', ''n''′) = ''p''}} factors both {{mvar|n}} and {{mvar|n}}', totally compromising both keys. Lenstra et al. note that this problem can be minimized by using a strong random seed of bit length twice the intended security level, or by employing a deterministic function to choose {{mvar|q}} given {{mvar|p}}, instead of choosing {{mvar|p}} and {{mvar|q}} independently.

[[Nadia Heninger]] was part of a group that did a similar experiment. They used an idea of [[Daniel J.&nbsp;Bernstein]] to compute the GCD of each RSA key {{mvar|n}} against the product of all the other keys {{mvar|n}}' they had found (a 729-million-digit number), instead of computing each {{math|gcd(''n'', ''n''′)}} separately, thereby achieving a very significant speedup, since after one large division, the GCD problem is of normal size.

Heninger says in her blog that the bad keys occurred almost entirely in embedded applications, including "firewalls, routers, VPN devices, remote server administration devices, printers, projectors, and VOIP phones" from more than 30 manufacturers. Heninger explains that the one-shared-prime problem uncovered by the two groups results from situations where the pseudorandom number generator is poorly seeded initially, and then is reseeded between the generation of the first and second primes. Using seeds of sufficiently high entropy obtained from key stroke timings or electronic diode noise or [[atmospheric noise]] from a radio receiver tuned between stations should solve the problem.<ref>{{Cite web | url=https://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs | title=New research: There's no need to panic over factorable keys–just mind your Ps and Qs | date=February 15, 2012 | website=Freedom to Tinker | first=Nadia | last=Heninger}}</ref>

Strong random number generation is important throughout every phase of public-key cryptography. For instance, if a weak generator is used for the symmetric keys that are being distributed by RSA, then an eavesdropper could bypass RSA and guess the symmetric keys directly.

===Timing attacks===
[[Paul Carl Kocher|Kocher]] described a new attack on RSA in 1995: if the attacker Eve knows Alice's hardware in sufficient detail and is able to measure the decryption times for several known ciphertexts, Eve can deduce the decryption key {{mvar|d}} quickly. This attack can also be applied against the RSA signature scheme. In 2003, [[Dan Boneh|Boneh]] and [[David Brumley|Brumley]] demonstrated a more practical attack capable of recovering RSA factorizations over a network connection (e.g., from a [[Secure Sockets Layer]] (SSL)-enabled webserver).<ref name="Boneh03">{{cite conference |url=http://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf |title=Remote timing attacks are practical |first1=David |last1=Brumley |first2=Dan |last2=Boneh |year=2003 |series=SSYM'03 |book-title=Proceedings of the 12th Conference on USENIX Security Symposium}}</ref> This attack takes advantage of information leaked by the [[Chinese remainder theorem]] optimization used by many RSA implementations.

One way to thwart these attacks is to ensure that the decryption operation takes a constant amount of time for every ciphertext. However, this approach can significantly reduce performance. Instead, most RSA implementations use an alternate technique known as [[blinding (cryptography)|cryptographic blinding]]. RSA blinding makes use of the multiplicative property of RSA. Instead of computing {{math|''c''<sup>''d''</sup> (mod ''n'')}}, Alice first chooses a secret random value {{mvar|r}} and computes {{math|(''r''<sup>''e''</sup>''c'')<sup>''d''</sup> (mod ''n'')}}. The result of this computation, after applying [[Euler's theorem]], is {{math|''rc''<sup>''d''</sup> (mod ''n'')}}, and so the effect of {{mvar|r}} can be removed by multiplying by its inverse. A new value of {{mvar|r}} is chosen for each ciphertext. With blinding applied, the decryption time is no longer correlated to the value of the input ciphertext, and so the timing attack fails.

===Adaptive chosen-ciphertext attacks===
In 1998, [[Daniel Bleichenbacher]] described the first practical [[adaptive chosen-ciphertext attack]] against RSA-encrypted messages using the PKCS&nbsp;#1&nbsp;v1 [[Padding (cryptography)|padding scheme]] (a padding scheme randomizes and adds structure to an RSA-encrypted message, so it is possible to determine whether a decrypted message is valid). Due to flaws with the PKCS&nbsp;#1 scheme, Bleichenbacher was able to mount a practical attack against RSA implementations of the [[Secure Sockets Layer]] protocol and to recover session keys. As a result of this work, cryptographers now recommend the use of provably secure padding schemes such as [[Optimal Asymmetric Encryption Padding]], and RSA Laboratories has released new versions of PKCS&nbsp;#1 that are not vulnerable to these attacks.

A variant of this attack, dubbed "BERserk", came back in 2014.<ref>{{cite web |title='BERserk' Bug Uncovered In Mozilla NSS Crypto Library Impacts Firefox, Chrome |date=25 September 2014 |url=https://www.darkreading.com/attacks-breaches/-berserk-bug-uncovered-in-mozilla-nss-crypto-library-impacts-firefox-chrome |access-date=4 January 2022}}</ref><ref>{{Cite web|url=https://www.mozilla.org/en-US/security/advisories/mfsa2014-73/|title=RSA Signature Forgery in NSS|website=Mozilla}}</ref> It impacted the Mozilla NSS Crypto Library, which was used notably by Firefox and Chrome.

===Side-channel analysis attacks===
A side-channel attack using branch-prediction analysis (BPA) has been described. Many processors use a [[branch predictor]] to determine whether a conditional branch in the instruction flow of a program is likely to be taken or not. Often these processors also implement [[simultaneous multithreading]] (SMT). Branch-prediction analysis attacks use a spy process to discover (statistically) the private key when processed with these processors.

Simple Branch Prediction Analysis (SBPA) claims to improve BPA in a non-statistical way. In their paper, "On the Power of Simple Branch Prediction Analysis",<ref>{{Cite conference |citeseerx = 10.1.1.80.1438 |title = On the power of simple branch prediction analysis |first1=Onur |last1=Acıiçmez |first2=Çetin Kaya |last2=Koç |first3=Jean-Pierre |last3=Seifert |pages = 312–320 |year = 2007 |book-title=Proceedings of the 2nd ACM Symposium on Information, Computer and Communications Security |series=ASIACCS '07 |doi=10.1145/1229285.1266999 }}</ref> the authors of SBPA (Onur Aciicmez and Cetin Kaya Koc) claim to have discovered 508 out of 512&nbsp;bits of an RSA key in 10 iterations.

A power-fault attack on RSA implementations was described in 2010.<ref>{{cite book |last1=Pellegrini |first1=Andrea |last2=Bertacco |first2=Valeria |last3=Austin |first3=Todd |chapter=Fault-based attack of RSA authentication |title=2010 Design, Automation & Test in Europe Conference & Exhibition (DATE 2010) |date=March 2010 |pages=855–860 |doi=10.1109/DATE.2010.5456933 |isbn=978-3-9810801-6-2 |access-date=21 November 2024 |chapter-url=https://ieeexplore.ieee.org/document/5456933}}</ref> The author recovered the key by varying the CPU power voltage outside limits; this caused multiple power faults on the server.

===Tricky implementation===
There are many details to keep in mind in order to implement RSA securely (strong [[Pseudorandom number generator|PRNG]], acceptable public exponent, etc.). This makes the implementation challenging, to the point that the book ''Practical Cryptography With Go'' suggests avoiding RSA if possible.<ref>{{cite web |last1=Isom |first1=Kyle |title=Practical Cryptography With Go |url=https://leanpub.com/gocrypto/read#leanpub-auto-rsa |access-date=4 January 2022}}</ref>