Post
Topic
Board Games and rounds
Re: Bitcoin Cipher/puzzle - 0.56 Prize ! Bitcoins
by
HugoTheSpider
on 19/09/2015, 18:54:07 UTC
Finally I managed to find the solution by searching 5Juu2CkB3XFdBzEcyH9dypNhDZ8fXgh6RQwwbo5* in 3h:50m:39s using an Intel i7-4xxx Smiley

The solution is:
#3 = XFdBz
#9 = ueBaf
#10 = eGYoMm5

I thank you very much for this interesting puzzle.

Congratulations! Did I read right that your bruteforce tool solves at a rate of 100,000 keys/s?
Yes and no. I created one bruteforce tool which could do 100,000 tries in one second which was being used for finding brain wallets only.

For this challenge, I created another brute force tool which did following:
1. Split the guesses in many batches
2. Assemble the first guess in the batch as a base58 string
3. Then do a base58_decode which outputs a 37 byte binary
4. Take byte #1 to #32 (counting from #0) and load it into the EC library (yes, you can ignore the checksum here)
5. Do an EC point multiplication p=G*k where p=public key, G=base point and k=your first guess
6. If ripemd160(sha256(p)) matches target, alert and stop
7. Do an EC point addition p=p+G and goto 6. until 58n/232 repetitions has been made. n is the number of characters missing at the end
8. Open a new batch and goto 2

This gave me the boost to try 500,000 valid keys in one second.
My computer found the key in under 4 hours instead of cracking for days because I told the bruteforcer to try a limited character set first. It was:
  • Alphabet 6Fabcdefghijkmnopqrstuvwxyz for puzzle #9, char #1,2,4,5
  • Alphabet 6abcdefghijkmnopqrstuvwxyzABCDEFGHJKLMNPQRSTUVWXYZ for puzzle #9, char #3
Puzzle #10 was auto-solved by the ECDSA point addition loop.


I would be happy to hear from the anonymous cracker what his/her approach was because I'm curious.