4
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ nice, i started drafting an answer but got distracted by other tasks $\endgroup$ – kodlu Mar 12 '18 at 10:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.