RSA Cryptography: Alice and Bob

Bob and Alice sending each other messages (AI generated picture)

Imagine trying to piece together a jigsaw puzzle with thousands of scattered pieces. It’s easy to make a mess, but nearly impossible to reassemble without knowing the original pattern. This is the core of a one-way function: simple to compute in one direction, but fiendishly difficult to reverse if you don’t know how the key. In the 1970s, as the world was on the brink of the digital age, scientists needed such a puzzle to protect sensitive information. The concept of a public-key cryptosystem had been theorized by Whitfield Diffie and Martin Hellman, where anyone could lock a message, but only the rightful owner could unlock it. The key missing piece? A one-way function that could scramble information beyond recognition, while allowing only those with the private key to restore it.

Unbeknownst to the public, British mathematician Clifford Cocks had secretly solved this puzzle in 1973 while working for the Government Communications Headquarters (GCHQ), but his work remained classified for decades. Meanwhile, in the open scientific community, Ron Rivest, Adi Shamir, and Leonard Adleman took on the same challenge. After months of failed attempts, including experiments with “knapsack-based” functions and polynomials, Rivest had a flash of insight during a sleepless night after a Passover dinner in 1977. By dawn, the RSA algorithm had taken form. This breakthrough, based on the complexity of factoring large prime numbers, would become the backbone of modern cryptography

In the RSA cryptosystem, Alice wants to send a secure message to Bob. Bob generates a pair of keys—one public and one private. Alice uses Bob’s public key to encrypt the message, and Bob uses his private key to decrypt it.

2. Key Generation (What Bob Does)

Bob generates his key pair as follows:

Bob chooses two large prime numbers, ${p}$ and ${q}$ .
He computes ${n = p \times q}$ , which is part of both his public and private keys.
Bob calculates Euler’s totient function ${\phi(n) = (p - 1)(q - 1)}$ , which is crucial for generating the private key.
Bob chooses an integer ${e}$ such that ${1 < e < \phi(n)}$ and ${\gcd(e, \phi(n)) = 1}$ . This ${e}$ is part of Bob’s public key.
He computes the modular inverse ${d}$ of ${e \mod \phi(n)}$ , i.e., ${e \cdot d \equiv 1 \pmod{\phi(n)}}$ . This ${d}$ is Bob’s private key.

Bob now has:

Public key: ${(n, e)}$ , which he shares with Alice.
Private key: ${(n, d)}$ , which he keeps secret.

3. Encryption (What Alice Does)

Alice encrypts the message ${M}$ using Bob’s public key:

Alice converts her message ${M}$ to a number such that ${0 \leq M < n}$ .
Alice calculates the ciphertext ${C}$ using Bob’s public key:
$\displaystyle C = M^e \mod n$
Alice sends the ciphertext ${C}$ to Bob.

4. Decryption (What Bob Does)

Bob decrypts Alice’s ciphertext using his private key:

Bob computes the original message ${M}$ by applying his private key:
$\displaystyle M = C^d \mod n$
Bob recovers the original message ${M}$ .

5. Example of RSA with Alice and Bob

Let’s go through an example where Alice sends Bob a message.

5.1. Key Generation (Bob’s Step)

Bob chooses ${p = 61}$ and ${q = 53}$ .
He calculates ${n = 61 \times 53 = 3233}$ .
He computes ${\phi(n) = (61 - 1)(53 - 1) = 3120}$ .
Bob selects ${e = 17}$ , where ${\gcd(17, 3120) = 1}$ .
Bob computes ${d = 2753}$ as the modular inverse of ${e \mod \phi(n)}$ .

Bob’s public key is ${(3233, 17)}$ and his private key is ${(3233, 2753)}$ .

5.2. Encryption (Alice’s Step)

Alice wants to send ${M = 65}$ to Bob. She encrypts the message using Bob’s public key:

$\displaystyle C = 65^{17} \mod 3233 = 2790$

Alice sends ${C = 2790}$ to Bob.

5.3. Decryption (Bob’s Step)

Upon receiving the ciphertext ${C = 2790}$ , Bob decrypts it using his private key:

$\displaystyle M = 2790^{2753} \mod 3233 = 65$

Thus, Bob recovers ${M = 65}$ .

6. Definitions and Theorems Used in RSA

Now that we are familiar with the RSA protocol we would like to better understand the math behind it: To do so we will cover a special case of Euler’s totient function, and then use it in Euler’s theorem, visit a law of how to divide congruences (‘modulo formulas’), and finally put the pieces of the puzzle together and prove the correctness of the ‘RSA way’ to recover a message.

6.1. Euler’s Totient Function

Euler’s totient function ${\phi(n)}$ is a central concept in number theory. For a given integer ${n}$ , ${\phi(n)}$ is defined as the number of positive integers less than ${n}$ that are coprime with ${n}$ (i.e., integers whose greatest common divisor with ${n}$ is 1).

In RSA, this function is used in the key generation process to help compute the private key. Computing the totient is easy in this case: if ${n=p \times q}$ where ${p}$ and ${q}$ are primes, then:

$\displaystyle \phi(n) = (p-1)(q-1)$

This is because the only numbers that divide ${pq}$ are ${p}$ and ${q}$ and thus the only non-coprime numbers are ${q, 2q, ..., (p-1)q}$ and ${p, 2p, ..., (q-1)p}$ . Now, to get the totient, let’s substract the number of non-coprime numbers, including the number ${1}$ , from ${n = pq}$ and obtain the result: ${pq-(p-1)-(q-1)-1}$ ${= pq-p-q+2 = (p-1)(q-1)}$

The totient function has many interesting properties and is deeply connected with modular arithmetic and cryptography. There will be a dedicated blog entry on Euler’s totient function in the near future, where its importance and fascinating properties will be explored in more detail.

6.2. Euler’s Theorem

Euler’s theorem states that if ${n}$ is a positive integer and ${a}$ is an integer such that ${\gcd(a, n) = 1}$ , then:

$\displaystyle a^{\phi(n)} \equiv 1 \pmod{n}$

where ${\phi(n)}$ is Euler’s totient function.

In RSA, Bob uses this theorem to ensure that his decryption works correctly. Specifically, if ${M}$ is coprime with ${n}$ , then:

$\displaystyle M^{\phi(n)} \equiv 1 \pmod{n}$

This result is crucial when proving that the RSA decryption correctly recovers Alice’s message.

6.3. Theorem on Congruences and Coprimes

Another key result used in RSA is the fact that if ${\gcd(a, m) = 1}$ , then congruences are invariant under division by ${a}$ . That is, if:

$\displaystyle a \cdot x \equiv a \cdot y \pmod{m}$

then it follows that:

$\displaystyle x \equiv y \pmod{m}$

This theorem is used when Bob computes his private key ${d}$ , as he ensures that ${e \cdot d \equiv 1 \pmod{\phi(n)}}$ , allowing the modular inverse to exist.

7. Proof of Correctness

We can now prove that Bob always recovers Alice’s message correctly. We need to show:

$\displaystyle M = C^d \mod n = (M^e)^d \mod n$

We know that ${e \cdot d \equiv 1 \pmod{\phi(n)}}$ , so there exists an integer ${k}$ such that:

$\displaystyle e \cdot d = 1 + k \cdot \phi(n)$

Thus, we have:

$\displaystyle M^{e \cdot d} = M^{1 + k \cdot \phi(n)} = M \cdot (M^{\phi(n)})^k$

By Euler’s theorem, ${M^{\phi(n)} \equiv 1 \pmod{n}}$ since ${\gcd(M, n) = 1}$ . Hence:

$\displaystyle M^{e \cdot d} \equiv M \pmod{n}$

This proves that decryption correctly recovers Alice’s original message ${M}$ .

8. Historical Background

The RSA algorithm was introduced in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman, hence the name RSA. This cryptosystem revolutionized digital security by introducing public-key cryptography, where encryption and decryption are done using different keys, unlike symmetric key algorithms that require the same key for both.

Clifford Cocks, an English mathematician working for the British intelligence agency Government Communications Headquarters (GCHQ), described a similar system in an internal document in 1973. However, given the relatively expensive computers needed to implement it at the time, it was considered to be mostly a curiosity and, as is publicly known, never deployed. His ideas and concepts were not revealed until 1997 due to its top-secret classification.

The concept of public-key cryptography was first proposed by Diffie and Hellman in 1976, but it was RSA that provided a practical and widely applicable method. Diffie and Hellman already used modular exponentiation, but did not consider prime factorization. The security of RSA relies on the difficulty of factoring large composite numbers, which has remained computationally challenging despite advances in algorithms and hardware.

However, Shor’s algorithm, a quantum algorithm developed by Peter Shor in 1994, can factor large numbers efficiently (making use of the very fast – logarithmic time complexity – quantum Fourier transformation). This means that Shor’s algorithm can efficiently solve the step of breaking down ${n = p \times q}$ into its prime factors ${p}$ and ${q}$ . If a quantum computer with sufficient number of qbits and precision is built, it would be able to use Shor’s algorithm to break RSA encryption by deriving the private key from the public key.

While classical algorithms for factoring take exponentially long for large numbers, Shor’s algorithm performs this task in polynomial time, posing a serious threat to RSA-based cryptography if large-scale quantum computers become a reality.

Interactive Python Demo: Bob and Alice in Cryptoland

In the appendix of this article, you will find a link to an interactive Python demonstration titled Bob and Alice in Cryptoland. This engaging visual tool illustrates the RSA encryption and decryption process using a familiar narrative: Bob and Alice exchanging secure messages.

The tooldemonstrates the core steps of the RSA protocol:

Key Generation: Bob’s process of creating the public and private keys.
Encryption: Alice’s transformation of her message into a ciphertext using Bob’s public key.
Decryption: Bob’s use of his private key to decrypt the ciphertext and recover the original message.

You can interact with the demo by generating new RSA keys or encrypting random messages, and follow the cryptographic process visually. The program uses arrows and step-by-step explanations to show how the information flows between Bob and Alice, making the RSA protocol easier to understand in practice. \medskip

Try it yourself and explore how RSA encryption works! You can access the demo through the following link: Interactive Python RSA Demo.

References

Rivest, R. L., Shamir, A., & Adleman, L. (1978). A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 21(2), 120-126.
Diffie, W., & Hellman, M. E. (1976). New Directions in Cryptography. IEEE Transactions on Information Theory, 22(6), 644-654.
Cocks, C. (1973). A Note on Non-Secret Encryption. GCHQ Document, Declassified in 1997.
Wilson, R. (2020). Number Theory: A Very Short Introduction (Vol. 636). Oxford University Press, USA.

Michael Emmerich

RSA Cryptography: Alice and Bob

Leave a comment Cancel reply

RSA Cryptography: Alice and Bob

Share this:

Leave a comment Cancel reply