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:
  m^ed (mod n) = m (mod n)
  where m is the number representing the message we want to encrypt.

In other 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. Then:

• to encrypt a message, we calculate m^e (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 m^ed 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:

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 large enough.

Terminology

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 m^e (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 m^e 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.)

---