a ciphertext equal to , but this is very unlikely to occur in practice. Decryption Alice can recover from by using her private key exponent by computing Given , she can recover the original message by reversing the padding scheme. Example Here is an example of RSA encryption and decryption. The parameters used here are artificially small, but one can also use OpenSSL to generate and examine a real keypair. Choose two distinct prime numbers, such as and . Compute giving Compute the Carmichael's totient function of the product as giving Choose any number that is coprime to 780. Choosing a prime number for leaves us only to check that is not a divisor of 780. Let . Compute , the modular multiplicative inverse of , yielding as The public key is . For a padded plaintext message , the encryption function is The private key is . For an encrypted ciphertext , the decryption function is For instance, in order to encrypt , one calculates To decrypt , one calculates Both of these calculations can be computed efficiently using the square-and-multiply algorithm for modular exponentiation. In real-life situations the primes selected would be much larger; in our example it would be trivial to factor (obtained from the freely available public key) back to the primes and . , also from the public key, is then inverted to get , thus acquiring the private key. Practical implementations use the Chinese remainder theorem to speed up the calculation using modulus of factors (mod pq using mod p and mod q). The values , and , which are part of the private key are computed as follows: Here is how , and are used for efficient decryption (encryption is efficient by choice of a suitable and pair): Signing messages Suppose Alice uses Bob's public key to send him an encrypted message. In the message, she can claim to be Alice, but Bob has no way of verifying that the message was from Alice, since anyone can use Bob's public key to send him encrypted messages. In order to verify the origin of a message, RSA can also be used to sign a message. Suppose Alice wishes to send a signed message to Bob. She can use her own private key to do so. She produces a hash value of the message, raises it to the power of (modulo ) (as she does