Stealth address : Crypto question

[Nicolas Dorier]

I am currently implementing Stealth address in NBitcoin.
My naive implementation from 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.

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 ?

[genjix]

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
$ sudo bash install-sx.sh

Install locally (non-root):

Code:

$ wget https://sx.dyne.org/install-sx.sh
$ bash install-sx.sh usr/

[dabura667]

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)
    #d and c are 32 byte hex strings
    #so first turn them into integers
    int_d = int(d.encode('hex'), 16)
    int_c = int(c.encode('hex'), 16)
    #then add them and modulo the order of the curve (constant)
    int_e = (int_d + int_c) % 115792089237316195423570985008687907852837564279074904382605163141518161494337L
    #convert into a 64 digit hex number with leading 0s at the beginning. (ie. if int_e was 196, you would have '000...(64 total digits)...0C4')
    str_e = '%064x' % int_e
    #convert that 64 hex digit string into a 32 byte hex string.
    return str_e.decode('hex')

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)

[telepatheic]

dabura667 you are slightly incorrect.

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 = (y_P - y_Q) / (x_P - x_Q) mod p

x_R = s² - x_P - x_Q mod p and y_R = -y_P + s(x_P - x_R) 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

[Nicolas Dorier]

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.

[dabura667]

dabura667 you are slightly incorrect.

Elliptic curve point addition is not the same as regular addition.

P + Q = R where

s = (y_P - y_Q) / (x_P - x_Q) mod p

x_R = s² - x_P - x_Q mod p and y_R = -y_P + s(x_P - x_R) 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

[piotr_n]

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.

[Nicolas Dorier]

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

[genjix]

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.

[piotr_n]

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"

[genjix]

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