November 16, 2010 In 1973, Clifford Cocks invented a method of
public-key cryptography in which the recipient of a message
holds a private key, known only to himself, and publishes a
public key, which may be used by anyone to send him a message
that only he will be able to read. Cocks worked for the British
security service GCHQ, so he was unable to publish his work. In
1978, three MIT professors, Ronald L. Rivest, Leonard M. Adelman
and Adi Shamir invented the same algorithm, independently, which
they patented in 1983. The algorithm is now known as RSA, after
their initials. The basic idea of RSA starts with two large
prime numbers of equal bit-length, p and q; their product n
becomes the modulus of the cryptosystem. The totient of n is
computed as φ(pq) = (p−1) × (q−1). Then two keys are chosen, the
encryption key e and the decryption key d, such that de ≡ 1 (mod
φ(pq)) and gcd(e, φ(pq)) = 1. Then, given a message m, an
integer on the range 0 < m <n, the message is encrypted by
computing me (mod n) and the