I know it's possible with ECDSA. How bout RSA?
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Can we extract public key from signature created by RSA
I assume the question is: we have both the message and the RSA signature; can we find an RSA public key that could have been used to sign that message?
The answer is no, it is infeasible.
On the other hand, if we have two signatures (to two different messages), and those messages, and if the RSA padding method was deterministic (e.g. RSASSA-PKCS1-v1_5), and the public exponent is not too large (e.g. 65537, which is common), and we can guess the hash function, then it becomes feasible.
The RSA verification relation is $\text{Pad}(M)^e \equiv S \pmod N$ (where $M$ is the message that was signed, $\text{Pad}$ is the deterministic function that hashes and pads the message, $S$ is the signature and $N$ is the modulus); here, we know everything except for $N$ (since $e$ is assumed small, we can iterate through the possibilities).
We can rewrite this as $\text{Pad}(M)^e - S = kN$ (for some integer $k$).
While the left hand side is computable, it is also huge; it would be infeasible to find the factor $N$.
On the other hand, given two such distinct message $M_1, M_2$ and two signatures $S_1, S_2$, we have:
$$\gcd( \text{Pad}(M_1)^e - S_1, \text{Pad}(M_2)^e - S_2 ) = kN$$
where (in this case) $k$ is likely to be small; we can compute the left hand size (for $e = 65537$, it's a bit of work, but still feasible), and once we hae that, it is easy enough to scrap off the small factor $k$ to recover $N$.
$\begingroup$
$\endgroup$
So far as I know, this is impossible unless the signature data structure includes more information than is necessary. You may want to ask on crypto.stackexchange.com to get a higher-confidence answer, though. Security.SE is about threats, attacks, and mitigations in general, but crypto.SE is where people who like to get into the mathematical details behind various ciphers (among other things) hang out.
It is conventional, when creating or sending signed data, to include your public key (potentially in an X.509 certificate) so that the recipient knows who signed it and can verify the signature. Of course, unless the public key is signed by a trusted third party (such as a certificate authority or somebody you trust in OpenPGP's web-of-trust model), or you already know what public key or at least public key fingerprint (hash) to expect, merely sending along a public key with a signature doesn't prove anything about who signed the message.
