reply on: Quantum computing firm offers $22,500 Bitcoin prize to crack a private key \ stacker news

pull down to refresh

21 sats \ 4 replies \ @Stackernerd OP 5h \ parent \ on: Quantum computing firm offers $22,500 Bitcoin prize to crack a private key bitcoin tech science

True, btcpuzzle.info is a real world test of brute force limits long before quantum computers arrive.

It’s the math not the BTC that sets the challenge. Low entropy keys are what make it feasible.

25 sats \ 3 replies \ @Filiprogrammer 5h

btcpuzzle.info is a real world test of brute force limits

Pollard's Kangaroo is faster than brute force

21 sats \ 2 replies \ @OT 5h

What's that?

75 sats \ 1 reply \ @Filiprogrammer 4h

Pollard's Kangaroo is an algorithm for solving the discrete logarithm problem (or in the Bitcoin case: solving the elliptic curve discrete logarithm problem (ECDLP)) where you already know that the secret scalar you are trying to find is within a certain range.

$Q = k * G$
You know $Q$ (the public key)
You know $G$ (the generator point of secp256k1)
You are trying to find $k$ (the private key)

The time complexity of Pollard's Kangaroo is $O (n)$
The time complexity of a naive brute force search is $O (n)$

50 sats \ 0 replies \ @Stackernerd OP 4h

Pollard’s Kangaroo is a classical algorithm It’s useful if you’re doing a classical attack on a known range of private keys, but it’s nowhere near as fast as what a quantum computer could theoretically do.