|
Title: Stealth address : Crypto question Post by: Nicolas Dorier on May 17, 2014, 12:04:04 AM I am currently implementing Stealth address in NBitcoin.
My naive implementation from https://wiki.unsystem.net/index.php/DarkWallet/Stealth#Theory (https://wiki.unsystem.net/index.php/DarkWallet/Stealth#Theory) works fine, but I don't know why. (Yes, it works... unexpectly... sometimes) When the Receiver have knowledge of sender's public key, then it can derive the private key, from what say https://wiki.unsystem.net/index.php/DarkWallet/Stealth#Theory (https://wiki.unsystem.net/index.php/DarkWallet/Stealth#Theory). Quote private key = d + c The great mystery for me is : private key should be 32 bytes, but this addition don't ensure that.d is generated randomly because it is a private key. c is generated randomly because it is a hash. When d and c are 32 bytes, by chance, I generate the private key correctly... but if it is not, I am toasted. So how could this possibly works ? Should I modulo N the addition ? But if I do, what about result less than 32 bytes ? When I modulo N, it works fine... but why I have never 31 bytes ? Title: Re: Stealth address : Crypto question Post by: genjix on May 17, 2014, 01:17:23 PM http://sx.dyne.org/stealth.html
About your question, see: https://github.com/libbitcoin/libwallet/blob/master/src/stealth.cpp#L124 d + c should always be 32 bytes. It's the addition defined by secp256k1 which is modulo the p value. See the sx command 'ec-add' to see what your results should look like. Install globally: Code: $ wget https://sx.dyne.org/install-sx.sh Install locally (non-root): Code: $ wget https://sx.dyne.org/install-sx.sh Title: Re: Stealth address : Crypto question Post by: dabura667 on May 17, 2014, 04:26:09 PM The order you should modulo with is:
115792089237316195423570985008687907852837564279074904382605163141518161494337 (in hex, 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141) Basically, once you get your number from adding the two private keys converted into integers, modulo against the above number. (this is the order for secp256k1) in python it might look like this. (super simplified using only simple python math opperands. Code: def add_modulo(d, c) Quote When I modulo N, it works fine... but why I have never 31 bytes ? You would place leading 0s to make it 32 bytes... so if your modulo was 31 bytes when converted to hex, you would put 0x00 as the first byte. 0x38DF...(31 bytes total) would become 0x0038DF...(32 bytes total) Title: Re: Stealth address : Crypto question Post by: telepatheic on May 17, 2014, 04:58:26 PM Edit: dabura667 is correct for private key operations. Elliptic curve point addition is not the same as regular addition. Edit: but this doesn't apply in this case P + Q = R where s = (yP - yQ) / (xP - xQ) mod p xR = s2 - xP - xQ mod p and yR = -yP + s(xP - xR) mod p In the case of secp256k1 the value of p is a large prime = 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1 = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F Title: Re: Stealth address : Crypto question Post by: Nicolas Dorier on May 17, 2014, 05:16:47 PM d + c should always be 32 bytes. It's the addition defined by secp256k1 which is modulo the p value. d and c is not an addition defined by secp256k1. D and C both are normally integers, not EC Points. I agree with P and Q, but my problem is with d and c. Their addition should give 32 bytes to be a valid private key. https://github.com/libbitcoin/libwallet/blob/master/src/stealth.cpp#L124 Genjix, your source is for the address generation, which is not the part that give me problem. It is the d + c part that I don't understand. But nevertheless, I'll create my test vector with sx, it will simplify the discovery of were my bug is. Title: Re: Stealth address : Crypto question Post by: dabura667 on May 17, 2014, 05:22:30 PM dabura667 you are slightly incorrect. Elliptic curve point addition is not the same as regular addition. P + Q = R where s = (yP - yQ) / (xP - xQ) mod p xR = s2 - xP - xQ mod p and yR = -yP + s(xP - xR) mod p In the case of secp256k1 the value of p is a large prime = 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1 = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F He was talking about adding the spend private key (32byte integer) and the shared secret hash (32 byte integer). So actually it is just normal math, not adding two EC points. d + c should always be 32 bytes. It's the addition defined by secp256k1 which is modulo the p value. Wait a second, d and c is not an addition defined by secp256k1. D and C both are normally integers, not EC Points. I agree with P and Q, but my problem is with d and c. Their addition should give 32 bytes to be a valid private key. https://github.com/libbitcoin/libwallet/blob/master/src/stealth.cpp#L124 Genjix, your source is for the address generation, which is not the part that give me problem. It is the d + c part that I don't understand. But nevertheless, I'll create my test vector with sx, it will simplify the discovery of were my bug is. If you can read Python, here's the method I simplified. https://github.com/spesmilo/sx/blob/master/src/obelisk/bitcoin.py#L1104 string_to_number and number_to_string are both methods from the ecdsa python library's util.py Title: Re: Stealth address : Crypto question Post by: piotr_n on May 17, 2014, 09:53:14 PM c'mon man. what is there to not understand?
you add two numbers and mod the result by a third one - which will give you a 256-bit/32-byte number. it wont be too long - if too short, just pad it with zeros on the first (msb) bytes. i think it just cannot be more simple. Title: Re: Stealth address : Crypto question Post by: Nicolas Dorier on May 17, 2014, 10:39:00 PM c'mon man. what is there to not understand? you add two numbers and mod the result by a third one - which will give you a 256-bit/32-byte number. it wont be too long - if too short, just pad it with zeros on the first (msb) bytes. i think it just cannot be more simple. The "mod order" is not specified in https://wiki.unsystem.net/index.php/DarkWallet/Stealth#Theory (https://wiki.unsystem.net/index.php/DarkWallet/Stealth#Theory), I added it, and it worked (mod N, of the curve). I then encourtered 1 case on 100 were it broke. This was when d + c were less than 32 bytes, which made me unsure of my solution (mod N), that I found, by pure luck instead than comprehension of underlying math. I then padded bytes, but did not work, the bug was because I was using little endian. (bouncy castle is using msb) With msb, as you said, it works perfectly, so it responds to my question. But the root on my problem was that I was unsure of my solution (using mod N in the private key calculation) since it seemed to broke randomly. Then I asked the question. Anyway, the Mod N + the padding msb did the trick and it works perfectly. Title: Re: Stealth address : Crypto question Post by: genjix on May 18, 2014, 03:00:22 PM let me know what info needs to be added to the wiki. you can also make an account and add the info for other devs.
Title: Re: Stealth address : Crypto question Post by: piotr_n on May 18, 2014, 03:38:15 PM you can also make an account and add the info for other devs. I made an account there, but I cannot edit the article, nor any other I found there.am I stupid and don't know how to use mediawiki, or what? all I see is a "view source" button where I'd expect "edit" Title: Re: Stealth address : Crypto question Post by: genjix on May 20, 2014, 02:15:03 PM you can also make an account and add the info for other devs. I made an account there, but I cannot edit the article, nor any other I found there.am I stupid and don't know how to use mediawiki, or what? all I see is a "view source" button where I'd expect "edit" piotr we have tons of spammers trying to attack the Wiki. Until we have a solution (working on it), PM me your nickname and I'll authorise you. Also you can PM me on Freenode IRC (genjix) in #darkwallet |