RSA Cryptography

Farhad Babaee·University of Bristol

Interactive notes from an outreach session on RSA cryptography (2025).

Introduction

Coding and decoding are constantly happening in our daily lives. Not only when you use your phone, but even now — as I am typing these words and you are reading them later — some of the most complex encoding and decoding imaginable is taking place. The thoughts in my head, arising from electrical activity and chemical processes in my brain cause my brain to send precise signals to my muscles, transforming intention into motion, and motion into words typed on a keyboard which is already several steps of encoding and decoding. As you read this text, your eyes decode patterns of light into letters, recognise words in the English language, and even detect and ignore irregularities such as typos (error-correction). Finally, these symbols transform into electrical signals and chemical processes in your brain, and my message is conveyed.

The purpose of these notes is to acquaint you with one particular method of coding and decoding used to secure our data: the RSA cryptosystem. As described on Wikipedia, the RSA cryptosystem is a public-key cryptosystem , and one of the oldest and most widely used methods for secure data transmission. The initialism “RSA” comes from the surnames of Ron Rivest, Adi Shamir, and Leonard Adleman, who publicly described the algorithm in 1977. An equivalent system was developed secretly in 1973 at the Government Communications Headquarters (GCHQ), the British signals intelligence agency, by the English mathematician Clifford Cocks, and was declassified in 1997. \[ 7 \equiv 1 \pmod 3. \]

In general, two numbers $a$ and $b$ are said to be congruent modulo $n$ if they have the same remainder when divided by $n$. We write this as:

\[ a \equiv b \pmod{n}. \]

This simply means that:

\[ a \text{ and } b \text{ leave the same remainder upon division by } n, \]

or equivalently,

\[ n \mid (a - b). \]

Modular Clocks

Can you reach a streak of 5 for the following game?

Modular Arithmetic Tricks with Congruences

Congruences behave very nicely with addition, subtraction, multiplication, and powers. If

\[ a \equiv b \pmod{n} \qquad\text{and}\qquad c \equiv d \pmod{n}, \]

then the following rules always hold:

\[ a + c \equiv b + d \pmod{n}, \] \[ ac \equiv bd \pmod{n}, \] \[ a^m \equiv b^m \pmod{n} \qquad \text{for any integer } m \ge 1. \]

These rules let us replace numbers with simpler congruent ones to make computations easier.

Examples

• Addition example: $17 \equiv 2 \pmod{5}$ and $23 \equiv 3 \pmod{5}$. Therefore, \[ 17 + 23 \equiv 2 + 3 \equiv 5 \equiv 0 \pmod{5}. \]
• Multiplication example: $14 \equiv 2 \pmod{12}$ and $11 \equiv -1 \pmod{12}$. Then \[ 14 \cdot 11 \equiv 2 \cdot (-1) \equiv -2 \equiv 10 \pmod{12}. \]
• Powers example: $7 \equiv -1 \pmod{8}$. Then \[ 7^2 \equiv (-1)^2 = 1 \pmod{8},\qquad 7^5 \equiv (-1)^5 = -1 \equiv 7 \pmod{8}. \]
• Another addition example: $52 \equiv 4 \pmod{6}$ and $19 \equiv 1 \pmod{6}$. Thus \[ 52 + 19 \equiv 4 + 1 = 5 \pmod{6}. \]
• Another multiplication example: $35 \equiv 3 \pmod{4}$ and $22 \equiv 2 \pmod{4}$. So \[ 35 \cdot 22 \equiv 3 \cdot 2 = 6 \equiv 2 \pmod{4}. \]
• Another powers example: Since $9 \equiv -1 \pmod{10}$, \[ 9^3 \equiv (-1)^3 = -1 \equiv 9 \pmod{10}. \]

These “magic tricks” let us simplify huge numbers by replacing them with small, congruent ones. But are these really magic or simple maths ideas? How do we prove that they actually hold and are valid?

How is RSA done?

In RSA, we start with two large primes $p$ and $q$, and compute $n = p \times q$. We also compute Euler’s function $\varphi(n) = (p - 1)(q - 1)$. We choose an encryption exponent $e$ such that $\gcd(e, \varphi(n)) = 1$, and compute the decryption exponent $d$ as the modular inverse of $e$ modulo $\varphi(n)$, so that:

\[ e \times d \equiv 1 \ (mod~\varphi(n)). \]

I'll skip the details of this computation, but this task is not difficult and it can be done using Bézout's identity

Assume Alice wants to send a message to Bob:

1. Bob generates an RSA key pair: public key $(n, e)$ and private key $d$.
2. Bob shares his public key $(n, e)$ openly. His private key $d$ is kept secret.
3. Alice converts her message to $m$ (a numerical form).
4. Alice encrypts $m$ using Bob’s public key: $c \equiv m^e \ (mod~n)$ (Encryption -- see Task 5 below).
5. Alice sends the ciphertext $c$ to Bob over an open channel.
6. Bob receives $c$ and decrypts it using his private key: $m \equiv c^d \ (mod~n)$ (Decryption -- see Task 7 below).
7. Bob recovers and reads the original message $m$.

This process ensures confidentiality: only Bob can decrypt the message because only he knows $d$.

Euler's Theorem

Behind this cryptographic method lies a mathematical idea that has been around for centuries, discovered by Leonhard Euler (1707–1783). To understand why RSA works, we first need to discuss Euler’s totient function.

We mentioned earlier that $\varphi(pq) = (p-1)(q-1)$ when $p$ and $q$ are distinct primes, but we have not yet properly defined what $\varphi(n)$ actually is.

The function $\varphi(n)$ is defined as the number of positive integers less than $n$ that are coprime to $n$ (that is, integers whose greatest common divisor with $n$ is $1$).

For example, to compute $\varphi(9)$, we list the numbers \[ \{1,2,3,4,5,6,7,8\} \] and cross off those that are not coprime to $9$. Since $3$ and $6$ share a common factor with $9$, they are excluded. The remaining numbers are $\{1,2,4,5,7,8\}$, so \[ \varphi(9) = 6. \]

Similarly, since $7$ is prime, every number less than $7$ is coprime to it. Therefore, \[ \varphi(7) = 6. \]

In general, Euler’s totient function satisfies two important properties:

• If $\gcd(a,b)=1$, then \[ \varphi(ab) = \varphi(a)\varphi(b). \]
• If $p$ is a prime number and $k \ge 1$, then \[ \varphi(p^k) = p^k - p^{k-1}. \]

Using these properties, we can easily compute $\varphi(n)$ when $n$ is a product of prime powers. In particular, if $n = pq$ with $p$ and $q$ distinct primes, then \[ \varphi(n) = (p-1)(q-1), \] which is exactly the formula used in RSA.

Euler’s Totient Theorem states that for any integer $a$ coprime to $n$:

\[ a^{\varphi(n)} \equiv 1 \pmod{n}. \]

In RSA, Euler’s theorem ensures that encryption and decryption correctly reverse each other when the message is coprime to $n$.

Why does RSA work?

To rely on a cryptographic method and to be sure that it always works, we need a bulletproof fact — something that can be shown to hold in all cases. Euler’s Theorem provides exactly that guarantee.

Why is the statement above bulletproof? Because it follows from a precise mathematical argument.

Factoring $n$ is hard

The security of RSA relies on the difficulty of factoring large integers $n = pq$, where $p$ and $q$ are large primes. The best classical algorithm known for factoring, the General Number Field Sieve (GNFS), has a sub-exponential running time. Below is a summary of the approximate feasibility of factoring different RSA key sizes; see [3].

Key Size (bits)	Approx. Digits	Status	Feasibility	Approximate Effort
512	155	Broken	Easy	Already factored; weeks
1024	308	Weak	Hard, possible in future	100,000 core-years
2048	617	Recommended	Infeasible	Billions of years estimated
3072	925	Strong	Infeasible	Beyond realistic capacity
4096	1234	Very strong	Infeasible	Beyond realistic capacity

Fermat's theorem and Fermat primality test

Mathematicals can come up with all sort of ideas to solve a problem. For example Fermat's little Theorem and probability tools to decompose a number into primes factors. Recall that Fermat's Little Theorem states that if $p$ is prime and $a$ is an integer not divisible by $p$, then:

\[ a^{p-1} \equiv 1 \ (mod~p). \]

Fermat primality test uses this to check if a number $n$ is prime:

1. Pick a random integer $a$ such that $1 < a < n - 1$.
2. Compute $a^{n-1} \mod~n$.
3. If result $\neq 1$, $n$ is composite.
4. If result $= 1$, $n$ is probably prime! (but might still be a Carmichael number).

This is a probabilistic test and may give false positives.

Order of $g$ and Shor's algorithm (Quantum Attack!)

I know a little about this, but as I explained during the session, for any integer $g$ coprime to $n$, there exists a smallest positive integer $p$ (called the order of $g$ modulo $n$) such that:

\[ g^p \equiv 1 \ (mod~n). \]

The idea is that starting from a guess which is a factor of $n$, $(g^{p/2} - 1)$ or $(g^{p/2} + 1)$ is a much better guess for being a factor of $n$. If we find one factor for $n$, since $n = pq$, then we are done! Finding this order is a hard problem classically and is related to factoring. Shor's algorithm, developed by Peter Shor, is a quantum algorithm that can efficiently find the order of $g$ modulo $n$. By finding this order, one can factor $n$ and break RSA security. Thus, quantum computers with enough qubits can break RSA by using Shor's algorithm, which is why post-quantum cryptography is being developed.

So we don't know for how long RSA will be safe. It's on the new generation of mathematicians to come up with new methods for cryptography! For details, see [2].

---

RSA Workshop Tasks

Task 1: Prime Identification

Identify whether each of the following numbers is prime:

\[ 11,\ 14,\ 17,\ 21,\ 23,\ 25,\ 29,\ 33,\ 37,\ 39. \]

Task 2: Coprime Pairs

Determine if the following pairs are coprime (i.e. $\gcd(a,b) = 1$):

\[ \begin{aligned} &(8, 15),\quad (14, 21),\quad (9, 16),\quad (10, 17),\\ &(18, 27),\quad (11, 20),\quad (12, 25),\quad (13, 22). \end{aligned} \]

Task 3: Compute $n$ and $\varphi(n)$

For each pair of primes $p$ and $q$, compute

\[ n = pq,\qquad \varphi(n) = (p-1)(q-1). \]

$p$	$q$	$n = pq$	$\varphi(n)$
3	11
5	13
7	17
11	19
13	23
17	29

Task 4: Choose $e$

For each case, choose an encryption exponent $e$ such that

\[ 1 < e < \varphi(n), \qquad \gcd(e,\varphi(n)) = 1. \]

$p$	$q$	$n$	$\varphi(n)$	$e$
3	11	33	20
5	13	65	48
7	17	119	96
11	19	209	180
13	23	299	264
17	29	493	448

Task 5: Encryption

Compute the ciphertext $c \equiv m^e \pmod n$ for each case.

Task 6: Verify the Key Equation

For each line below, you are given $p$, $q$, $n$, $\varphi(n)$, the encryption exponent $e$, and an explicit decryption exponent $d$.

$p$	$q$	$\varphi(n)$	$e$	$d$	$ed \equiv ?$ (mod $\varphi(n)$)
3	11	20	3	7
5	13	48	5	29
7	17	96	5	77
11	19	180	7	103
13	23	264	5	53
17	29	448	3	299

Task 7: Decryption

Below are the ciphertexts $c$ you obtained in Task 5 and the corresponding decryption exponents $d$ from Task 6.

Case	$n$	$c \equiv m^e \ (mod~n)$	$d$	$c^d \ (mod~n)$
(a)	33	8	7
(b)	65	48	29
(c)	119	4	77
(d)	209	136	103
(e)	299	156	53
(f)	493	343	299

Compute the decrypted message for each line by evaluating

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

and confirm that you recover the original message $m$.

Task 8: Hacking. Factor $n$ and Find $\varphi(n)$

For each $n$ below:

1. Factor $n$ as $n = pq$ with $p$ and $q$ prime.
2. Compute $\varphi(n)$.

\[ 1241,\quad 4579,\quad 84611,\quad 273307,\quad 716141. \]

References

1. [1]Lenstra, A. K., & Verheul, E. R. (2001). Selecting Cryptographic Key Sizes. Journal of Cryptology. Available at: https://www.iacr.org/archive/asiacrypt2001/22480516.pdf
2. [2]Shor, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5), 1484–1509.
3. [3]RSA Factoring Challenge Results. See: https://en.wikipedia.org/wiki/RSA_Factoring_Challenge