The RSA algorithm
For performing RSA encryption with Java, you
luckily don't need to know all the gory details of how RSA works. But it's worth having
an overview, at least so that you can understand the terminology.
(Note that outside of Java, you do need to know some of these details to use RSA securely;
luckily, at least Sun's implementation solves some potential security issues that you
could otherwise run into if you just used RSA "without thinking about it".)
OK, hold on to your hat...
Basic RSA equation
The essential idea is as follows:
- we pretend that our message to encrypt is a number (although
conceptually, we want to encrypt/decrypt some arbitrary series of bytes, we can
always put them together and treat them as a big number);
- we pick two large prime numbers, call them p and q;
- we multiply p and q together to form the modulus (n);
- it is then mathematically possible to find two exponents,
generally called e and d, so that:
med (mod n) = m (mod n)
where m is the number representing the message we want to encrypt.
words, if we raise m to the power e, taking the answer modulo n,
there exists some other number d, so that raising the result to d (and
taking the answer modulo n again) gets us back to the original number.
Thus, we have a way to perform encryption then decryption, each using a
different number: e in one case and d in the other.
Using the RSA equation in practice
Once we've picked values for p and q (remember, these are random large
primes), we need to pick suitable corresponding values for e and d.
In practice, it's easiest to just use some small value of e that we know
is suitable (65537 is commonly used), and then calculate the corresponding d.
- to encrypt a message, we calculate me (mod n);
- to get back to the original message, the person on the other end will
take this number and raise it again to the power d (overall, that
means between them they'll have calculated med and gotten
back to the original message);
- the person encrypting needs to know only the
values of e and n— these two numbers therefore
become the public key;
- only the person decrypting needs
to know the value of d (and the value of n)— these
two numbers therefore form the private key.
How to calculate d
The method of calculating d actually turns out to be the
basis of the security of RSA:
It is mathematically easy to find d if and only if
you know p and q, but otherwise, it is extremely difficult.
Remember that p and q are initially chosen by the person creating
the key pair, but then these numbers are discarded (or at least, kept secret) once
d has been calculated;
only the result of multiplying the two numbers together (n = pq) is made public
(along with e),
and in practice, this multiplication cannot be undone if p and q are
The following terminology is generally used, and is useful to know when
working with the Java RSA classes:
- n is called the modulus;
- e is the public exponent;
- d is the private exponent;
- the public key consists of the pair (e, n);
- the private key consists of the pair (d, n)—
though in fact n is publically known.
Security of RSA
Purely in theory, RSA could be attacked as follows:
- somebody could factorise n to get the corresponding
p and q, but there is no publically known way to factorise
numbers efficiently, so that this becomes impossible in practice if n is
sufficiently large (say, a few thousand bits);
- somebody could come up with "some other way" of calculating d given
e and n— again, no such method is known (or at least,
not publically known) at present;
- if the original message is predictable,
somebody could make repeated guesses at the original message, calculating
me (mod n) each time— where m is the guess in question—
until the result matched the encrypted version.
To get round the latter problem,
it is important to make sure
that the message is unpredictable by appending random padding.
Sun's implementation handles this (but another implementation might not by default).
Adding padding also solves a problem with very short messages: if the message is
so short that me is less than n, then an attacker can
simply calculate the eth root of m to retrieve the message. (Once it
exceeds n, and so the number is actually reduced modulo n,
such a calculation isn't feasible.)