The Keystone of Modern Cryptography: Euler's Totient Function and its Application in RSA

Euler's totient function, φ(n), is a cornerstone of number theory that counts the positive integers up to `n` that are relatively prime to `n`. Its properties, particularly that φ(pq) = (p-1)(q-1) for distinct primes p and q, are fundamental. This function underpins Euler's Totient Theorem, which states that `a^φ(n) ≡ 1 (mod n)` for any integer `a` that is relatively prime to `n`. This theorem provides a powerful tool for manipulating exponents within modular arithmetic. The abstract principles of Euler's totient function find their most significant real-world application in the RSA public-key cryptosystem. In RSA, two large prime numbers, `p` and `q`, are used to generate a public modulus `n=pq`. The value of φ(n) is then calculated and kept secret. This secret value is used to create a private key `d` that is mathematically linked to a public key `e` through the relationship `d * e ≡ 1 (mod φ(n))`. The security of the entire system hinges on the fact that calculating φ(n) without first knowing `p` and `q` is computationally infeasible. When a message is encrypted using the public key, it can only be decrypted with the corresponding private key. The mathematical proof of why RSA works is a direct application of Euler's Totient Theorem. This elegant connection between pure mathematics and applied cryptography demonstrates how abstract number theory concepts can be leveraged to build the secure communication systems that underpin our modern digital world.

Introduction to Number Theory in Cryptography

In the digital age, securing information is paramount. Cryptography, the science of secure communication, relies heavily on principles from a branch of pure mathematics known as number theory. At the heart of one of the most widely used public-key cryptosystems, RSA, lies a beautifully elegant concept: Euler's Totient Function. This function provides the mathematical 'trapdoor' that makes RSA secure, allowing anyone to encrypt a message but only the intended recipient to decrypt it.

Section 1: Defining Euler's Totient Function (φ(n))

Euler's totient function, denoted as φ(n) (pronounced 'phi of n'), is a fundamental concept in number theory.

Definition: For a positive integer n, the totient φ(n) is the count of positive integers less than or equal to n that are relatively prime to n.

Two integers a and b are considered relatively prime (or coprime) if their greatest common divisor (GCD) is 1. That is, gcd(a, b) = 1.

Example 1: Calculating φ(10) To find φ(10), we list the integers from 1 to 10 and find which ones are relatively prime to 10. The integers are: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Let's check the GCD of each with 10:

• gcd(1, 10) = 1 (Relatively Prime)
• gcd(2, 10) = 2
• gcd(3, 10) = 1 (Relatively Prime)
• gcd(4, 10) = 2
• gcd(5, 10) = 5
• gcd(6, 10) = 2
• gcd(7, 10) = 1 (Relatively Prime)
• gcd(8, 10) = 2
• gcd(9, 10) = 1 (Relatively Prime)
• gcd(10, 10) = 10

The numbers relatively prime to 10 are {1, 3, 7, 9}. There are 4 such numbers. Therefore, φ(10) = 4.

Section 2: Properties and Calculation of φ(n)

Calculating φ(n) by listing all numbers becomes impractical for large n. Fortunately, there are properties that simplify this calculation, especially for the numbers used in cryptography.

1. For a prime number p:

Since a prime number p has only two divisors (1 and itself), all integers from 1 to p-1 are relatively prime to p. Therefore, φ(p) = p - 1. Example: φ(7) = 7 - 1 = 6. The numbers {1, 2, 3, 4, 5, 6} are all relatively prime to 7.

1. For two distinct prime numbers p and q:

This is the most critical property for the RSA algorithm. If n = p q, the function is multiplicative: φ(n) = φ(p q) = φ(p) φ(q) = (p - 1)(q - 1). Example: For n = 77, we have p=7 and q=11. φ(77) = φ(7) φ(11) = (7 - 1) (11 - 1) = 6 10 = 60.

Section 3: Euler's Totient Theorem

Euler's totient function leads to a powerful theorem that forms the mathematical backbone of RSA decryption.

Theorem Statement: If a and n are relatively prime positive integers, then: a^φ(n) ≡ 1 (mod n)

This means that when a is raised to the power of φ(n), the result has a remainder of 1 when divided by n.

Example: Verifying with n=10 and a=3 We know gcd(3, 10) = 1 and φ(10) = 4. According to the theorem, 3^4 ≡ 1 (mod 10). Let's check: 3^4 = 81. When 81 is divided by 10, the remainder is indeed 1. So, 81 ≡ 1 (mod 10) holds true.

Section 4: The RSA Cryptosystem - A Practical Application

The RSA algorithm, named after its inventors Rivest, Shamir, and Adleman, is an asymmetric cryptosystem. This means it uses two different keys: a public key for encrypting data and a private key for decrypting it. The security of RSA hinges on the computational difficulty of factoring large numbers.

Here is how Euler's totient function is used to generate these keys and enable the encryption/decryption process.

Step 1: Key Generation

1. Choose Primes: Select two very large, distinct prime numbers, p and q. (In practice, these are hundreds of digits long).
2. Calculate Modulus: Compute n = p * q. This n is part of both the public and private keys.
3. Calculate Totient (The Secret): Compute φ(n) = (p - 1)(q - 1). This value is the crucial 'trapdoor' information and must be kept secret. Without knowing p and q, it is computationally infeasible to calculate φ(n) for a large n.
4. Choose Public Exponent: Choose an integer e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1. This e becomes the public key exponent.
5. Calculate Private Exponent: Compute the private key exponent d as the modular multiplicative inverse of e modulo φ(n). This means d must satisfy the congruence relation: *d e ≡ 1 (mod φ(n))**.

• Public Key: {e, n} (Shared with everyone)
• Private Key: {d, n} (Kept secret by the recipient)

Step 2: Encryption A sender wants to encrypt a message M (represented as an integer where 0 ≤ M < n). They use the recipient's public key {e, n}: C = M^e (mod n) The resulting value C is the ciphertext.

Step 3: Decryption The recipient receives the ciphertext C and uses their own private key {d, n} to decrypt it: M = C^d (mod n)

Section 5: The Mathematical Proof - Why RSA Decryption Works

How does C^d (mod n) magically return the original message M? The proof lies in Euler's Totient Theorem.

1. We start with the decryption formula: C^d (mod n).
2. Substitute C with its definition from the encryption step: (M^e)^d (mod n) = M^(e*d) (mod n).
3. From key generation, we know e d ≡ 1 (mod φ(n)). By the definition of modular congruence, this means e d can be written as k * φ(n) + 1 for some integer k.
4. Substitute this into the exponent: M^(k*φ(n) + 1) (mod n).
5. Using exponent rules, this is equivalent to: (M^φ(n))^k * M^1 (mod n).
6. Now, applying Euler's Totient Theorem (M^φ(n) ≡ 1 (mod n)), the expression simplifies to:

(1)^k M (mod n) = 1 M (mod n) = M (mod n).

Thus, the decryption process successfully recovers the original message M, all thanks to the properties of Euler's totient function.

Browse public study notes