Lecture 18: Encryption #2 - Public Key Systems

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 2005 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.

Lecture 18: Encryption #2 -- Public Key Systems

previous | start | next