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?

up vote 2 down vote accepted

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)

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.