### The RSA Algorithm

 RSA encrypts messages through the following algorithm, which is divided into 3 steps:1. Key GenerationI. Choose two distinct prime numbers p and q.II. Find n such that n = pq.n will be used as the modulus for both the public and private keys.III. Find the totient of n, ϕ(n)ϕ(n)=(p-1)(q-1).IV. Choose an e such that 1 < e < ϕ(n), and such that e and ϕ(n) share no divisors other than 1 (e and ϕ(n) are relatively prime).e is kept as the public key exponent.V. Determine d (using modular arithmetic) which satisfies the congruence relationde ≡ 1 (mod ϕ(n)).In other words, pick d such that de - 1 can be evenly divided by (p-1)(q-1), the totient, or ϕ(n).This is often computed using the Extended Euclidean Algorithm, since e and ϕ(n) are relatively prime and d is to be the modular multiplicative inverse of e. d is kept as the private key exponent.The public key has modulus n and the public (or encryption) exponent e. The private key has modulus n and the private (or decryption) exponent d, which is kept secret.2. EncryptionI. Person A transmits his/her public key (modulus n and exponent e) to Person B, keeping his/her private key secret.II. When Person B wishes to send the message "M" to Person A, he first converts M to an integer such that 0 < m < n by using agreed upon reversible protocol known as a padding scheme.III. Person B computes, with Person A's public key information, the ciphertext c corresponding toc ≡ me (mod n).IV. Person B now sends message "M" in ciphertext, or c, to Person A.3. DecryptionI. Person A recovers m from c by using his/her private key exponent, d, by the computationm ≡ cd (mod n).II. Given m, Person A can recover the original message "M" by reversing the padding scheme.This procedure works sincec ≡ me (mod n),cd ≡(me)d (mod n),cd ≡ mde (mod n).By the symmetry property of mods we have thatmde ≡ mde (mod n).Since de = 1 + kϕ(n), we can writemde ≡ m1 + kϕ(n) (mod n), mde ≡ m(mk)ϕ(n) (mod n),mde ≡ m (mod n).From Euler's Theorem and the Chinese Remainder Theorem, we can show that this is true for all m and the original messagecd ≡ m (mod n), is obtained.Why RSA Encryption is secureReferences1.  http://www.di-mgt.com.au/rsa_alg.html