8.4 Building a Small RSA System

Section 8.3 built three tools:

• modular exponentiation performs arithmetic inside a finite residue system;

• the extended Euclidean algorithm finds modular inverses;

• the Chinese Remainder Theorem relates computations modulo different coprime factors.

RSA assembles these tools into a public-key cryptosystem.

This section uses tiny numbers so every step remains visible. Such keys are educational only and provide no real security.

The public-key idea

In a traditional shared-key system, the sender and receiver must already share one secret key.

A public-key system instead uses a related pair:

• a public key may be distributed to anyone and is used here for encryption;

• a private key is kept secret and is used here for decryption.

Knowing the public key should not make the private operation practical to reconstruct when real parameters are large.

RSA represents a message block by an integer $m$ in the range

where $n$ is part of the public key.

Euler’s totient counts invertible residues

Before generating keys, we need one new function.

For a positive integer $n$, Euler's totient function $\varphi(n)$ counts the integers in

that are coprime to $n$.

For example, the numbers below $10$ that are coprime to $10$ are

so

If $p$ is prime, every integer from $1$ through $p-1$ is coprime to $p$. Therefore

If $p$ and $q$ are distinct primes, then

One way to see this is to count numbers from $1$ through $pq$ and exclude multiples of $p$ or $q$. Inclusion–exclusion gives

Euler’s theorem explains the exponent cycle

Euler's theorem states that if $\gcd(m,n)=1$, then

This means that powers of a residue coprime to $n$ return to $1$ after an exponent of $\varphi(n)$.

RSA chooses two exponents whose product is congruent to $1$ modulo $\varphi(n)$. Euler's theorem then makes one exponent undo the other.

RSA key generation, one step at a time

Step 1: choose two distinct primes

Choose

Real RSA uses much larger randomly generated primes.

Step 2: form the modulus

Multiply the primes:

The modulus $n$ belongs to both keys.

Step 3: compute the totient

Because $p$ and $q$ are distinct primes,

Step 4: choose the public exponent

Choose an integer $e$ satisfying

and

Choose

It is valid because $\gcd(3,40)=1$.

Step 5: compute the private exponent

Choose $d$ as the modular inverse of $e$ modulo $\varphi(n)$:

Here

so

The resulting keys are

and

The primes and totient must also remain secret in a real system because they make $d$ easy to reconstruct.

Build a toy RSA key machine from prime cartridges. The workshop rejects repeated or composite inputs, maps every possible public exponent against the totient, and runs the extended Euclidean gears to derive a private exponent only when the inverse certificate is valid.

Encrypting a message block

With public key $(n,e)$, encrypt a message integer $m$ by computing

where $c$ is the ciphertext.

Let

It is a valid block because $0\le7<55$. Encrypt using $(55,3)$:

So the transmitted ciphertext is

Decrypting with the private exponent

Decrypt by computing

For the toy key,

Directly evaluating $13^{27}$ creates an unnecessarily large integer. Instead, use repeated squaring.

Compute powers whose exponents double:

Because

combine the corresponding rows:

Thus

which recovers the original message.

Why the exponents undo each other

The key equation

means that some integer $k$ satisfies

For a message $m$ coprime to $n$, Euler's theorem gives

Encryption followed by decryption raises $m$ to exponent $ed$, so the original residue returns.

This proof assumed $\gcd(m,n)=1$. RSA also works for all residues modulo a product of distinct primes; a complete proof checks the congruence separately modulo $p$ and modulo $q$, then uses the Chinese Remainder Theorem. The coprime case above contains the core exponent-cycle idea.

Repeated squaring is an algorithm

An exponent can be written as a sum of powers of $2$. Repeated squaring computes only those powers:

and reduces modulo $n$ after every multiplication.

This requires only $O(\log e)$ squaring and multiplication stages for exponent $e$, instead of multiplying $m$ by itself $e-1$ times. It connects modular arithmetic back to the logarithmic growth analysis of Chapter 5.

Route a numerical message through a public encryption booth and a private decryption booth. A live exponent ladder exposes each square-and-multiply residue, while tampering with the ciphertext or swapping the private exponent lets learners observe exactly when recovery fails.

Why the classroom system is not secure

Our modulus $55$ is immediately factored as $5\cdot11$. Anyone who factors $n$ can compute $\varphi(n)$ and reconstruct $d$ from public exponent $e$.

Real RSA security depends on carefully generated large primes and mature cryptographic implementations. Raw textbook RSA is deterministic and vulnerable to multiple attacks. Secure applications use standardized randomized padding, such as RSA-OAEP for encryption, and vetted libraries.

Never design a production cryptosystem by copying the toy arithmetic in this section. Its purpose is to reveal the mathematical mechanism, not to specify secure software.

Chapter bridge

Chapter 8 developed arithmetic structure for integers: divisibility led to unique prime factorizations, Euclid's algorithm produced gcd and Bézout coefficients, congruence created finite residue systems, CRT aligned several systems, and RSA combined them into a public-key mechanism.

Chapter 9 introduces discrete probability. Counting from Chapter 6 will define probabilities, while modular and cryptographic examples will motivate random choices and uncertainty.