Topic: Compressed keys, Y from X (Read 3136 times)
I'm glad that helped!
And so it worked in my language as well. 
https://github.com/piotrnar/gocoin/blob/master/tools/versigmsg.go
Thanks again, @jackjack!
https://github.com/piotrnar/gocoin/blob/master/tools/versigmsg.go
Thanks again, @jackjack!
It's the ECC multiplication
You can look at lines 216->237 for algorithm
To understand:
http://cs.ucsb.edu/~koc/ccs130h/notes/ecdsa.pdf
http://en.wikipedia.org/wiki/Elliptic_curve_cryptography
http://en.wikipedia.org/wiki/Elliptic_curve
OK - thanks a lot, man!You can look at lines 216->237 for algorithm
To understand:
http://cs.ucsb.edu/~koc/ccs130h/notes/ecdsa.pdf
http://en.wikipedia.org/wiki/Elliptic_curve_cryptography
http://en.wikipedia.org/wiki/Elliptic_curve
That's all I needed to know.
It's the ECC multiplication
You can look at lines 216->237 for algorithm
To understand:
http://cs.ucsb.edu/~koc/ccs130h/notes/ecdsa.pdf
http://en.wikipedia.org/wiki/Elliptic_curve_cryptography
http://en.wikipedia.org/wiki/Elliptic_curve
etc...
You can look at lines 216->237 for algorithm
To understand:
http://cs.ucsb.edu/~koc/ccs130h/notes/ecdsa.pdf
http://en.wikipedia.org/wiki/Elliptic_curve_cryptography
http://en.wikipedia.org/wiki/Elliptic_curve
etc...
Indeed, it looks cool and simple - and it works!
But can you please tell me what the "R*s" (in line 406) actually does?
I mean, you have (decimals):
... and R*s gives you a point having:
So how do I multiply a point by a number to get such a result? I mean, not using python..
But can you please tell me what the "R*s" (in line 406) actually does?
I mean, you have (decimals):
Code:
Rx = 102145896445573563625240447116654222837109247557536823325858067433615090286321
Ry = 64919894836278270547560110097107560214300342546989031110129938591497073087260
s = 46415740558353013011708862292271156479711188487571029354677187424581448381078
Ry = 64919894836278270547560110097107560214300342546989031110129938591497073087260
s = 46415740558353013011708862292271156479711188487571029354677187424581448381078
... and R*s gives you a point having:
Code:
x = 112793881772482502863430761842017408792441979840968192252645857563994847441261
y = 47321320458075246750488099844078925876574705494449064910511016586200529015312
y = 47321320458075246750488099844078925876574705494449064910511016586200529015312
So how do I multiply a point by a number to get such a result? I mean, not using python..
I don't find that as complicated as in bitcoin-qt
Your specific problem is only between lines 361->412. I even left the print's so you can uncomment them to see the values
Just delete everything after line 530 and put this
Your specific problem is only between lines 361->412. I even left the print's so you can uncomment them to see the values
Just delete everything after line 530 and put this
Code:
verifySignature('mqMmY5Uc6AgWoemdbRsvkpTes5hF6p5d8w','H+HUh1GiTw22BMhqRwbSET/4aYCFIuivSgTyU/A+qH7xZp5gz61zp//WMFTbpNDbiMYoYz7pD88NYg/0DekcMpY=','test')
I don't get where those values come from...
See https://github.com/jackjack-jj/jasvet/blob/master/jasvet.py
Line 361
Thanks! I will have a look..See https://github.com/jackjack-jj/jasvet/blob/master/jasvet.py
Line 361
I was hoping that it would actually be less complicated than what I see in bitcoind+openssl
I don't get where those values come from...
See https://github.com/jackjack-jj/jasvet/blob/master/jasvet.py
Line 361
See https://github.com/jackjack-jj/jasvet/blob/master/jasvet.py
Line 361
At some point (in ec_GFp_simple_set_compressed_coordinates function) I do have:
... but then, the function calls EC_POINT_set_affine_coordinates_GFp to "assign" these x,y values into the R - and after this the R's, x and y are:
Code:
x: e1d48751a24f0db604c86a4706d2113ff869808522e8af4a04f253f03ea87ef1
y: 8f875bbc497b680cfe288eeda4bfb1da78af6703afdfaaf580e9e656ad62531c
y: 8f875bbc497b680cfe288eeda4bfb1da78af6703afdfaaf580e9e656ad62531c
... but then, the function calls EC_POINT_set_affine_coordinates_GFp to "assign" these x,y values into the R - and after this the R's, x and y are:
Code:
Rx : 7E677C42747BBDEF47AFAA51001D55A82D8C2B643EF74D6E014F64DCFD31BBA0
Ry : 0D1081A16E20A8839D892ACC384529CA4547D007B58559483991C3EB77DC71BC
Ry : 0D1081A16E20A8839D892ACC384529CA4547D007B58559483991C3EB77DC71BC
I'm finishing the code, it's coming in the following hours
Here's what I get for your test:
Yeah - that was actually my first guess, that the "Rx" should be the same as the "r", while Ry should be calculated in the same way as we calc Y from 02||X, for a compressed public key.Here's what I get for your test:
Code:
fb: 1b
recid: 0
r: e1d48751a24f0db604c86a4706d2113ff869808522e8af4a04f253f03ea87ef1
s: 669e60cfad73a7ffd63054dba4d0db88c628633ee90fcf0d620ff40de91c3296
Rx: e1d48751a24f0db604c86a4706d2113ff869808522e8af4a04f253f03ea87ef1
Ry: 8f875bbc497b680cfe288eeda4bfb1da78af6703afdfaaf580e9e656ad62531c
recid: 0
r: e1d48751a24f0db604c86a4706d2113ff869808522e8af4a04f253f03ea87ef1
s: 669e60cfad73a7ffd63054dba4d0db88c628633ee90fcf0d620ff40de91c3296
Rx: e1d48751a24f0db604c86a4706d2113ff869808522e8af4a04f253f03ea87ef1
Ry: 8f875bbc497b680cfe288eeda4bfb1da78af6703afdfaaf580e9e656ad62531c
But after I put some debugs into bitcoin's key.cpp, it seems that the EC_POINT_set_compressed_coordinates_GFp that is called from there returns completely different X.
I'm finishing the code, it's coming in the following hours
Here's what I get for your test:
As for Q:
Q = inv_r * ( R*s + G*minus_e )
Here's what I get for your test:
Code:
fb: 1b
recid: 0
r: e1d48751a24f0db604c86a4706d2113ff869808522e8af4a04f253f03ea87ef1
s: 669e60cfad73a7ffd63054dba4d0db88c628633ee90fcf0d620ff40de91c3296
Rx: e1d48751a24f0db604c86a4706d2113ff869808522e8af4a04f253f03ea87ef1
Ry: 8f875bbc497b680cfe288eeda4bfb1da78af6703afdfaaf580e9e656ad62531c
recid: 0
r: e1d48751a24f0db604c86a4706d2113ff869808522e8af4a04f253f03ea87ef1
s: 669e60cfad73a7ffd63054dba4d0db88c628633ee90fcf0d620ff40de91c3296
Rx: e1d48751a24f0db604c86a4706d2113ff869808522e8af4a04f253f03ea87ef1
Ry: 8f875bbc497b680cfe288eeda4bfb1da78af6703afdfaaf580e9e656ad62531c
As for Q:
Q = inv_r * ( R*s + G*minus_e )
May it be because it is a signature from a testnet address?
Also I was giving the intermediate R - not the Q, that comes at the end.
How to calc the Q - this was supposed to be my next question, because is seems to be even more screwed up
And then, at the very end, they take the X and Y from the Q (that is already called a "public key"):
.. and turn it into an actual bitcoin public key, where:
So how much more crazy could it be?
I spent about 6 hours today trying to figure it out, before finally deciding to seek some help on the forum.
Code:
bitcoind -testnet verifymessage mqMmY5Uc6AgWoemdbRsvkpTes5hF6p5d8w "H+HUh1GiTw22BMhqRwbSET/4aYCFIuivSgTyU/A+qH7xZp5gz61zp//WMFTbpNDbiMYoYz7pD88NYg/0DekcMpY=" test
true
And this was a compressed key.true
Also I was giving the intermediate R - not the Q, that comes at the end.
How to calc the Q - this was supposed to be my next question, because is seems to be even more screwed up
And then, at the very end, they take the X and Y from the Q (that is already called a "public key"):
Code:
Q.X: 6130AE7913286EC4D8296AEB7361420C259CD11478FB24FEDA77F81E256059AA
Q.Y: B3A6E7A704FCC0A59AC40BD364336A629483453CF39BB060F92354434B44F636
Q.Y: B3A6E7A704FCC0A59AC40BD364336A629483453CF39BB060F92354434B44F636
.. and turn it into an actual bitcoin public key, where:
Code:
X: 05eb0c4f42ecf74ab8789f2855ef33cad6ac0ec1ba6b7179578cb9f218e7793d
So how much more crazy could it be?
I spent about 6 hours today trying to figure it out, before finally deciding to seek some help on the forum.
In the mean time, could you post the message and address that give this signature?
It seems odd because Rx = r + {0;1}*q and this doesn't correspond to your example at all (first bits should be the same as q=0xffffffffffffffff...)
For exemple, signing 'bitcoin' with private key '\x01'*32 gives
It's from the top of my head, I'll post the code when I have access to my dev computer
It seems odd because Rx = r + {0;1}*q and this doesn't correspond to your example at all (first bits should be the same as q=0xffffffffffffffff...)
For exemple, signing 'bitcoin' with private key '\x01'*32 gives
Code:
Flag: 1c -> uncompressed key and Rx=r+0*q
r: b6392b8e0250550a0a068e8ba68891d555a34eb48fe6266ae042b3c689265586
s: b220ecbbe88b379812fbc920afcb15a4bd17a73f7555a5fea92b3b4c6a187523
So Rx=b6392b8e0250550a0a068e8ba68891d555a34eb48fe6266ae042b3c689265586r: b6392b8e0250550a0a068e8ba68891d555a34eb48fe6266ae042b3c689265586
s: b220ecbbe88b379812fbc920afcb15a4bd17a73f7555a5fea92b3b4c6a187523
It's from the top of my head, I'll post the code when I have access to my dev computer
I'm about to release a code for signing in Armory
If I understood correctly, it should solve your problem
OK - I'll be looking forward for it..If I understood correctly, it should solve your problem
Cheers
I'm about to release a code for signing in Armory
If I understood correctly, it should solve your problem
If I understood correctly, it should solve your problem
I have a slightly different question, but since there are some real math experts in this topic already, please let me ask it in here.
I need to write a function that recovers a public key from ECDSA signature.
It's the algorithm described in section 4.6.1 of the SEC1 spec - it seems simple, but I guess I am just too stupid to get it
Let's say that we have a signature of:
So, the operation I need to do first, is the equivalent of openssl's ec_GFp_simple_set_compressed_coordinates().
It takes X and the parity of Y, and returns some point R - right?
From what I see the actual result, for the example inputs, should be:
Could anyone please tell me how to calculate this R, preferably with some example, in python or whatever..?
I was trying to reverse engineer how openssl does it, but analyzing that code has not got me too far, so far...
Also, if you could please explain me what is an "octet string" and how is it different from a big integer expressed as MSB encoded string of bytes?
I need to write a function that recovers a public key from ECDSA signature.
It's the algorithm described in section 4.6.1 of the SEC1 spec - it seems simple, but I guess I am just too stupid to get it
Let's say that we have a signature of:
Code:
R = E1D48751A24F0DB604C86A4706D2113FF869808522E8AF4A04F253F03EA87EF1
S = 669E60CFAD73A7FFD63054DBA4D0DB88C628633EE90FCF0D620FF40DE91C3296
The 1st byte of this signature is 0x1F, but I don't think it matters at this stage. Actually it does a bit, since it says that bit(0) of Y is 0.S = 669E60CFAD73A7FFD63054DBA4D0DB88C628633EE90FCF0D620FF40DE91C3296
So, the operation I need to do first, is the equivalent of openssl's ec_GFp_simple_set_compressed_coordinates().
It takes X and the parity of Y, and returns some point R - right?
From what I see the actual result, for the example inputs, should be:
Code:
Rx : 7E677C42747BBDEF47AFAA51001D55A82D8C2B643EF74D6E014F64DCFD31BBA0
Ry : 0D1081A16E20A8839D892ACC384529CA4547D007B58559483991C3EB77DC71BC
Ry : 0D1081A16E20A8839D892ACC384529CA4547D007B58559483991C3EB77DC71BC
Could anyone please tell me how to calculate this R, preferably with some example, in python or whatever..?
I was trying to reverse engineer how openssl does it, but analyzing that code has not got me too far, so far...
Also, if you could please explain me what is an "octet string" and how is it different from a big integer expressed as MSB encoded string of bytes?
I prefer 2+Y.Bit(0) 
You can also think of it as 0x02+mod(Y,2)
02 if Y is even, 03 if odd
thanks
02 if Y is even, 03 if odd
Jump to: