# Discrete Logarithm in Cryptography By [Arya](https://paragraph.com/@aryaethn) · 2022-07-09 --- 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 Exchange --------------------------- In 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 Arithmetic In 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. ### Logarithm Now let’s define the function logarithm. We define ![Definition of logarithm](https://storage.googleapis.com/papyrus_images/5edeb061387038457900079154f0e1bc93d0078a5018ef624b08dbf6b45848aa.png) Definition of logarithm Which 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 Logarithm Table 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 13](https://storage.googleapis.com/papyrus_images/5cbf770ad2eed0bad294c1c519e60b3bf99f26d105320e924085f397d921523b.png) b^a mod 13 This table also give you the discrete logarithm mod 13. As an example ![An example of DLog](https://storage.googleapis.com/papyrus_images/24e4740485df5629bd93cdfe80ba3cab6506c72de4fd7c266488798954c8535e.png) An example of DLog and ![Another example of DLog](https://storage.googleapis.com/papyrus_images/df6256e1c80b93aebb2c1886168eb191f889cbc2cfc96fa6b4131f42c909cf75.png) Another example of DLog As 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 Cryptography Let’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. --- *Originally published on [Arya](https://paragraph.com/@aryaethn/discrete-logarithm-in-cryptography)*