Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Understanding Discrete Logarithm 
3.
Introduction to Modulo Arithmetic 
4.
Problems on Discrete Logarithms 
5.
Frequently Asked Questions 
5.1.
Specify some Cryptography tools used frequently in today’s age.
5.2.
What forms of cryptography are used in blockchain?
5.3.
How is cryptography used in cryptocurrency?
6.
Conclusion 
Last Updated: Mar 27, 2024

Let’s practice some Discrete Logarithms

Introduction

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? 

hacker

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. 

Coffee

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. 

Coffee

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. 

Coffee

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:

modulo arithmetic

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….

modulo arithmetic

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. 

clock

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.  

modulo arithmetic

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, 5mod 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

modulo arithmetic

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 5to 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. 

modulo arithmetic

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. 

5mod 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. 

modulo arithmetic

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 

  1. 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. 
     
  2. 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. 
     
  3. Compute ‘X’ in 2( 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.

You can also refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingSystem Design, and many more!

Head to our practice platform, Coding Ninjas Studio, to practice top problems, attempt mock tests, read interview experiences and interview bundles, follow guided paths for placement preparations, and much more.

Happy learning, ninja!

Live masterclass