AvL42 (OP)
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
April 08, 2013, 04:18:19 PM |
|
For the sake of my own understanding, I'm trying to do my own signmessage and verifymessage implementation. Things I've found out so far are that the message gets a string "Bitcoin Signed Message:\n" prepended to it and then hashed (sha256? whatever CHashWriter produces), and for the result a flag-byte (e.g. 1B) and then the "r" and "s" are concatenated (not sure yet about endianness of those) and the resulting 65-bytestring is base64-encoded. The flag "1B" is supposed to mean: "first key with even y". Now, I'm signing message "foo" for address http://blockchain.info/fb/15mjvo a couple of times and the signature (after base64-decoding) randomly starts with 1b or 1c. But the pubkey corresponding to the address (as can be verified from existing spends from that address) definitely has an odd y coorddinate. What public key does the signmessage implementation actually use? PS: with google and also with this site's and bitcoin.it/wiki's search feature I failed to find a decent description of the algorithm used, and all my attempts to verify bitcoind's signatures with my own code failed so far. For now, I'm using the real pubkey for verification, not yet reconstructing anything from flag,r,s.
|
|
|
|
jackjack
Legendary
Offline
Activity: 1176
Merit: 1257
May Bitcoin be touched by his Noodly Appendage
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
April 08, 2013, 04:23:26 PM |
|
I'm in the train so it's not really practical to write something, but you can look at pywallet's way to sign/verify I'm not sure about how compressed public keys are handled though
|
Own address: 19QkqAza7BHFTuoz9N8UQkryP4E9jHo4N3 - Pywallet support: 1AQDfx22pKGgXnUZFL1e4UKos3QqvRzNh5 - Bitcointalk++ script support: 1Pxeccscj1ygseTdSV1qUqQCanp2B2NMM2 Pywallet: instructions. Encrypted wallet support, export/import keys/addresses, backup wallets, export/import CSV data from/into wallet, merge wallets, delete/import addresses and transactions, recover altcoins sent to bitcoin addresses, sign/verify messages and files with Bitcoin addresses, recover deleted wallets, etc.
|
|
|
AvL42 (OP)
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
April 08, 2013, 05:36:47 PM |
|
I'm in the train so it's not really practical to write something, but you can look at pywallet's way to sign/verify I'm not sure about how compressed public keys are handled though
Picked the latest version (it said 3 days ago on https://github.com/jackjack-jj/pywallet), and examined it. All the signing-related stuff had some "DER"-stuff around it, and on hashing the message no preamble is added, so I wonder, if this signing/verifying is even compatible with the satoshi client. The Satoshi-client produces signatures that don't show any sign of "DER"- encoding. The basic sign/verify math I've already implemented. My problem is the "conventions" for the interface that satoshi-client is using. PS: upon reading in your source, I noticed that you do "r = p1.x()". That should really be "r = p1.x() % n". The probability for r >= n are actually "much" higher than that of it being zero. Still searching for official satoshi-client sign&verify technical documentation.
|
|
|
|
jackjack
Legendary
Offline
Activity: 1176
Merit: 1257
May Bitcoin be touched by his Noodly Appendage
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
April 08, 2013, 05:50:18 PM |
|
I'm sure the satoshi client uses the DER format because it uses it for transactions DER is "\x30\x02"+len(r)+r+"\x02"+len(s)+s
Also, I don't use the sign and verify fonctions that are in KEY class, it's sign_digest and verify_digest
|
Own address: 19QkqAza7BHFTuoz9N8UQkryP4E9jHo4N3 - Pywallet support: 1AQDfx22pKGgXnUZFL1e4UKos3QqvRzNh5 - Bitcointalk++ script support: 1Pxeccscj1ygseTdSV1qUqQCanp2B2NMM2 Pywallet: instructions. Encrypted wallet support, export/import keys/addresses, backup wallets, export/import CSV data from/into wallet, merge wallets, delete/import addresses and transactions, recover altcoins sent to bitcoin addresses, sign/verify messages and files with Bitcoin addresses, recover deleted wallets, etc.
|
|
|
AvL42 (OP)
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
April 08, 2013, 06:29:46 PM |
|
I'm sure the satoshi client uses the DER format because it uses it for transactions DER is "\x30\x02"+len(r)+r+"\x02"+len(s)+s
Also, I don't use the sign and verify fonctions that are in KEY class, it's sign_digest and verify_digest
Well, it doesn't. Just check it. satoshi-client's signmessage output (after decoding away the base64 wrapper) doesn't start with \0x30. They decoupled the message signing from transaction signing, so a naive user couldn't inadvertedly sign a payment when signing some "random" data given by someone. That's also the reason why satoshi-client adds a fixed preamble to the text. See satoshi-source: file: "rpcwallet.cpp" search for "signmessage"/"verifymessage". PS: On looking at the source again, I'm now quite confident, that the preamble+message are indeed sha256'ed twice. I'm still having trouble to understand CKey::SetCompactSignature().
|
|
|
|
Mike Hearn
Legendary
Offline
Activity: 1526
Merit: 1129
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
April 08, 2013, 07:18:05 PM |
|
|
|
|
|
AvL42 (OP)
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
April 08, 2013, 08:51:59 PM |
|
Yes! Thanks! My head was quite aching on the C-API of openssl with all the BN_* and EC_* functions and every simple operation wrapped with an "if" for error-handling... There is some thing I don't yet understand: Why is there a test to multiply some ECGroup element times ECGroup-order and check that its the Infinity element? Isn't that always so? Checking that the point is on the curve would be much faster/ simpler: just apply the coordinates to the EC-equation. My previous question on why the flag was "1b" for a pubkey with odd Y was solved meanwhile: the Flag is not about the public key, but about that point reconstructed from "r", the "k*G" originally generated from the random number k. PS: pub-key recovery from flag,r,s now works for signatures I created myself, but not yet with signatures created from satoshi client, so I guess there's another gotcha I've yet to find.
|
|
|
|
Mike Hearn
Legendary
Offline
Activity: 1526
Merit: 1129
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
April 09, 2013, 02:19:11 PM |
|
It ends up not being infinity if the recId is not correct. It's possible to do key recovery just by incrementing the recId, though that isn't how we use it in Bitcoin text signatures.
|
|
|
|
AvL42 (OP)
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
April 09, 2013, 03:51:47 PM |
|
It ends up not being infinity if the recId is not correct. It's possible to do key recovery just by incrementing the recId, though that isn't how we use it in Bitcoin text signatures.
Incrementing the recId should really never be necessary, when we have either the public key directly at hand (as in transaction's secScripts), or the flag-byte (1b-22) from the short sig (as in message-signing). My point is, that while P**n==O is some CPU-costly test for "point on curve", (y_P)^2 == (x_P)^3 + 7 is also a test for it, and by orders of magnitude faster to evaluate. Also, the satoshi code (as well as bitcoinj) both multiply n by (recId/2), where (recId/2) is never anything else than 0 or 1. So instead of "x = (recId/2)*n + r", there could be saving the BN_mul and do "x=r; if (recId/2) { x += n }" (pseudocode, here). This snippet is merely undoing the "r=x(mod n)" part of signing, afterall. I'm primarily wondering if that piece of code just hasn't ever been reviewed after first sketch, or if I am far off on the wrong track...
|
|
|
|
Mike Hearn
Legendary
Offline
Activity: 1526
Merit: 1129
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
April 09, 2013, 05:05:07 PM |
|
I don't think you're on the wrong track. The code was written just by following the algorithm laid out in the SEC documents. Once it worked, we stopped and moved on to other things. Verifying text signatures is not a common operation so there's no reason to optimise it.
|
|
|
|
AvL42 (OP)
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
April 09, 2013, 10:05:30 PM |
|
I don't think you're on the wrong track. The code was written just by following the algorithm laid out in the SEC documents. Once it worked, we stopped and moved on to other things. Verifying text signatures is not a common operation so there's no reason to optimise it.
Makes sense. Thanks for answering ![Smiley](https://bitcointalk.org/Smileys/default/smiley.gif)
|
|
|
|
Pieter Wuille
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
April 09, 2013, 10:19:20 PM |
|
I think you are right. The check for verifying whether multiplying by the order ended up at infinity is part of the algorithm specified in the SEC specification, but is actually mathematically trivial for curves with cofactor=1 (which is the case for secp256k1).
|
I do Bitcoin stuff.
|
|
|
AvL42 (OP)
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
April 10, 2013, 09:32:56 AM |
|
I think you are right. The check for verifying whether multiplying by the order ended up at infinity is part of the algorithm specified in the SEC specification, but is actually mathematically trivial for curves with cofactor=1 (which is the case for secp256k1).
I'm not sure I understand you... The cofactor==1 primarily means that the group doesn't have any other members than powers of G. Is the "mathematically trivial" part just that the multiplication algorithm can decide to calculate P**exp or equivalently (- P **(n - exp)), the latter of which for exp==n turns into immediate infinity (maybe falling back to a mere point-on-curve check), or is there something I've missed?
|
|
|
|
Pieter Wuille
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
April 10, 2013, 09:35:32 AM |
|
I mean that for curves with cofactor==1, for every point that lies on the curve n*point will be infinity, thus that check can indeed be skipped.
|
I do Bitcoin stuff.
|
|
|
AvL42 (OP)
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
April 10, 2013, 10:49:09 AM Last edit: April 10, 2013, 11:00:20 AM by AvL42 |
|
I mean that for curves with cofactor==1, for every point that lies on the curve n*point will be infinity, thus that check can indeed be skipped.
I read the comments in that part of bitcoin-source as saying that they use P*n==O as a check for "P is valid", in order to weed out wrong guesses of recId as early as possible. Unless the openssl-function does a point-on-curve check beforehand (if it does, then it seemingly doesn't document so for EC_POINT_mul), that "early weedout" might just be a dummy. It wouldn't matter for overall correctness, anyway. The whole checking is only done on *generating* the signature, as the openssl- function for obtaining r and s doesn't provide the information for the flag. Why isn't pub-key-extraction also used in transactions? It seems to me, that this could be used even retro-actively for old blocks. It just needs to be stated (and controlled by an extra flag in the flag-byte) that to recalculate tx-hashes or block-hashes, the signScripts would need to be "patched" to old format. That's like they already get temporarily patched upon signing, too.
|
|
|
|
Mike Hearn
Legendary
Offline
Activity: 1526
Merit: 1129
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
April 10, 2013, 03:40:08 PM |
|
It could have been used on transactions but Satoshi did not know it was possible and/or was unable to implement it. He had several misconceptions about elliptic curve cryptography and generally treated OpenSSL has a block box (as evidenced by the fact that signatures don't have their DER padding removed when the rest of the protocol is so tight and optimized).
|
|
|
|
|