4.1.6 Public Key Recovery Operation
Given an ECDSA signature (r, s) and EC domain parameters, it is generally possible to determine
the public key Q, at least to within a small number of choices.
This is useful for generating self-signed signatures.
This is also useful in bandwidth constrained environments, when transmission of public keys cannot
be afforded. Entity U could send a signature to entity V , who recovers QU. Entity V can look
up the public key in some certificate or directory, and if it matches then the signature can be
accepted. Alternatively, entity U may transmit the signature together with the certificate except
that the public key is omitted from the certificate. For example, in long certificate chains signed
with ECDSA, bandwidth can be saved by omission of the public keys.
Potentially, several candidate public keys can be recovered from a signature. At a small cost, the
signer can generate the ECDSA signature in such a way that only one of the candidate public keys
is viable, and such that the verifier has a very small additional cost of determining which is the
correct public key.
Input: The public key recovery operations takes as input:
1. Elliptic curve domain parameters T = (p, a, b, G, n, h) or T = (m, f(x), a, b,G, n, h) at the
desired security level.
2. A message M.
3. An ECDSA signature value (r, s) that is valid on message M for some public key to be
determined.
Output: An elliptic curve public key Q for which (r, s) is a valid signature on message M.
Actions: Find public key Q as follows.
1. For j from 0 to h do the following.
1.1. Let x = r + jn.
1.2. Convert the integer x to an octet string X of length mlen using the conversion routine
specified in Section 2.3.7, where mlen = d(log2 p)/8e or mlen = dm/8e.
1.3. Convert the octet string 0216kX to an elliptic curve point R using the conversion routine
specified in Section 2.3.4. If this conversion routine outputs “invalid”, then do another
iteration of Step 1.
1.4. If nR 6= O, then do another iteration of Step 1.
1.5. Compute e from M using Steps 2 and 3 of ECDSA signature verification.
1.6. For k from 1 to 2 do the following.
1.6.1. Compute a candidate public key as:
Q = r−1(sR − eG).
1.6.2. Verify that Q is the authentic public key. (For example, verify the signature of a
certification authority in a certificate which has been truncated by the omission of
Q from the certificate.) If Q is authenticated, stop and output Q.
1.6.3. Change R to −R.
2. Output “invalid”.