can recovered public keys from a given ECDSA signature be invalid?

[pooya87]

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

[1714050742]

1714050742

[1714050742]

1714050742

[amaclin1]

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}

Code:

  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 ( ) );
    }
  }

[keychainX]

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

[pooya87]

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

[amaclin1]

Let me reproduce this algo. Sorry for this dirty code.

Take arbitrary transaction
https://www.blockchain.com/btc/tx/6e0f7cefae07e38d442d7ba48468b099d4d1576d805d44f7e5a8ad05e49c3f6e

Decode it

Code:

getrawtransaction 6e0f7cefae07e38d442d7ba48468b099d4d1576d805d44f7e5a8ad05e49c3f6e 1

Code:

{
  "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

Code:

304402201c26b64441facf0542e468c4dee616a6369509f031e93ae0429097bb325325fd022057719f5cbc6a277b9078e027ec5104b5b5e4b5814480b6bfe2fa4f67a278684b

Assume we do not know the public key

Code:

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:

Code:

"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