when decrypting a message), and attaches it as a "signature" to the message. When Bob receives the signed message, he uses the same hash algorithm in conjunction with Alice's public key. He raises the signature to the power of (modulo ) (as he does when encrypting a message), and compares the resulting hash value with the message's hash value. If the two agree, he knows that the author of the message was in possession of Alice's private key and that the message has not been tampered with since being sent. This works because of exponentiation rules: Thus the keys may be swapped without loss of generality, that is, a private key of a key pair may be used either to: Decrypt a message only intended for the recipient, which may be encrypted by anyone having the public key (asymmetric encrypted transport). Encrypt a message which may be decrypted by anyone, but which can only be encrypted by one person; this provides a digital signature. Proofs of correctness Proof using Fermat's little theorem The proof of the correctness of RSA is based on Fermat's little theorem, stating that for any integer and prime , not dividing . We want to show that for every integer when and are distinct prime numbers and and are positive integers satisfying . Since is, by construction, divisible by both and , we can write for some nonnegative integers and . To check whether two numbers, such as and , are congruent , it suffices (and in fact is equivalent) to check that they are congruent and separately. To show , we consider two cases: If , is a multiple of . Thus med is a multiple of . So . If , where we used Fermat's little theorem to replace with 1. The verification that proceeds in a completely analogous way: If , med is a multiple of . So . If , This completes the proof that, for any integer , and integers , such that , Notes Proof using Euler's theorem Although the original paper of Rivest, Shamir, and Adleman used Fermat's little theorem to explain why RSA works, it is common to find proofs that rely instead on Euler's theorem. We want to show that , where is a product of two different prime numbers, and and are positive integers satisfying . Since and are positive, we can write for some non-negative