Subject: Mobile Computing

Difficulty: Medium

Marks: 4 Marks

RSA is named after it‘s inventors: Ron Rivest, Adi Shamir, and Len Adleman at MITRSA is public key algorithm. The RSA scheme is a block cipher in which the plaintext and ciphertext are integers between 0 and n-1 for some n. A typical size for n is 1024 bits, or 309 decimal digits. That is, n is less than 21024.

Before stating RSA let us see main ingredients used in algorithm:

p,q, two prime numbers : (private, chosen)

n = pq : (public, calculated)

e, with gcd (f(n),e) = 1; 1< e < f(n): (public, chosen)

d k e-1 (mod f(n)) : (private, calculated)

RSA algorithm works as follow:

1. Choose two prime numbers p and Q.
2. Multiply p and q to generate n. n will be used as the modulus.
3. Calculate ɸ (n) = (p-1) * (q-1). ɸ (n) is the Euler‘s totient function. ɸ (p) is the number of positive integers less than p and relatively prime to p.
4. Choose a number e such that it is relatively prime to ɸ (n).
5. Find d such that it is multiplicative inverse of e, d = $e^{-1}$ mod ɸ (n).
6. (e,n) is the public key and (d,n) is the private key.
7. To encrypt, we use the formula (Ciphertext block) = $(Plaintext \ block)^{e}$ mod n.
8. To decrypt, we use the formula (Plaintext block) = $(Ciphertext \ blcok)^{d}$ mod n.

RSA Algorithm Example

1. Choose p = 3 and q = 11
2. Compute n = p x q = 3 x 11 = 33
3. Compute φ(n) = (p - 1) x (q - 1) = 2 x 10 = 20
4. Choose E such that 1 < E <φ (n) and e and n are co-prime. Let e = 7

5. Compute a value for d such that (D x E) % φ(n) = 1.

   One solution is d = 3 [(3 * 7) % 20 = 1]

6. Public key is (E, n) => (7, 33)

7. Private Key is (D, n) => (3, 33)