7  RSA scheme I

The RSA scheme is one of the most important asymmetric-key systems, and is widely used as part of the steps in encrypting Internet communications.

The RSA scheme is named after the surnames of its three inventors: Ron Rivest, Adi Shamir, and Leonard Adleman. Although they were the first to publicly describe the RSA system in 1977, an equivalent algorithm had in fact been discovered four years ago by Clifford Cocks, who worked at GCHQ.

7.1 Introduction

The RSA scheme revolves around modular arithmetic, which the previous page touched briefly on.

Specifically, it assumes that the message you want to transmit is first translated into an integer \(m\) (which stands for message).

Question: Can you come up with a way of translating a plain-text message into an integer?

  1. The encoding step involves the sender taking the message \(m\) and raising it to a power \(e\) (for ‘encryption’), modulo some number \(n\):

    \[c \equiv m^e \mod n\]

    where \(c\) is the ciphertext. The combination of \(e\) and \(n\) forms the public key of the RSA scheme.

  2. This ciphertext is then passed to the recipient, who then decodes it by raising it to a power \(d\) (for ‘decryption’), modulo \(n\):

    \[m \equiv c^d \mod n.\]

    \(d\) forms part of the private key, which only the recipient is allowed to know.

The two equations above imply together that:

\[m \equiv (m^e)^d \mod n,\]

and crucially, this is true of all messages \(m < n\), meaning that the keys can be used for whatever message you choose to send.

In general, if we just pick any random numbers \(e\), \(d\), and \(n\), this will not be true! The RSA scheme works because these numbers are specifically chosen in a way that not only satisfies the equation above, but is also difficult to reverse-engineer.

Specifically, if you were an attacker and you knew the public key (i.e. \(e\) and \(n\)) as well as the ciphertext \(c\), it’s still extremely difficult to find the correct value of \(d\) to correctly decode the message.

7.2 Key generation

Because the RSA scheme is asymmetric, it only works for communication in one way. The recipient is responsible for generating the three integers \(e\), \(d\), and \(n\). They do so using the following algorithm:

  1. Choose two prime numbers \(p\) and \(q\), and set \(n = pq\).

    For example, if we choose \(p = 5\) and \(q = 13\), then \(n = 65\).

  2. Calculate the totient function, defined by \(\phi = (p - 1)(q - 1)\). (That symbol is the Greek letter phi.) In this case, we would have \(\phi = 4 \times 12 = 48\).

    Then, choose an integer \(e\) which is smaller than \(\phi\) and has no common prime factors with \(\phi\). Here, the only prime factors of \(48\) are \(2\) and \(3\): so, a valid choice would be \(e = 5\).

    \(e\) and \(n\) are part of the public key, and can be shared with the sender.

  3. Finally, choose \(d\) such that \(de \equiv 1 \bmod\phi\).

    In this case, we need \(d \times 5 \equiv 1 \bmod 48\): the smallest value of \(d\) for which this holds true is \(d = 29\). (Can you verify this?)

    \(d\) is part of the private key, and must be kept secret.

This setup ensures that regardless of what message \(m\) is being sent, \[(m^e)^d \equiv m \bmod n,\] as required by the RSA algorithm.

Try this out using the interactive form here. It has been pre-filled with the numbers from the example above, but you should try it out with your own choice of numbers.

  • Step 1: Choose \(p\) and \(q\) (must be prime)

    \(p\): \(q\):      

  • Step 2: Choose \(e\) (encryption key: must be smaller than \(\phi\), and cannot share prime factors with \(\phi\))

    \(e\):      

  • Step 3: Choose \(d\) (decryption key: must satisfy \(de \equiv 1 \bmod \phi\))

    \(d\):      

  • Step 4: Choose \(m\) (message: must be smaller than \(n\))

    \(m\):

7.3 Next steps

We’ve managed to show here that the RSA scheme works. However, there are several questions that remain:

  1. Unless you chose very small numbers for \(p\), \(q\), and \(e\), you probably found it hard to calculate \(d\). How can this be done quickly?
  2. How do we know that the RSA scheme is secure? Is it possible to obtain the private key, \(d\), if you have the public key (\(e\) and \(n\))?
  3. why does the RSA algorithm work at all, i.e. why is it always true that \((m^e)^d \equiv m \bmod n\)?

We’ll cover the first two questions in the remainder of today.

The proof that RSA works requires slightly more mathematical knowledge than we’ve seen so far, so we will not be covering it today. If you are curious, you can find it on Wikipedia!