In the world of cryptography, where the protection of sensitive information is paramount, mathematicians and cryptographers have devised ingenious methods to safeguard data from prying eyes. One such method that plays a pivotal role in modern encryption is Euler’s Totient Function, a mathematical concept that finds its application in a wide range of cryptographic algorithms. In this blog post, we delve into the fascinating world of Euler’s Totient Function, with a particular focus on its significance when applied to the square of a composite number, n, where n is the product of two prime numbers, p and q. This scenario is not only crucial in the realm of number theory but also forms the foundation of the Paillier Cryptosystem, a cryptographic system renowned for its ability to perform homomorphic operations on encrypted data while ensuring security and privacy. Join us as we unlock the secrets of this intricate mathematical concept and explore how it underpins the security of the Paillier Cryptosystem.
Theory 1 – Paillier’s usage of Totient Function
Φ(n2) = n.Φ(n)
🙋♂️ You may consider to enroll my top-rated cryptography course on Udemy
where n is the product of two primes p and q
n = pq where p and q are prime numbers
We have to prove two theorems to prove this main theory.
Theory 2 – Totient Function of Two Prime Bases
If n can be represented as product of many primes bases as
n = p1k1 p2k2
Hint: This is also called prime factorization of n
Then totient function is still multiplicative as:
Φ(n) = Φ(p1k1 p2k2) = Φ(p1k1)Φ(p2k2)
Proof of Theory 2
We have recently proven that totient function is multiplicative in a previous blog post, if p and q are coprimes.
Φ(n) = Φ(pq) = Φ(p)Φ(q)
This rule can be extended if n is the product of two prime bases because two prime base numbers will still be coprimes.
n = p1k1 p2k2
P1 = p1k1 = p1.p1. … p1 -> k1 times p1
P2 = p2k2 = p2.p2. … p2 -> k2 times p2
There is no common number in equations P1 and P2, and no terms can also be simplified. So, p1k1 and p2k2 must be coprimes if p1 and p2 are coprimes. We proven that Euler’s totient function is still multiplicative if n is the product of two prime bases.
Φ(n) = Φ(p1k1 p2k2) = Φ(p1k1)Φ(p2k2)
Theory 3 – Totient Function of Prime Power
Totient function of some prime base can be represented as prime number to the power of back power of n times totient function of prime itself.
Φ(pn) = p(n-1)Φ(p)
Proof of Theorem 3
The Euler’s Totient Function, denoted as φ(n), calculates the count of positive integers less than or equal to n that are coprime (have no common factors other than 1) with n. So, we will check numbers in [1, pn] and exclude numbers that not coprime to pn.
A = {1, 2, 3, …, pn}
So, there are pn numbers in this total set.
|A| = pn
Hint: we already know that the maximum number in this set pn is not coprime to pn but we will exclude it later.
Now, let’s find numbers that not coprime to pn.
B = {p, 2p, 3p, …, (pn-1)p}
So, there are pn-1 numbers that not coprime to pn in set B.
|B| = pn-1
The maximum number in the set B is pn itself. We are dropping it when we exclude the items in set B from set A.
Φ(pn) = |A| – |B|
Φ(pn) = pn – pn-1
Φ(pn) = pn(1 – 1/p)
Φ(pn) = pn( (p – 1) / p)
Φ(pn) = pn-1 (p – 1)
Φ(pn) = pn-1 Φ(p)
Combination of Theory 2 and Theory 3
Now, let’s merge these two theorems:
Φ(pn) = pn-1 Φ(p)
Φ(p1k1 p2k2) = Φ(p1k1)Φ(p2k2)
According to Theory 3, p1k1 and p2k2 can be represented as:
Φ(p1k1) = p1k1-1 Φ(p1)
Φ(p2k2) = p2k2-1 Φ(p2)
Then, theorem 2 can be represented as:
Φ(p1k1 p2k2) = Φ(p1k1)Φ(p2k2) = p1k1-1 Φ(p1) p2k2-1 Φ(p2)
Paillier requires Φ(n2) where n = pq and p and q are primes. Let’s put value 2 to k1 and k2.
Φ(n2) = Φ(p2q2)
Φ(n2) = Φ(p2)Φ(q2)
Φ(n2) = p2-1 Φ(p) q2-1 Φ(q)
Simplify the powers
Φ(n2) = p Φ(p) q Φ(q)
Rearrange the order of items
Φ(n2) = p q Φ(p) Φ(q)
pq was equal to n
Φ(n2) = n Φ(p) Φ(q)
Totient function of p times totient function of q can be restored as totient function of pq
Φ(n2) = n Φ(pq)
pq can be restored to n again
Φ(n2) = n Φ(n)
As stated in the theory 1, totient function of n squared can be represented as n times totient function of n if n is the multiplication of two primes p and q.
Hint: even though this is exactly equal to the Theory 3, this is just coincidence. Theory 3 can be applied if and only if base is prime number but here n is the product of two primes. In other words, n cannot be a prime. We have to merge Theory 2 and Theory 3 to prove Φ(n2) = n Φ(n).
Conclusion
In conclusion, Euler’s Totient Function, a fundamental concept in number theory, has proven to be a cornerstone in the realm of cryptography, particularly when dealing with composite numbers like n = pq, where p and q are prime factors. Its ability to quantify the number of coprime integers to n not only provides a deep understanding of number theory but also serves as a vital component in encryption schemes such as the Paillier Cryptosystem. As we’ve seen, this ingenious mathematical concept facilitates secure computations on encrypted data, ensuring the confidentiality and integrity of sensitive information in an increasingly interconnected and data-driven world. Euler’s Totient Function’s legacy endures in the intricate tapestry of modern cryptography, a testament to the enduring power of mathematical principles in the pursuit of privacy and security.
Like this blog? Support me on Patreon
