There are three parts in RSA
1. Key generation: where you will generate two keys a public key and a private key.
2. Encryption: where you use the public key and data to generate the ciphertext.
3. Decryption: where you use the ciphertext generated in the previous step and the private key to obtain the original data.
Let’s try to understand the example below. Most probably you will be given 4 values and you will be asked to generate public key private key ciphertext and decrypt the ciphertext.
You are given p = 61 and q = 53. You are given e = 17 and the data to be encrypted as m = 65
Step 1. Calculate the public and private keys.
1. You multiply p and q together and find their product
n = p x q
In our example n = 61 x 53 = 3233
2. Find the totient of n. If n has two factors p and q, then totient φ (n) = (p-1)(q-1). We already know p and q so the totient of n, φ (n) = (61 – 1) x (53 – 1) = 60 x 52 = 3120.
3. You need to choose a value for e, which is between 1 and φ (n) which is 3120 in this case. In this case let's e is 17.
4. Compute the modular inverse of 17 mod φ (n). This is the hard part.
A multiplicative inverse of x mod y will be a number which when multiplied by x and the product divided by y gives the remainder 1.
We can use the calculator here http://ptrow.com/perl/calculator2.pl
Put modulus as the φ (n) value which is 3120 in this case, use a = 17 and hit the 1/a button, the result will be the multiplicative inverse. Let us call the multiplicative inverse d, which comes out to be 2753.
5. Once you have calculated the multiplicative inverse, you have both the public and the private keys with you.
Public key is (n = 3233, e = 17).
Private key is (n = 3233, d = 2753).
Step 2. Now we encrypt the data given to us using the public key we calculated.
The formula for encryption is
C = m e (mod n)
C = 65 17 (mod 3233) = 2790
Step 3. The result from step 2 is the ciphertext, now we want to decrypt it to obtain the original data m. To do so we need the private key and the following formula.
M = C d (mod 3233)
M = 2790 2753 (mod 3233) = 65.
