Author

Topic: Stealth address : Crypto question (Read 1062 times)

legendary
Activity: 1232
Merit: 1076
May 20, 2014, 09:15:03 AM
#11
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
legendary
Activity: 2053
Merit: 1356
aka tonikt
May 18, 2014, 10:38:15 AM
#10
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"
legendary
Activity: 1232
Merit: 1076
May 18, 2014, 10:00:22 AM
#9
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.
hero member
Activity: 714
Merit: 662
May 17, 2014, 05:39:00 PM
#8
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.
legendary
Activity: 2053
Merit: 1356
aka tonikt
May 17, 2014, 04:53:14 PM
#7
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.
sr. member
Activity: 475
Merit: 252
May 17, 2014, 12:22:30 PM
#6
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.



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
hero member
Activity: 714
Merit: 662
May 17, 2014, 12:16:47 PM
#5
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.



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.
jr. member
Activity: 56
Merit: 1
May 17, 2014, 11:58:26 AM
#4
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 = (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
sr. member
Activity: 475
Merit: 252
May 17, 2014, 11:26:09 AM
#3
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')

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)
legendary
Activity: 1232
Merit: 1076
May 17, 2014, 08:17:23 AM
#2
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/
hero member
Activity: 714
Merit: 662
May 16, 2014, 07:04:04 PM
#1
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.

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 ?
Jump to: