# ECDSA pubkey recovery issue

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 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, $$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?

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