Steps • Explanation • Viability • Encryption • Decryption
- First select two distinct prime numbers, say p and q. (preferably big to score a decent level of security)
Can be generated using a primality test.
Fermat’s test can be used, although practically Miller Rabin’s test is more sought after.
-
Take their product as n i.e. n = p*q, which is the modulus of both the keys.
-
Then calculate the Euler’s totient for the above, given by ϕ(n) = (p-1)*(q-1).
-
Proceed by choosing a public key e such that e > 2 and coprime to the totient i.e., gcd(e, totient) must be equal to 1.
-
Choose a corresponding private key d such that it satisfies the equation or e*d mod ϕ(n) = 1.
d is the multiplicative inverse of e modϕ(n).
Public key comprises of (e, n) and private key comprises of (d).
As e is much smaller than d, encrypting a message using RSA is much faster than decrypting it.
-
Ciphertext is calculated using the equation c = memodn, where m is the message to be encrypted.
-
With the help of c and d thus obtained, we can decrypt the message using m = cdmodn.
The Euler’s totient φ(n) of a positive integer n greater than 1 is defined to be the number of positive integers less than n that are coprime (only positive divisor being 1 or the gcd between the two numbers being 1) to n. (φ(1) is defined to be 1)
When n is prime, ϕ(n) = n-1, as in the case of Fermat’s theorem.
Plaintext and ciphertext are integers between 0 and n-1 for some n.
-
Encryption and decryption are of the following form, for some plaintext M and ciphertext C:
- C = Me(mod n)
- M = Cd(mod n) = (Me)d(mod n) = Med(mod n)
-
Each communicating entity has one public-key (e, n) or private-key (d, n) pair, where both e and d are in fact the multiplicative inverse (modϕ(n)) of the other.
- e and d are inverses (modϕ(n)), or ed ≡ 1 (modϕ(n))
- ed = 1 + kϕ(n), for some k.
- Med(mod n) = M1 + kϕ(n)(mod n) = M1 x (M ϕ(n))k(mod ϕ(n)) = M1 x 1k(mod n) = M. (Euler’s theorem)
Therefore, to decrypt a ciphertext C = Med(mod n), we only need to calculate Cd(mod n), since we know C = Me(mod n) => Cd(mod n) = Med(mod n) => Cd(mod n) = M. (with Med(mod n) being M)
The RSA cryptosystem is based on the theorem which implies that the inverse of the function a->aemodn (where e is the public encryption exponent) is the function b->bdmodn, (where d is the private decryption exponent) which provides the difficulty of computing ϕ(n) without knowing the factorization of n. (and thus the difficulty of computing d arises in addition)
This can only be solved by factorizing n (since every number is essentially a product of primes) and only the owner of the private key knows the factorization (primes p and q whose product yields n). This ‘factoring problem’ is the security point, with greater chances of the encryption to be secure for large values of n, or for large primes considered. The fact that only n is publicly disclosed, along with the given difficulty to factor large numbers (it is computationally infeasible to factor a large value of n to get d) gives the guarantee that no one else knows the factorization and the encrypted message, thus making it viable.
| Input: RSA public key (n,e), plaintext m ∈ [0,n-1] | Output: Ciphertext c, (Compute c = me(mod n), return c) |
|---|
| Input: RSA public key (n,e), RSA private key d, ciphertext c | Output: Plaintext m, (Compute m = cd(mod n), return m) |
|---|