Big mistake in the article: the discrete log is not a trapdoor function, as far as we know, and elliptic curve crypto does not rely on trapdoors.
A trapdoor function is when you have a function hard to invert (for any x, given y = f(x), find x), which inversion becomes very easy once you know some additional info.
For instance in RSA, given c = m^e mod N, it is hard to find m. Unless you know d such that e*d = 1 mod phi(N), then you can easily find m by computing m = c^d mod N.
There is no known way of easily inverting exponentiation on finite groups.
To quote Wikipedia, "Functions related to the hardness of the discrete logarithm problem [...] are not known to be trapdoor functions, because there is no known "trapdoor" information about the group that enables the efficient computation of discrete logarithms. "
> This is a great trapdoor function because if you know where the starting point (A) is and how many hops are required to get to the ending point (E), it is very easy to find the ending point. On the other hand, if all you know is where the starting point and ending point are, it is nearly impossible to find how many hops it took to get there.
> Public Key: Starting Point A, Ending Point E
> Private Key: Number of hops from A to E
So basically the number of hops is the secret. Couldn't I simply "brute force" the hop count? Does this mean that a higher hop count is equal to a better private key?
You can't, this is called ECDLP (Elliptic Curve Discrete Logarithm Problem) and the cornerstone of elliptic curve cryptography security.
Currently the ECDLP problem can only be solved by Pollard Rho which requires exponential time though recent advances by Barbulescu et al on the Tower Number Field Sieve significantly reduced the security of ECC in 2017 (by 10~30 bits, i.e. what was though 128-bit secure i.e. 256-bit curves keys are now somewhere between 100~115-bit secure).
Note that the DLP problem (Discrete Logarithm Problem) which is the corner stone of RSA security has significantly more efficient algorithms than Pollard Rho as it can use techniques taken from integer factorization.
It is known however that asymmetric ECC can be broken by quantum computers in polynomial (?) or polylogarithmic (?) time by quantum computer and so new techniques, for example Isogeny-based ECC are being actively researched.
Yes, the bruteforce attack is a valid one. No, because usually the private key is around 256 bits, so you need to compute 2^255 hops on average to find the key.
The current biggest supercomputer can compute 10^17 flops/sec, assume you can do as many hops/sec. It still requires you 10^52 years to find the key.
The same is true for RSA : given a number N, find the two prime numbers p, q such that N = p * q. Trivial for N=15, a computer can do 13201225834171 = 1564571 * 8437601 in a matter of a second. However, current RSA N numbers have ~627 digits and we don't expect them to be factored in a reasonable amount of time.
As the other commenter said, there are much more efficient algorithms than bruteforce, but for current RSA keys (2048 bits) and ECC keys (256 bits), they are not reasonably efficient.
> Does this mean that a higher hop count is equal to a better private key?
So yes, the size of the key is a very important indicator of the strength of the key (but long keys can still be super weak if you don't generate them correctly). However bigger keys also result in longer encryption/decryption times.
[+] [-] plopilop|5 years ago|reply
A trapdoor function is when you have a function hard to invert (for any x, given y = f(x), find x), which inversion becomes very easy once you know some additional info. For instance in RSA, given c = m^e mod N, it is hard to find m. Unless you know d such that e*d = 1 mod phi(N), then you can easily find m by computing m = c^d mod N.
There is no known way of easily inverting exponentiation on finite groups.
To quote Wikipedia, "Functions related to the hardness of the discrete logarithm problem [...] are not known to be trapdoor functions, because there is no known "trapdoor" information about the group that enables the efficient computation of discrete logarithms. "
[+] [-] lanecwagner|5 years ago|reply
[+] [-] quaker20|5 years ago|reply
[+] [-] agazso|5 years ago|reply
Thanks!
[+] [-] thatsmee|5 years ago|reply
> Public Key: Starting Point A, Ending Point E
> Private Key: Number of hops from A to E
So basically the number of hops is the secret. Couldn't I simply "brute force" the hop count? Does this mean that a higher hop count is equal to a better private key?
[+] [-] mratsim|5 years ago|reply
Currently the ECDLP problem can only be solved by Pollard Rho which requires exponential time though recent advances by Barbulescu et al on the Tower Number Field Sieve significantly reduced the security of ECC in 2017 (by 10~30 bits, i.e. what was though 128-bit secure i.e. 256-bit curves keys are now somewhere between 100~115-bit secure).
Note that the DLP problem (Discrete Logarithm Problem) which is the corner stone of RSA security has significantly more efficient algorithms than Pollard Rho as it can use techniques taken from integer factorization.
https://en.wikipedia.org/wiki/Discrete_logarithm
It is known however that asymmetric ECC can be broken by quantum computers in polynomial (?) or polylogarithmic (?) time by quantum computer and so new techniques, for example Isogeny-based ECC are being actively researched.
[+] [-] plopilop|5 years ago|reply
Well, yes and no.
Yes, the bruteforce attack is a valid one. No, because usually the private key is around 256 bits, so you need to compute 2^255 hops on average to find the key.
The current biggest supercomputer can compute 10^17 flops/sec, assume you can do as many hops/sec. It still requires you 10^52 years to find the key.
The same is true for RSA : given a number N, find the two prime numbers p, q such that N = p * q. Trivial for N=15, a computer can do 13201225834171 = 1564571 * 8437601 in a matter of a second. However, current RSA N numbers have ~627 digits and we don't expect them to be factored in a reasonable amount of time.
As the other commenter said, there are much more efficient algorithms than bruteforce, but for current RSA keys (2048 bits) and ECC keys (256 bits), they are not reasonably efficient.
> Does this mean that a higher hop count is equal to a better private key?
So yes, the size of the key is a very important indicator of the strength of the key (but long keys can still be super weak if you don't generate them correctly). However bigger keys also result in longer encryption/decryption times.
[+] [-] unknown|5 years ago|reply
[deleted]