Trying to exaplain the working of rsa algorithm in encryption RSA algorithm uses the following procedure to generate public and private keys:
Select two large prime numbers, p and q.
Multiply these numbers to find n = p x q, where n is called the modulus for encryption and decryption.
Choose a number e less than n, such that n is relatively prime to (p - 1) x (q -1). It means that e and (p - 1) x (q - 1) have no common factor except 1. Choose "e" such that 1<e < φ (n), e is prime to φ (n),
gcd (e,d(n)) =1
If n = p x q, then the public key is <e, n>. A plaintext message m is encrypted using public key <e, n>. To find ciphertext from the plain text following formula is used to get ciphertext C.
C = me mod n
Here, m must be less than n. A larger message (>n) is treated as a concatenation of messages, each of which is encrypted separately.
To determine the private key, we use the following formula to calculate the d such that:
De mod {(p - 1) x (q - 1)} = 1
Or
De mod φ (n) = 1
The private key is <d, n>. A ciphertext message c is decrypted using private key <d, n>. To calculate plain text m from the ciphertext c following formula is used to get plain text m.
m = cd mod n
Let's take some example of RSA encryption algorithm: Example 1:
This example shows how we can encrypt plaintext 9 using the RSA public-key encryption algorithm. This example uses prime numbers 7 and 11 to generate the public and private keys.
Explanation:
Step 1: Select two large prime numbers, p, and q.
p = 7
q = 11
Step 2: Multiply these numbers to find n = p x q, where n is called the modulus for encryption and decryption.
First, we calculate
n = p x q
n = 7 x 11
n = 77
Step 3: Choose a number e less that n, such that n is relatively prime to (p - 1) x (q -1). It means that e and (p - 1) x (q - 1) have no common factor except 1. Choose "e" such that 1<e < φ (n), e is prime to φ (n), gcd (e, d (n)) =1.
Second, we calculate
φ (n) = (p - 1) x (q-1)
φ (n) = (7 - 1) x (11 - 1)
φ (n) = 6 x 10
φ (n) = 60
Let us now choose relative prime e of 60 as 7.
Thus the public key is <e, n> = (7, 77)
Step 4: A plaintext message m is encrypted using public key <e, n>. To find ciphertext from the plain text following formula is used to get ciphertext C.
To find ciphertext from the plain text following formula is used to get ciphertext C.
C = me mod n
C = 97 mod 77
C = 37
Step 5: The private key is <d, n>. To determine the private key, we use the following formula d such that:
De mod {(p - 1) x (q - 1)} = 1
7d mod 60 = 1, which gives d = 43
The private key is <d, n> = (43, 77)
Step 6: A ciphertext message c is decrypted using private key <d, n>. To calculate plain text m from the ciphertext c following formula is used to get plain text m.
m = cd mod n
m = 3743 mod 77
m = 9
In this example, Plain text = 9 and the ciphertext = 37