The Discrete Logarithm Problem

Network Security: The Discrete Logarithm Problem
Topics discussed:
1) Analogy for understanding the concept of Discrete Logarithm Problem (DLP).
2) Explanation of the Discrete Logarithm Problem (DLP) with examples.
3) Features of a prime number and primitive root/generator.
4) Strength of one-way function.
Follow Neso Academy on Instagram: @nesoacademy (bit.ly/2XP63OE)
Contribute: www.nesoacadem...
Memberships: bit.ly/2U7YSPI
Books: www.nesoacadem...
Website ► www.nesoacadem...
Forum ► forum.nesoacad...
Facebook ► goo.gl/Nt0PmB
Twitter ► / nesoacademy
Music:
Axol x Alex Skrindo - You [NCS Release]
#NetworkSecurityByNeso #Cryptography #NetworkSecurity #DiscreteLogarithmProblem

[@GijsvanDam]

First time someone explained this in a way that is understandable to me.

[@stefanoskoutsouflakis3802]

Great explanation! Just a minor objection: The difficulty is not due to the infinite number of solutions (as suggested at 5:00). The main challenge lies in the computational effort required to find even the smallest such x, when p is a very large prime.

[@_Redu]

You should also mention what makes the discrete logarithm problem any useful than normal modulo problem. Such as x mod 35. x = 52 and x = 857 and infinitely many x values would yield 17. So let me tell the part that makes using power important. The base (b) and the modulo (m) are known publicly and your secret is the powering integer x. Bob chooses a secret x and sends p = b^x mod m to Alice. Alice also knows the public values b and m and chooses her secret integer y. Then she does two things, 1) sends q = b^y mod m to Bob 2) Calculates s = (p^y) mod m. Bob receives q from Alice and calculates s = (q^x) mod m. Now both Alice and Bob share the same secret s to establish an encryptided commumination by relying on it. Anybody who sees the public values b, m, p, q is not able to calculate s easily without knowing x or y. For example Bob choses x = 8 and sends Alice 5^8 mod 17 = 16. Alice chooses y = 13 and sends Bob 5^13 mod 17 = 3. Bob receives 3 from Alice and calculates (3^8) mod 17 = 16. Alice receives 16 from Bob and calculates (16^13) mod 17 = 16. So now they both know that their secret key is 16.

[@charlesjayaraonettem1662]

Dear sir, this is an excellent way to understand. We request you to give clear and short notes for this (with respect to student aspect ).

[@user-sp2ex2tp9z]

thanks you neso academy you're the best

[@utilizator1701]

Can not wait for the next lecture.

[@sinaasadiyan]

Very great explanation

[@snehathombre7640]

Very nicely explained. Thank you!

[@Alokkumar-tp8tt]

damn good, finally it's crystal clear

[@ritikaggarwal9386]

2 is not a prime generator of 7 tho

[@788home]

Beautiful, thank you. 5^x mod 17 produces all 16 integers less than 17. But what about 16^x mod 17? 16 is relatively prime to 17 (a prime), but [16^x mod 17] has members that are not. This yields a [1,16,1,16,...] pattern. In fact, bases 2, 4, 8, 9, 13, 15 , and 16 all result in 'short' cycles (Some numbers between 1 and 16 are not output). Doesn't this severely impact the solutions space ?

[@JL-pg4pj]

For making coffee we don't obviously need milk

[@dr.anitapradhan5489]

mam excellent explanation,Thank you very much Hare Krishna

[@pavani8943]

please put PPT'S for C Programming

[@simomonti8986]

beautiful explanation but coffe isn't made with milk Bruh

[@SmithnWesson]

5:40 Your explanation is faulty.
It is hard to find x in 5^x = 12, not because there are multiple satisfying values in the congruence class.
That is NOT what makes the problem hard.
Problem is hard because you would have to look at all values between 1 and 16 to find the one that works.

[@mubin_ru]

❤️❤️❤️❤️❤️