Public Key Encryption RSA Algorithm
Dr. Natarajan Meghanathan
Assistant Professor of Computer Science Jackson State University, Jackson MS
E-mail:
[email protected] Public Key Encryption
Motivation: Key distribution problem of symmetric encryption system Let KPRIV and KPUB be the private key and public key of a user. Then,
P = D(KPRIV, E(KPUB, P)) With some, public key encryption algorithms like RSA, the following is also true: P = D(KPUB, E(KPRIV, P))
In a system of n users, the number of secret keys for point-to-point communication is n(n-1)/2 = O(n2). With the public key encryption system, we need 2 keys (one public and one private key) per user. Hence, the total number of keys needed is 2n = O(n).
RSA Algorithm
The RSA algorithm uses two keys, d and e, which work in pairs, for decryption and encryption, respectively. A plaintext message P is encrypted to ciphertext by: C = Pe mod n The plaintext is recovered by: P = Cd mod n Because of symmetry in modular arithmetic, encryption and decryption are mutual inverses and commutative. Therefore, P = Cd mod n = (Pe)d mod n = (Pd)e mod n Thus, one can apply the encrypting transformation first and then the decrypting one, or the decrypting transformation first followed by the encrypting one.
Key Choice for RSA Algorithm
The encryption key consists of the pair of integers (e, n) and the decryption key consists of the pair of integers (d, n). Finding the value of n:
Choose two large prime numbers p and q (approximately at least 100 digits each) The value of n is p * q, and hence n is also very large (approximately at least 200 digits). Trump card of RSA: A large value of n inhibits us to find the prime factors p and q.
Choosing e:
Choose e to be a very large integer that is relatively prime to (p-1)*(q-1). To guarantee the above requirement, choose e to be greater than both p-1 and q-1
Choosing d:
Select d such that (e * d) mod ((p-1)*(q-1)) = 1 In other words, d is the multiplicative inverse of e in class modulo (p-1)*(q-1)
Example for RSA Algorithm
Let p = 11 and q = 13. Find the encryption and decryption keys. Choose your encryption key to be at least 10. Show the encryption and decryption for Plaintext 7
Solution: The value of n = p*q = 11*13 = 143 (p-1)*(q-1) = 18*12 = 120 Choose the encryption key e = 11, which is relatively prime to 120 = (p-1)*(q-1). The decryption key d is the multiplicative inverse of 11 modulo 120. Run the Extended Euclid algorithm with m = 120 and n = 11. We find the decryption key d to be also 11 (the multiplicative inverse of 11 in class modulo 120) The encryption key is (11, 143) The decryption key is (11, 143)
Example for RSA Algorithm
Encryption for Plaintext P = 7 Ciphertext C = Pe mod n = 711 mod 143
Ciphertext is 106
Example for RSA Algorithm
Decryption for Ciphertext C = 106 Plaintext P = Cd mod n = 10611 mod 143
Plaintext is 7
Another Example for RSA Algorithm
Let p = 17 and q = 23. Find the encryption and decryption keys. Choose your encryption key to be at least 10. Show the encryption and decryption for Plaintext 127
Solution: The value of n = p*q = 17*23 = 391 (p-1)*(q-1) = 16*22 = 352 Choose the encryption key e = 13, which is relatively prime to 352 = (p-1)*(q-1). The decryption key d is the multiplicative inverse of 13 modulo 352. Run the Extended Euclid algorithm with m = 352 and n = 13. The multiplicative inverse is -27 (-27 + 352) = 325 We find the decryption key d to be 325 (the multiplicative inverse of 13 in class modulo 352) The encryption key is (13, 391) The decryption key is (325, 391)
Another Example for RSA Algorithm
Encryption for Plaintext P = 127 Ciphertext C = Pe mod n = 12713 mod 391
Ciphertext is 213
Another Example for RSA Algorithm
Decryption for Ciphertext C = 213 Plaintext P = Cd mod n = 213325 mod 391
Plaintext is 127
