[mratsim]

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.

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.

[nmadden]

The Tower Number Field Sieve is only applicable to pairing-based ECC though, right? It doesn't impact the security of the curves used in most mainstream crypto (Curve25519, NIST P-256 etc).

[mratsim]

Indeed, though if the authors are saying

> The number field sieve algorithm is still far from being fully understood, in particular for extension fields that are so important for pairing-based cryptography.

I won't say I understand it either. But it indeed seems to only be applicable in towers of extension fields which are only used for pairing-based cryptography.

[plopilop]

Nitpicking, but RSA does not rely on the DLP, rather on factorisation and modular roots. I guess you meant Elgamal or Diffie-Hellman?

[Znafon]

The discrete logarithm is the inverse operation of exponentiation and modulo. Being able to find a discrete logarithm quickly would break RSA.

[vmilner]

Shor's algorithm does exactly that by using quantum computation to solve discrete logarithms.

[plopilop]

I don't think so. Computing the discrete log of g^x assumes g to be known. In RSA the ciphertext is c = m^e and by definition, m is unknown.

The reverse operation of RSA is the modular e-th root, not the discrete log.

[archgoon]

Pick a base k.

  log_k(c) = e*log_k(m)

  log_k(c)*e^-1 = log_k(m)

Raising k by both sides yields

  k^(log_k(c)*e^-1) => m

[plopilop]

I don't think this works mod N. Since N is not a prime, you have no guarantee that for k your base, c belongs to the multiplicative group generated by k.

Take for instance N = 15, you can't find a log base 12 of 7, for instance (12 -> 9 -> 3 -> 6 -> 12). So you'd first need to find a fitting base, not sure how hard this is.

It has been proven [0] that factoring is as hard as solving DLP, but RSA also relies on the modular e-th root hypothesis, which we don't know to be as hard or easier than factoring.

In the end, because of [0] is you solve DLP you solve factoring yes, but we usually don't talk about DLP for RSA, even if as I said I was nitpicking.

[0] https://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/5973.html