4 ms·

For those curious, the reason why a public key lets you find a private key more efficiently is Pollard's rho algorithm: https://en.wikipedia.org/wiki/Pollard%27

• CamperBob2 2y ago
  These keys are based on elliptic curves rather than products of primes, aren't they?
  • matthewdgreen 2y ago
    There is one rho algorithm for discrete logarithms and one for factoring. Published three years apart.
    • sltkr 2y ago
      Neither of which helps with elliptic curve cryptography.
      • arcastroe 2y ago
        the problem of finding discrete logarithms is the same problem as breaking elliptic curve cryptography.
        • GTP 2y ago
          Technically, while the two problems share the same name, the one on elliptic curves is matematically different from the one over finite fields modulo a prime number.
          • deleted 2y ago
            [deleted]
          • AnotherGoodName 2y ago
            I politely don’t understand this. It’s taught in cryptography 101 that breaking ecc is just solving the discrete logarithm problem and there’s a ton of online articles about how to break ecc if you’ve solved the discrete logarithm problem (not that anyone has).
            • GTP 2y ago
              It's indeed called the discrete logarithm problem both in the case of finite fields modulo some number and elliptic curves modulo a number. In the first case, you are reversing an exponentiation, so you're indeed computing a logarithm. But in the case of elliptic curves you're not dealing with exponentiation, you're instead reversing the multiplication of a curve element (i. e. a point) by a scalar. The two problems (and the way you solve them) look similar in the end, and I think this is why we ended up using the same name. But, if we nitpick, those are different operations and so the two problems are different, despite the similarities. Note for cryptographers/matematicians: I know that "reversing" isn't the correct term here, so you could accuse me of the same sin I'm calling out in my previous comment. But it makes the explanation shorter while still conveying the correct meaning in the end.
            • AlexCoventry 2y ago
              There's a family of discrete logarithm problems, one for each representation of a group. (Where I mean "representation" in the usual sense, not the precise mathematical one. It's an important distinction because the secp256k1 group, for instance, is isomorphic to all cyclic groups of the same order, but the discrete logarithm problem on secp256k1 is harder than the additive group on Z/<order of secp256k1>Z, because the isomorphism is computationally intractable.) So there isn't simply one monolithic discrete logarithm problem.
      • n2d4 2y ago
        Pollard's rho algorithm can be applied to not just numbers but any cyclic group, which secp256k1 (the elliptic curve used by Bitcoin) is.
  • mrb 2y ago
    Yes, specifically secp256k1
• andrewla 2y ago
  This seems orthogonal to the concept. More efficiently than what? Having the public key is easier than having an address because an address is the hash of a public key. So in order to crack an address, you must first find a public key that produces that address, and then find a private key corresponding to the public key.
  • n2d4 2y ago
    More efficient than brute forcing a private key, as you would have to do when you don't have the public key. Sure, finding a private key whose public key's hash is given might be 2x slower, but Pollard's rho algorithm is 2^128 times faster. Asymptotically, an additional hash at the end doesn't matter when you brute force. But it prevents you from using Pollard's rho algorithm, which does make a difference asymptotically.