Title: can recovered public keys from a given ECDSA signature be invalid?
Post by: pooya87 on June 18, 2019, 05:05:31 AM
when recovering public keys for this signature posted here: https://bitcointalk.org/index.php?topic=996318.msg51506455#msg51506455 i come up with 2 public keys Q using Q = r-1(sR-eG) where r and s are from signature (r,s) and R is a point calculated from x = r + jn j∈[0,1] and n and G are curve parameters.
The problem is that when i use first Q with signature, i can verify the signature. but when i use the second Q the verification fails. so i am wondering whether this is normal or is my calculations incorrect (missing a step)?
Title: Re: can recovered public keys from a given ECDSA signature be invalid?
Post by: amaclin1 on June 18, 2019, 06:06:41 AM
Why not to test your code with other test vectors? As far as I remember, we can recover public key {X,Y} from signature {R,S} and digest {Z} for ( int i ( 0 ); i < 4; i++ ) { if ( ECDSA_SIG_recover_key_GFp ( eckey, esig, digest.constPtr ( ), 32, i, 1 ) ) { QByteArray pubkey; pubkey.resize ( 65 ); quint8* pbegin = (quint8*)pubkey.data ( ); i2o_ECPublicKey ( eckey, &pbegin ); _trace ( pubkey.toHex ( ).constData ( ) ); } }
Title: Re: can recovered public keys from a given ECDSA signature be invalid?
Post by: keychainX on June 18, 2019, 09:08:58 AM
when recovering public keys for this signature posted here: https://bitcointalk.org/index.php?topic=996318.msg51506455#msg51506455 i come up with 2 public keys Q using Q = r-1(sR-eG) where r and s are from signature (r,s) and R is a point calculated from x = r + jn j∈[0,1] and n and G are curve parameters.
The problem is that when i use first Q with signature, i can verify the signature. but when i use the second Q the verification fails. so i am wondering whether this is normal or is my calculations incorrect (missing a step)?
can you post the steps or the two public keys, it would be easier to tell you what went wrong. /KX
Title: Re: can recovered public keys from a given ECDSA signature be invalid?
Post by: pooya87 on June 18, 2019, 10:12:20 AM
Why not to test your code with other test vectors?
Test Vectors can only tell you whether your final result is correct not if you missed a step. can you post the steps or the two public keys, it would be easier to tell you what went wrong.
for j from 0 to cofactor (which is 1): x = r + jn find y using 0x02|x as the compressed point check R=(x,y) is on curve for k from 1 to 2: Q = r-1(sR-eG) {Q is a point} check Q is on curve => if true -> return as one of the result if not -> R=-R
03f0cabd53153b1bce21e2ef45d31d6043abccc59305db5d27f5e3b40cf17e5e3b <- the correct pubkey 0259eafa3c2a9dedce9a4b7723cab126b259ca5f9d1f537efa73880b33b96199fd
Title: Re: can recovered public keys from a given ECDSA signature be invalid?
Post by: amaclin1 on June 18, 2019, 11:09:08 AM
Let me reproduce this algo. Sorry for this dirty code. Take arbitrary transaction https://www.blockchain.com/btc/tx/6e0f7cefae07e38d442d7ba48468b099d4d1576d805d44f7e5a8ad05e49c3f6e Decode it getrawtransaction 6e0f7cefae07e38d442d7ba48468b099d4d1576d805d44f7e5a8ad05e49c3f6e 1
{ "txid": "6e0f7cefae07e38d442d7ba48468b099d4d1576d805d44f7e5a8ad05e49c3f6e", "hash": "6e0f7cefae07e38d442d7ba48468b099d4d1576d805d44f7e5a8ad05e49c3f6e", "version": 2, "size": 223, "vsize": 223, "weight": 892, "locktime": 0, "vin": [ { "txid": "df7494b2a7da2bd6db734541b3a9b0fa544ca5c0799dacde14ef7987a155bae7", "vout": 1, "scriptSig": { "asm": "304402201c26b64441facf0542e468c4dee616a6369509f031e93ae0429097bb325325fd022057719f5cbc6a277b9078e027ec5104b5b5e4b5814480b6bfe2fa4f67a278684b[ALL] 02e752ab1a7a9c652a8c6005343edff02cd29ab91f6d68190d29bdd32fdaf5f721", "hex": "47304402201c26b64441facf0542e468c4dee616a6369509f031e93ae0429097bb325325fd022057719f5cbc6a277b9078e027ec5104b5b5e4b5814480b6bfe2fa4f67a278684b012102e752ab1a7a9c652a8c6005343edff02cd29ab91f6d68190d29bdd32fdaf5f721" }, "sequence": 4294967295 } ], "vout": [ { "value": 0.01510000, "n": 0, "scriptPubKey": { "asm": "OP_HASH160 69f37485c1eed1d9f5696f39a7d8d0241422c79b OP_EQUAL", "hex": "a91469f37485c1eed1d9f5696f39a7d8d0241422c79b87", "reqSigs": 1, "type": "scripthash", "addresses": [ "3BMEXFJcAuHoFNnG8ENsMsf7hrpvUksdF4" ] } }, { "value": 0.35345922, "n": 1, "scriptPubKey": { "asm": "OP_DUP OP_HASH160 22ce3ee00f8c41bd39d46d403e083a89d684cd45 OP_EQUALVERIFY OP_CHECKSIG", "hex": "76a91422ce3ee00f8c41bd39d46d403e083a89d684cd4588ac", "reqSigs": 1, "type": "pubkeyhash", "addresses": [ "14B33iezr3Pk72MgWkeM7Lr15nQqAXNWCx" ] } } ], "hex": "0200000001e7ba55a18779ef14deac9d79c0a54c54fab0a9b3414573dbd62bdaa7b29474df010000006a47304402201c26b64441facf0542e468c4dee616a6369509f031e93ae0429097bb325325fd022057719f5cbc6a277b9078e027ec5104b5b5e4b5814480b6bfe2fa4f67a278684b012102e752ab1a7a9c652a8c6005343edff02cd29ab91f6d68190d29bdd32fdaf5f721ffffffff02700a17000000000017a91469f37485c1eed1d9f5696f39a7d8d0241422c79b8702561b02000000001976a91422ce3ee00f8c41bd39d46d403e083a89d684cd4588ac00000000", "blockhash": "0000000000000000001fb4cba1d00fabd675ecba090b827fd29888d0b2021e60", "confirmations": 1, "time": 1560853115, "blocktime": 1560853115 }
Signature is 304402201c26b64441facf0542e468c4dee616a6369509f031e93ae0429097bb325325fd022057719f5cbc6a277b9078e027ec5104b5b5e4b5814480b6bfe2fa4f67a278684b Assume we do not know the public key static QList<QByteArray> recover ( const MyKey32& digest, const QByteArray& signature ) { QList<QByteArray> result; MyKey32 R; MyKey32 S; xassert ( MyByteArray ( signature ).isEcdsaSignature ( R, S ) ); ECDSA_SIG* esig = ECDSA_SIG_new ( ); BN_bin2bn ( R.constPtr ( ), 32, esig -> r ); BN_bin2bn ( S.constPtr ( ), 32, esig -> s );
EC_KEY* eckey = EC_KEY_new_by_curve_name ( NID_secp256k1 );
for ( int i ( 0 ); i < 4; i++ ) { if ( ECDSA_SIG_recover_key_GFp ( eckey, esig, digest.constPtr ( ), 32, i, 1 ) ) { QByteArray pubkey; pubkey.resize ( 65 ); quint8* pbegin = (quint8*)pubkey.data ( ); i2o_ECPublicKey ( eckey, &pbegin );
if ( digest.verify ( pubkey, signature ) ) result.append ( pubkey );
for ( int i = 2; i <= 3; i++ ) { pubkey.data ( )[0] = i; pubkey.resize ( 33 ); if ( digest.verify ( pubkey, signature ) ) result.append ( pubkey ); } } } return result; }
static void check ( ) { const MyByteArray data ( QByteArray::fromHex ( "0200000001e7ba55a18779ef14deac9d79c0a54c54fab0a9b3414573dbd62bdaa7b29474df010000006a47304402201c26b64441facf0542e468c4dee616a6369509f031e93ae0429097bb325325fd022057719f5cbc6a277b9078e027ec5104b5b5e4b5814480b6bfe2fa4f67a278684b012102e752ab1a7a9c652a8c6005343edff02cd29ab91f6d68190d29bdd32fdaf5f721ffffffff02700a17000000000017a91469f37485c1eed1d9f5696f39a7d8d0241422c79b8702561b02000000001976a91422ce3ee00f8c41bd39d46d403e083a89d684cd4588ac00000000" ) ); const Stream stream ( data ); const Transaction tx ( stream ); const TxInput in ( tx.getInput ( 0 ) ); const MyKey20 address ( MyKey20::of ( "1Ldy6LLQvA9ohG3bNNt32FHkGaTN16Z3N" ) ); //const MyByteArray pubkey ( QByteArray::fromHex ( "02e752ab1a7a9c652a8c6005343edff02cd29ab91f6d68190d29bdd32fdaf5f721" ) ); const MyByteArray signature ( QByteArray::fromHex ( "304402201c26b64441facf0542e468c4dee616a6369509f031e93ae0429097bb325325fd022057719f5cbc6a277b9078e027ec5104b5b5e4b5814480b6bfe2fa4f67a278684b" ) ); const MyKey32 digest ( in.tx.getRawHash ( in.getInputIndex ( ), address.p2pkh ( ) ) );
//xassert ( digest.verify ( pubkey, signature ) ); //_trace ( "verify passed" );
QList<QByteArray> result = recover ( digest, signature );
for ( int i ( 0 ); i < result.size ( ); i++ ) { const MyByteArray pub ( result.at ( i ) ); const MyKey20 key ( pub.hash160 ( ) ); if ( key == address ) qDebug ( ) << QString ( "%1 matched" ).arg ( pub.toHex ( ).constData ( ) ); else qDebug ( ) << QString ( "%1 failed" ).arg ( pub.toHex ( ).constData ( ) ); } } The output is: "047e8c09ef70ea081b6154f8417f869ffd6ff13fb64929d2da8ddfe897d3659f63b8500b6acf8cadbfb4e1465d928e2d8c416daab4c4247b93dee4a57832d19b3c failed" "027e8c09ef70ea081b6154f8417f869ffd6ff13fb64929d2da8ddfe897d3659f63 failed" "04e752ab1a7a9c652a8c6005343edff02cd29ab91f6d68190d29bdd32fdaf5f7218c37f8625d158227c48ed3fb76dc5c9761dd82a4d117ca59cc5887d9c0d0586c failed" "02e752ab1a7a9c652a8c6005343edff02cd29ab91f6d68190d29bdd32fdaf5f721 matched" You see, that I was able to recover four correct public keys for this signature and digest and one of them ( 02e752ab1a7a9c652a8c6005343edff02cd29ab91f6d68190d29bdd32fdaf5f721 ) matches the address
|