href="#fb3_img_img_a3e3e91f-d368-54e4-92ec-0b35ee0a9eb7.png" alt="phi left-parenthesis upper N right-parenthesis"/>, the key's owner can find a number such that – she finds the value of separately modulo and , and combines the answers. (mod ) is now computed as (mod ), and decryption works because of Fermat's theorem:
Similarly, the owner of a private key can operate on a message with it to produce a signature
and this signature can be verified by raising it to the power mod (thus, using and as the public signature verification key) and checking that the message is recovered:
Neither RSA encryption nor signature is safe to use on its own. The reason is that, as encryption is an algebraic process, it preserves certain algebraic properties. For example, if we have a relation such as that holds among plaintexts, then the same relationship will hold among ciphertexts and signatures . This property is known as a multiplicative homomorphism; a homomorphism is a function that preserves some mathematical structure. The homomorphic nature of raw RSA means that it doesn't meet the random oracle model definitions of public key encryption or signature.
Another general problem with public-key encryption is that if the plaintexts are drawn from a small set, such as ‘attack’ or ‘retreat’, and the encryption process is deterministic (as RSA is), then an attacker might just precompute the possible ciphertexts and recognise them when they appear. With RSA, it's also dangerous to use a small exponent to encrypt the same message to multiple recipients, as this can lead to an algebraic attack. To stop the guessing attack, the low-exponent attack and attacks based on homomorphism, it's sensible to add in some randomness, and some redundancy, into a plaintext block before encrypting it. Every time we encrypt the same short message, say ‘attack’, we want to get a completely different ciphertext, and for these to be indistinguishable from each other as well as from the ciphertexts for ‘retreat’. And there are good ways and bad ways of doing this.
Crypto theoreticians have wrestled for decades to analyse all the things that can go wrong with asymmetric cryptography, and to find ways to tidy it up. Shafi Goldwasser and Silvio Micali came up with formal models of probabilistic encryption in which we add randomness to the encryption process, and semantic security, which we mentioned already; in this context it means that an attacker cannot get any information at all about a plaintext that was encrypted to a ciphertext , even if he is allowed to request the decryption of any other ciphertext not equal to [778]. In other words, we want the encryption to resist chosen-ciphertext attack as well as chosen-plaintext attack. There are a number of constructions that give semantic security, but they tend to be too ungainly for practical use.
The usual real-world solution is optimal asymmetric encryption padding (OAEP), where we concatenate the message with a random nonce , and use a hash function to combine them:
In effect, this is a two-round Feistel cipher that uses as its round function. The result, the combination , is then encrypted with RSA and sent. The recipient then computes as and recovers as [213]. This was eventually proven to be secure. There are a number of public-key cryptography standards; PKCS #1 describes OAEP [995]. These block a whole lot of attacks that were discovered in the 20th century and about which people have mostly forgotten, such as the fact that an opponent can detect if you encrypt the same message with two different RSA keys. In fact, one of the things we learned in the 1990s was that randomisation helps make crypto protocols more robust against all sorts of attacks, and not just the mathematical
href="#fb3_img_img_a3e3e91f-d368-54e4-92ec-0b35ee0a9eb7.png" alt="phi left-parenthesis upper N right-parenthesis"/>, the key's owner can find a number 