Skip to main content

Section 4.6 The RSA Cryptosystem

The RSA Cryptosystem (after Rivest, Shamir, Adleman) is a public-key cryptosystem that is used for data transmission. A public key (based on two large primes \(p\) and \(q\)) is given out, and anyone who would like to send a message to the receiver can use this public key to encrypt the data. Any encrypted message can only be decrypted with the private key, that only the receiver knows. This is based on the fact that factoring the number \(N = pq\) is very difficult.

Before exploring the RSA Cyptosystem, first try proving the following two statements:

Suppose \(p\) is prime and \(e \geq 1\) such that \(\gcd(e,p-1) = 1\text{.}\)

  1. Why does \(e\) have an inverse modulo \(p-1\text{?}\)
  2. Prove that the congruence
    \begin{equation*} x^e \equiv c \pmod{p} \end{equation*}
    has the unique solution \(x \equiv c^d \pmod{p}\) where \(d\) is the inverse of \(e\) modulo \(p-1\text{.}\)

Suppose \(p,q\) are distinct primes and \(e \geq 1\) such that \(\gcd\left(e,(p-1)(q-1)\right) = 1\text{.}\) Prove that the congruence

\begin{equation*} x^e \equiv c \pmod{pq} \end{equation*}

has the unique solution \(x \equiv c^d \pmod{pq}\) where \(d\) is the inverse of \(e\) modulo \((p-1)(q-1)\text{.}\)

Exploration 4.6.1. Alice sends Bob a message.

Suppose that Alice wants to send Bob an encrypted message, so that eavesdroppers are not able to decipher the data being transmitted. Bob sets up a public key as follows:

  • Bob takes the two primes \(p = 7\) and \(q = 13\text{,}\) and multiplies them to get \(N = 91\text{.}\)
  • Bob then picks another number \(e\) such that \(\gcd(e,(p-1)(q-1)) = 1\text{.}\) Suppose he chooses \(e=5\text{.}\)

He then publishes the pair \((N = 91,e = 5)\) as his public key.

(a)

Bob will later need the inverse \(d\) of \(e=5\) modulo \((p-1)(q-1)\text{.}\) What is \(d\text{?}\) (The integer \(d\) is the private key of the RSA algorithm.)

Now suppose that Alice wants to send the message ROFL, which she encodes as the four numbers \(18 \ 15 \ 6 \ 12\text{.}\) Alice will now use Bob's public key \((N,e)\) to encrypt her message.

(b)

Encrypt each of Alice's four numbers by compute \(x^e \mmod{N}\) for each one. For instance, when \(x = 18\text{,}\) we get \(18^5 \mmod{91} = 44\text{.}\)

(c)

Raise each result from the previous part to \(d\) modulo \(N\text{.}\) This is how Bob decrypts Alice's transmission, so \(d\) is sometimes called the decryption key.

(d)

Explain why exponentiating each part of the encrypted message to \(d\) yields the original message from Alice.

Note that the choice of \(N = 91\) in Exploration 4.6.1 was to merely illustrate how the RSA Cryptosystem works. Practically speaking, the two primes \(p\) and \(q\) would have to be very large in order that \(N = pq\) be very difficult to factor (and hence make \(d\) difficult to obtain).

Write up a complete general explanation of how and why the RSA Cryptosystem works.

Explain why in Checkpoint 4.6.2 it suffices to pick \(d\) to be an inverse of \(e\) modulo

\begin{equation*} \frac{(p-1)(q-1)}{\gcd(p-1,q-1)} \end{equation*}

instead of modulo \((p-1)(q-1)\text{.}\)