integer . Assuming that is relatively prime to , we have where the second-last congruence follows from Euler's theorem. More generally, for any and satisfying , the same conclusion follows from Carmichael's generalization of Euler's theorem, which states that for all relatively prime to . When is not relatively prime to , the argument just given is invalid. This is highly improbable (only a proportion of numbers have this property), but even in this case, the desired congruence is still true. Either or , and these cases can be treated using the previous proof. 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., ) and small values of the (i.e., ), the result of is strictly less than the modulus . In this case, ciphertexts can be decrypted easily by taking the th root of the ciphertext over the integers. If the same clear-text message is sent to or more recipients in an encrypted way, and the receivers share the same exponent , but different , , and therefore , 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. This attack was later improved by Don Coppersmith (see Coppersmith's attack). Because RSA encryption is a 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. RSA has the property that the product of two ciphertexts is equal to the encryption of the product of the respective plaintexts. That is, . Because of this multiplicative property, a chosen-ciphertext attack is possible. E.g., an attacker who wants to know the decryption of a ciphertext may ask the holder of the private key to decrypt an unsuspicious-looking ciphertext for some value chosen by the attacker. Because of the multiplicative property, ' is the encryption of . Hence, if the attacker is successful with the attack, they