RSA ALGORITHM

The full form of RSA is Ron Rivest, Adi Shamir and Len Adleman who invented it in 1977.

The RSA cryptosystem is the  public key cryptography algorithm . It can be used to encrypt a message without the need to exchange a secret key separately. 

It can be used for both public key encryption and digital signatures.

Its security is based on the difficulty of factoring large integers.

If A can send an encrypted message to  B without any prior exchange of secret keys. A just uses B’s public key to encrypt the message and B decrypts it using the private key, which only he knows.

Algorithm:

1. Generate two large random primes, p and q
2. Compute n = pq and  φ = (p-1)(q-1).
3. Choose an integer e, 1 < e < phi, such that gcd(e, φ) = 1.
4. Compute the secret exponent d, 1 < d < φ, such that ed ≡ 1 (mod φ). 
5. The public key is (n, e) and the private key (d, p, q). Keep all the values d, p, q and phi secret. [We prefer sometimes to write the private key as (n, d) because you need the value of n when using d. Other times we might write the key pair as ((N, e), d).)

Encryption:

c = m^e mod n.

Decryption:

m=c^d mod n.

where c is cipher text and m is message

For example:

QUESTION:  UGC NET DEC 2015 PAPER 2

Using p=3, q=13, d=7 and e=3 in the RSA algorithm, what is the value of ciphertext for a plain text 5?

(A) 13                 (B) 21

(C) 26                 (D) 33

Explanation:

Step 1 : write given data

p=3, q=13, d=7, e=3, M=5, C=?

Step 2: follow the algorithm and put these values 

C = M^e mod n

n = p*q = 3*13 = 39

C = 5^3 mod 39

= 8 Ans