The Two Primes and the Totient Function: How RSA Encryption Generates Public and Private Keys

In 1977, three researchers at the Massachusetts Institute of Technology—Ron Rivest, Adi Shamir, and Leonard Adleman—published a cryptographic algorithm that fundamentally altered how digital information is secured. Their system, known as RSA, solved a critical logistical vulnerability in secure communication: how two parties can exchange encrypted messages without ever sharing a secret key beforehand. The mechanism they designed relies entirely on the properties of prime numbers and a specific mathematical formula known as Euler's totient function.[1]

Today, when a modern web browser connects to a secure server, it routinely relies on this exact mathematical operation. The protocol executes calculations on numbers that stretch to 2,048 bits in length, which translates to roughly 617 decimal digits. These massive numbers are not chosen arbitrarily; their sheer size is the primary defense mechanism protecting global financial transactions, secure emails, and digital identities from brute-force computational attacks.[1]

Before the introduction of asymmetric cryptography, encryption was almost exclusively symmetric. This meant the exact same key was used to both scramble and unscramble a message. This created a severe logistical vulnerability, as the key itself had to be transmitted securely—often via physical courier—before any secret communication could begin. If an adversary intercepted the key during transit, the entire encryption system was compromised.

Public-key cryptography splits this process into two distinct keys: a public key that anyone can use to encrypt a message, and a private key that only the recipient holds to decrypt it. The mathematical challenge lies in ensuring that the private key cannot be reverse-engineered from the public key, even though the two are mathematically bound together. To achieve this, cryptographers rely on one-way functions—mathematical operations that are easy to perform in one direction but prohibitively difficult to reverse.

To generate an RSA key pair, the system begins by selecting two distinct, enormous prime numbers, typically denoted as p and q. These primes are multiplied together to produce a composite number, N, which serves as the modulus for both the public and private keys. While multiplying p and q takes a modern computer fractions of a millisecond, reversing the process—finding the original primes from the product N—is computationally infeasible for sufficiently large numbers.[1]

This one-way difficulty, known as the integer factorization problem, forms the outer defensive wall of RSA encryption. However, simply multiplying two primes together does not create a functional encryption system. The algorithm requires a specific mathematical structure to lock the data with one key and unlock it with another. The system needs a trapdoor—a piece of hidden information that makes reversing the function easy for the key owner, but impossible for anyone else.[1]

This is where Euler's totient function, written as φ(N), provides the necessary mathematical trapdoor. Named after the 18th-century Swiss mathematician Leonhard Euler, the totient function counts how many positive integers up to N are coprime to N. Two numbers are considered coprime if they share no common divisors other than 1. For example, the numbers 8 and 15 are coprime because their prime factors do not overlap, even though neither number is prime itself.[2]

For a prime number p, calculating the totient function is remarkably simple. Because a prime number has no divisors other than 1 and itself, every single positive integer less than p is coprime to it. Therefore, the value of φ(p) is always exactly p - 1. This foundational property of prime numbers is the engine that drives the entire RSA algorithm.[2]

The totient function possesses another critical property: it is multiplicative for coprime numbers. This means that if you multiply two distinct prime numbers, p and q, the totient of their product is equal to the product of their individual totients. Consequently, the value of φ(N) for the RSA modulus is exactly (p - 1) × (q - 1).[1][2]

This specific calculation is the hidden bridge that makes RSA work. If a computer system knows the original primes p and q, calculating φ(N) requires only a trivial subtraction and multiplication. However, if an attacker only knows the public modulus N, calculating φ(N) is effectively impossible without first factoring N into its constituent primes. The totient function is easy to cross if you hold the primes, but invisible if you only hold their product.[1][5]

With φ(N) calculated, the system selects a public exponent, e. This number must be greater than 1, less than φ(N), and strictly coprime to φ(N). In modern implementations, the number 65,537 is frequently chosen for e because it is a prime number that allows for highly efficient binary calculations. The public key is then broadcast to the world as the pair of numbers (N, e).[1]

To create the private decryption key, the system must find a value d such that multiplying d by e yields a remainder of 1 when divided by φ(N). In the language of modular arithmetic, d is the modular multiplicative inverse of e modulo φ(N). Because calculating d strictly requires knowing φ(N), only the party that generated the original primes can compute the private key.[1][2]

When a sender wants to transmit a secure message, they first convert the plaintext into a numerical value M. They then raise M to the power of the public exponent e, and divide the result by the modulus N to find the remainder. This remainder becomes the ciphertext C, which can be safely transmitted across an open network.[1]

To decrypt the ciphertext, the recipient performs the exact same mathematical operation, but uses their private key. They raise the ciphertext C to the power of d, and divide by N to find the remainder. The mathematics of the algorithm guarantee that this operation perfectly reverses the encryption, returning the original message M.[1]

This guarantee rests on Euler's theorem, a generalization of Fermat's little theorem, which dictates how exponents behave in modular arithmetic. As mathematician and consultant John D. Cook notes regarding the underlying number theory, Fermat's little theorem—first stated in 1640—is "relatively arcane, easy to prove, and extremely useful," forming the basis for the modular arithmetic that RSA relies upon. Euler's theorem ensures that because d and e were generated using φ(N), the encryption and decryption steps perfectly cancel each other out.[3][4]

While the theoretical mathematics of RSA are sound, the practical implementation must be flawless to remain secure. If the chosen primes are too close together, or if the random number generator used to select them is predictable, attackers can deduce the keys without solving the full factorization problem. Real-world systems must also employ complex padding schemes to prevent attackers from manipulating the ciphertext to reveal the underlying message.[1][5]

Furthermore, the rise of quantum computing poses a definitive long-term threat to the algorithm. In 1994, mathematician Peter Shor published a quantum algorithm that could factor large integers exponentially faster than any known classical method. A sufficiently powerful quantum computer running Shor's algorithm would bypass the difficulty of the factorization problem entirely, rendering the totient trapdoor useless.[1]

The National Institute of Standards and Technology (NIST) has already begun preparing for this eventuality, outlining a transition to post-quantum cryptographic standards that do not rely on integer factorization. Until such quantum machines are physically realized at scale, however, the mathematical relationship between two prime numbers and Euler's totient function continues to secure the foundation of the global digital economy.[5]