How RSA is public key algorithm?

Answer 1

RSA (which derives from the first initials of the last names of Prof. Ronald Rivest, Dr. Adi Shamir, and Prof. Leonard Adleman who first publicly described it) is an algorithm for public-key cryptography. A British mathematician named Clifford Cooks, who was then working for the UK intelligence agency GCHO, developed an equivalent system which was documented in an internal document in 1973, but because most computers of the time were not ready to handle the intensity of the computations it was never deployed (as far as is publicly known). That original work was not revealed until 1998 due to its top-secret classification, and Rivest, Shamir, and Adleman devised RSA independently of that classified work.

RSA is a very popular algorithm now and assumed to be secure given sufficiently long keys and the use of up-to-date implementations. It is the first algorithm known to be suitable for both encryption AND signing - although not usually at the same time.

The attached link goes into more detail on the nuts and bolts of the algorithm, but the basics are:

1) two large prime numbers, p and q are chosen at random

2) through a series of mathematical operations, two keys d and e.

3) the key d is held as the private key by the originator (it is kept secret)

4) the originator publishes the public key e and n- the product of the two original primes, i.e. n=p·q

5) messages encrypted or signed with d can only be decrypted or authenticated using n and e (and using the appropriate math of the RSA algorithm).

6) messages encrypted using d can only be decrypted and read by the holder of the private key, d.

7) RSA can be used to "sign" a message by creating a hash of the message, then using the private key to encrypt the hash, and then attaching this "signature" to the message. The recipient can authenticate the source of the message by using the public key to decrypt the signature and comparing the value of the decrypted hash to their own hash of the same message. As long as the two agree, the message must have come from the holder of the private key and the message has not been tampered with. If the two hashes DON'T match then either the sender does not have the private key (and thus we would assume is NOT who they claim to be) or the message has been tampered with or corrupted.