For the love of Prime Numbers-Part 2

In my previous post For the love of Prime Numbers-Part 1, we looked at the prime factorization problem and its application in modern cryptography. In this post let's look at the Discrete Logarithms Problem(DLP) and its application in cryptographic algorithms.

The DLP is another key concept in mathematics that is widely applied in modern cryptography because it's considered very hard to solve for large prime numbers. Imagine you have a combination lock that you use to lock your bike. You set the combination to a random four-digit number, and you're the only one who knows what the combination is. It's easy to lock your bike by turning the dial to the right combination, but it would be very difficult for someone else to figure out the combination by trying different numbers. It could potentially take 10^4 or 10,000 possible combinations. This means that someone trying to guess the combination might have to try 10,000 different numbers before finding the right one, making it a one-way function, sort of.

When working with natural logarithms, it's possible to estimate the value of a given logarithm if we know the values of the logarithms of two nearby numbers. This is because natural logarithms have a continuous and smooth curve, which means that the values of the logarithms are closely related to the values of the numbers.

For example, if we know that the natural logarithm of 3 is 1.098612 and the natural logarithm of 5 is 1.609438, we can estimate that the natural logarithm of 4 would be around 1.386294. This is because the natural logarithm function is a monotonically increasing function(its graph increases with increasing values of the equation) and therefore the logarithm of a number between 3 and 5 will be between the logarithms of 3 and 5.

On the other hand, when working with discrete logarithms, it's not possible to estimate the value of a given logarithm if we know the values of the logarithms of two nearby numbers. This is because in discrete logarithms the values of the logarithms are not closely related to the values of the numbers. For example, if we know that the discrete logarithm of 2^72 (mod 131) is 3, and the discrete logarithm of 2^46(mod 131) is 5, we can't estimate the value of y in 4=2^y (mod 131)

Let's use a simple Python code to compute the values of y

def mod_exp(x, p)
? ? return pow(2, x, p)

# List of x values
x_values = [72, 2, 46, 73, 96]
p = 131

for x in x_values:
? ? y = mod_exp(x, p)
? ? print(f"For x = {x}, y = 2^x mod 131 = {y}"):        

In the table below, If you compare the x values of the natural logarithm and discrete logarithm, in the natural logarithm the x and y values are monotonically increasing. Whereas in discrete logarithms, the x value is distinct, non-continuous, and doesn't increase monotonically for a monotonically increasing y value. For example, in the natural logarithm, if x values 1.3869 and 1.79175 are known, we can reliably predict the x value of "5". Whereas it's not easy to predict the x value of "5" in a discrete logarithm knowing the x value of "4" and "6" like in natural logarithm

The discrete logarithm (dlog) is based on modular arithmetic. The goal of dlog is to find the exponent x in the equation y= g^x (mod p), where g is a known base; the generator or the primitive root of p, y is a known result, and p is a known prime number( in real applications it's a very large prime). Suppose we have a prime number p = 131, generator g = 2, and, y = 3. Let's find the number x such that y = g^x mod p. In other words, we want to find x such that 3 = 2^x (mod 131).

We can use the following brute force steps:

1. We can start by trying different values of x from 1 to 130 and calculate 2^x mod 131 for each value.
2. We can find that 2^72(mod 131) is 3
3. Therefore, the value of x that satisfies the equation is x=72

The problem is to find x, given g, p, and y. It is a one-way function, which means it's easy to compute g^x mod p for any x, but it's hard to find x given g, p, and y.

Natural logarithm (ln) is used in Mathematics, Data Science, Physics, and Engineering while discrete logarithm (dlog) is primarily used in cryptography.

Let's visualize the above concept with a list of x values from 1 through 131 using natural logarithms.

import matplotlib.pyplot as plt
import numpy as np

x = np.linspace(1, 131, 131)
y = np.log(x)

plt.plot(x, y)
plt.xlabel('x')
plt.ylabel('ln(x)')
plt.title('Plot of ln(x) from 1 to 131')
plt.grid()
plt.show()        

Now for comparison, let's visualize the list of x values from 1 through 131 using discrete logarithms.

import matplotlib.pyplot as plt

p =131
g =2
x = list(range(0, p))
y = [pow(g, i, p) for i in x]
plt.scatter(x, y)
plt.xlabel('x')
plt.ylabel(f'{g}^x mod {p}')
plt.show()        

If you look at the plots above, you can visually infer for the natural logarithm we have a continuous and smooth curve. Whereas for discrete logarithms, the scatter plot doesn't show any pattern or relationship between x and y.

One way to solve the discrete logarithm problem is to use a brute-force search, which involves trying all possible values of x until the correct value is found. However, it's important to note that solving DLP for very large prime numbers and large exponents is computationally infeasible for classical computers, and there is no known efficient algorithm for solving it. This is the reason why DLP is used in many encryption methods such as the Diffie-Hellman key exchange, the ElGamal encryption scheme, and the DSA digital signature algorithm.

Let's look at Diffie-Hellman key exchange protocol, which uses the discrete logarithm problem to enable two parties to exchange a shared secret key over a public communication channel. The security of the protocol is based on the difficulty of solving the discrete logarithm problem (DLP) in a finite field.

Let's try to understand the Diffie-Hellman key exchange concept through a classical example. Imagine you have two paint bottles, one is blue and one is yellow. You mix them to make a new color, a variant of green, let's say "fancy green". But you don't know how much of each color you need to mix again to make "fancy green". So, you start experimenting by adding a little bit of blue and a little bit of yellow, but it doesn't turn out to be the same green. You keep trying different amounts of blue and yellow, but it's hard to figure out the exact combination. It's like looking for a needle in a haystack to find the right amounts of blue and yellow to make green. This is similar to the Discrete Logarithms Problem, it's about trying to find the right answer, or the right combination of numbers, among many possibilities.

Here's an example of how the Diffie-Hellman key exchange protocol works using Python:

# For illustration only, not tested for large prime numbers

# Alice and Bob agree on a prime number p and a generator g
p = 131
g = 2 # primitive root of 131 

# Alice chooses a secret number a and computes A = g^a mod p
a = 12
A = (g ** a) % p

# Bob chooses a secret number b and computes B = g^b mod p
b = 15
B = (g ** b) % p

# Alice and Bob exchange A and B over the public channel

# Alice computes the shared secret key s1 = B^a mod p
s1 = (B ** a) % p
print("Alice's shared seceret is " + str(s1))

# Bob computes the shared secret key s2 = A^b mod p
s2 = (A ** b) % p
print("Bob's shared seceret is " + str(s2))

# The shared secret key is the same for Alice and Bob
assert s1 == s2         

As you can see, the shared secret key is calculated by both parties by raising the received public value to the power of their secret value and then taking the modulo of the prime number. The security of the protocol relies on the difficulty of solving the DLP, that is, finding the secret values (a or b) given only the public values (A or B) and the prime number p.

Since the DLP is considered infeasible, an attacker would not be able to determine the secret values and as such, would not be able to compute the shared secret key in reasonable time.

A big shout out to R. Ravindraraj for his invaluable contribution to my research work in applied cryptography. His expertise in mathematics has greatly aided my comprehension of the subject matter. I also would like to acknowledge his thorough proofreading of my articles.

Here is a fun fact, it's observed that prime numbers form a spiral distribution pattern when stretched to a very large set. The exact pattern of prime numbers in a spiral pattern is not yet well understood and remains a mystery. However, there are quite a few things in nature that resemble this distribution, for instance, spiral galaxies!

We will explore more in the next post, stay tuned.