Editing RSA cryptosystem (section)

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