The Math in Public-key Cryptography explained in simple words

Public-key cryptography, also called as asymmetric key cryptography, is a method of encryption that uses two different keys — a public key and a private key — to encrypt and decrypt data. Public-key cryptography relies on mathematical functions that are easy to compute in one direction, but difficult to compute in the opposite direction. In this way, it ensures that only the intended recipient can decrypt the message, even if the encrypted message is intercepted by a third party.

Source: https://utimaco.com/

Creating public and private keys

Public and private keys are created using mathematical functions based on modular arithmetic and the properties of co-prime numbers. Here is a step-by-step example of how public and private keys are created:

1. Select two prime numbers: To create a public and private key pair, two different prime numbers must be selected. For example, let’s choose p = 17 and q = 23.
2. Compute n: Compute the product of the two prime numbers. n = p * q = 17 * 23 = 391.
3. Compute φ(n): Compute the Euler’s totient/phi function of n, which is the number of positive integers less than n that are co-prime to n. φ(n) = (p-1) * (q-1) = 16 * 22 = 352.
4. Choose a co-prime number: Choose a number e that is co-prime to φ(n). In other words, e should have no common factors with φ(n) other than 1. For example, let e = 5.
5. Compute the private key: Compute the private key d, which is the multiplicative/modular inverse of e modulo φ(n). In other words, d is the number such that (d * e) mod φ(n) = 1. In this example, d = 141.
6. Public and Private Key Pair: The public key is (n, e) and the private key is (n, d).

To encrypt a message m using the public key (n, e), we first convert the message into a number m using a chosen encoding method. Then, we apply the encryption function C(m) = m^e mod n, which generates the encrypted message.

To decrypt the encrypted message C using the private key (n, d), we apply the decryption function D(C) = C^d mod n, which recovers the original message.

For example, let’s say we want to encrypt the message M = “HELLO” using the public key (391, 5). First, we convert the message into a number m = 72736576 using ASCII encoding. Then, we apply the encryption function C(m) = m^e mod n = 72736576⁵ mod 391 = 113.

To decrypt the encrypted message C = 113 using the private key (391, 141), we apply the decryption function D(C) = C^d mod n = 113¹⁴¹ mod 391 = 72736576, which recovers the original message “HELLO”.

Why and How the Math works to ensure security?

Why prime numbers are used (17 and 23 in the example above) and why are they multiplied?

This is done because it is computationally difficult to factorize a large number into its prime factors, which provides security for the encryption algorithm. Solutions such as Eratosthenes sieve are used for prime factorization, however for a very large prime numbers, it is computationally expensive.

What are co-prime numbers?

Two positive integers are said to be co-prime if they have no common factors other than 1. In other words, their greatest common divisor (GCD) is 1. For example, 2 and 3 are co-prime since their only common factor is 1. On the other hand, 4 and 6 are not co-prime since they have a common factor of 2. Co-prime numbers are also known as relatively prime or mutually prime numbers.

What is multiplicative inverse and modular inverse?

The multiplicative inverse of a number is the number that, when multiplied by the original number, yields a product of 1. In other words, it is the reciprocal of the number. For example, the multiplicative inverse of 2 is 1/2, because 2 multiplied by 1/2 is equal to 1.

Extrapolating this idea to including a modulo would mean that if e is relatively prime (co-prime) to φ(n), i.e. gcd(e, φ(n)) = 1, then there exists a d such that d = 1/e mod φ(n), i.e d * e = 1 mod φ(n). For every e, if a d exists, then that d is unique.

Why use Euler’s Totient function or Euler’s Phi? And, why is it used?

φ(n) is number of positive integers less than n that are co-prime to n. φ(n) counts the positive integers that are less than or equal to n and are relatively prime to n. Let’s imagine we have two prime numbers, p and q. The product of these two numbers gives us n, which is used as the modulus for both the public and private keys in RSA. The totient of n, φ(n), is then calculated as (p-1)*(q-1). Let’s first prove that φ(n) = (p-1)*(q-1).

When n is a prime number, every number less than n is relatively prime to n, so φ(n) equals n-1 for a prime number n. We are working with n = p*q, where p and q are distinct prime numbers. The numbers that are not relatively prime to n are precisely the multiples of p and the multiples of q. There are q multiples of p less than n, and p multiples of q less than n.

But since p and q are distinct primes, the multiples intersect precisely at their common multiples, which are multiples of p*q = n. There is exactly one multiple of n less than n. In simpler words, when we say p and q are distinct primes, it means they are different prime numbers with no common factors other than 1. The numbers that are multiples of both p and q are exactly the multiples of their product, which is p*q. And in our case, p*q is equal to n.

So, the count of positive integers less than n that are not relatively prime to n is q (multiples of p) + p (multiples of q) — 1 (common multiples).

The count of positive integers less than n that are relatively prime to n is then n — the count of those that aren’t. Substituting the values, we get:

n — (p + q — 1) = pq — p — q + 1 = (p-1)(q-1), since n = pq. QED

The merit of using Euler’s totient lies in Euler’s theorem, which states that if p and q are co-prime numbers, then q to the power of φ(p) is congruent to 1 (mod p). This theorem underpins the mathematics that make public key cryptography, i.e. the encryption and decryption of it, work.

Without trying to prove Euler’s theorem, lets get into its foundations. If a number “a” is coprime to n (meaning “a” and n share no factors other than 1), then “a” raised to the power of the totient of n, is congruent to 1 modulo n. So, Euler’s theorem can be written as:

a^((p-1)(q-1)) ≡ 1 (mod n)

Thus Euler’s theorem gives us a neat trick for ‘undoing’ the encryption. When someone wants to send you a secret message, they ‘lock’ it using your public key, which involves raising their message (as a number) to the power of your public key, then looking at the remainder when they divide by “n”. To ‘unlock’ the message, you raise it to the power of your private key, and again look at the remainder when you divide by “n”. Euler’s theorem guarantees that this process will return the original message. Without Euler’s theorem and the use of the totient, we wouldn’t have a practical way to ‘unlock’ the encrypted message.

Summary

In the fascinating world of public-key cryptography, a cornerstone of data security in today’s digital age, mathematics plays an indispensable role. Central to this is Euler’s Theorem, a principle that underpins the secure exchange of information across networks. Through this mathematical mechanism, public-key cryptography allows the creation of two interlinked keys, one for encryption (public) and one for decryption (private), enabling secure communication in an increasingly interconnected world. Without Euler’s theorem and the ingenious application of its principles in public-key cryptography, the landscape of modern data security would look vastly different.