RSA encrypts messages through the following algorithm, which is divided into 3 steps:1. Key Generation
I. Choose two distinct prime numbers p and q.
II. Find n such that n = pq.
n will be used as the modulus for both the public and private keys.
III. Find the totient of n, ϕ(n)
IV. Choose an e such that 1 < e < ϕ(n), and such that e and ϕ(n) share no divisors other than 1 (e and ϕ(n) are relatively prime).
e is kept as the public key exponent.
V. Determine d (using modular arithmetic) which satisfies the congruence relation
de ≡ 1 (mod ϕ(n)).
In other words, pick d such that de - 1 can be evenly divided by (p-1)(q-1), the totient, or ϕ(n).
This is often computed using the Extended Euclidean Algorithm, since e and ϕ(n) are relatively prime and d is to be the modular multiplicative inverse of e.
d is kept as the private key exponent.
The public key has modulus n and the public (or encryption) exponent e. The private key has modulus n and the private (or decryption) exponent d, which is kept secret.
I. Person A transmits his/her public key (modulus n and exponent e) to Person B, keeping his/her private key secret.
II. When Person B wishes to send the message "M" to Person A, he first converts M to an integer such that 0 < m < n by using agreed upon reversible protocol known as a padding scheme.
III. Person B computes, with Person A's public key information, the ciphertext c corresponding to
c ≡ me (mod n).
IV. Person B now sends message "M" in ciphertext, or c, to Person A.
I. Person A recovers m from c by using his/her private key exponent, d, by the computation
m ≡ cd (mod n).
II. Given m, Person A can recover the original message "M" by reversing the padding scheme.
This procedure works since
c ≡ me (mod n),
cd ≡(me)d (mod n),
cd ≡ mde (mod n).
By the symmetry property of mods we have that
mde ≡ mde (mod n).
Since de = 1 + kϕ(n), we can write
mde ≡ m1 + kϕ(n) (mod n),
mde ≡ m(mk)ϕ(n) (mod n),
mde ≡ m (mod n).
From Euler's Theorem and the Chinese Remainder Theorem, we can show that this is true for all m and the original message
cd ≡ m (mod n), is obtained.
Why RSA Encryption is secure