RSA Made Simple

As we all know, when designing a protocol for electronic communication we must continually bear in mind the security goals we need to satisfy. For example, we may wish to prevent our messages from being read by eavesdroppers, or to digitally sign our messages to guarantee that no-one else could have sent them. Cryptography, the science of encrypting and decrypting messages (almost invariably using ciphers), is the method of choice for these tasks.

An alternative method of trying to avoid our messages being read by a third party is steganography. This involves hiding the message being sent, e.g. in the pixels of an otherwise innocuous-looking image. A famous example is the message sent by Histiaeus of Miletus on the head of one of his slaves: he shaved the man's head, wrote the message and then waited for his hair to regrow before sending him to deliver the message. It goes without saying that this rather ingenious trick is only suitable for non-urgent messages.

One particularly interesting type of cryptography is asymmetric, or public key, cryptography. The idea works as follows. Everyone has two keys, a public key and a private key, neither of which can be derived from the other. They publish the public key and keep the private key hidden somewhere safe. The keys are such that:

• Messages encrypted with one of the keys can only be decrypted using the other.
• Each key can only decrypt messages encrypted with its partner.

Thus, if Alice wants to send a message to Bob that only the latter can read, she encrypts the message with Bob's public key, and (provided the encryption scheme is secure) can be sure that Bob is the only person who can decrypt it again, as only he has knowledge of his own private key.

To digitally sign a message to Bob to guarantee that it came from her, on the other hand, she would encrypt the message with her own private key. The encrypted message can be read by anyone, since Alice's public key is public knowledge, but only Alice can have sent the message, as no-one else had her private key and thus no-one else could have encrypted a message which could only be read using her public key. The two security goals we mentioned above can thus be amply satisfied by public key cryptography.

As a theory, this is all well and good, but it remains to be shown how to implement such a scheme. This is where RSA enters the picture.

The RSA algorithm

The RSA algorithm was first described in a 1977 paper by Ron Rivest, Adi Shamir and Leonard Adleman (hence the name), three researchers working at MIT, although an equivalent algorithm had actually been invented (but not published, for security reasons) by a GCHQ mathematician called Clifford Cocks four years earlier. Its foundation is the belief that factoring the product of two humongously large primes is computationally infeasible, i.e. it can't be done on a computer in a sensible amount of time. In theory, it should be possible (by choosing suitably large primes) to make it take an expected time longer than the expected lifetime of the universe, even if we used all the computers on Earth, but in practice this is rarely done. All that's really necessary is to make sure it can't be decrypted before the encrypted information's 'use by' date, i.e. the time at which the information contained within the message ceases to be of any use to an attacker. (It's worth noting that not all systems in current use achieve even this modest goal.)

Starting from the assumption of computational infeasibility, it is possible to generate suitable public and private keys which are mutual inverses but cannot be derived from each other. Let's take a closer look at how this works.

Key pair generation

We start by randomly guessing two large (distinct) primes, p and q . This sounds difficult, but in practice it has been shown that the probability of a given number n being prime is roughly 1/ln n . (As an example, for 100-digit numbers this means that roughly 1 in every 230 numbers is prime.) Furthermore, efficient primality-testing algorithms like Miller-Rabin can be used to tell us whether a given number is prime or not. To pick two large primes, therefore, we simply guess lots of large random numbers and keep the first two primes we come across.

From these primes, we compute the product n = p × q and define φ( n = ( p -1)( q -1). (Note that under the assumption that n cannot be factored, φ( n ) cannot be derived from n without knowledge of p or q .) We pick a small number e coprime to φ( n ) (65537 is a common choice), i.e. gcd( e ,φ( n )) = 1 and compute d = e ^-1 mod φ( n ) using an algorithm called the Extended Euclidean Algorithm. Finally, we publish ( e , n ) as our public key and keep ( d , n ) as our private key. All of this relies on a lot of mathematics (which is unfortunately beyond the scope of a short article like this one), but the basic steps are relatively easy to follow. The key point is that given either of the keys we've just generated and no additional information, it is computationally infeasible to calculate the other without being able to factor n , since we have no way of calculating φ( n ) from n .

Encryption and decryption

Encryption and decryption are both done the same way in RSA. Both use something called modular exponentiation. This is very like raising something to a power, but in modular arithmetic rather than the normal way of doing things. As an example, 2 ³ ≡ 3 mod 5, since 8 leaves remainder 3 when divided by 5. For RSA, then, we take a numeric encoding, m , of our message, and encrypt it using

c = m e mod n

To decrypt it, we do

m' = c d mod n

and we will find that m' = m . The reason this is true is down to a theorem produced by Euler, which tells us that for n > 1 and a ∈ Z _n * = { b |0 < b < n and gcd( b , n ) = 1},

a ^{φ( n )} ≡ 1(mod n ).

Assuming that m ∈ Z ⁿ *, therefore, our proof that m' = m goes through as follows:

m' = c ^d mod n
= ( m ^e mod n ) ^d mod n
= m ^ed mod n
= m ^{1+ k φ( n )} mod n
= ( m ×( m ^{k φ( n )} mod n ))mod n
= ( m ×( m ^{φ( n )} mod n ) ^k )mod n ))mod n
= ( m ×(1 ^k mod n ))mod n
= ( m ×1)mod n
= m

The proof relies on various properties of modular arithmetic, such as that , etc. The key point to note is that ed = 1 + k φ( n ) for some k , since ed ≡ 1 + mod φ( n ). Having finished this proof, we now know that encrypting and decrypting the message will get us back to where we started from.

As mentioned before, it is also possible to use RSA for digital signing. This turns out to be very simple. Instead of encrypting our message with the public key and decrypting it with the private key, we swap them round. So a signed version of m can be produced by doing

s = m d mod n

and verified using

m' = s e mod n .

Once again, m' = m , using an entirely analogous proof.

RSA in Java

The theory behind RSA is interesting (if tricky in places), and I seriously recommend that you look into it in more detail. For the rest of this article, however, I want to approach things from a more practical standpoint and discuss how to use RSA in your Java code. This turns out to be rather simple, as an implementation already exists in the Java standard libraries. It works internally by treating ASCII text as a number in base 256 and then applying the RSA algorithm using the modPow method of java.math.BigInteger . (For more details, you might want to examine the files RSACipher.java and RSACore.java in the OpenJDK implementation at http://openjdk.java.net .)

Let's start by looking at how to generate keys (see Listing 1). The process is relatively straightforward: we start by getting a KeyPairGenerator instance which will generate RSA key pairs, initialise it using a key-size (1024 bits) and a 'cryptographically-secure' pseudo-random number generator (i.e. a random number generator which satisfies a number of desirable cryptographic properties), and use it to generate the keys. Finally, we extract the required private and public keys from the returned KeyPair .

      import java.security.KeyPair;
      import java.security.KeyPairGenerator;
      import java.security.SecureRandom;
      import java.security.interfaces.RSAPrivateKey;
      import java.security.interfaces.RSAPublicKey;

      ...

      KeyPairGenerator keyGen =
         KeyPairGenerator.getInstance("RSA");
      SecureRandom random =
         SecureRandom.getInstance("SHA1PRNG", "SUN");

      keyGen.initialize(1024, random);

      KeyPair pair = keyGen.generateKeyPair();
      RSAPrivateKey priv =
         (RSAPrivateKey)pair.getPrivate();
      RSAPublicKey pub =
         (RSAPublicKey)pair.getPublic();

      ...
  

Having generated the keys, we can use them to encrypt and decrypt messages. A simple example of this is shown in Listing 2. We get an instance of Cipher to do the actual encryption, initialise it with the required mode and RSA key, and set it to work on our message with a call to doFinal . Decryption works the same way. Note that the doFinal method works on byte arrays rather than strings (for various reasons, one of which is to allow it to encrypt more arbitrary data), so we have to convert between the two, but other than that there's very little effort we have to put in to get it to work.

Listing 2 shows a simple example using javax.crypto.Cipher.

    import javax.crypto.Cipher;

    ...

    // Create the cipher
    Cipher rsaCipher = Cipher.getInstance("RSA");

    // Initialize the cipher for encryption
    rsaCipher.init(Cipher.ENCRYPT_MODE, pub);

    // Cleartext
    byte[] cleartext = "This is just an example".getBytes();
    System.out.println("Original cleartext: " + new String(cleartext));

    // Encrypt the cleartext
    byte[] ciphertext = rsaCipher.doFinal(cleartext);
    System.out.println("Ciphertext: " + new String(ciphertext));

    // Initialize the same cipher for decryption
    rsaCipher.init(Cipher.DECRYPT_MODE, priv);

    // Decrypt the ciphertext
    byte[] cleartext1 = rsaCipher.doFinal(ciphertext);
    System.out.println("Final cleartext: " + new String(cleartext1));

    ...
  

Conclusions

RSA can be a complicated algorithm to fully understand, but using it in Java is relatively simple. If you take a look at the internal implementation of the algorithm (the source for the Java libraries is freely-downloadable), you'll see that the actual code which does the encryption and decryption amounts to a single line, namely a call to BigInteger.modPow . The only real work being done apart from that is converting between the textual and numeric representations of a message, and even that is relatively straightforward. This makes it easy to (for example) port the RSA implementation to other languages. For one of my current projects, I've ported it to PHP (another language for which a BigInteger class is conveniently available) with much less than an hour's work. Writing an implementation I trusted from scratch could easily have taken several days.

Ultimately, I hope that the message you'll take away from this article is that cryptography is interesting and worth exploring further. Algorithms like RSA may seem very mathematical and slightly scary, but with the ever-increasing emphasis placed on the security of our communications, it is vital that we make the effort to understand the tools we need to ensure it. Existing implementations of algorithms allow us to see how the mathematical theories translate into practical code, something that we as programmers can more readily understand, and are thus a valuable resource when trying to get to grips with a seemingly complicated algorithm like RSA.

Addendum

During the review process for this article, a number of interesting points were raised by the review team (many thanks). In particular, Roger Orr highlighted one very good reason for the Java implementers to choose byte arrays over strings for their implementation. Since the latter are immutable and Java itself is a garbage-collected language, the data contained in strings hangs around in memory until the garbage collector reclaims it. This can present a security hole, since anyone who can access your process's memory can continue to access (for example) the plaintext of your message, and you have no way to prevent this. Byte arrays, in contrast, don't suffer from the same issue, as the data in them can be manually overwritten with random rubbish.

The motto of this tale is that there is more to security than just cryptography. The best cryptography in the world won't help you if someone has access to your plaintext. This article doesn't pretend to be about security in general (it was intended more as a cryptographic taster), but it does go to show that security in a wider context can be seriously hard.