RSA Encryption Algorithm

RSA Encryption Algorithm

RSA is a public key encryption algorithm developed by Rivest, Shamir and Adleman. Its
strength lies in the tremendous difficulty in factorization of large numbers. RSA is a block
cipher and the plain text is encrypted in blocks. The plain text and cipher text are integers
between 0 and n-1, for some n, discussed subsequently. Let the plain text block be
represented using a k-bit integer and let 2k be the largest integer that the block can hold, then
2k <n should be true. The integer value that the plain text block represents has to be lesser
than n, otherwise the arithmetic is done (modulo n) which prevents the encryption/decryption
process from being unique.

Step 1: Find two primes p and q randomly, a few decimal digits apart (each of size at least
150 decimal digits). By randomly, we mean by the help of a pseudo random number
generator. If the output of the pseudo random number z is even, we check if z+1 is prime and
if not z+3 and so on. This can be done by a suitable primality test. According to the prime
number theorem, the frequency of numbers near z is (1/log z), so with O(z) tests we can find a
prime>=z.
Step 2: Compute n=p*q.

Step 3: Now choose a random integer e, (0<e<phi(n) ), such that e*d==1 mod phi(n) and
gcd(e, phi(n) )=1. We find d=e-1 mod phi(n) using the extended euclidean algorithm. Since
the inverse is unique, i.e. gcd(e, phi(n) )=1, we are certain that there is exactly one solution
between 0 and phi(n) that satisfies the above equation.
The public key is: (e,n).
The private key is: (d,n).

Step 4: Let M be the plain text and C be the cipher text.

Encryption
f(M) = C =Me mod n

Decryption
f -1(C) = M =Med mod n=Mk*phi(n)+1 = M.

Now, two cases arise
Case 1: If gcd(M,n)=1, then by the corollary of Euler’s theorem, Me*d==M mod n, since that
e*d==1 mod phi(n).

Case 2: If gcd(M,n)>1 and M< n=pq, then M=hp or M=lq (for arbitrary integers h and l).
We have, Mphi(q)==1 mod q (By Euler’s theorem)
Therefore, Mk*phi(p)*phi(q)==1 mod q.
or Mk*phi(n)==1 mod q.
or Mk*phi(n) =1+ cq, (for arbitrary integer c).
or Mk*phi(n)+1 =M(1+ cq) (On multiplying both sides by M)
or Mk*phi(n)+1 =M+ mcq
or Mk*phi(n)+1 =M+ (hp)cq
or Mk*phi(n)+1 =M+ hc(pq)
or Mk*phi(n)+1 =M+ hc(n)
or Mk*phi(n)+1 =M mod n, as required.

Thus, in both the cases, we have the correct decryption.

Note: RSA is susceptible to block replay attacks and a suitable chaining mode such as Cipher
Block Chain(CBC) may be used. All classical ciphers are vulnerable to the man in the middle
attack unless the legitimate communicating parties have a previously shared secret. It is
informative to go through [1] for a comprehensive list of attacks on RSA and [2] is an
excellent guide for writing practical algorithms. Both are easily available for download over
the internet.

An example of the RSA algorithm: We now look at an over simplified example for
illustrating the algorithm.
Let p=3 and q=11, be two randomly selected primes.
n=3*11=33
phi(n)=(3-1)*(11-1)=20

We choose randomly, e such that gcd(e,20)=1. Let e=7, gcd(20,7)=1. Thus there exists an
integer d such that 7*d==1 mod 20 or d=7-1 20,

gcd(20,7)
20=2.7+6
7=1.6+1
Therefore,
1=7-6
=7-(20-2.7)
= -(1).20 +(3).7
So, d=3.
Let the plain text M=2.
Then C=27 mod 33=29.
and M=293 mod 33=2, as desired