Game 2: First person to crack this gets 5 BTC [SOLVED]

[Ean]

When I tried to solve the last puzzle I got some ideas. Therefore I decided to give away the prize.

The new riddle:
t+3HVMPwe1rr96QryQdZtZt1LWfcXnEFSG9rKiRuv8ewxwvUmZMH1zwn/Xi4

(Address: 1QE6bWhqizxUVuq55GjL1SErVKH9YCHb7e)

[scintill]

Awesome!  It's like a new brand of "capture the flag"

So, same rules as last time?

[Ean]

So, same rules as last time?

More or less. You get 7 days, but I don't think I can give any hints without give it away.

[Ean]

Okay, I'll give you a clue:
It's not base64.

[scintill]

Okay, I'll give you a clue:
It's not base64.

Ahh, I hit dead ends investigating that angle with the last one, so I didn't think much of it this time, especially since it looks the same!

I had some ideas for non-base64, but they don't seem to be working out.  If you feel like giving another hint, maybe you can answer this: Is there significant extraneous or missing information?  (I guess the last one had a few extra bits, but for purposes of a hint I wouldn't consider them extra.)

[Ean]

Is there significant extraneous or missing information?

Nothing is missing.
In a way, you could say it's not encoded at all ...

[mb300sd]

I can't figure it out.. If thats not base64, I have no idea where to start. I assume you're also using 7-bit since its the same length.

[Ean]

It's actually closer to the answer than you think.
In a way, you don't even need to decode.

[MelMan2002]

Read the + and / as mathematical operators.  The rest is in base58Check.

private key: 5KEzAJbyWBoJdjiDAMatvGTjUTurFsyweGknk8r29tUGSS7k5o9

[Ean]

Read the + and / as mathematical operators.  The rest is in base58Check.

private key: 5KEzAJbyWBoJdjiDAMatvGTjUTurFsyweGknk8r29tUGSS7k5o9

Congratulations!
Now you just have to take the coins.

[MelMan2002]

Thought I did - have I not? 

[Ean]

Thought I did - have I not? 

I suppose.
But I can still see them in Electrum ...

[xzion]

can you give a bit more details on how to get the right result?
i still can't get it to work  

EDIT: nevermind, got it. good challenge!

[MelMan2002]

can you give a bit more details on how to get the right result?
i still can't get it to work 

Details on Base58Check can be found here:
https://en.bitcoin.it/wiki/Base58Check_encoding

Either you find a calculator that can handle a custom number system (my searches were fruitless but I'm sure that they exist) or you convert it to a number system that you can use to do the divide and addition operations.

To convert "Xi4" to base 10, for example, you would have (30*58^2)+(41*58^1)+(3*58^0)=103301

[MelMan2002]

I suppose that the other option is to do the division by hand in Base58Check but...that can be rather tricky.

[Ean]

I used these python functions for the conversion to and from integer numbers:

Code:

__b58chars = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
__b58base = len(__b58chars)

def b58encode(v):
    result = []
    while v > 0:
        v, mod = divmod(v, __b58base)
        result.append(__b58chars[mod])
    return ''.join(result[::-1])

def b58decode(v):
    return sum(__b58chars.find(c) * __b58base ** i for i, c in enumerate(v[::-1]))

[scintill]

Good job, MelMan2002!

If anyone else is wondering, here's how I replicated the result in PHP:

Code:

<?php

// adapted from
// http://darklaunch.com/2009/08/07/base58-encode-and-decode-using-php-with-example-base58-encode-base58-decode
function base58_decode($num) {
    $alphabet = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz';
    $len = strlen($num);
    $decoded = 0;
    $multi = 1;
 
    for ($i = $len - 1; $i >= 0; $i--) {
        $decoded = bcadd($decoded, bcmul($multi, strpos($alphabet, $num[$i])));
        $multi = bcmul($multi, strlen($alphabet));
    }
 
    return $decoded;
}

function base58_encode($num) {
    $alphabet = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz';
    $base_count = strlen($alphabet);
    $encoded = '';
 
    while (bccomp($num, $base_count) >= 0) {
        $div = bcdiv($num, $base_count, 0);
        $mod = bcsub($num, bcmul($base_count, $div));
        $encoded = $alphabet[$mod] . $encoded;
        $num = $div;
    }
 
    if ($num) {
        $encoded = $alphabet[(int)$num] . $encoded;
    }
 
    return $encoded;
}

// http://us2.php.net/manual/en/ref.bc.php#99130
function bcdechex($dec) {
    $last = bcmod($dec, 16);
    $remain = bcdiv(bcsub($dec, $last), 16);

    if($remain == 0) {
        return dechex($last);
    } else {
        return bcdechex($remain).dechex($last);
    }
}

$num = base58_decode('3HVMPwe1rr96QryQdZtZt1LWfcXnEFSG9rKiRuv8ewxwvUmZMH1zwn');

$num = bcdiv($num, base58_decode('Xi4'));
$key = bcadd(base58_decode('t'), $num);
echo base58_encode($num), "\n";
echo substr(bcdechex($num), 2, 64), "\n";

(No warranty or anything on this code )

If I paste the base58 output into the WIF field on Casascius' address utility, appending "?", it calculates the correct private address and adjusts the WIF to match the correct answer.  I'm not sure if this adjustment is because of a bug in my program, or if it's part of the checksum stuff.

The hex goes in fine, although I'll have to read about base58check to see why the substr is necessary.

I'm curious Ean, did you purposely camouflage this to look like base64, even the same length as the last one?  If so it seems to have been effective!

[Ean]

I'm curious Ean, did you purposely camouflage this to look like base64, even the same length as the last one?

Of course.

[MelMan2002]

I'm curious Ean, did you purposely camouflage this to look like base64, even the same length as the last one?

Of course.

Yes, very clever Ean - I enjoyed the challenge.   Thank you!

[xzion]

wasn't using the correct order of operations. doh!