The RSA public key cryptographic system

The RSA system was invented in 1977 by Ron Rivest, Adi Shamir and Leon Adleman (US patent 4,405,829). It is based on the assumption that it is easy to multiply two prime numbers, but difficult to divide the result again into the two prime numbers. To create her public/private key pair, and to encrypt and decrypt messages, Alice now must do some complicated calculations.

Because the RSA system is rather slow, it is most often used to encrypt a so-called "session key". This session key in turn is used to encrypt the actual message with a (fast) secret key encryption system.

Introduction

The RSA system involves several calculations modulo a certain number. Calculating modulo some number means that the outcome of a calculation can never be larger than this number. A common example is seconds and minutes on the clock. If it is now 14:58 and we add five minutes, the outcome is 15:03 and not 14:63. Time is thus calculated modulo 60. Using modulo calculation means that the mathematical computations can be implemented very efficiently.

Generating the RSA public and private keys

First, Alice chooses two large prime numbers, referred to as p and q. She then takes a number e that is not divisible by either p or q. The number e, together with the product of p and q is Alice's public key.

Second, Alice computes a number d that is the mathematical inverse of e when calculating modulo (p-1) times (q-1). This means that if you multiply e by d, and you divide the result by (p-1) times (q-1), you end up with 1. The number d, together with the product of p and q is Alice's private key.

The security of the RSA system lies in the fact that it is very difficult to compute p and q given only n. If Eve were able to find p and q, she could compute d just like Alice did and then she could read any message sent to Alice.

Encrypting and decrypting messages

To encrypt a message using Alice's public key, Bob first obtains a copy of this public key. He then raises the message to the power e modulo p times q. In mathematical notation, the encrypted message c is equal to me mod pq.

Alice subsequently raises the encrypted message c to the power d, also modulo p modulo q. This gives her the original message m. In mathematical notation: m = cd mod pq.

An example of RSA key generation and encryption

Let's say Alice chose as prime numbers p = 5 and q = 11. She then chooses e = 7, because 7 is not divisible by 5 or 11. Alice now must find a number d that, multiplied with 7, results in 1 modulo 40. After all, (5-1)*(11-1) = 4*10 = 40. Using trial and error Alice discovers that 23 times 7 equals 161, which is 4 times 40 plus 1. Hence she will use d = 23. If Alice were in a real-life situation instead of in this example, she would be using something called the extended Euclidian algorithm to efficiently compute the right value for d.

Now Bob receives a copy of Alice's public key, which is the number e = 7 and the number 55 (p times q). Bob now would like to send Alice the message "2". A simple message, but quite significant for Bob and Alice. Bob now computes 2 to the power of 7 modulo 55 as follows:

27 mod 55 = 128 mod 55 = 2*55 + 18 = 18 mod 55

When Alice receives the message "18" from Bob, she raises the message to the power 23, also modulo 55. This gives her:

1823 mod 55 = 181 *182 * 184 * 1816 mod 55 = 18*49*36*26 mod 55 = 825552 = 15010*55 + 2 = 2 mod 55.

And Alice knows what that means!