Bitcoin Forum
November 20, 2017, 04:28:31 AM *
News: Latest stable version of Bitcoin Core: 0.15.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: In search of specification of signmessage and verifymessage  (Read 1099 times)
AvL42
Full Member
***
Offline Offline

Activity: 195


View Profile
April 08, 2013, 04:18:19 PM
 #1

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.
1511152111
Hero Member
*
Offline Offline

Posts: 1511152111

View Profile Personal Message (Offline)

Ignore
1511152111
Reply with quote  #2

1511152111
Report to moderator
1511152111
Hero Member
*
Offline Offline

Posts: 1511152111

View Profile Personal Message (Offline)

Ignore
1511152111
Reply with quote  #2

1511152111
Report to moderator
1511152111
Hero Member
*
Offline Offline

Posts: 1511152111

View Profile Personal Message (Offline)

Ignore
1511152111
Reply with quote  #2

1511152111
Report to moderator
Join ICO Now A blockchain platform for effective freelancing
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1511152111
Hero Member
*
Offline Offline

Posts: 1511152111

View Profile Personal Message (Offline)

Ignore
1511152111
Reply with quote  #2

1511152111
Report to moderator
jackjack
Legendary
*
Offline Offline

Activity: 1120


May Bitcoin be touched by his Noodly Appendage


View Profile
April 08, 2013, 04:23:26 PM
 #2

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
Full Member
***
Offline Offline

Activity: 195


View Profile
April 08, 2013, 05:36:47 PM
 #3

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 Offline

Activity: 1120


May Bitcoin be touched by his Noodly Appendage


View Profile
April 08, 2013, 05:50:18 PM
 #4

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
Full Member
***
Offline Offline

Activity: 195


View Profile
April 08, 2013, 06:29:46 PM
 #5

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
*
expert
Offline Offline

Activity: 1526


View Profile
April 08, 2013, 07:18:05 PM
 #6

The bitcoinj implementation might be easier to understand?

https://code.google.com/p/bitcoinj/source/browse/core/src/main/java/com/google/bitcoin/core/ECKey.java#510
AvL42
Full Member
***
Offline Offline

Activity: 195


View Profile
April 08, 2013, 08:51:59 PM
 #7


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
*
expert
Offline Offline

Activity: 1526


View Profile
April 09, 2013, 02:19:11 PM
 #8

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
Full Member
***
Offline Offline

Activity: 195


View Profile
April 09, 2013, 03:51:47 PM
 #9

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
*
expert
Offline Offline

Activity: 1526


View Profile
April 09, 2013, 05:05:07 PM
 #10

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
Full Member
***
Offline Offline

Activity: 195


View Profile
April 09, 2013, 10:05:30 PM
 #11

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
Pieter Wuille
Legendary
*
qt
Offline Offline

Activity: 1050


View Profile WWW
April 09, 2013, 10:19:20 PM
 #12

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

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
AvL42
Full Member
***
Offline Offline

Activity: 195


View Profile
April 10, 2013, 09:32:56 AM
 #13

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
Legendary
*
qt
Offline Offline

Activity: 1050


View Profile WWW
April 10, 2013, 09:35:32 AM
 #14

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.

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
AvL42
Full Member
***
Offline Offline

Activity: 195


View Profile
April 10, 2013, 10:49:09 AM
 #15

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
*
expert
Offline Offline

Activity: 1526


View Profile
April 10, 2013, 03:40:08 PM
 #16

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).
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!