Given a message and signature, find a public key that makes the signature valid Given a message $M$ and a signature $S$, is it feasible to find a RSA public key $(n,e)$ such that $S$ verifies as a valid signature on $M$ (using this public key)?

What if we're given one public key $(n,e)$ where the signature verifies (presumably, the public key of the original signer), and we want to find a second public key $(n',e')$ that also makes $S$ verify as a valid signature on $M$?  Is there an efficient algorithm to construct such a public key, and if so, how would you do it?  (We'll probably want $n'$ to be the same length, in bytes, as $n$.  Assume the RSA signature algorithm is using proper padding, e.g., PKCS #1.)
Actually, it does appear to be feasible to construct such a public key, with the caveats that:


the public exponent $e$ will be large.  While this is legal, most public keys have a small $e$
the modulus may be more vulnerable than usual to a specific (normally nonoptimal) factorization method.  However, how vulnerable it is can be controlled.


(Note: I'll use $N$ to designate the modulus; I want to use $n$ to mean 'the number of bits within the modulus).

Now, the problem can be summarized as: given values $S$ and $M$ (and $n$, which is the size of the representation of $S$), find a value $N$ and a value $e$ such that $Pad(M) = S^e \bmod N$ and $S &lt; N &lt; 2^n$

The reason for the upper bound on $N$ is how RSA signature verification works; they expect $S$ to be a bytevector the same length as the modulus; if we introduce a modulus which is larger than the signature, the verification process will fail, even if the math would happen to work out.

One obvious way to do this is to find a two primes $p, q$ and odd exponents $e_p, e_q$ such that:


$Pad(M) \equiv S^{e_p} \bmod p$
$Pad(M) \equiv S^{e_q} \bmod q$
$S &lt; pq &lt; 2^n$
There exists a value $e$ such that $e \equiv e_p \mod p - 1$ and $e \equiv e_q \mod q-1$


The last is a nontrivial condition, because $p-1, q-1$ are not relatively prime.  And, this generalizes in an obvious way to more than two primes; it turns out that two primes works for us.

Now, if we pick our primes $p, q$ first, we're stuck with solving discrete log problems to find $e_p, e_q$.  You might assume this is difficult; however, it turns out that discrete logs modulo a large prime can be easy, if the prime is properly chosen; in this case, we get to pick the primes.

If $p-1$ has $k$ prime factors, the largest of which is $r$, then a discrete log problem modulo $p$ can be solved in $O(k \sqrt{r})$ time.

We take advantage of this by doing the following:


Select a set of moderate sized prime values $p_1, p_2, ..., p_i$ and compute $p = 2 \prod p_i + 1$, and make sure that $p$ is prime
Also make sure that $Pad(M)$ and $S$ are either both quadratic residues, or both quadratic nonresidues modulo $p$; if they differ, then either $e_p$ will not exist, or it will be even, neither of which works for us.
Use the $O(k\sqrt{r})$ algorithm to find $e_p$
If $e_p$ happens to be even (which can happen if both $Pad(M)$ and $S$ are quadratic residues), then add $\prod p_i$ to it; this will make it odd, and also preserve the relation $Pad(M) \equiv S^{e_p} \bmod p$


We then do the same procedure to find $q, e_q$, noting that we need to look for values $q$ of the right size (to make $pq$ be within the range $S &lt; pq &lt; 2^N$), and that there are no common primes in the sets $p_i$ and $q_i$; this will likely prevent $e$ from existing.

If we follow these steps, then $e$ will exist, and we've solved the problem.

The only thing left to note is the size of the subprimes $p_i, q_i$.  That turns out to be a bit of a balancing act; if these subprimes are $m$ bits long, then the above procedure takes around $O(2^{m/2})$ time; however, it turns out that the Pollard's p-1 method can factor modulii of this form in $O(2^m)$ time. If we are concerned about someone applying this specific factorization method, then we need to select $m$ carefully.  If we select $m=80$ (that is, our subprimes are 80 bits), then we'll be taking around $2^{40}$ computations, which is probably on the hairy edge of "feasible", while Pollard's method would take around $2^{80}$ time (and it appears unlikely to me that anyone would invest that kind of time).