Editing RSA cryptosystem (section)

==Padding==

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

===Padding schemes===
To avoid these problems, practical RSA implementations typically embed some form of structured, randomized [[Padding (cryptography)|padding]] into the value {{mvar|m}} before encrypting it. This padding ensures that {{mvar|m}} does not fall into the range of insecure plaintexts, and that a given message, once padded, will encrypt to one of a large number of different possible ciphertexts.

Standards such as [[PKCS1|PKCS#1]] have been carefully designed to securely pad messages prior to RSA encryption. Because these schemes pad the plaintext {{mvar|m}} with some number of additional bits, the size of the un-padded message {{mvar|M}} must be somewhat smaller. RSA padding schemes must be carefully designed so as to prevent sophisticated attacks that may be facilitated by a predictable message structure. Early versions of the PKCS#1 standard (up to version 1.5) used a construction that appears to make RSA semantically secure. However, at [[International Cryptology Conference|Crypto]] 1998, Bleichenbacher showed that this version is vulnerable to a practical [[adaptive chosen-ciphertext attack]]. Furthermore, at [[Eurocrypt]] 2000, Coron et al.<ref>{{Cite book |last1=Coron |first1=Jean-Sébastien |last2=Joye |first2=Marc |last3=Naccache |first3=David |last4=Paillier |first4=Pascal |title=Advances in Cryptology — EUROCRYPT 2000 |chapter=New Attacks on PKCS#1 v1.5 Encryption |date=2000 |editor-last=Preneel |editor-first=Bart |series=Lecture Notes in Computer Science |volume=1807 |language=en |location=Berlin, Heidelberg |publisher=Springer| pages=369–381 |doi=10.1007/3-540-45539-6_25 |isbn=978-3-540-45539-4 |doi-access=free}}</ref> showed that for some types of messages, this padding does not provide a high enough level of security. Later versions of the standard include [[Optimal Asymmetric Encryption Padding]] (OAEP), which prevents these attacks. As such, OAEP should be used in any new application, and PKCS#1&nbsp;v1.5 padding should be replaced wherever possible. The PKCS#1 standard also incorporates processing schemes designed to provide additional security for RSA signatures, e.g. the Probabilistic Signature Scheme for RSA ([[RSA-PSS]]).

Secure padding schemes such as RSA-PSS are as essential for the security of message signing as they are for message encryption. Two USA patents on PSS were granted ({{US patent|6266771}} and {{US patent|7036014}}); however, these patents expired on 24 July 2009 and 25 April 2010 respectively. Use of PSS no longer seems to be encumbered by patents.{{Original research inline|date=August 2019}} Note that using different RSA key pairs for encryption and signing is potentially more secure.<ref>{{Cite web | url=https://www.di-mgt.com.au/rsa_alg.html#weaknesses | title=RSA Algorithm}}</ref>