The discrete logarithm problem is a cryptography concept that underlies the basis of much of modern cryptography.
In general the discrete logarithm problem states that for the equation
bk (mod p) = awhere
b
, a
, and p
are known values and p
is prime, finding k
is hard.This is hard because of modular arithmetic; in order to find k, you would need to brute force it. Furthermore, there are an infinite number of solutions because you don't know how many times p
b^k
is. The values b
and p
are also specifically chosen values which make this problem harder as some values (especially lower values and non-prime values) are easy to solve (easy in that it doesn't take much time but the time complexity is still the same).
Although there is no proof that the discrete logarithm problem is actually hard, but it is believed to be hard as no one has found a way to actually compute the logarithm quickly.
But Bitcoin actually uses a slightly different version of this problem known as the Elliptic Curve Discrete Logarithm Problem (ECDLP). With EC math, b
is actually a point on an elliptic curve, it has an x
and a y
value. Rather than raising b
to some number k
, you actually do EC scalar multiplication with some number k
, so it is
bk (mod p) = a
What this boils down do is adding b
to itself k
times, and the security comes from the fact that it is hard to figure out what two points were added together to get a third point.
The process of adding an EC curve point to itself means that you find a tangent line to the point, extend the line to where it intersects the curve, and the invert the y
value of that point. Doing this, and reversing it, over the real numbers isn't that hard, but EC cryptography is done over a finite field of order p
which is a large prime, which means that all values are (mod p)
so, when you graph the curve, it's all over place in your graph. This means that, given a point on the curve, it is hard to figure out what other points were added to get to that point so it is thus hard to reverse this process.
In both ECDLP and the normal DLP, k
is the private key and solving either discrete log problem would result in you finding the private key k
.
There are algorithms such as Shors algorithm which can allow quantum computers to solve the discrete log problem.
Note that this stuff is hard and I am not a cryptography expert. This is just how I understood things and it may not be necessarily correct or make sense.
You can get bonuses upto $100 FREE BONUS when you:
π° Install these recommended apps:
π² SocialGood - 100% Crypto Back on Everyday Shopping
π² xPortal - The DeFi For The Next Billion
π² CryptoTab Browser - Lightweight, fast, and ready to mine!
π° Register on these recommended exchanges:
π‘ Binanceπ‘ Bitfinexπ‘ Bitmartπ‘ Bittrexπ‘ Bitget
π‘ CoinExπ‘ Crypto.comπ‘ Gate.ioπ‘ Huobiπ‘ Kucoin.
Comments