This is an article in a series on Cryptography for the Everyday Developer. Follow along to learn the basics of modern cryptography and encryption.

Modern cryptography relies heavily on number theory. One of the simplest but most important tools in the number theorist’s toolkit is the Euclidean algorithm. This algorithm, and its extension, the extended Euclidean algorithm, form the basis for practical cryptographic operations such as modular inversion. This blog post walks through both algorithms, with an explanation of why they are important to public key cryptography.

The Greatest Common Divisor

To begin, let’s start with the greatest common divisor ($gcd$). The greatest common divisor of two integers is the largest integer that divides both without leaving a remainder.

A common solution for finding the greatest common divisor is prime factorization: continuously divide the number by the smallest prime that divides evenly. For example, consider the two numbers $r_0 = 27$ and $r_1 = 21$.

The prime factorization of $r_0 = 3 \cdot 3 \cdot 3 = 27$. Similarly, the prime factorization of $r_1 = 3 \cdot 7 = 21$. With this factorization in hand, you can find the greatest common divisor by finding the largest common prime factor between the two numbers. In this case, the greatest common factor, or $\gcd$ is $3$, written as $\gcd(27,21) = 3$.

Prime factorization works fine for small numbers. But cryptography deals with numbers that are hundreds or thousands of digits long, and finding prime factors for those numbers is essentially impossible with any known algorithms. We need a faster approach, which is provided by the Euclidean algorithm.

The Euclidean Algorithm

The Euclidean algorithm computes the $\gcd$ without relying on factorization by repeatedly applying the following identity:

$$ \gcd(a,b) = \gcd(b, a \mod b) $$

In other words, the $\gcd$ doesn’t change if we replace the larger number, $b$, with the remainder when dividing by the smaller number, $a \mod b$. We repeat this process until the remainder is zero. The last non-zero remainder is the $\gcd$.

In pseudocode, the algorithm can be expressed simply. For example, in Python, which allows assigning to multiple variables in a single operation, the entire algorithm for $\gcd$ is:

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

This process scales easily to large numbers, and it is efficient: the number of steps grows logarithmically with the size of the numbers.

The Extended Euclidean Algorithm

The Extended Euclidean Algorithm finds not just the $\gcd$ of two numbers, but also expresses that $\gcd$ as a linear combination of those numbers.

$$ \gcd(a,b) = a \cdot x + b \cdot y $$

For example, we can take two numbers $240$ and $46$ and express the $\gcd$ as $\gcd = 240 \cdot x + 46 \cdot y$. To do this, we repeat the procedure used for the regular Euclidean algorithm, but keep track of some of the values used along the way. According to the Euclidean algorithm, we can find $\gcd(240, 46)$ with the following steps:

240 = 46 × 5 + 10
46 = 10 × 4 + 6
10 = 6 × 1 + 4
6 = 4 × 1 + 2
4 = 2 × 2 + 0

So $\gcd(240, 46) = 2$.

Now, we work backwards to express our final answer $2$ in terms of $240$ and $46$ by using regular algebraic substitutions that keep our final answer $2$ on the left-hand side of the equation:

2 = 6 - 4 × 1
2 = 6 - (10 - 6 × 1) × 1
2 = 6 × 2 - 10 × 1
2 = (46 - 10 × 4) × 2 - 10 × 1
2 = 46 × 2 - 10 × 9
2 = 46 × 2 - (240 - 46 × 5) × 9
2 = 46 × 47 - 240 × 9

The end result is $2 = 240 \cdot (-9) + 46 \cdot 47$ which can be verified as $240(-9) + 46(47) = -2160 + 2162 = 2$

This may look abstract, but the result is crucial in practice: it gives us a way to compute modular inverses, which are essential to public key cryptography.

Modular Inverses

In modular arithmetic, we often want to “divide” by a number. Unfortunately, division in the usual sense doesn’t exist with modular numbers, and instead we use the modular inverse operation.

A modular inverse of a modulo $m$ is a number $x$ such that:

$$ a \cdot x \equiv 1 \mod m $$

In other words: $a \cdot x = 1 + k \cdot m$ for some integer $k$, which rearranges to $1 = a \cdot x − k \cdot m$. This looks very much like the equation for computing the $\gcd$ as a linear combination using the Extended Euclidean Algorithm. This ability to compute modular inverses efficiently is critical for public-key cryptography; it allows us to “undo” modular multiplication.

Euler’s Totient Function: The Key to RSA

To understand how modular inverses enable encryption, we need to introduce Euler’s totient function, denoted $\phi(n)$. This function counts how many positive integers less than $n$ are coprime to $n$ (share no common factors except 1).

The totient function has two elegant properties:

For a prime $p$, every number less than $p$ is coprime to it, so $\phi(p) = p - 1$
For a product of two primes $p$ and $q$, if $n = p \cdot q$, then $\phi(n) = (p - 1) \cdot (q - 1)$

Euler’s theorem gives us the crucial insight: if $\gcd(a, n) = 1$, then:

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

This seemingly abstract property is what makes RSA encryption possible.

From Number Theory to Cryptography

So far we have dealt with abstract number theory, which is difficult to follow. To connect this to cryptography, we can simplify things down by exploiting an asymmetry in how we compute multiplication and division using modular arithmetic. In particular, there are some operations that are easy to calculate, and some that are hard.

Easy operations: Multiplication and exponentiation modulo $n$
Hard operations: Finding modular inverses and factoring large numbers

RSA exploits this asymmetry for secure encryption by exploiting a simple fact: recovering the private key from the public values requires factoring the key into its prime factors, which is a hard problem. On the other hand, generating a private key is relatively easy: remember the coefficients calculated using the Extended Euclidean Algorithm? They’re exactly what we need to generate the private key that makes RSA work.

Choose two large prime numbers, $p$ and $q$, and compute $n = p \cdot q$
Calculate $\phi(n) = (p - 1) \cdot (q - 1)$
Select a exponent $e$ that is coprime to $\phi(n)$. $e$ is the public portion of the RSA public-private key.
Use the Extended Euclidean Algorithm to find the modular inverse $d$, where $e \cdot d \equiv 1 \mod \phi(n)$

The pair $(e, n)$ becomes your public key that anyone can use to encrypt messages. The pair $(d, n)$ becomes your private key that only you possess for decryption.

Encryption and Decryption:

With these values in hand, encryption and decryption are relatively easy operations:

To encrypt a message $m$, compute $c = m^e \mod n$
To decrypt a ciphertext $c$, compute $m = c^d mod n$

The security of RSA rests on a simple fact: recovering the private key $d$ from the public values $e$ and $n$ requires factoring $n$ into its prime factors $p$ and $q$. Without that factorization, you cannot compute $\phi(n)$, and without $\phi(n)$, you cannot find $d$.

This is where the Extended Euclidean Algorithm proves its worth. Those coefficients we calculated earlier? They’re exactly what we need to generate the private key that makes RSA work. The gap between easy multiplication and hard factorization isn’t just a mathematical curiosity—it’s the cornerstone of modern public-key cryptography that secures everything from online banking to encrypted messaging.

The Greatest Common Divisor#

The Euclidean Algorithm#

The Extended Euclidean Algorithm#

Modular Inverses#

Euler’s Totient Function: The Key to RSA#

From Number Theory to Cryptography#