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<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}(sRzG)$ 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?

Asked by user41860 (1 )
Dec 07, 2016 at 13:01