0.3 BTC Bounty -- C++ Big Integer Math Problem

[Envrin]

Post a working solution to the problem below, along with your BTC address, and I'll send you 0.3 BTC.  First come, first served.  For proof that I do pay bounties instantly upon a working solution, please see this thread.

Basically, I need to do a bunch of the math calculations in C++ (using Qt), and am stuck with deriving a BIP32 child key.  I do have a fair bit done though.  I can input a BIP32 private key, pick it apart, get the public key using ECDSA (compressed or uncompressed), I can encode the address from the key, and so on.

However, I'm stuck on deriving a child key.  I can do the math just fine with PHP's gmp library, but I can't get the results from the PHP and C++ code to match up.  They should match up perfectly, since it's just math.  I've tried both, QCA (http://delta.affinix.com/docs/qca/) and just using BIGNUM data type to no avail.  So here's the problem:


Compressed Public Key:  023E4740D0BA639E28963F3476157B7CF2FB7C6FDF4254F97099CF8670B505EA59
Private Key:            5c22f8937210130ad1bbc50678a7c0a119a483d47928c323bf0baa3a57fa547d
Chain Code:             180c998615636cd875aa70c71cfa6b7bf570187a56d8c6d054e60b644d13e9d3
Key Index:              35 (00000023)


Here's a small chunk of code I currently have.

Code:

QByteArray pubkey = "023E4740D0BA639E28963F3476157B7CF2FB7C6FDF4254F97099CF8670B505EA5900000023";
QByteArray privkey = "5c22f8937210130ad1bbc50678a7c0a119a483d47928c323bf0baa3a57fa547d";
QByteArray chain_code = "180c998615636cd875aa70c71cfa6b7bf570187a56d8c6d054e60b644d13e9d3";

// HMAC SHA512 Hash
QCA::MessageAuthenticationCode hmac("hmac(sha512)", QCA::SecureArray());
QCA::SecureArray karr(chain_code);
QCA::SymmetricKey sk(karr);
hmac.setup(sk);
hmac.update(QCA::hexToArray(pubkey));

// Parse resulting hash
QByteArray result = hmac.final().toByteArray();
QCA::SecureArray arr_left(result.left(32));
QCA::SecureArray arr_key(privkey);

// Get big integers
QCA::BigInteger bnl(arr_left);
QCA::BigInteger bnk(arr_key);
QCA::BigInteger bno("115792089237316195423570985008687907852837564279074904382605163141518161494337");

// Do the math
bnl += bnk;
bnl %= bno;

// Return
QByteArray new_key = bnl.toArray().toByteArray().toHex();
return new_key;

The HMAC SHA512 hash is fine, and I get the correct result from both, PHP and C++, which is:  fa634546bbddad6f51e8a7ff05976e0d8813aafb656bf0c7cacb53a200e9e3e624e199e9e83fa03 eedd5056ac2de8482be17fcb6d85ebf15faa1976e5df957aa

However, that's where it ends.  Basically, I need the remainder of ((bnl + bnk) / bno).  Problem seems to start just after the addition, as the results I get are just slightly different:

PHP:   56863dda2dedc07a23a46d057e3f2eaea1b82ecfde94b3eb89d6fddc58e43863
C++    156863dda2dedc07a23a46d057e3f2eaea1b82ecfde94b3eb89d6fddc58e43863

For whatever reason, the C++ variant is throwing an extra '1' on the beginning.  If I try to convert any of the integers into strings, they're completely off from what PHP gives me as strings for the numbers.  Anyway, here's the current results I get for the new private key:

PHP:   56863dda2dedc07a23a46d057e3f2eafe70951e92f4c13afca049f4f88adf722
C++:   56863dda2dedc07a23a46d057e3f2eaea1b82ecfde94b3eb89d6fddc58e43863

I need a solution in C++ (using QCA, BIGNUM, whatever -- although I would prefer QCA) that does the proper math, and gives me the same result I'm getting in PHP.  If you know how, please post your solution here along with your BTC address, and I'll send 0.3 BTC right away.  Thanks!

[1714110363]

1714110363

[1714110363]

1714110363

[Babba D]

I have someone who can do this for like 0.05 btc , but i don't have any if u pay me 0.05 btc now i will send him and get it solved , after solved u can pay me rest 0.025 otherwise i give u -ve rep . BTC  address always in my signature space

[Envrin]

I have someone who can do this for like 0.05 btc , but i don't have any if u pay me 0.05 btc now i will send him and get it solved , after solved u can pay me rest 0.025 otherwise i give u -ve rep . BTC  address always in my signature space

Ummm, let's not and say we did.

[Babba D]

I have someone who can do this for like 0.05 btc , but i don't have any if u pay me 0.05 btc now i will send him and get it solved , after solved u can pay me rest 0.025 otherwise i give u -ve rep . BTC  address always in my signature space

Ummm, let's not and say we did.

k np

[yayayo]

I'm not a C++ programmer and haven't a proper setup to test anything, but I smell the problem could have something to do with the array conversion at this step:

Code:

QByteArray new_key = bnl.toArray().toByteArray().toHex();

Is it possible that within this concatenated conversion process an additional array element is allocated which must be stripped off?


Edit1: Sorry, logical mistake... the error must have occured earlier.

Edit2: Question: What is the result if you calculate the same as:

Code:

// Do the math
bnl %= bno;
bnk %= bno;

bnl += bnk;
bnl %= bno;

?


ya.ya.yo!

[Envrin]

Sorry yayayo, but nope!

Ok, 0.4 BTC it is then!  I'm going to get some sleep, but I'll check this thread right upon waking up, and if anyone can resolve this, you'll have an extra 0.4 BTC to your name.  At current market rate, that's about $200.  Not bad...

Again, first come, first served.  Post your solution here publicly, so I know you were first.

[elbandi]

Could you pastebin the php code?

(i got different HMAC SHA512... :/ )

Elbandi

[elitenoob]

Sorry yayayo, but nope!

Ok, 0.4 BTC it is then!  I'm going to get some sleep, but I'll check this thread right upon waking up, and if anyone can resolve this, you'll have an extra 0.4 BTC to your name.  At current market rate, that's about $200.  Not bad...

Again, first come, first served.  Post your solution here publicly, so I know you were first.

i Suggest you to put funds into some escrow wallet, else you may just get away with the info you need without paying

[Envrin]

Could you pastebin the php code?

(i got different HMAC SHA512... :/ )

Elbandi

Sure, full contents of the bip32.h and bip32.cpp files are at:

http://pastebin.com/vCqtspFV

Then here's the code I'm currently running just to test the different functions:

Code:

bip32 *bp32 = new bip32();
bp32->import("xprv9s21ZrQH143K2JF8RafpqtKiTbsbaxEeUaMnNHsm5o6wCW3z8ySyH4UxFVSfZ8n7ESu7fgir8imbZKLYVBxFPND1pniTZ81vKfd45EHKX73");
QByteArray pubkey = bp32->private_to_public();
QString addr = bp32->get_addr();
bp32->get_definition_tuple("35");

QString ckey = bp32->derive_child_key();
txtPrivateKey->setPlainText(ckey);

Pretty much all functions are working fine, albeit some are incomplete.  The one I need help with is the last function there, derive_child_key().  Everything seems to work fine, up until I do that modulus operation.  Then it simply craps out, and doesn't seem to perform any math at all, as it doesn't modify the bnl variable at all.

[Envrin]

Had a request for the PHP code as well, so here's a chunk of code that works fine. 

Code:

<?php

$chain_code = "180c998615636cd875aa70c71cfa6b7bf570187a56d8c6d054e60b644d13e9d3";
$private_key = "5c22f8937210130ad1bbc50678a7c0a119a483d47928c323bf0baa3a57fa547d";
$pubkey = "023E4740D0BA639E28963F3476157B7CF2FB7C6FDF4254F97099CF8670B505EA5900000023";

// Hash data
$I = hash_hmac('sha512', pack("H*", $pubkey), pack("H*", $chain_code));
$I_l = substr($I, 0, 64);
$I_r = substr($I, 64, 64);
		
// Initialize curve
$g = SECcurve::generator_secp256k1();
$n = $g->getOrder();

// Generate key		
$key = str_pad(gmp_strval(gmp_Utils::gmp_mod2(gmp_add(gmp_init($I_l, 16), gmp_init($private_key, 16)), $n), 16), 64, '0', STR_PAD_LEFT);
if(!isset($key)) return FALSE;

echo "NEW KEY:  $key\n";

?>

That gmp_Utils::mod2() function can be found at the very top of this Github page.

For that PHP code to work properly you need the entire library at:  https://github.com/Bit-Wasp/bitcoin-lib-php

[ndnh]

Turns out, i don't know a thing about C++

In simple words, what is the question? Can you simplify it?

http://www.mibsoftware.com/php2cpp/
http://sourceforge.net/projects/binaryphp/

is it just that you are getting a 1 you shouldn't be getting?

is this part correct?

Code:

/ Get key
   [b] if (key_type == "private") {
        decoded.remove(0, 1);
        key = decoded.left(32);
        decoded.remove(0, 32);[/b]
    } else {
        key = decoded.left(33);
        decoded.remove(0, 33);
    }

[ndnh]

and try this instead:

bnl = bnl + bnk
bnl = bnl % bno  or is it bnl = bno % bnl ?

[Envrin]

Oh shit, I got it!  I don't really know how, but I did.  Just used this:

Code:

    // Do the math
    bnl += bnk;
    QCA::BigInteger bnd(bnl);
    bnd /= bno;

    if (bnd > 0) {
        bnd *= bno;
        bnl -= bnd;
    } else { bnl -= bno; }

    // Return
    QByteArray new_key = bnl.toArray().toByteArray();
    return new_key.remove(0, 1).toHex();

Sorry, reward now closed!

[ndnh]

Oh shit, I got it!  I don't really know how, but I did.  Just used this:

Code:

    // Do the math
    bnl += bnk;
    QCA::BigInteger bnd(bnl);
    bnd /= bno;

    if (bnd > 0) {
        bnd *= bno;
        bnl -= bnd;
    } else { bnl -= bno; }

    // Return
    QByteArray new_key = bnl.toArray().toByteArray();
    return new_key.remove(0, 1).toHex();

Sorry, reward now closed!

From my limited knowledge, i think the entire problem came from this %=

if you have any problems like this, just post it on stackoverflow.

Can u still say whether this works?

and try this instead:

bnl = bnl + bnk
bnl = bnl % bno  or is it bnl = bno % bnl ?

try both.

[Envrin]

Can u still say whether this works?

and try this instead:

bnl = bnl + bnk
bnl = bnl % bno  or is it bnl = bno % bnl ?

Nope, I can't use operations like that (eg. bnl = bnl + bnk).  It throws errors for some reason, hence why I have "bnl += bnk" type operations instead.  That's the only way I can get it to compile without errors.  Documentation says "bnl = bnl + bnk" should work fine, but it doesn't for me at least.

Then things like "bnl %= bno" work fine for just standard integers, but don't seem to work at all for QCA::BigInteger data types.  Not sure why, but doesn't.

Well, that was a fun 3 days...

[b4basit]

is this running wanna try  

[elbandi]

hmm...

Oh shit, I got it!  I don't really know how, but I did.  Just used this:

Yeah, it works, because you simply remove the first character ( new_key.remove(0, 1).toHex() ).

Anyway, this code

Code:

    QCA::BigInteger bnd(bnl);
    bnd /= bno;

    if (bnd > 0) {
        bnd *= bno;
        bnl -= bnd;
    } else { bnl -= bno; }

equivalent to the modulo division ( bnl % bno), only just incorrectly (if bnd is 1 and bno is 2, after /=, bnd will 0, else is runing and bnl is -1)...