# How rare are 1024-bit $B$-smooth numbers?

What is the probability that if I choose a random $1 < r < n - 1$, $r^{65537} \pmod n$ will be $B$-smooth? $n$ is a 1024-bit RSA modulus.

The Wikipedia pages on smooth numbers and the Dickman function are too obtuse for me to understand enough to calculate for my particular case.

I was contemplating an attack on something that uses a broken PKCS #1 v1.5 signature padding check. I figured that if I found find many such $r$, I could forge signatures by manipulating the unchecked parts of the "message representative" to make it factor over the factor base $B$. The signature then would be calculable as a linear matrix.

This all resembles parts of the quadratic sieve algorithm. Quadratic sieve would be too difficult to do on a 1024-bit number, so it's quite possible that this attack idea is infeasible just from the rarity of smooth numbers.

If $n$ is a 1024-bit RSA modulus usable with $e=65537$ (as in the attack contemplated, and for >99.99% of $n=p\;q$ with $p$ and $q$ prime), then $r\mapsto r^{65537}\bmod n$ is a permutation of the set $[2,n-2]$. Thus if $r$ is uniformly random in this set, then so is $r^{65537}\bmod n$. For cryptanalytic purposes, it suffices that $r$ is chosen independently of the particular $n$.
The proportion of $B$-smooth among these is $\psi(n,B)/n$, and for fixed ratio $u=\log(n)/\log(B)$ and large $n$ that's $\rho(u)+O(1/\log(n))$, where $\rho$ is Dickman's function [in its modern definition; Donald E. Knuth's The Art of Computer Programming, section 4.5.4, studies $F(x)=\rho(1/x)$ ]. In cryptanalysis, $\rho(\log(n)/\log(B))$ is often used as an approximation of the density of $B$ smooth, ignoring the $O(1/\log(n))$ term. Caution: I can't tell how justified that is!
For example, if $B=2^{256}$, the proportion of $B$-smooth among integers less than $2^{1024}$ is approximately $\rho(1024/256)=\rho(4)\approx 0.00491\approx2^{-7.67}$. For $B=2^{128}$ that approximation is down to $\rho(8)\approx2^{-24.88}$.
Here is a table of $\log_2(\rho(u))$ for $u$ from $1$ to $25$ by steps of $\frac1 4$ (obtained using that code). $$\begin{array}{r|rrrrrrrrr} u&+0&+\frac1 4&+\frac1 2&+\frac3 4&+1\\ \hline 1&0\ \ \ \ \ &-0.36&-0.75&-1.18&-1.70\\ 2&-1.70&-2.30&-2.94&-3.62&-4.36\\ 3&-4.36&-5.14&-5.95&-6.79&-7.67\\ 4&-7.67&-8.58&-9.51&-10.47&-11.46\\ 5&-11.46&-12.47&-13.50&-14.56&-15.64\\ 6&-15.64&-16.73&-17.84&-18.98&-20.12\\ 7&-20.12&-21.29&-22.47&-23.67&-24.88\\ 8&-24.88&-26.11&-27.35&-28.61&-29.87\\ 9&-29.87&-31.15&-32.45&-33.75&-35.07\\ 10&-35.07&-36.40&-37.74&-39.09&-40.45\\ 11&-40.45&-41.82&-43.21&-44.60&-46.00\\ 12&-46.00&-47.41&-48.83&-50.26&-51.70\\ 13&-51.70&-53.15&-54.61&-56.07&-57.54\\ 14&-57.54&-59.02&-60.51&-62.01&-63.51\\ 15&-63.51&-65.03&-66.55&-68.07&-69.61\\ 16&-69.61&-71.15&-72.69&-74.25&-75.81\\ 17&-75.81&-77.38&-78.95&-80.53&-82.12\\ 18&-82.12&-83.71&-85.31&-86.92&-88.53\\ 19&-88.53&-90.15&-91.77&-93.40&-95.04\\ 20&-95.04&-96.68&-98.32&-99.97&-101.63\\ 21&-101.63&-103.29&-104.96&-106.63&-108.31\\ 22&-108.31&-109.99&-111.68&-113.37&-115.07\\ 23&-115.07&-116.77&-118.48&-120.19&-121.91\\ 24&-121.91&-123.63&-125.35&-127.08&-128.82\\ \end{array}$$ For $\psi(n,B)/n$ with bounding or/and lower $B$, one can use Bernstein's psibound.