Hey Ninja. Have you ever worried that someone might steal the information you share on WhatsApp? How are you assured that the information you share on social media will be only visible to the end user? There might be a case your enemy is sitting in the middle to steal your confidential information. What do you think about how Social media applications secure your messages from the third person?
They use Cryptography algorithms to secure your information and make sure that they are only accessible to the user you are supposed to send.
So, what’s new in this article?
In this article, we will walk over the Discrete Logarithms Problem. We will also discuss the one-way function and its strength and this will help in cryptography techniques.
Let us start now:
Understanding Discrete Logarithm
Before understanding the Discrete Logarithm, let us take an Analogy of how to make COFFEE.
To make Coffee we need Milk + Coffee powder.
When we have the right items, we can prepare whatever we want to. Right? We have just learned how to prepare a coffee. Isn’t it so easy? 🫡
So, it is easy in one direction.
Now, think of the reverse situation in which you are given a coffee and asked to estimate the exact quantity of milk and coffee powder used to prepare that Coffee. This is certainly a difficult or impractical task. Hence, it is not easy in the reverse direction.
To conclude the example, preparing the coffee in one direction is easy but in the reverse direction is hard or impractical.
How is this relatable to our topic today? You will understand the analogy of this example later in this article.
For the time being, let us discuss some mathematics concepts:
Introduction to Modulo Arithmetic
When we divide two integers, the equation looks like this:
where,
A is the dividend,
B is the divider,
Q is the Quotient,
R is the Remainder.
Many times, you must have seen we are only interested in finding the Remainder. A special operator called the modulo operator ( abbreviated as mod ) represents the Remainder of two integers.
A mod B = R
The above equation represents A modulo B is equal to R. Here, B refers to the modulus.
For example:
5 mod 17 = 5
The other name of modulo Arithmetic is Clock Arithmetic. Why is it so? Let us find out:
Example:
Given - Modulus = 4
X mod 4 =?
Where X is starting from 0,1,2….
Each time, the remainders increase from zero to one less than the number we are dividing by. After that, the sequence is repeated. This enables us to represent the modulo operator with circles. We can now say that it is rotating in a clockwise direction. Thus, it is also known as Clock Arithmetic.
We write 0 at the top of a circle and continue clockwise writing integers 1, 2, 3, ... up to one less than the modulus.
Let us take an example to understand DLP:
Consider a prime number 17, and a clock with 17 units.
We can see that the clock is from 1 to 17 and 17 is a prime number and we are taking the number 5 which is the primitive root of the number 17.
How to verify whether the number is the primitive root of the prime number. In the above example, if 5 is the primitive root of 17, then 51 mod 17, 52 mod 17 …… up to 516 mod 17, i.e., if 17 is the prime number denoted as p, then 5p-1 mod p must give Unique results.
During the computation of the above equations, we get unique results, hence we can say that 5 is a primitive root of 17. So, from 51 to 516 we are getting a result that is Uniformly Distributed. It is an important property of prime numbers and primitive roots.
So, what we understood from the above concept is that when we deal with 5X mod 17 and when we start giving numbers for X- 1,2,3,4…. then the result is equally distributed. This is only applicable when a modulus is a prime number and there is a primitive root to that prime number.
If the X is given then computing 5X mod 17 is easy to perform but think of the reverse situation.
Say, you are having 5X mod 17 = 12, and you are required to find X that can fulfill the equation. Now finding what could be at the X’s place is difficult because X can be many.
59 mod 17 is 12, 520 mod 17 is 12, 541 mod 17 will be 12 and the list goes on.
If you recall the example taken at the starting of the article, making coffee is easy but finding the exact quantity of milk and coffee powder when the coffee is given is hard to find.
This is the important property of the One-Way function.
Let us now see the theoretical aspects:
In the discrete Logarithm problem, we will be computing x for gx mod p, where g is the primitive root for the prime number p.
For the smaller value of p, finding X is easy, but for large values finding x is very hard. So, the strength of the one-way function is depending on how much time it takes to break it. This strength can be used in Cryptography so that the hacker cannot easily decrypt the message.
The only possibility a hacker can apply is Brute Force Approach, i.e., the Hit and Trail method.
Here, the equation can be represented in the form of Discrete Logarithms:
5x mod 17 = 12, it can be written as:
x = dlog5,17(12), where x is a discrete log of 5 mod 17 of 12.
Let us now solve some problems on Discrete Logarithms:
Problems on Discrete Logarithms
Compute 5i mod 13 = 8. Determine i.
Brute Force Approach: i = 0,1,2,.... Substitute the values of i one by one: 50 mod 13 = 1 ❌ 51 mod 13 = 5 ❌ 52 mod 13 = 12 ❌ 53 mod 13 = 8 ✅ Ans = 3 = dlog5,13 (8), where 3 is the discrete log of 5 mod 13 of 8.
Compute log2 9 mod 11
Here, p (prime number) = 11 g (base) = 2 X = 9 Below is the equation, we are going to adopt to solve the question: logg X = n (mod p), Here, we are required to find n. We can write this : X = gn (mod p) Now, substitute all the given values in the equation: 9 = 2n mod 11 Now this question became same as the previous one. Try n = 1,2,3…. 21 mod 11 = 2 ❌ 22 mod 11 = 4 ❌ 23 mod 11 = 8 ❌ 24 mod 11 = 5 ❌ 25 mod 11 = 10 ❌ 26 mod 11 = 9 ✅ The answer to this question = 6.
Compute ‘X’ in 2X ( mod 7 ) = 4
Try x = 1,2,3… 21 mod 7 = 2 ❌ 22 mod 7 = 4 ✅ The answer will be 2.
Frequently Asked Questions
Specify some Cryptography tools used frequently in today’s age.
Some of the most widely used cryptography tools are Security Token, JCA, SignTool.exe, CertMgr.exe, and Docker.
What forms of cryptography are used in blockchain?
Asymmetric-key algorithms and hash functions are the two cryptographic algorithms used in blockchains.
How is cryptography used in cryptocurrency?
With the help of cryptography, cryptocurrency transactions are anonymous, secure, and "trustless," meaning there is no need for a bank, credit card company, government, or another intermediary to be present. Instead, you can conduct business with anyone without knowing anything about them.
Conclusion
To conclude the discussion, we have extensively discussed Discrete Logarithm in Cryptography along with problems based on the same. We have also gone through the one-way function and looked at its strength. We have also discussed how in cryptography, one can use Discrete Logarithms, as finding the exponential is very hard as the prime number grows.
If you like this article and want to learn more about Cryptography, please refer to these articles and enhance your knowledge.