written 4.8 years ago by | • modified 4.8 years ago |

**Subject**: Mobile Computing

**Difficulty**: Medium

**Marks**: 4 Marks

**1 Answer**

0

1.1kviews

Explain RSA algortithm. OR Explain step-by-step procedure of RSA algorithm.

written 4.8 years ago by | • modified 4.8 years ago |

**Subject**: Mobile Computing

**Difficulty**: Medium

**Marks**: 4 Marks

ADD COMMENT
EDIT

0

34views

written 4.8 years ago by | • modified 4.8 years ago |

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:**

- Choose two prime numbers p and Q.
- Multiply p and q to generate n. n will be used as the modulus.
- 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.
- Choose a number e such that it is relatively prime to ɸ (n).
- Find d such that it is multiplicative inverse of e, d = $e^{-1}$ mod ɸ (n).
- (e,n) is the public key and (d,n) is the private key.
- To encrypt, we use the formula (Ciphertext block) = $(Plaintext \ block)^{e}$ mod n.
- To decrypt, we use the formula (Plaintext block) = $(Ciphertext \ blcok)^{d}$ mod n.

**RSA Algorithm Example**

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

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

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

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

ADD COMMENT
EDIT

Please log in to add an answer.