Cryptography
public-key elliptic-curves dsa key-recovery
Updated Fri, 20 May 2022 02:19:16 GMT

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}(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?

Solution

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)

External links referenced by this document: