previous |
start |
next
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 2003 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.
previous |
start |
next