What is the probability of attacking SHA1 used in RSA signature with small exponent?
This is not an answer; rather, I attempt to improve the method outlined in the question.

Problem statement (slightly simplified): it is given an RSA public key $(N,e)$ with $2^{n-1}&lt;N&lt;2^n$, $n=2048$, $e=41$, a hash function $H=\operatorname{SHA-1}$ with output of $w=160$ bits. It is asked an $(m,s)$ with $0\le s&lt;N$ and $H(m)=(s^e\bmod N)\bmod2^w$.

Note: for simplicity, I ignore the six given (message, signature) pairs and that the $(m,s)$ to exhibit must not be among them. These $(m_i,s_i)$ are such that $0\le s_i&lt;N$ and $(s_i^e\bmod N)=H(m_i)+c$ with known $c=2^{n-15}-2^{8+v+w}+2^w b$, $v=120$, $2^{v-8}\le b&lt;2^v$, $b=\mathtt{0x3021300906052b0e03021a05000414}$ (that's by definition of EMSA-PKCS1-v1_5).



As noted in the question, for any given $m$ with $H(m)$ odd, if there exists an odd $s$ such that $(m,s)$ is a solution to our problem and $0\le s&lt;\Big\lceil\sqrt[e]N\Big\rceil$, then we can efficiently find that $s$ by computing $h=H(m)$ and solving for $w$-bit $s$ the equation $s^e\equiv h\bmod 2^w$; we keep $s$ as solution if $s&lt;\Big\lceil\sqrt[e]N\Big\rceil$.

If we try this for a random $m$, each attempt costs an average of two hashes to find $H(m)$ odd, finding one solution to the equation $s^e\equiv h\bmod 2^w$, and succeeds with probability about $\epsilon=\sqrt[e]N/2^{w+1}\approx2^{(n-1/2)/e-1-w}$; that's slightly under $2^{-111}$ and as is, this strategy is doomed.



Notice that for any given $m$, if there exists $r\ge0$ with $r+H(m)$ odd and odd $s$ such that $(m,s)$ is a solution to our problem and $\Big\lceil\sqrt[e]{r N}\Big\rceil\le s&lt;\Big\lceil\sqrt[e]{(r+1)N}\Big\rceil$, then we can find that $s$ by computing $h=H(m)$, and solving for $r$ of appropriate parity and $w$-bit $s$ the equation $s^e\equiv(h+r N)\bmod 2^w$; we keep $s$ as solution if $\Big\lceil\sqrt[e]{r N}\Big\rceil\le s&lt;\Big\lceil\sqrt[e]{(r+1)N}\Big\rceil$.

If we just enumerate small incremental $r$ of the appropriate parity, compute $h'=h+r N\bmod 2^w$, and solve for $w$-bit $s$ the equation $s^e\equiv h'\bmod 2^w$, then for each $r$ we have probability about $\epsilon_r=\left(\sqrt[e]{(r+1)N}-\sqrt[e]{r N}\right)/2^{w+1}$ that $s$  turns out to be in the correct range; that is, $\epsilon_r=\begin{cases}
\epsilon=\sqrt[e]N/2^{w+1}&amp;\text{ if }r=0\\\left(\sqrt[e]{1+1/r}-1\right)\;\epsilon&amp;\text{ if }r&gt;0\end{cases}$
This is an improvement if the cost of solving $s^e\equiv h'\bmod 2^w$ is much lower that the cost of a hash (or if our messages $m$ are heavily constrained). In particular, if $h=H(m)$ turns out to be even, we formerly abandoned that $m$, and now have probability about $\epsilon_1\approx\epsilon/59$ that the solution $s$ to $s^e\equiv(h+N)\bmod 2^w$ is acceptable.

Also, when solving $s^e\equiv(h+r N)\bmod 2^w$, if we compute $s$ bit by bit starting from the low-order bits, we can abandon as soon as we have enough bits that it is certain that $s$ is not in the appropriate range.

Perhaps a simultaneous search of $(r,s)$ is feasible; I'll be thinking about it. As the saying (attributed to the NSA) goes: attacks only get better; they never get worse.