Title: Is possible get public key from signature? Post by: Frodek on October 11, 2019, 02:29:24 PM Transaction inputs script are usually (but coinbase) 73 bytes signature + 65 bytes key.
But in rare cases I see is only 73 bytes signature. Is possible get 65 or 33 key from it? I see https://learnmeabitcoin.com/guide/digital_signatures_signing_verifying (https://learnmeabitcoin.com/guide/digital_signatures_signing_verifying) https://learnmeabitcoin.com/guide/digital_signatures (https://learnmeabitcoin.com/guide/digital_signatures) But I don't know which bytes is messages which is "r" and "s" to divide. I wanna example how to get key from 73 bytes signature (or maybe from signature and message=other fields of input, like amount etc?) Title: Re: Is possible get public key from signature? Post by: Coding Enthusiast on October 11, 2019, 04:14:07 PM First let's get something out of the way, "scripts" are just scripts. Think of them as a series of data and commands that programmatically define the locking and unlocking conditions for each transaction. They don't have to contain signature + public key. They can have multiple signatures or no signatures at all. For example this script I posted recently (https://bitcointalk.org/index.php?topic=5169180.msg51977316#msg51977316) is a simple mathematical formula (2+3=5) as the signature!
In bitcoin when an ECDSA signature is provided it will always be accompanied by the corresponding public key. In other words the blockchain already contains the pubkey you just have to first have to figure out the type of script they are using and locate it based on that. There can be lots of scripts but a handful are the most common (and considered standard): - P2PK (uncommon these days) -> the public key will be in previous transaction's (tx being spent) PubkeyScript (aka scriptpub) - P2PKH (aka legacy) -> pubkey is in SignatureScript (aka scriptsig) - P2SH -> in common cases the pub key(s) are in redeem script which is the last item being pushed in SignatureScript - P2WPKH (aka native SegWit) -> pubkey is in witness item corresponding to the input index. - P2WSH (aka native SegWit script hash) -> similar to P2SH but it will be in witness items - nested SegWit (P2WPKH-P2SH and P2WSH-P2SH) are similar to their native counterparts and have the "sig+pub" in their witness The only thing remaining is to deserialize the transaction bytes into an object (or basically read it byte by byte) to get to the public key. A short example (https://www.blockchain.com/btc/tx/d4a73f51ab7ee7acb4cf0505d1fab34661666c461488e58ec30281e2becd93e2?show_adv=true): Script Sig: Code: 483045022100f3581e1972ae8ac7c7367a7a253bc1135223adb9a468bb3a59233f45bc578380022059af01ca17d00e41837a1d58e97aa31bae584edec28d35bd96923690913bae9a0141049c02bfc97ef236ce6d8fe5d94013c721e915982acd2b12b65d9b7d59e20a842005f8fc4e02532e873d37b96f09d6d4511ada8f14042f46614a4c70c0f14beff5 Code: 48 <-push Title: Re: Is possible get public key from signature? Post by: Frodek on October 11, 2019, 08:43:24 PM Thanks!
I previously thougt that "r" and "s" is one array r and s are relative smaller numbers than key How compute key? I have "r" and "s" but what is number "message". Whose numbers I must divide by them? Code: 049c02bfc97ef236ce6d8fe5d94013c721e915982acd2b12b65d9b7d59e20a842005f8fc4e02532e873d37b96f09d6d4511ada8f14042f46614a4c70c0f14beff5 But is possible compute key from r and s knowing "message"? Title: Re: Is possible get public key from signature? Post by: bitaps on October 11, 2019, 09:15:06 PM Yes it is possible but each signature corresponds to 4 possible public key (only 2 in most cases) and you should check all of them
please read this https://crypto.stackexchange.com/questions/60218/recovery-public-key-from-secp256k1-signature-and-message implementation on python https://github.com/bitaps-com/pybtc/blob/master/pybtc/functions/script.py#L432 This is example of usage https://github.com/bitaps-com/pybtc/blob/master/pybtc/transaction.py#L895 https://github.com/bitaps-com/pybtc/blob/master/pybtc/test/transaction_constructor.py#L561 Title: Re: Is possible get public key from signature? Post by: Coding Enthusiast on October 12, 2019, 03:38:01 AM r and s are relative smaller numbers than key If by "key" you mean the public key, you can't define "smaller or bigger" for points (pubkey is also a point). As for the length of them in bytes or the values compared to each other (r with pubkey.x) there still is no reason for it being smaller or bigger. These are numbers that could take up from 1 byte to 32 bytes (ignoring the sign byte). How compute key? I have "r" and "s" but what is number "message". The SE link (https://crypto.stackexchange.com/questions/60218/recovery-public-key-from-secp256k1-signature-and-message) posted by above user explains it. The "message" for a transaction is double SHA256 hash of the serialized transaction in a different way depending on the SigHashType and the output type (PublicScript) that is being spent. Example of SigHashType.ALL and P2PKH output: https://bitcoin.stackexchange.com/questions/32628/redeeming-a-raw-transaction-step-by-step-example-required Title: Re: Is possible get public key from signature? Post by: achow101 on October 12, 2019, 05:14:27 AM Transaction inputs script are usually (but coinbase) 73 bytes signature + 65 bytes key. In those cases, the public key is in the blockchain as part of the output. The output is a P2PK output. Bitcoin does not use public key recovery anywhere in transaction validation.But in rare cases I see is only 73 bytes signature. Is possible get 65 or 33 key from it? I see https://learnmeabitcoin.com/guide/digital_signatures_signing_verifying (https://learnmeabitcoin.com/guide/digital_signatures_signing_verifying) https://learnmeabitcoin.com/guide/digital_signatures (https://learnmeabitcoin.com/guide/digital_signatures) But I don't know which bytes is messages which is "r" and "s" to divide. I wanna example how to get key from 73 bytes signature (or maybe from signature and message=other fields of input, like amount etc?) R and s are part of the signature. The signature is a DER encoded signature, and the breakdown of the encoding is given by Coding Enthusiast above. Thanks! It is. In Bitcoin, it is one item: a DER encoded signature. Because it is encoded, it can be further broken down into the R and s components. This is done by signature verifiers; Bitcoin itself (i.e. consensus and the script evaluator), do not care that it is encoded and just treat the signature as a single array.I previously thougt that "r" and "s" is one array r and s are relative smaller numbers than key The key itself can be broken down into X and Y components, each of which are of the same magnitude of R and s. The key is also encoded.How compute key? I have "r" and "s" but what is number "message". The message is the double SHA256 of the transaction with some modification. For your specific example/question, this SE question and answer should be sufficient: https://bitcoin.stackexchange.com/questions/3374/how-to-redeem-a-basic-tx.r and s are two numbers that represent x and y coordinates on the elliptic curve used in bitcoin (secp256k1). They are not. The signature is not a curve point.R is the X component of the "public key" of the nonce. S is just a scalar computed by the ECDSA formula. Title: Re: Is possible get public key from signature? Post by: bitaps on October 12, 2019, 05:33:05 AM How compute key? I have "r" and "s" but what is number "message". The message is the double SHA256 of the transaction with some modification. For your specific example/question, this SE question and answer should be sufficient: https://bitcoin.stackexchange.com/questions/3374/how-to-redeem-a-basic-tx.The "message" in bitcoin transaction signing process this is sighash. We have 2 classes of sighash today, first one is sighash for non segwit inputs and second for segwit inputs. Sighash calculation algorithm: for non witness inputs explained here: https://en.bitcoin.it/wiki/OP_CHECKSIG python implementation: https://github.com/bitaps-com/pybtc/blob/master/pybtc/transaction.py#L947 tests and examples: https://github.com/bitaps-com/pybtc/blob/master/pybtc/test/sighash.py#L14 for witness inputs defined in BIP 143 https://github.com/bitcoin/bips/blob/master/bip-0143.mediawiki#specification python implementation: https://github.com/bitaps-com/pybtc/blob/master/pybtc/transaction.py#L1020 tests and examples: https://github.com/bitaps-com/pybtc/blob/master/pybtc/test/sighash.py#L521 Title: Re: Is possible get public key from signature? Post by: Frodek on October 14, 2019, 04:05:17 PM I can' t understand because is
48 <-push 30-45 <-seq. tag + len Hexadecinal 0x48 because in script.h is Code: enum opcodetype Title: Re: Is possible get public key from signature? Post by: Coding Enthusiast on October 14, 2019, 04:14:47 PM I can' t understand because is 0x48 is len, not push? True, it is length of the data to be "pushed" onto the stack. These bytes (from 0x01 to 0x4b) have no name because there is no point in naming them since they each indicate the length equal to their value, so they could be referred to as "push" OPs. Title: Re: Is possible get public key from signature? Post by: Frodek on October 15, 2019, 04:38:39 PM I see Bitcoin method:
Quote bool CPubKey::RecoverCompact(const uint256 &hash, const std::vector<unsigned char>& vchSig) { What is compact signature? It have 65 bytes instead of 73. This are r+s numbers alone?if (vchSig.size() != COMPACT_SIGNATURE_SIZE) return false; int recid = (vchSig[0] - 27) & 3; bool fComp = ((vchSig[0] - 27) & 4) != 0; secp256k1_pubkey pubkey; secp256k1_ecdsa_recoverable_signature sig; if (!secp256k1_ecdsa_recoverable_signature_parse_compact(secp256k1_context_verify, &sig, &vchSig[1], recid)) { return false; } if (!secp256k1_ecdsa_recover(secp256k1_context_verify, &pubkey, &sig, hash.begin())) { return false; } unsigned char pub[PUBLIC_KEY_SIZE]; size_t publen = PUBLIC_KEY_SIZE; secp256k1_ec_pubkey_serialize(secp256k1_context_verify, pub, &publen, &pubkey, fComp ? SECP256K1_EC_COMPRESSED : SECP256K1_EC_UNCOMPRESSED); Set(pub, pub + publen); return true; } How I find if r have 32 or 33 bytes? Title: Re: Is possible get public key from signature? Post by: bitaps on October 15, 2019, 06:06:21 PM Bitcoin used DER signature format:
Code: Format: 0x30 [total-length] 0x02 [R-length] [R] 0x02 [S-length] [S] [sighash] Code: compact signature = [R][S] Code: static int secp256k1_ecdsa_sig_parse(secp256k1_scalar *rr, secp256k1_scalar *rs, const unsigned char *sig, size_t size) { secp256k1_der_parse_integer used to parse R and S from DER https://github.com/bitcoin/bitcoin/blob/452bb90c718da18a79bfad50ff9b7d1c8f1b4aa3/src/secp256k1/src/ecdsa_impl.h#L99 Title: Re: Is possible get public key from signature? Post by: Coding Enthusiast on October 15, 2019, 06:32:27 PM R and S is always 32 bytes after DER encoding r and s are both at most 32 bytes with 1 byte for sign if the most significant bit is set (they can be smaller than 32 bytes). Title: Re: Is possible get public key from signature? Post by: bitaps on October 15, 2019, 06:36:49 PM In context of compact signature format r and s 32 bytes, this is not about actual value
Title: Re: Is possible get public key from signature? Post by: Frodek on October 16, 2019, 04:56:07 PM Now, let try it with example: (this exmaple is from LTC block 500186, but for Bitcoin this should be similar)
hash (big endian) 3f74be6a1fbd15a5e1101c48e7e31b7777c68fb125f143587d19e1e1c157575c signature (72 bytes) 304502205d2cb95368167baa75ff86a36827a732ac1ab4ea5c9f53ebebf1c2ae738cc9db0221009 cbec84f5941c7a85a76ef4c617b66a0c52e66e9ec5e8374480521d57a588eb701 key (33 bytes) 026795b2f312bf34204cd314d06b165ca8bb56702eb5ff27b57acfd7c8051e75d8 From signature I tried two methods of extract r and s, first is mine procedure: Code: void decodeSignature(vector<unsigned char> &signature, vector<unsigned char> &rnumber, vector<unsigned char> &snumber) This procedure give me: r= 205d2cb95368167baa75ff86a36827a732ac1ab4ea5c9f53ebebf1c2ae738cc9 s=21009cbec84f5941c7a85a76ef4c617b66a0c52e66e9ec5e8374480521d57a588e is easy to verify that its are substring of signature hex string Second method: is using secp256k1_ecdsa_sig_parse Code: uint8_t rr[32], rs[32]; 1. I must write signature.size()-1 instead of signature.size() because else is called secp256k1_der_read_len and len mismatch with byte signature[1] meaing len = 69 But output are: r = dbc98c73aec2f1ebeb539f5ceab41aac32a72768a386ff75aa7b166853b92c5d s = b78e587ad521054874835eece9662ec5a0667b614cef765aa8c741594fc8be9c both len are 32 instead of 32 and 33, Next I concat s+r (mine, because second method give me 32 and 32 not 33) and call method: Code: vchSig.insert(vchSig.end(), snumber.begin(), snumber.end()); Code: if (i < bits_ng && (n = wnaf_ng[i])) { I must use not miny but r and s returned by second method? But the are both 32 bytes and is called signature.size()-1 Title: Re: Is possible get public key from signature? Post by: Frodek on October 17, 2019, 03:06:36 PM Two problems:
1. When I secp256k1_ecdsa_sig_parse with sample signature, len mismatch 2. Result are two 32 bytes numbers, whereas COMPACT_SIGNATURE_SIZE = 65 (32+33, not 32 +32) Title: Re: Is possible get public key from signature? Post by: BrewMaster on October 17, 2019, 03:11:46 PM This procedure give me: r= 205d2cb95368167baa75ff86a36827a732ac1ab4ea5c9f53ebebf1c2ae738cc9 s=21009cbec84f5941c7a85a76ef4c617b66a0c52e66e9ec5e8374480521d57a588e is easy to verify that its are substring of signature hex string you are forgetting to move your pointer forward after you read the integer lengths after "int intLen = bytesBegin[ptr];" and "intLen = bytesBegin[ptr];" lines. the result is that your r and s values have an extra byte in then (20 and 21 respectively). Title: Re: Is possible get public key from signature? Post by: achow101 on October 17, 2019, 05:18:58 PM R and S is always 32 bytes after DER encoding r and s are both at most 32 bytes with 1 byte for sign if the most significant bit is set (they can be smaller than 32 bytes). This procedure give me: You have an off by one error in your code somewhere. s begins with 009c.... The 0x21 byte is the length.r= 205d2cb95368167baa75ff86a36827a732ac1ab4ea5c9f53ebebf1c2ae738cc9 s=21009cbec84f5941c7a85a76ef4c617b66a0c52e66e9ec5e8374480521d57a588e is easy to verify that its are substring of signature hex string Even so, s would still be a 33 byte value. This is because, again, DER requires positive signed integers. However compact signatures use big endian unsigned integers which are always positive. This means that in converting from DER to compact, you can drop leading 0x00 bytes as those are only there to make the integer a positive signed integer. Two problems: The size of a compact signature here does not refer to just the r and s values. It also includes one additional byte for the recovery id. This is because compact signatures in Bitcoin are only used for signed messages which do public key recovery (as you are trying to do). The recovery id is the first byte of the signature, the rest is the compact signature that you expect (32 byte R followed by 32 byte s).1. When I secp256k1_ecdsa_sig_parse with sample signature, len mismatch 2. Result are two 32 bytes numbers, whereas COMPACT_SIGNATURE_SIZE = 65 (32+33, not 32 +32) Title: Re: Is possible get public key from signature? Post by: Frodek on October 18, 2019, 06:27:52 PM What I am wrong using only Bitcoin code?
I move source code from key_tests.cpp : Code: .................... Code: vector<uint8_t> vch; but is ff0000007d5671f4de5e3d054859e06f20919cc3d882220266c7a16014560000160000000000000 04d32a26014560000a0f9bcdbff7e0000000000000000000000 Maybe trash in - trash out, hash is bad or signature is bad, but why in result is so zeros, even if we get first 33 bytes from 65 bytes note: string str = HexStr(rkeymy.begin(), rkeymy.end()); give me empty string, because size is 0, all 65 bytes are trash because Code: bool CPubKey::RecoverCompact(const uint256 &hash, const std::vector<unsigned char>& vchSig) { --------------- NOW is without old problems r = 205d2cb95368167baa75ff86a36827a732ac1ab4ea5c9f53ebebf1c2ae738cc9 s = 009cbec84f5941c7a85a76ef4c617b66a0c52e66e9ec5e8374480521d57a588eb7 but key is 0229364d20762e423fb1d93d1fa05150a2d0277f49feaff924405785de9b6abb4d - look ok, but I want key 026795b2f312bf34204cd314d06b165ca8bb56702eb5ff27b57acfd7c8051e75d8 What I do wrong? I give one LTC transaction input. I give script (thus r and s) give key from script to verify message to recover script I give hash previous transaction, it is ok? another: hash Be 57ad3c7b7ce0654e43ecf7477879c167dcfb079614a1f785a5e87b84823f7d47 signature (71 bytes) 304402200f2f95941a847d5f43d241297e98de0da340cdb4232176be61babd7572b641b30220353 ed805ecda266dfc8ebf56c142239030d3e8be432d3590aeeacfdae15b8abc01 key (33 bytes) 025a76dd6561c1da7be001fa3b7aab0c56496be0230d06c5cd28bdec6ca6a71c85 - can't recover and other can't recover, only can (with other pubkey than derived fro script) hash Be 3f74be6a1fbd15a5e1101c48e7e31b7777c68fb125f143587d19e1e1c157575c signature (72 bytes) 304502205d2cb95368167baa75ff86a36827a732ac1ab4ea5c9f53ebebf1c2ae738cc9db0221009 cbec84f5941c7a85a76ef4c617b66a0c52e66e9ec5e8374480521d57a588eb701 WARNING: only first signature has 32+33 int numbers within, else have 32+32 or 33+33, it is possible? I call: Code: myRecover("3f74be6a1fbd15a5e1101c48e7e31b7777c68fb125f143587d19e1e1c157575c", Code: void myRecover(string hashStr, string signatureStr) { Title: Re: Is possible get public key from signature? Post by: Frodek on October 23, 2019, 10:37:41 AM Main problem: there are two ways of signing: normal key1.Sign(hashMsg, sign1) and compat key1.SignCompact(hashMsg, csign1) and one recovering rkey1.RecoverCompact(hashMsg, csign1)
CKey::SignCompact uses secp256k1_ecdsa_sign_recoverable but CKey::Sign uses secp256k1_ecdsa_sign (not recoverable) and uses extra_entropy. It is impossible recover public key from normal signed message? Warning: inputs signatures are normal signed (70-72 bytes) not compact (65 bytes) followed by key. Is any way to verify? Title: Re: Is possible get public key from signature? Post by: achow101 on October 23, 2019, 08:14:57 PM It is extremely likely that you are parsing the hex strings into bytes improperly (or maybe not at all). What do your "hashFromString" and "hashFromStringLE" functions do/work?
Also, the signature is not a hash nor anything little endian, so I don't know why you are passing that into a function named "hashFromStringLE". It isn't hashed either. Lastly, as has been said multiple times, RecoverCompact takes 65 byte signatures which you can retrieve from the 72 byte one by extracting R and s. Again, R and s BOTH may have leading 0 bytes due to signed integers. You can drop the leading 0 byte so that both R and s are 32 bytes long. If they are shorter than 32 bytes (that is possible), then you need to pad 0's in front of them until they are 32 bytes. The first byte of the compact signature needs to be a recovery id. If you have done everything correctly but are still getting the wrong public key, try different recovery ids. There are 4 possible public keys you can recover from the signature, the recovery id just specifies which of those 4. Since you don't have a recovery id, you need to just guess. |