# Discrete Logarithm in Cryptography

**Published by:** [Arya](https://paragraph.com/@aryaethn/)
**Published on:** 2022-07-09
**URL:** https://paragraph.com/@aryaethn/discrete-logarithm-in-cryptography

## Content

Discrete logarithm is one of the most important parts of cryptography. This mathematical concept is one of the most important concepts one can find in public key cryptography. Let’s first determine a very basic algorithm to make public keys in cryptography and then describe how discrete logarithm can help us in this algorithm.Diffie-Hellman Key ExchangeIn this method, there are two people, Alice and Bob, who want to make a safe channel to exchange messages, which Eve is an untrusted person who wants to see messages. For this to happen, they need to determine a key and then use this key to exchange messages. Let’s define the algorithm below:Firstly, Alice and Bob choose a modulus p, a very big prime number, and a base g, which is a primitive root modulo p. (If you don’t know what is a primitive root, don’t worry. We will talk about that later)Secondly, Alice chooses a secret integer a, and sends g^a mod p to Bob. Eve can see g^a mod p.Then, Bob chooses a secret integer b, and sends g^b mod p to Alice. Eve can see g^b mod p.Then Alice calculates g^(ab) mod p by powering g^b mod p to a. Bob also calculates g^(ab) mod p using g^a mod p and b.g^(ab) mod p will be the mutual key they will use to send messages.g^a mod p is Alice’s public key and a is Alice’s secret key.g^b mod p is Bob’s public key and b is Bob’s secret key.In this protocol Eve cannot compute g^(ab) mod p, because Eve would need a or b to compute g^(ab) mod p, which cannot find because Eve would need to calculate log g^a mod p which is a discrete logarithm. Discrete logarithm is a “hard” problem, so Eve cannot calculate the logarithm above. We are going to talk about discrete logarithm and describe why it is a hard problem. Before diving deep in to discrete logarithm, we are going to talk about modular arithmetic.Modular ArithmeticIn modular arithmetic there is a modulo m which every integer number will be presented as the remainder in the division of the number by m. As an example if m = 10 then 23 will be presented as 3 and if m = 16 then 96 will be presented as 0. In other words 96 will be congruent to 0 modulus 16 and 23 is congruent to 3 modulus 10.LogarithmNow let’s define the function logarithm. We defineDefinition of logarithmWhich we call b the basis, and k the solution of the logarithm. This equation means that a = b^k. In discrete logarithm, k will be a remainder to a modulo like p. Let’s determine an example for discrete logarithm.Discrete LogarithmTable below shows the first 12 basis and first 12 exponents modulo 13. As an example when you try to calculate 5^8 mod 13 you get 1 and calculating 7^4 gives you 9.b^a mod 13This table also give you the discrete logarithm mod 13. As an exampleAn example of DLogandAnother example of DLogAs you can see discrete logarithm can be not unique. If all the logarithms from exponent 0 up until exponent p-1, where p is the modulo, happen and they are unique we call that basis the primitive root. For example primitive roots of modulo 13 are 2, 6, 7, and 11. The feature of primitive roots is that when they are powered to some integer it will uniquely identify one of the integers between 1 and p-1 where p is the modulo.Discrete Logarithm in CryptographyLet’s determine what happens to Alice if she wants to calculate g^a mod p where g is a primitive root modulo p and p is a big prime number and a is a secret integer. Alice will write a in the basis of 2. Then she calculates g mod p, g^2 mod p, g^4 mod p, g^8 mod p, g^16 mod p, … Calculating these numbers will only cost Alice log a computing steps because she only needs to multiplies g^x mod p to g^x mod p to get g^(2x) mod p. Then is it only necessary for Alice to use those numbers that sum of their exponents makes a in the basis of 2. So Alice only needs O(log a) steps to calculate g^a mod p. The same procedure is sufficient for Bob to computes g^b mod p. But finding a from g^a mod p is a hard problem since g^a mod p is not unique and many exponents of g can be congruent to each other. So to find a Eve should calculate g mod p, g^2 mod p, g^3 mod p, g^4 mod p, g^5 mod p, … and use every exponent that gives the same modulus as a modulo p. So this gives Eve O(a) steps for finding a to use it finding g^(ab) mod p. The same procedure is needed to find b. Assuming that p, g, a, and b are big 600 digits numbers, this will give Alice and Bob a very little number of steps to calculate g^(ab) mod p, maybe less than 10,000 steps. But Eve needs more that 10^600 steps to find g^(ab) mod p. To feel how big this number is, let’s emphasise that all the atoms in the known universe by the humans are about 10^80 and this number is 10^520 times bigger than that. So with the computation power humans today have, it would take Eve billions billions years to find g^(ab) mod p but it takes only less than 0.5 second for Alice and Bob to compute it.

## Publication Information

- [Arya](https://paragraph.com/@aryaethn/): Publication homepage
- [All Posts](https://paragraph.com/@aryaethn/): More posts from this publication
- [RSS Feed](https://api.paragraph.com/blogs/rss/@aryaethn): Subscribe to updates
- [Twitter](https://twitter.com/AriaNaraghi): Follow on Twitter