ECDSA pubkey recovery issue

Question

I try to recover public key from the given message $m$ and pair $(r, s)$ using curve that satisfies standard RFC7091. I am using algorithm from one of secp256k1 implementation but it seems that not any random $k$, that is $0<k<N$ give me a pair $(r, s)$ that I can recover a valid public key. I did check this question How does recovering the pubkey from ECDSA signature works and tried to use curve with this parameters $P=23, a=13, b=10, N=19, G=(18, 2)$ but I've got a valid pubkey with specified message only on very small subset of values $k$.

Is there any solution how I can calculate restrictions for $(r, s)$ generated pair to determine that my signature will be recoverable or I just have to try re-do signing operation until I get a valid one?

UPDATE: I have figured out that there are different algorithms for signing/verifying in ECDSA and RFC7091:

• In ECDSA we compute s as $s=k^{-1}(z+rd_A)\mod n$
• In RFC7091 we compute s as $s=(zk+rd_A)\mod n$

where $z$ is the hash of message, $d_A$ is the private key, $k$ is random in $0<k<n$, $n$ is the subgroup order and $r$ is calculated similar to both algorithms.

So the recovery formula for pubkey in ECDSA: $Q=r^{−1}(sR−zG)$ shouldn't work correctly because of different value of $s$ producing by both algorithms.

Is there any possibility to modify recovery formula to work for RFC7091 standard?

Answer 1

The signature validation logic from RFC7091 is effectively:

$$r \stackrel{?}= abs( h^{-1}sP - h^{-1}rQ )$$

where $r, s$ are values from the signature, $h$ is the message hash (converted into an integer), $P$ is the EC group generator, and $Q$ is the public key, and $abs$ is a function that maps a point to its x coordinate.

You know everything except for $Q$; you can recover that by using simple algebra; you would find the two points $R, R'$ with $r$ as an x-coordinate, and then $Q$ is one of:

$$r^{-1}(sP - hR)$$ $$r^{-1}(sP - hR')$$

(where you compute $r^{-1}$ modulo the curve order)