The RSA encryption algorithm was invented by Ronald Rivest, Adi Shamir, and Leonard Adleman in 1977. It is an asymmetric encryption algorithm that relies on the infeasibility of factoring large numbers. An asymmetric algorithm uses two differen keys: one public and one private. Someone who wants to send you a message privately uses the public key to encrypt their message. Messages encrypted with your public key can only be decrypted with your own private key, which you never have to send out. Other algorithms that rely on the same key for encryption and decryption are less secure, because the key has to be transmitted secretly.

Because of the enormity of the numbers generally used by the RSA algorithm, it is rarely used to encrypt entire messages. Rather, it is used to encrypt an encryption key which is then used to encrypt the message using a symmetric algorithm. This system has the benefit of being much faster than pure RSA, and it eliminates the security problems usually associated with symmetric algorithms.

The first step to creating an RSA key pair is to generate two prime numbers, usually called p and q. These numbers are generally several hundred bits long, but have no real constraints. Then we multiply p and q to get n, which is called the modulus. The length of the modulus is used to show the strength of the encryption: RSA-768 uses a 768 bit modulus, RSA-1024 has a 1024 bit modulus, etc. Then, we choose the public exponent, e, such that 1 < e < n and e is coprime (has no common prime factors) to (p-1)(q-1). The public key consists of the public exponent e and modulus n. Then, the private exponent d is calculated to be the inverse of e mod (p-1)(q-1). That is, ed-1 is divisible by (p-1)(q-1). The private key consists of the private exponent d and the modulus n.

A message is encrypted using RSA by first breaking it into blocks of certain lengths, such as 64 bits. Each of these blocks is considered to be one number, not a string of characters. Then, for each number m, we calculate the ciphertext c by the formula c = m^e % n, where ^ is the exponent operator and % is the modulus operator. To decrypt, we retrieve m from c by the formula m = c^d % n.

The difficulty of breaking this cryptosystem resides in getting the private exponent d from the public exponent e and the modulus n. The only way of doing this is to factor the modulus n into the prime numbers p and q. Currently, at the bit lengths used today (768+), this is not possible in a reasonable amount of time. RSA Security, Inc. sponsors challenges to determine the factoring capabilities of today's algorithms and hardware. The most recent challenge completed at the time of this writing was a 512-bit modulus. It took 292 personal computers approximately 3.7 months to complete the initial step. The final step took 224 hours and 3.2 GB of memory on a Cray supercomputer. The current RSA recommendation of 1024 bits is about 7 million times harder to factor than 512 bits, and would take 6 terabytes of memory, which is currently not available even on the most advanced supercomputers.

With access to a decent multiple-precision integer library, implementing an RSA cryptosystem is not difficult. Speed concerns are prohibitive with large messages, but with large enough bit lengths, it is nearly impossible to break.

Example Code