Bitcoin Forum
November 21, 2017, 12:34:44 PM *
News: Latest stable version of Bitcoin Core: 0.15.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: 0.3 BTC Bounty -- C++ Big Integer Math Problem  (Read 3478 times)
Envrin
Sr. Member
****
Offline Offline

Activity: 307


Flixxo - Watch, Share, Earn!


View Profile
September 23, 2014, 06:33:55 PM
#1

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!


X       ▄▄█████████▄▄
    ▄██▀▀         ▀▀██▄
  ▄██▀              ▀██▄
 ▄██     ██▄▄          ██▄
▄██      █████▄▄        ██▄
██       ████████▄▄      ██
██       ███████████▄    ██
██       ██████████▀     ██
▀██      ███████▀       ██▀
 ▀██     ████▀         ██▀
  ▀██▄   █▀          ▄██▀
    ▀██▄▄         ▄▄██▀
       ▀▀█████████▀▀
.flixxo    X▄████████████████████▄
██████████████████████
██████████████████████
████████████▀▀███████
█████▀████░░░░░░▄████
█████░░░░░░░░░░▄█████
█████▄░░░░░░░░░░██████
██████░░░░░░░░░███████
███████░░░░░░▄████████
████▄▄░░░░▄▄██████████
██████████████████████
██████████████████████
▀████████████████████▀
▄████████████████████▄
██████████████████████
█████████▀█▀██████████
██████▀▀▀▀▀████████
██████▄▄░░▄▄▄░░███████
████████░░███░░███████
████████░░░░░░▀███████
████████░░███▄░░██████
██████▀▀░░▀▀▀░░░██████
██████▄▄▄▄▄▄███████
█████████▄█▄██████████
██████████████████████
▀████████████████████▀
X[[]]X
1511267684
Hero Member
*
Offline Offline

Posts: 1511267684

View Profile Personal Message (Offline)

Ignore
1511267684
Reply with quote  #2

1511267684
Report to moderator
Join ICO Now Coinlancer is Disrupting the Freelance marketplace!
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1511267684
Hero Member
*
Offline Offline

Posts: 1511267684

View Profile Personal Message (Offline)

Ignore
1511267684
Reply with quote  #2

1511267684
Report to moderator
1511267684
Hero Member
*
Offline Offline

Posts: 1511267684

View Profile Personal Message (Offline)

Ignore
1511267684
Reply with quote  #2

1511267684
Report to moderator
1511267684
Hero Member
*
Offline Offline

Posts: 1511267684

View Profile Personal Message (Offline)

Ignore
1511267684
Reply with quote  #2

1511267684
Report to moderator
Babba D
Member
**
Offline Offline

Activity: 112

yes my email is 49kasimk@gmail.com


View Profile
September 23, 2014, 08:05:43 PM
#2

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
Sr. Member
****
Offline Offline

Activity: 307


Flixxo - Watch, Share, Earn!


View Profile
September 23, 2014, 08:10:42 PM
#3

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.


X       ▄▄█████████▄▄
    ▄██▀▀         ▀▀██▄
  ▄██▀              ▀██▄
 ▄██     ██▄▄          ██▄
▄██      █████▄▄        ██▄
██       ████████▄▄      ██
██       ███████████▄    ██
██       ██████████▀     ██
▀██      ███████▀       ██▀
 ▀██     ████▀         ██▀
  ▀██▄   █▀          ▄██▀
    ▀██▄▄         ▄▄██▀
       ▀▀█████████▀▀
.flixxo    X▄████████████████████▄
██████████████████████
██████████████████████
████████████▀▀███████
█████▀████░░░░░░▄████
█████░░░░░░░░░░▄█████
█████▄░░░░░░░░░░██████
██████░░░░░░░░░███████
███████░░░░░░▄████████
████▄▄░░░░▄▄██████████
██████████████████████
██████████████████████
▀████████████████████▀
▄████████████████████▄
██████████████████████
█████████▀█▀██████████
██████▀▀▀▀▀████████
██████▄▄░░▄▄▄░░███████
████████░░███░░███████
████████░░░░░░▀███████
████████░░███▄░░██████
██████▀▀░░▀▀▀░░░██████
██████▄▄▄▄▄▄███████
█████████▄█▄██████████
██████████████████████
▀████████████████████▀
X[[]]X
Babba D
Member
**
Offline Offline

Activity: 112

yes my email is 49kasimk@gmail.com


View Profile
September 23, 2014, 08:12:13 PM
#4

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
Legendary
*
Offline Offline

Activity: 1092



View Profile
September 23, 2014, 08:42:11 PM
#5

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
Sr. Member
****
Offline Offline

Activity: 307


Flixxo - Watch, Share, Earn!


View Profile
September 23, 2014, 10:02:32 PM
#6

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.

X       ▄▄█████████▄▄
    ▄██▀▀         ▀▀██▄
  ▄██▀              ▀██▄
 ▄██     ██▄▄          ██▄
▄██      █████▄▄        ██▄
██       ████████▄▄      ██
██       ███████████▄    ██
██       ██████████▀     ██
▀██      ███████▀       ██▀
 ▀██     ████▀         ██▀
  ▀██▄   █▀          ▄██▀
    ▀██▄▄         ▄▄██▀
       ▀▀█████████▀▀
.flixxo    X▄████████████████████▄
██████████████████████
██████████████████████
████████████▀▀███████
█████▀████░░░░░░▄████
█████░░░░░░░░░░▄█████
█████▄░░░░░░░░░░██████
██████░░░░░░░░░███████
███████░░░░░░▄████████
████▄▄░░░░▄▄██████████
██████████████████████
██████████████████████
▀████████████████████▀
▄████████████████████▄
██████████████████████
█████████▀█▀██████████
██████▀▀▀▀▀████████
██████▄▄░░▄▄▄░░███████
████████░░███░░███████
████████░░░░░░▀███████
████████░░███▄░░██████
██████▀▀░░▀▀▀░░░██████
██████▄▄▄▄▄▄███████
█████████▄█▄██████████
██████████████████████
▀████████████████████▀
X[[]]X
elbandi
Hero Member
*****
Offline Offline

Activity: 492


View Profile
September 23, 2014, 11:57:29 PM
#7

Could you pastebin the php code?

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

Elbandi
elitenoob
Hero Member
*****
Offline Offline

Activity: 672


Scam Detector


View Profile
September 24, 2014, 12:46:13 AM
#8

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 Wink
Envrin
Sr. Member
****
Offline Offline

Activity: 307


Flixxo - Watch, Share, Earn!


View Profile
September 24, 2014, 06:03:30 AM
#9

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.



X       ▄▄█████████▄▄
    ▄██▀▀         ▀▀██▄
  ▄██▀              ▀██▄
 ▄██     ██▄▄          ██▄
▄██      █████▄▄        ██▄
██       ████████▄▄      ██
██       ███████████▄    ██
██       ██████████▀     ██
▀██      ███████▀       ██▀
 ▀██     ████▀         ██▀
  ▀██▄   █▀          ▄██▀
    ▀██▄▄         ▄▄██▀
       ▀▀█████████▀▀
.flixxo    X▄████████████████████▄
██████████████████████
██████████████████████
████████████▀▀███████
█████▀████░░░░░░▄████
█████░░░░░░░░░░▄█████
█████▄░░░░░░░░░░██████
██████░░░░░░░░░███████
███████░░░░░░▄████████
████▄▄░░░░▄▄██████████
██████████████████████
██████████████████████
▀████████████████████▀
▄████████████████████▄
██████████████████████
█████████▀█▀██████████
██████▀▀▀▀▀████████
██████▄▄░░▄▄▄░░███████
████████░░███░░███████
████████░░░░░░▀███████
████████░░███▄░░██████
██████▀▀░░▀▀▀░░░██████
██████▄▄▄▄▄▄███████
█████████▄█▄██████████
██████████████████████
▀████████████████████▀
X[[]]X
Envrin
Sr. Member
****
Offline Offline

Activity: 307


Flixxo - Watch, Share, Earn!


View Profile
September 24, 2014, 06:26:07 AM
#10


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($I064);
$I_r substr($I6464);

// 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_l16), gmp_init($private_key16)), $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

X       ▄▄█████████▄▄
    ▄██▀▀         ▀▀██▄
  ▄██▀              ▀██▄
 ▄██     ██▄▄          ██▄
▄██      █████▄▄        ██▄
██       ████████▄▄      ██
██       ███████████▄    ██
██       ██████████▀     ██
▀██      ███████▀       ██▀
 ▀██     ████▀         ██▀
  ▀██▄   █▀          ▄██▀
    ▀██▄▄         ▄▄██▀
       ▀▀█████████▀▀
.flixxo    X▄████████████████████▄
██████████████████████
██████████████████████
████████████▀▀███████
█████▀████░░░░░░▄████
█████░░░░░░░░░░▄█████
█████▄░░░░░░░░░░██████
██████░░░░░░░░░███████
███████░░░░░░▄████████
████▄▄░░░░▄▄██████████
██████████████████████
██████████████████████
▀████████████████████▀
▄████████████████████▄
██████████████████████
█████████▀█▀██████████
██████▀▀▀▀▀████████
██████▄▄░░▄▄▄░░███████
████████░░███░░███████
████████░░░░░░▀███████
████████░░███▄░░██████
██████▀▀░░▀▀▀░░░██████
██████▄▄▄▄▄▄███████
█████████▄█▄██████████
██████████████████████
▀████████████████████▀
X[[]]X
ndnh
Legendary
*
Offline Offline

Activity: 1288


New Decentralized Nuclear Hobbit


View Profile
September 24, 2014, 06:46:07 AM
#11

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
Legendary
*
Offline Offline

Activity: 1288


New Decentralized Nuclear Hobbit


View Profile
September 24, 2014, 07:04:15 AM
#12

and try this instead:

bnl = bnl + bnk
bnl = bnl % bno  or is it bnl = bno % bnl ?
Envrin
Sr. Member
****
Offline Offline

Activity: 307


Flixxo - Watch, Share, Earn!


View Profile
September 24, 2014, 07:06:20 AM
#13

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!


X       ▄▄█████████▄▄
    ▄██▀▀         ▀▀██▄
  ▄██▀              ▀██▄
 ▄██     ██▄▄          ██▄
▄██      █████▄▄        ██▄
██       ████████▄▄      ██
██       ███████████▄    ██
██       ██████████▀     ██
▀██      ███████▀       ██▀
 ▀██     ████▀         ██▀
  ▀██▄   █▀          ▄██▀
    ▀██▄▄         ▄▄██▀
       ▀▀█████████▀▀
.flixxo    X▄████████████████████▄
██████████████████████
██████████████████████
████████████▀▀███████
█████▀████░░░░░░▄████
█████░░░░░░░░░░▄█████
█████▄░░░░░░░░░░██████
██████░░░░░░░░░███████
███████░░░░░░▄████████
████▄▄░░░░▄▄██████████
██████████████████████
██████████████████████
▀████████████████████▀
▄████████████████████▄
██████████████████████
█████████▀█▀██████████
██████▀▀▀▀▀████████
██████▄▄░░▄▄▄░░███████
████████░░███░░███████
████████░░░░░░▀███████
████████░░███▄░░██████
██████▀▀░░▀▀▀░░░██████
██████▄▄▄▄▄▄███████
█████████▄█▄██████████
██████████████████████
▀████████████████████▀
X[[]]X
ndnh
Legendary
*
Offline Offline

Activity: 1288


New Decentralized Nuclear Hobbit


View Profile
September 24, 2014, 07:08:45 AM
#14

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
Sr. Member
****
Offline Offline

Activity: 307


Flixxo - Watch, Share, Earn!


View Profile
September 24, 2014, 07:25:30 AM
#15

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...


X       ▄▄█████████▄▄
    ▄██▀▀         ▀▀██▄
  ▄██▀              ▀██▄
 ▄██     ██▄▄          ██▄
▄██      █████▄▄        ██▄
██       ████████▄▄      ██
██       ███████████▄    ██
██       ██████████▀     ██
▀██      ███████▀       ██▀
 ▀██     ████▀         ██▀
  ▀██▄   █▀          ▄██▀
    ▀██▄▄         ▄▄██▀
       ▀▀█████████▀▀
.flixxo    X▄████████████████████▄
██████████████████████
██████████████████████
████████████▀▀███████
█████▀████░░░░░░▄████
█████░░░░░░░░░░▄█████
█████▄░░░░░░░░░░██████
██████░░░░░░░░░███████
███████░░░░░░▄████████
████▄▄░░░░▄▄██████████
██████████████████████
██████████████████████
▀████████████████████▀
▄████████████████████▄
██████████████████████
█████████▀█▀██████████
██████▀▀▀▀▀████████
██████▄▄░░▄▄▄░░███████
████████░░███░░███████
████████░░░░░░▀███████
████████░░███▄░░██████
██████▀▀░░▀▀▀░░░██████
██████▄▄▄▄▄▄███████
█████████▄█▄██████████
██████████████████████
▀████████████████████▀
X[[]]X
b4basit
Full Member
***
Offline Offline

Activity: 196


View Profile
September 24, 2014, 09:33:51 AM
#16

is this running wanna try  Roll Eyes

donate 14V9xuWy2fRzchkpK44ZeDbjdJprXLP2qC
elbandi
Hero Member
*****
Offline Offline

Activity: 492


View Profile
September 24, 2014, 11:48:33 AM
#17

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)...

Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!