RSA

In 1978, Rivest, Shamir and Adleman of MIT proposed a number-theoretic way of implementing a Public Key Cryptosystem. Their method has been widely adopted. The basic technique is:

Choose two large prime numbers, p and q.
compute n = p * q and x = (p-1)*(q-1)
Choose a number relatively prime to x and call it d. This means that d is not a prime factor of x or a multiple of it.
Find e such that e * d = 1 mod x.

To use this technique, divide the plaintext (regarded as a bit string) into blocks so that each plaintext message P falls into the interval 0 <= P < n. This can be done by dividing it into blocks of k bits where k is the largest integer for which 2^k < n is true.

To encrypt: C = P^e (mod n)
To decrypt: P = C^d (mod n)

The public key, used to encrypt, is thus: (e, n) and the private key, used to decrypt, is (d, n))

RSA Example -- Key Generation

To create the public key, select two large positive prime numbers `p` and `q`	`p` `= 7, q = 17` Large enough for us!
Compute `(p-1) * (q-1)`	`x` `= 96`
Choose an integer `E` which is relatively prime to `x`	`E` `= 5`
Compute `n` `= p * q`	`n` `= 119`
`K_p` is then `n` concatenated with `E`	`K_p` `= 119, 5`

To create the secret key, compute D such that (D * E) mod x = 1

K_s = 119, 77

RSA Example -- Encryption and Decryption

To compute the ciphertext `C` of plaintext `P`, treat `P` as a numerical value	`P` `= 19`
`C` `= P^E mod n`	`C` `= 66`

To compute the plaintext `P` from ciphertext `C`:
`P` `= C^D mod n`	`P` `= 19`

RSA in Practice

RSA works because knowledge of the public key does not reveal the private key. Note that both the public and private keys contain the important number n = p * q. The security of the system relies on the fact that n is hard to factor -- that is, given a large number (even one which is known to have only two prime factors) there is no easy way to discover what they are. This is a well known mathematical fact. If a fast method of factorisation is ever discovered then RSA will cease to be useful.

It is obviously possible to break RSA with a brute force attack -- simply factorise n. To make this difficult, it's usually recommended that p and q be chosen so that n is (in 2002 numbers) at least 1024 bits.

One excellent feature of RSA is that it is symmetrical. We already know that if you encrypt a message with my public key then only I can decrypt that ciphertext, using my secret key. However, it also turns out that a message encrypted with my secret key can only be decrypted with my public key. This has important implications, see later.

The RSA algorithm operates with huge numbers, and involves lots of exponentiation (ie, repeated multiplication) and modulus arithmetic. Such operations are computationally expensive (ie, they take a long time!) and so RSA encryption and decryption are incredibly slow, even on fast computers. Compare this to the operations involved in DES (and other single-key systems) which consist of repeated simple XORs and transpositions. Typical numbers are that DES is 100 times faster than RSA on equivalent hardware. Furthermore, DES can be easily implemented in dedicated hardware (RSA is, generally speaking, a software-only technology) giving a speed improvement of up to 10,000 times.

Public Key Cryptography In Summary

A public key is used to encrypt and a separate, different private key to decrypt the message.
Each party involved generates a key pair.
Each party publishes their public key. This is made widely known to all potential communication partners.
Each party secures their private key, which must remain secret.
Assuming A desires to send a message to B, A first encrypts the message using B's public key.
B can decrypt the message using its private key. Since no one else knows B's private key, this is absolutely secure -- no one else can decrypt it.
There still remain difficult problems of authentication of public keys, compromised keys, bogus & out of date keys. Further, Public Key encryption is very, very slow compared to single key systems.
A very useful and common way of using public key cryptography is as a means of establishing/distributing secret keys for conventional single key cryptography, see later.