Given a message and signature, find a public key that makes the signature valid

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 < N < 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 < pq < 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 < pq < 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).

[revised to better highlight the semi-realistic (2.) where an easy attack might work for $e=3$ by sneaking a forged $N$ of about $368$ bits even if the original modulus is much bigger]

It seems conceivable to go beyond Poncho's great answer and make the public key $(N,e)$ acceptable by a standard implementation that have constraints on $e$; I'll assume some discrete set of odd values in range $[3\dots2^{32}]$. Except in (1.) below, I'll also assume the message padding of RSASSA-PKCS1-V1_5 with SHA-1 as in PKCS#1: $\operatorname{Pad}_n(M)=2^{8\cdot\lceil n/8\rceil-15}-K+\operatorname{SHA-1}(M)$ for $n>360$, with $K=2^{288}-2^{160}\cdot3021300906052b0e03021a05000414_{16}$.

The problem is:
given given one or several signature(s) $S$, one or several message(s) $M$ (perhaps depending on $S$), allowable integer(s) $n$ (perhaps depending on some measure of the size of $S$), allowable integer(s) $e$, and how to compute padded message(s) $\operatorname{Pad}_n(M)$,
find acceptable parameters $(S,M,n,e)$ and an odd integer $N$ of exactly $n$ bits,
such that $N$ divides $S^e-\operatorname{Pad}_n(M)$, and (if that's checked as part of signature verification) $N>S$.

How hard that problem is depends:

• Heavily, on what checks the signature verification procedure does before accepting signature $S$ of message $M$ with respect to a public key $(N,e)$, and in particular on the number of bits $n$ in the public modulus $N$. This can be, starting from the most lenient:

  1. Check that $\operatorname{Pad}(M)\equiv S^e\pmod N$ for some padding independent of $n$. In that case, $(N,e)=(5,3)$ has a 20% chance to be a solution for a random $S$ and message $M$. If such very small $N$ are allowable and there is some freedom on $e$, the problem is very easy even for a single $(S,M)$ pair: the adversary tries a few $e$ until $S^e-\operatorname{Pad}(M)$ has one (or two) small odd factor, and uses that factor (or their product) as $N$.
  2. Check that $\operatorname{Pad}_n(M)=S^e\bmod N$. Notice it implies $N>\operatorname{Pad}_n(M)$, but still allows the adversary to creep in any $n>360$, regardless of the original public modulus.
  3. One of the above, and $N>S$, which in practice will force the adversary to use $n$ almost as big as in the original public modulus; if she has $i$ signature $S$ to choose from, odds are that the smallest $S$ allows to lower $n$ in the forged $N$ by only about $\log_2(i)$ bits compared to the original. Such check $N>S$ is mandated by most signature standards (including PKCS#1). However, in the usual setup where $N$ is trusted, it does not harm security of signature verification to omit that test, and I have seen an implementation that omits it, with rationale: the right signature can be trivially derived from any signature made allowable by the omission.
  4. Some of the above, and a check of $n$ versus the size of the bytestring coding $S$. This will further restrict $n$. For example, PKCS#1 mandates that $S$ is a bytestring of exactly $\lceil n/8\rceil$ bytes; however some implementations change that to at most (perhaps because signatures are treated as an ASN.1 integer at some point, and these loose their leading zero bits), and some implementations may omit this test entirely, and decide on the padding based on $N$, not $S$.
  5. Some of the above, plus a hard check that $n$ is among a fixed set of value. That is mandated by some standards, such as FIPS 186-3, which allows only $n\in\{1024,2048,3072\}$; combined with either (3.) or (4.), that forces the adversary to use exactly the original $n$.
• On if the adversary has a large supply of $S$ (I assume she is content with success for one $S$), or/and a large supply of $M$ (the question does not consider that, but it is entirely possible in some practical cases that the adversary has the freedom to choose among many messages $M$ that suit her goal, independently of the signature $S$).
• On what values of $e$ are allowable.

Except in (1.), the problem of finding a divisor of $n$ bits for the huge $S^e-\operatorname{Pad}_n(M)$ is non-trivial. Depending mostly on the allowable $n$ given the checks performed, it might remain tractable as follows:

• Make a partial factorization of $S^e-\operatorname{Pad}_n(M)$ for some allowable parameters $(S,M,n,e)$, using the well polished arsenal of factorization techniques applicable to random integers of about $\max(e\cdot||S||,||\operatorname{Pad}_n(M)||)$ bits (trial division, then Pollard's rho, then Pollard's p-1, then perhaps Pollard's p+1, then ECM, then perhaps some variant of MPQS or GNFS if a remaining composite factor has a few hundred bits), as $S^e-\operatorname{Pad}_n(M)=2^i\cdot\prod p_j\cdot\prod c_j$, where the $p_j$ are odd factor less than $2^n$, and the $c_j$ are higher factor(s). Typically the $c_j$ (if any) are either a single huge composite that is too costly to factor, or a single huge prime; and the $p_j$ are primes of low to moderate size, except for the highest $p_j$ when there are no $c_j$ (in which case the highest $p_j$ can be composite, and/or approach $n$ bits).
• Try to find a subset of these $p_i$ such that $n-1<\sum log_2(p_i)<n$ computed approximately (change $n-1$ to $\log_2(S)$ if $N>S$ is a requirement and we use an $S$ with $S\ge2^{n-1}$). This is a particularly loose knapsack problem, and is often easily tractable when $\sum log_2(p_i)$ is even slightly over $n$ (the small factors are used as adjustment variables). If this can't be done, move to another candidate for $(S,M,n,e)$.
• Set $N=\prod p_i$ for those $p_i$ in the exhibited subset of the knapsack. In the unlikely case that $N$ is not acceptable due to rounding errors, move to another knapsack solution, or another candidate for $(S,M,n,e)$.

The best $n$ are among the lowest allowed considering what the signature verification procedure allows with our supply of $S$ and $M$.

A large freedom on $M$ and/or having a pool of $S$ to choose from significantly helps, for it allows to concentrate the bulk of the factoring effort on those few $S^e-\operatorname{Pad}_n(M)$ which have a lot of small odd factors, which makes for less other $p_j$ to find by more sophisticated methods, and further makes the fine adjustment of the knapsack quite easy.

With ample supply of $(S,M)$ the attack is easy for $n\in[361\dots368]$. I would not bet on up to what $n$ it might actually work. However GMP-ECM is routinely used to uncover >200-bit factors of >10000-bit numbers, and this seems in the right ballpark for $n=768$, perhaps more. The feasibility has to do with the odds that a random $m$-bit integer has an at-least $n$-bit divisor with all its factors at most $k$ bits, which I asked here.

$e=3$ gives the most manageable $S^e-\operatorname{Pad}_n(M)$, and does not seem to reduce significantly the number of $p_i$ to choose from. $e=2^{16}+1$ is annoying, but does not seem unsurmountable, especially if checks by the implementation allow $n\in[361\dots368]$.

I have purposely not made any check that $\gcd(p_i-1,e)=1$, or that $p_i$ is at least some bound so that $N$ is not trivially factorisable, or that $N$ is composite; for usual implementations of RSA signature verification do not check any of these.

The problem may have practical applications. Here is a reasonable study case, where the adversary has full freedom on $M$. The legitimate user has downloaded a file, its detached signature (possibly including reference to the public key by an identifier, but not a hash), and has the genuine public key. The adversary gains write access to the file, the public key, but not the signature (which the legitimate user write-protected).

The attack would allow the adversary to modify the file while maintaining apparent integrity when the signature is checked. Notice that by modifying the end of the forged file, the adversary has a cheap way to change $\operatorname{Pad}_n(M)$ (only the end of the hash needs to be recomputed).