2

Hi I was just looking for some information on how long it would take to crack a private key in bitcoin using a brute force approach and I couldn't find a very good answer for how long it takes to check whether one specific key (or every key) would work.

So essentially what I am asking is how long would the elliptic curve multiplication process take to check whether a single private key would work for a given public key (on average), thanks :)

Improve this question

1 Answer 1

Reset to default
1

The only way to determine the private key associated with a given public key is by a brute force method, spanning the entire 2^256 key space. More specifically, any number from 0x1 to 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364140 (order of G) is a valid private key.

According to an article on wikipedia on brute force cryptography, it would take 50 supercomputers that could check 10^18 keys per second about 3x10^51 years to exhaust the 256 bit key space. However, this number fails to account for theoretical limits of energy consumption and computation from Landauer's principle. I decided to put in some work to show the theoretical limits.

Landauer's Principle

Laundauer's principle basically provides us with the lower limit of energy consumption needed to flip a bit as a function of temperature (it is much more complex, but we can leave that aside for now.) That lower limit is given by the formula: kT * ln(2) (where k is the Boltzmann constant (1.38*10^-23) and T is temperature in Kelvin scale.) So, for a 2^256 key space, that energy is 2^256*kT*ln(2). The energy that I'm calculating below, is only to generate keys in the 2^256 key space, and does not involve the energy to generate public keys from them and check the result.

Since I'm in Mumbai, I will take the liberty to use temperature of 25 degree celsius or 298 Kelvin. Using the above formula, E = 2^256*kT*ln(2), we get energy as 3.3x10^56. According to this article, the global electricity consumption was 21,700 TWh in 2017. That's equivalent to 7.8*10^19 Joules. So, even assuming that world's entire electricity supply is diverted to generation of the keys in 256-bit key space, we would still need electricity that is 5*10^36 times more than that is generated today.

Improve this answer
4
  • 1
    There are better (known) ways than brute force to determine the private key using for example Baby-step giant-step or Pollard's rho algorithm. Both have running time in O(sqrt(n)) where in our case n is close to 2^256.
    – nickler
    Mar 21, 2019 at 15:14
  • @nickler That's why we use 256-bit keys with elliptic curve algorithms even though 128 bits is sufficient for AES keys. The public key does leak some information about the private key, and we need the private key to still have enough hidden information left over after that to be secure.
    – David Schwartz
    Mar 21, 2019 at 19:16
  • @DavidSchwartz just out out curiosity, do you have any sources talking about how the public key leaks information? I would be quite interested in reading that :)
    – Matt
    Mar 21, 2019 at 23:20
  • 1
    @Matt See either Big Step / Little Step or Pollard's Rho for details. A simple way to get the general idea is that if you guess at the private key and the public key that results is not close to the actual public key, your guess at the private key cannot be close to the real private key. So you don't have to try every possible private key.
    – David Schwartz
    Mar 22, 2019 at 0:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.