5
$\begingroup$

Suppose on of the RSA prime factors $p$ is the range of $\sqrt{N}$, in particular it holds that $|p-\sqrt{N}|<\sqrt[4]{N}$

I want to show that RSA can be broken in time poly(log N)

Given hint: $N = pq = (\frac{p+q}2)^2 - (\frac{p-q}2)^2 $ , also $\frac{p+q}2 \approx \sqrt{N}$

$\textbf{This is my approach:}$

First of all, we can calculate $\sqrt{N}$

From $|p-\sqrt{N}|<\sqrt[4]{N}$ we know that $p$ can only be $2 \sqrt[4]{N}$ distinct values, namely anything in$ \{\sqrt{N}- \sqrt[4]{N}, ...,\sqrt{N} + \sqrt[4]{N} \}$

Of course $\sqrt{N}$ is usually not a whole number, but we can round up

So now we can test for every element $p$ in this set, if $p | N$ , in which case we could easily calculate the other factor

If i am not mistaken, this reduced bruteforce would cost $\mathcal{O} ( \sqrt{N} )$ , which does not seem to match with what we want to show, e.g. $\mathcal{O} ( \sqrt{N} )$ $\not=$ poly(log N)

$\endgroup$
0
8
+500
$\begingroup$

Although this might not be the solution you're looking for, the Coppersmith theorem offers a simple answer to this.

The (general) Coppersmith theorem states: let $f(x)$ be a monic univariate polynomial of degree $d$ with coefficients modulo a positive integer $n$. One can find all integers $x$ such that $|x| \le n^{\beta^2/d}$ and $\gcd(f(x), n) \ge n^{\beta}$ (or $f(x) = 0 \bmod b$, $b$ an unknown divisor of $n$ of size $\ge n^{\beta}$) in time polynomial in $\log n$ and $d$.

Now here we have $|p - \sqrt{n}| < n^{1/4}$. Setting $f(x) = x - \lfloor \sqrt{n} \rfloor$, this means that there is an $x_0$ bounded in absolute value by $n^{\left(1/2\right)^2} = n^{1/4}$ such that $\gcd(x_0 - \lfloor \sqrt{n} \rfloor, n) \ge n^{1/2}$ (that is, a factor of $n$), and such an $x_0$ can be found in polynomial time in $\log n$.

$\endgroup$
2
  • 1
    $\begingroup$ Do you know who published this nice technique? It seems way better (or less hopeless, rather) in practice than Fermat factoring. And it makes the prescription $\lvert p–q\rvert>2^{(n_\text{len}/2)–100}$ of FIPS 186-4, section B.3.1, item 2(d) look even stranger. Of course, probability that $|p-\sqrt n|<\sqrt[4]n$ is so low [ $\lesssim14/2^{(n_\text{len}/4)}$ with the prescribed ranges for $p$ and $q$ I believe] that, even combined with Lehman's enhancement, it's still not a factorization technique applicable to RSA moduli. $\endgroup$ – fgrieu May 10 at 8:46
  • 4
    $\begingroup$ Well, knowing that $|p - \sqrt{n}| \le n^{1/4}$ is really the same as saying that you know half of the most significant bits of a factor. So Coppersmith already did this back in 1996. However his method was more complicated and used a bivariate polynomial. Boneh and Howgrave-Graham first came up with the theorem as above. May popularized it in his PhD thesis. $\endgroup$ – Samuel Neves May 10 at 19:04
1
$\begingroup$

TL;DR This is exactly what is needed for the Fermat factoring method to succeed fast.

It is easy to show that $q$ is also within a range of $\sqrt[4]{N}$ of $\sqrt{N}$ up to a little discrepancy.

Then, we can approximate $p+q$ as $2\sqrt{N}$:

$(p+q) - 2\sqrt{N} = \sqrt{(p+q)^2} - 2\sqrt{N} = \sqrt{(p-q)^2 + 4N} - 2\sqrt{N} = 2\sqrt{N}(\sqrt{(q-p)^2/4N+1}-1)$

Using $0 \le q-p\le 2\sqrt[4]{N}$ and $\sqrt{1+x}-1 = x/2 + O(x^2)$,

$0 \le (p+q) - 2\sqrt{N} \le 2\sqrt{N}(\sqrt{1/\sqrt{N}+1}-1) = 2\sqrt{N}( 1/2\sqrt{N} + O(1/N) = 1 + O(1/\sqrt{N}).$

We see that the approximation is valid up to a small constant. Thus, the Fermat method succeeds immediately or we can also use a few candidate for $p+q$ to factor $N=pq$.

$\endgroup$

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.