Are there any signatures where the recid (v) is equal to 29,30 (or 33,34 compressed)?

Question

Peter Wuille recently explained how ECDSA pubkey recovery is done, in response to my question.

So it's basically that for a given base64 signature, the value v in v,r,s provides the specific coordinates, hence the recid (recovery ID).

Example from BitcoinCore test vectors:

> sig =
> "H8PgOb/liZzt3QQHJn9kLBqH7E/i+SC6JTwYGtdNdOjnXzFqXnHMZqP7oZ1wb1QiQ3H/kF8xC9Yx7pK9ddlx8TA"
> addr = "1K5Z1nxN4mjUgCLpSXMRkeZxuAMpbn2CQB" wif =
> "KwfJTiKdcjNMjBu4ksgGd21EZXz6JomoZNbirP3nfd3K9ZMXMEUi"
> 
> v,r,s = vrs = (31,
> 88597177789312009809148107221292570613390338668815747761545214128303675599079L,
> 43057030252916568867525408201971649068117337291455262356277580652864892694832L)

The value of v is 27 + recid for uncompressed keys and 31 + recid for compressed keys.

Ive run a Python loop using pybitcointools which signs a message using a random key, and I've yet to ever see v=29 or v=30. Why is this? Is it by design, or is it just a very low probability event?

Answer 1

For random signatures, it is an extremely low probability event. Around 1 in 2¹²⁸, so it will likely never ever actually happen.

However, you can easily construct a valid signature that has one of those, and the recovery algorithm will give you an actual public key for it. It just won't be a public key anyone actually knows the secret key for.