RSA

This is an algorithm used for public key cryptography. The algorithm was suggested in 1977 by Ran Rivest, Adi Samir and Len Adleman therefore called RSA. The algorithm can be described as follows.

Key Generation:

• Choose two large random prime numbers P and Q of approximately equal size.
  
• Compute n = P . Q and fi = (p-1) . (Q-1)
  
• Choose an integer positive integer e, which is less than fi, such that gcd(e,fi)=1
  
• Compute secret component d, such that d is positive and less than fi, and e.d = 1 (mod fi)
• Declare public key (n,e) and the private key as (n,d)

n is known as modulus. e is known as encryption exponent, and d is known as decryption exponent.

--------------------------------------------------------------------------------------
Now let A wants to send a message m to B.

Encryption By A:

1. Obtain B's public key (n,e)
2. When message to be send is m. compute c = (m^e) mod n
3. Send c to B.

Decryption By B:

1. B uses his private key (n,d) to compute m = (c^d) mod n
2. m is the required message.

--------------------------------------------------------------------------------------
What actually digital signature is ?
Let you want to send a message to a recipient, you prepare the message and send it to the recipient, but the problem here is that the recipient on getting the message want to be sure that message is actually written by you. To satisfy this requirement you have to provide some additional information to the recipient that makes him sure about your authorization to the message. This additional information is called digital signature. The final line is that, to send a message X you actually have to send the pair (X, digital signature for X).

For example let A wants to put digital signature on any of his document DOC

Digital Signature:

1. Create a message digest of the information to be sent. In our case A uses any of the hash function (let f) to find message digest f(DOC)
2. represent this digest as an integer m between 0 and n-1. In our case take modulus i.e. m=f(DOC) mod n.
3. Use own private key (n,d) to compute the signature s=(m^d) mod n
4. Send this signature s to the recipient. in full send (DOC,s) to receiver
   

Signature Verification:
receiver gets (DOC,s) from the sender

1. Use the sender's public key (n,e) to compute integer v=(s^e) mod n, this is the process of extraction of the message digest
2. Independently compute the message digest of the information that has been signed, that is compute f(DOC)
3. if both message digests are identical, the signature is valid.
   

--------------------------------------------------------------------------------------