Return to Answer

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}$.

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}$.

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.

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.

• 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 athier 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 determine $n$ used to determine the padding from $N$ alone.
  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\}$. In practice 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.

• 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.