RSA
In 1977, shortly after the idea of a public key
system was proposed, three mathematicians, Ron Rivest, Adi Shamir and Len
Adleman gave a concrete example of how such a method could be implemented. To
honour them, the method was referred to as the RSA Scheme. The system uses a
private and a public key. To start two large prime numbers are selected and then
multiplied together; n=p*q.
If we let f(n) = (p-1) (q-1), and e>1 such that GCD(e, f(n))=1. Here e will have
a fairly large probability of being co-prime to f(n), if n is large enough and e
will be part of the encryption key. If we solve the Linear Diophantine equation;
ed congruent 1 (mod f(n)), for d. The pair of integers (e, n) are the public key
and (d, n) form the private key. Encryption of M can be accomplished by the
following expression; Me = qn + C where 0<= C < n. Decryption would be the
inverse of the encryption and could be expressed as; Cd congruent R (mod n)
where 0<= R < n. RSA is the most popular method for public key encryption and
digital signatures today.