discrete logarithm problem

As a quick reminder, a logarithm is, in general, an "inverse exponentiation". That is, if , then .

A discrete logarithm is in contrast to a normal, or continuous, logarithm. It's discrete nature means it's dealing with integers (as opposed to real numbers) and that you are working with modulo's, and therefore in a particular group, or field of numbers (e.g., would be a field/group of 5 numbers, 0 - 4). I don't want to put the mod in the wrong place, so see Wikipedia: Discrete Logarithm: Definition. The grand takeaway is with the modulo, it means you are staying in the same number group/set/field.

As it turns out, no efficient algorithm is known for calculating discrete logarithms (except for Shor's quantum algorithm, though it is allegedly infeasible for the foreseeable future (see cryptography#post-quantum cryptography)). This is known as the "discrete logarithm problem". The most efficient methods seem to be (according to the Wikipedia page) based on the naive strategy of brute-forcing the answer. That is, if you were trying to find such that (I'm not sure where the mod goes), then you start with and starting raising to the power of increasing integers until you get .

It is pretty mind blowing how such a simple-to-express problem is not computationally feasible to solve. The sniffer, Z from above, can know , , and , and will not be able to find .

I won't do better than the explanation on Wikipedia: DHKE: Cryptographic Explanation, but I'll try anyways.

and are public. A and B pick private numbers and , and calculate and . Those are then shared, meaning Z has sniffed , , , . A and B can now calculate , which is effectively, . Z knows almost everything! Z knows , , , , but cannot calculate any of , , or . It's all been mixed together and due to the DLP, it cannot feasibly be unmixed.