RSA Encryption algorithm

R.S.A. stands for Rivest, Shamir and Adleman - the three cryptographers who invented the first practical commercial public key cryptosystem. Today it is used in web browsers, email programs, mobile phones, virtual private networks, secure shells, and many other places. Exactly how much security it provides is debatable, but with sufficiently large keys you can be confident of foiling the vast majority of attackers. Until recently the use of RSA was very much restricted by patent and export laws. However, the patent has now expired and US export laws have been relaxed.

Introduction

The basics of cryptography - Alice wants to talk to Bob, in private. more...

RSA Algorithm

A description of the algorithm, and a simple example of its use. more...

Implementation

A simple implementation in Java, to demonstrate how this is done. more...

Practicalities

There are many practical issues to address when using cryptography, beyond just the algorithms. more...

Mathematics

A mathematical proof that RSA works, which I've made as simple as possible. more...

The Problem

Alice and Bob want to communicate in secret, while Eve wants to eavesdrop. Alice and Bob could be military jets, on-line businesses or just friends trying to have a private conversation. They can't stop Eve listening to their radio signals (or tapping their phone line, or whatever), so what can they do to keep their communication secret?

Symmetric Encryption

One solution is for Alice and Bob to exchange a digital key, so they both know it, but it's otherwise secret. Alice uses this key to encrypt messages she sends, and Bob reconstructs the original messages by decrypting with the same key. The encrypted messages (ciphertexts) are useless to Eve, who doesn't know the key, and so can't reconstruct the original messages. With a good encryption algorithm, this scheme can work well, but exchanging the key while keeping it secret from Eve is a problem. This really requires a face to face meeting, which is not always practical.

Public Key Encryption

Public key encryption is different, because it splits the key up into a public key for encryption and a secret key for decryption. It's not possible to determine the secret key from the public key. In the diagram, Bob generates a pair of keys and tells everybody (including Eve) his public key, while only he knows his secret key. Anyone can use Bob's public key to send him an encrypted message, but only Bob knows the secret key to decrypt it. This scheme allows Alice and Bob to communicate in secret without having to meet.

However, if Eve can tamper with Alice and Bob's communication as well as passively listening, she could substitute her public key for Bob's, and then decrypt Alice's messages using her own private key. The practicalities section explains how problems like this are avoided.

Overview

Key Generation Generate two large prime numbers, p and q Let n = pq Let m = (p-1)(q-1) Choose a small number e, coprime to m Find d, such that de % m = 1 Publish e and n as the public key. Keep d and n as the secret key.	Encryption C = Pe % n
	Decryption P = Cd % n
	x % y means the remainder of x divided by y

The reasons why this algorithm works are discussed in the mathematics section. Its security comes from the computational difficulty of factoring large numbers. To be secure, very large numbers must be used for p and q - 100 decimal digits at the very least.
I'll now go through a simple worked example.

Key Generation

1) Generate two large prime numbers, p and q

To make the example easy to follow I am going to use small numbers, but this is not secure. To find random primes, we start at a random number and go up ascending odd numbers until we find a prime. Lets have:

p = 7
q = 19

2) Let n = pq

n = 7 * 19
  = 133

3) Let m = (p - 1)(q - 1)

m = (7 - 1)(19 - 1)
  = 6 * 18
  = 108

4) Choose a small number, e coprime to m

e coprime to m, means that the largest number that can exactly divide both e and m (their greatest common divisor, or GCD) is 1. Euclid's algorithm is used to find the GCD of two numbers, but the details are omitted here.

e = 2 => GCD(e, 108) = 2 (no)
e = 3 => GCD(e, 108) = 3 (no)
e = 4 => GCD(e, 108) = 4 (no)
e = 5 => GCD(e, 108) = 1 (yes!)

5) Find d, such that de % m = 1

This is equivalent to finding d which satisfies de = 1 + nm where n is any integer. We can rewrite this as d = (1 + nm) / e. Now we work through values of n until an integer solution for e is found:

n = 0 => d = 1 / 5 (no)
n = 1 => d = 109 / 5 (no)
n = 2 => d = 217 / 5 (no)
n = 3 => d = 325 / 5 
           = 65 (yes!)

To do this with big numbers, a more sophisticated algorithm called extended Euclid must be used.

Public Key n = 133 e = 5

Secret Key n = 133 d = 65

Communication

Encryption

The message must be a number less than the smaller of p and q. However, at this point we don't know p or q, so in practice a lower bound on p and q must be published. This can be somewhat below their true value and so isn't a major security concern. For this example, lets use the message "6".

C = P^e % n
  = 6⁵ % 133
  = 7776 % 133
  = 62

Decryption

This works very much like encryption, but involves a larger exponentiation, which is broken down into several steps.

P = C^d % n
  = 62⁶⁵ % 133
  = 62 * 62⁶⁴ % 133
  = 62 * (62²)³² % 133
  = 62 * 3844³² % 133
  = 62 * (3844 % 133)³² % 133
  = 62 * 120³² % 133

We now repeat the sequence of operations that reduced 62⁶⁵ to 120³² to reduce the exponent down to 1.

  = 62 * 36¹⁶ % 133
  = 62 * 99⁸ % 133
  = 62 * 92⁴ % 133
  = 62 * 85² % 133
  = 62 * 43 % 133
  = 2666 % 133
  = 6

And that matches the plaintext we put in at the beginning, so the algorithm worked!