RSA:

1. RSA is a public key encryption algorithm.

2. RSA is derived from its inventors Rivest, Shamir and Adleman in 1978.

Steps:

1. Choose two different large random prime numbers say “p” and “q”.
2. Calculate n = p * q. Since “n” is the modulus for the public key and the private keys
3. Calculate the totient: Ø (n) = (p - 1)(q - 1)
4. Choose an integer “e” such that 1 < e < Ø (n) and “e” is co-prime to Ø (n) i.e. “e” and Ø (n) share no factors other than 1.
5. Find out decryption key “d” such that e * d = 1 mod (p - 1) (q - 1).
6. Encrypt the message “m” using encryption key e, c = m^e mod n.
7. Decrypt the message “m” using decryption key d, m = c^d mod n.

• The RSA Algorithm is a popular Public-Key encryption Technique.
• It is based on exponentiation in a finite field over integers module a prime
• The integers used by this method is very large make it difficult to solve (by an attacker w/o the key)
• There are two set of keys in this method: a private key and a public key.

• Initially we begin with finding two prime numbers p and q.

  Care must be taken that these two prime numbers must be sufficiently large.

  A guess-and-check method to find these numbers will be nice.

• Next we need two exponents e (encryption key)and d(decryption key);

  Of these both we guess the value of e randomly such that :

  $1 \lt e \lt Φ(n) and GCD(e, Φ(n))=1…………\{Note: Φ(n)=(p-1)*(q-1) \}$

• Next, to find the d value (decryption key) , we use the formula: e.d=1 mod Φ(n) and 0≤d≤n

  This is solved by using Extended Euclid’s Method shown in Q-1.

• Now, we publish the public key which can be read by anyone. The public key is made up of PU= {e,n} . Any third party can access this public-key and encrypt the message.

• You CANNOT decrypt a message using the public key.
• The Private key, on the other had is kept secret. The private key is given as PR={d,n}