Editing RSA cryptosystem (section)

===Attacks against plain RSA===
There are a number of attacks against plain RSA as described below.
* When encrypting with low encryption exponents (e.g., {{math|1=''e'' = 3}}) and small values of the {{mvar|m}} (i.e., {{math|''m'' &lt; ''n''<sup>1/''e''</sup>}}), the result of {{math|''m''<sup>''e''</sup>}} is strictly less than the modulus {{mvar|n}}. In this case, ciphertexts can be decrypted easily by taking the {{mvar|e}}th root of the ciphertext over the integers.
* If the same clear-text message is sent to {{mvar|e}} or more recipients in an encrypted way, and the receivers share the same exponent {{mvar|e}}, but different {{mvar|p}}, {{mvar|q}}, and therefore {{mvar|n}}, then it is easy to decrypt the original clear-text message via the [[Chinese remainder theorem]]. [[Johan Håstad]] noticed that this attack is possible even if the clear texts are not equal, but the attacker knows a linear relation between them.<ref>{{cite book |first=Johan |last=Håstad |chapter=On using RSA with Low Exponent in a Public Key Network |title=Advances in Cryptology – CRYPTO '85 Proceedings |series=Lecture Notes in Computer Science |volume=218 |year=1986 |pages=403–408 |doi=10.1007/3-540-39799-X_29 |isbn=978-3-540-16463-0 }}</ref> This attack was later improved by [[Don Coppersmith]] (see [[Coppersmith's attack]]).<ref>{{cite journal |first=Don |last=Coppersmith |s2cid=15726802 |title=Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities |journal=[[Journal of Cryptology]] |volume=10 |issue=4 |pages=233–260 |year=1997 |doi=10.1007/s001459900030 |url=https://www.di.ens.fr/~fouque/ens-rennes/coppersmith.pdf |citeseerx=10.1.1.298.4806 }}</ref>
* Because RSA encryption is a [[deterministic algorithm|deterministic encryption algorithm]] (i.e., has no random component) an attacker can successfully launch a [[chosen plaintext attack]] against the cryptosystem, by encrypting likely plaintexts under the public key and test whether they are equal to the ciphertext. A cryptosystem is called [[semantically secure]] if an attacker cannot distinguish two encryptions from each other, even if the attacker knows (or has chosen) the corresponding plaintexts. RSA without padding is not semantically secure.<ref>{{Cite book|last1=Goldwasser|first1=Shafi|last2=Micali|first2=Silvio|title=Proceedings of the fourteenth annual ACM symposium on Theory of computing - STOC '82 |chapter=Probabilistic encryption & how to play mental poker keeping secret all partial information |date=1982-05-05|chapter-url=https://doi.org/10.1145/800070.802212|location=New York, NY, USA|publisher=Association for Computing Machinery|pages=365–377|doi=10.1145/800070.802212|isbn=978-0-89791-070-5|s2cid=10316867 |author-link1=Shafi Goldwasser |author-link2=Silvio Micali }}</ref>
* RSA has the property that the product of two ciphertexts is equal to the encryption of the product of the respective plaintexts. That is, {{math|''m''<sub>1</sub><sup>''e''</sup>''m''<sub>2</sub><sup>''e''</sup> ≡ (''m''<sub>1</sub>''m''<sub>2</sub>)<sup>''e''</sup> (mod ''n'')}}. Because of this multiplicative property, a [[chosen-ciphertext attack]] is possible. E.g., an attacker who wants to know the decryption of a ciphertext {{math|''c'' ≡ ''m''<sup>''e''</sup> (mod ''n'')}} may ask the holder of the private key {{mvar|d}} to decrypt an unsuspicious-looking ciphertext {{math|''c''′ ≡ ''cr''<sup>''e''</sup> (mod ''n'')}} for some value {{mvar|r}} chosen by the attacker. Because of the multiplicative property, {{mvar|c}}' is the encryption of {{math|''mr'' (mod ''n'')}}. Hence, if the attacker is successful with the attack, they will learn {{math|''mr'' (mod ''n''),}} from which they can derive the message {{mvar|m}} by multiplying {{math|''mr''}} with the modular inverse of {{mvar|r}} modulo {{mvar|n}}.{{citation needed|reason=Someone had to have noticed this and published first, they should be cited|date=February 2015}}
* Given the private exponent {{mvar|d}}, one can efficiently factor the modulus {{math|1=''n'' = ''pq''}}. And given factorization of the modulus {{math|1=''n'' = ''pq''}}, one can obtain any private key ({{mvar|d}}',&nbsp;{{mvar|n}}) generated against a public key ({{mvar|e}}',&nbsp;{{mvar|n}}).<ref name="Boneh99"/>