Identity

In this post, we'll explore how the RSA algorithm works. The title "Identity" might seem strange at first, but you'll discover how cryptographic algorithms like RSA fundamentally rely on mathematical identities to function.

Before talking about more specific details, let's take a look at several common anecdotes around this topic.

Asymmetric cryptography

I've heard about basic cryptographic approaches like (1) shifting characters by a fixed number of positions, and (2) using the same key for both encryption and decryption. I know these are easy to break and aren't secure methods. I've also heard about an asymmetric approach that uses different public and private keys. Even though the keys are different, they somehow work together magically. This is fascinating, but how does it actually work? I can't understand it at all. The below RSA algorithm process does not make sense at all!

The RSA Process:

• Party A wants to send a secure message to Party B that no one else can intercept and read
• First, Party B generates a key pair: a public key $(n, e)$ that anyone can see, and a private key $d$ that only Party B knows
• Party B shares their public key $(n, e)$ with Party A (and potentially with everyone - it's meant to be public)
• Party A takes their message, encrypts it using Party B's public key $(n, e)$, and sends the encrypted message to Party B
• Party B receives the encrypted message and decrypts it using their private key $d$

Inverse

When I was young, I was asked to calculate the inverse of some value. For example, the inverse of 2 is 1/2. It seemed easy - just $\frac{1}{n}$. But now I ask again: the inverse with respect to what? As I progressed to higher classes, I learned about inverse matrices like $\mathbf{A}^{-1}$. But what does "inverse matrix" actually mean? Inverse with respect to what operation? These concepts seemed straightforward at the time, but now I realize I never truly understood what "inverse" fundamentally means. The question that haunts me now is deeper: when we say "inverse," we must ask - inverse with respect to what reference point? What operation? The very concept of inverse seems meaningless without understanding the underlying structure it operates within. This realization troubles me because I thought I understood something so basic, yet I now see I was merely following mechanical procedures without grasping the essential meaning.

Our Journey

Having our shared experiences in mind, let's begin our journey. I don't believe there's true asymmetry in the mathematics underlying cryptography. If we had two completely different handles, how could they communicate back and forth? It would be impossible. It is like expecting two completely unrelated objects to somehow recognize each other. That simply cannot happen.

The reality is that these two seemingly different things are actually closely related through mathematical symmetry. If we understand one, we can determine the other. Therefore, even in asymmetric cryptography, we are fundamentally talking about mathematical symmetry beneath the surface.

This leads us to the central question: what lies at the heart of this relationship? The answer is "Identity." This is where the concept of inverse becomes crucial - inverse operations create symmetry around identity. Consider this: if I know 2, I automatically know 1/2 because they are inversely related. Related with respect to what? Identity. Specifically, multiplicative identity. The numbers 2 and 1/2 are multiplicative inverses because their product equals the identity 1. They exist in perfect symmetry through their inverse relationship around the identity element 1.

Similarly, $\mathbf{A} \times \mathbf{A^{-1}} = \mathbf{I}$. When we talk about "asymmetric keys," we're not referring to completely different entities. Though they appear different, they are related in a fundamentally symmetric manner through their inverse relationship with respect to identity.

This reveals the truly fascinating aspect for cryptography: performing an operation and then performing its inverse returns us to identity. The second operation essentially undoes the first. In cryptography, encrypting something and then applying its inverse operation returns us to identity. The inverse operation is decryption - we have undone the encryption!

However, if this symmetric inverse relationship around identity were so easy to solve (calculate) like 2 and 1/2, our information could not be securely protected. Anyone would be able to decrypt our precious assets simply by computing the inverse. Therefore, we introduce modular arithmetic (mod operations), which classifies numbers in terms of their remainders when divided by a modulus.

Modular arithmetic is not straightforward to calculate, especially when finding inverses becomes computationally difficult. At the same time, it has cyclicity - numbers "wrap around" after reaching the modulus. This mathematical framework transforms simple inverse relationships into computationally hard problems, forming the foundation of secure cryptographic systems. Now, how do we know when numbers return to identity in modular arithmetic? This is where Euler's brilliant insight comes into play.

Euler's theorem - Another Identity

Probably Euler is one of the most well-known mathematicians. Together with Gauss, his name is everywhere. We will briefly enjoy what he has left for us in this area.

This is that famous Euler's theorem.

Let $n$ be a positive integer and let $a$ be an integer such that $\gcd(a,n) = 1$. Then $$a^{\varphi(n)} \equiv 1 \pmod{n}$$ where $\varphi(n)$ is Euler's totient function.

This is hard to grasp at first glance, so let's interpret a bit. This theorem tells us that if we raise $a$ to the power of $\varphi(n)$, the result is congruent to $1 \pmod{n}$, provided that $\gcd(a,n) = 1$.

This is fundamentally about multiplicative identity in modular arithmetic - when we repeatedly exponentiate, we eventually cycle back to the identity element (which is 1).

From Euler's theorem $a^{\varphi(n)} \equiv 1 \pmod{n}$, we can see that: $a \times a^{\varphi(n)-1} \equiv 1 \pmod{n}$

This shows us that $a^{\varphi(n)-1}$ is the multiplicative inverse of $a$ modulo $n$. Here we see perfect symmetry around identity, involving modular arithmetic. It combines everything we have discussed: identity, inverse relationships, and how exponentiation cycles back to 1.

But what exactly is $\varphi(n)$? What does it mean for us?

The Euler's totient function $\varphi(n)$ counts how many numbers from 1 to $(n-1)$ are relatively prime to $n$ (meaning their greatest common divisor with $n$ is 1). This function is the key to understanding when exponentiation cycles back to identity in modular arithmetic. Later, I will explain more detail about this function.

Just a moment. What is this $\gcd(a, n) = 1$ condition? The gcd means Greatest Common Divisor, and this condition describes a concept called coprime or relatively prime. It means these numbers share no common factors other than 1. For example, 3 and 5 are coprime because their only common divisor is 1. But 3 and 9 are not coprime since $\gcd(3, 9) = 3 \neq 1$. This condition is crucial for Euler's theorem to work, ensuring we can find multiplicative inverses in modular arithmetic.

Exploiting Euler's Identity

Now that we understand how modular multiplicative identity works with beautiful symmetry, let's exploit this for cryptography. Assume $M$ is the original message we want to send securely.

Following Euler's theorem: $$M^{\varphi(n)} \equiv 1 \pmod{n}, \text{ where }\gcd(M, n) = 1$$

If we raise both sides to any power $k$: $$ (M^{\varphi(n)})^k = M^{\varphi(n) \cdot k} \equiv 1^k = 1 \pmod{n} $$

Now, if we multiply both sides by $M$: $$ M \cdot M^{\varphi(n) \cdot k} = M^{1+ \varphi(n) \cdot k} \equiv M \pmod{n} $$

We're almost there! Looking at both sides, we can see the original message $M$ appears again. This shows us that exponentiating with $1+ \varphi(n) \cdot k$ brings us back to the original message. Let's rewrite this insight more simply by setting $ed = 1+ \varphi(n) \cdot k$: $$ M^{1+ \varphi(n) \cdot k} = M^{e \times d} = (M^{e})^d \equiv M \pmod{n} $$

This reveals the brilliant "engineered" core of RSA: exponents $e$ (encryption) and $d$ (decryption) are multiplicative inverses in the exponent space.

The RSA Process

• Sender encrypts $M$ and sends $C = M^{e} \bmod n$
• Receiver decrypts by computing $C^{d} \bmod n = (M^{e})^{d} \bmod n = M^{ed} \bmod n$

But wait. We still haven't shown how $M^{ed} \bmod n$ gives us back $M$!

The Final Step

Here's the key: we know that $ed = 1 + k\varphi(n)$ for some integer $k$.

Therefore:

$$M^{ed} = M^{1 + k\varphi(n)} = M^1 \cdot M^{k\varphi(n)} = M \cdot (M^{\varphi(n)})^k$$

By Euler's theorem: $M^{\varphi(n)} \equiv 1 \pmod{n}$,

$$M^{ed} \equiv M \cdot 1^k = M \pmod{n}$$

Since $M < n$ in RSA (the message is smaller than the modulus), we have:

$$M^{ed} \bmod n = M$$

We recover the original message! Simply calculating $M^{ed} \bmod n$ gives us back $M$. $\textbf{Voilà!}$

In mathematics, seemingly different values and operations often reveal underlying symmetries that unify them in elegant ways. These connections demonstrate the deep structural beauty inherent in mathematical relationships. I hope you have also enjoyed discovering this mathematical beauty together with me throughout our exploration.

Before we wrap up, let's discuss several key points that I intentionally left out for easier progression. Since they are crucial for complete understanding, they're worth sharing explicitly.

• Message size constraint: To make the above reasoning work, $n$ should be larger than $M$, due to the nature of the remainder operation in mathematics. In real RSA applications, this is practically guaranteed since we normally select $n$ from a 2048-bit space, whereas each character's numeric representation is much smaller.
• Why modular arithmetic over trigonometry: Both modular arithmetic and trigonometric functions repeat in cycles, but they work differently. RSA uses modular arithmetic because it works with integers, which computers handle perfectly without rounding errors. It also creates the specific mathematical "locks and keys" that make RSA secure: we can easily multiply numbers but it's extremely hard to factor them back. Trigonometric functions like sine and cosine create smooth, flowing cycles with real numbers. In machine learning, things like positional embeddings use trigonometric functions because they need smooth and continuous patterns that can capture subtle relationships between positions. The choice comes down to whether you need exact integer cycles or smooth continuous cycles.
• Euler's totient function and prime factorization: In Euler's theorem (which generalizes Fermat's Little Theorem so that $a$ and $n$ don't need to be prime), the totient function plays a critical role. This function counts the numbers relatively prime to $n$ up to $(n-1)$. The computational challenge is that $\varphi(n)$ becomes extremely hard to compute when $n$ is large. So even when we share $n$ publicly, malicious attackers cannot easily calculate $\varphi(n)$ and decrypt messages using the known $e$. Why is prime factorization mentioned so frequently in RSA cryptography? Because we know that $\varphi(n) = (p-1) \times (q-1)$ when $n$ is the product of primes $p$ and $q$. Therefore, we randomly select two large prime numbers and generate $n$ as their product. This allows us to easily calculate $\varphi(n)$. However, without knowing the underlying $p$ and $q$, computing $\varphi(n)$ becomes practically impossible. Here lies the computational asymmetry: multiplication is easy, but factorization is extraordinarily difficult.
• Conditions for RSA key generation: For the equation $ed = 1 + k\varphi(n)$ to have solutions for $e$ and $d$, we need $\gcd(e, \varphi(n)) = 1$. This means $e$ and $\varphi(n)$ must be relatively prime. When this condition is met, the multiplicative inverse $d$ exists and can be computed using the Extended Euclidean Algorithm. Notably, there are multiple solutions - if $d$ is a solution, then $d + m\varphi(n)$ is also a solution for any integer $m$ due to the modular nature. However, we typically choose the smallest positive value of $d$ for practical efficiency.
• Congruence explained: "Congruent" in mathematics means numbers belong to the same equivalence class in modular arithmetic. When we say $a \equiv b \pmod{n}$, it means $a$ and $b$ have the same remainder when divided by $n$. Importantly, congruence is a relationship of equivalence, not equality. The numbers themselves may be different, but they share this specific property relative to the modulus $n$.
• Understanding modular arithmetic: Modular arithmetic can be challenging to grasp initially, but it becomes intuitive with hands-on practice. The best approach is to work through concrete examples, calculating step by step to see how these operations behave. For instance, try computing $7^1, 7^2, 7^3, 7^4, \ldots$ modulo 12 and observe the pattern that emerges. The crucial insight is that modular arithmetic creates cyclicity - numbers eventually repeat in predictable patterns. Once you discover this cyclical nature, even computations with very large numbers become manageable. Understanding this pattern is fundamental to grasping why RSA works - it's not just abstract mathematics, but a beautiful demonstration of how cyclical patterns in modular arithmetic enable secure cryptography.