4
$\begingroup$

I need some insight in how to break the following RSA problem:

From an RSA encryption scheme you know that the algorithm that generated the RSA modulus $N$ always outputs moduli of the form $N = pq$ such that the difference between $q^2$ and $p$ is not bigger than $2^8$ in absolute value.

My question is: Shall I try to factor $N$? Which method should I use if so?

Somewhat related is this question.

Edit:
Solving for $q$, I have that $q$ is between the square root of $p-2^8$ and the square root of $p+2^8$.

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
7
$\begingroup$

You can find the factor $q$ just by taking the cube root of $N$ and rounding to the nearest integer!

If $N = pq$ where $p = q^2 + \delta$, then: $$\sqrt[3]N = \sqrt[3]{q(q^2 + \delta)} = \sqrt[3]{q^3 \left( 1+\frac{\delta}{q^2}\right)} = q \cdot \sqrt[3]{1+\frac{\delta}{q^2}}.$$

Thus, as long as $2|\delta| < q$ then, given that $|1-x| \le |1-x^3|$ for all $x \ge 0$: $$\left|q - \sqrt[3]N\right| = q\left|1 - \sqrt[3]{1 + \tfrac{\delta}{q^2}}\right| \le q\left|1 - \left(1 + \tfrac{\delta}{q^2}\right)\right| = \tfrac{|\delta|}{q} < \tfrac12,$$ and so $\sqrt[3]N$ rounds to $q$.

(A more precise calculation, using the fact that $q \ge 2$ and that $|1-\sqrt[3]{1+x}| \le \frac{|x|}2$ for all $|x| \le \frac12$, shows that this actually works even up to $|\delta| < q$.)

More generally, even if $|\delta|$ could be several times as large as $q$, you could still solve the problem efficiently by starting with the approximate solution $\tilde q = \sqrt[3]N$ and testing nearby integers $q \approx \tilde q$ until you find one that evenly divides $N$.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ I'm sceptical of your series for $\sqrt[3]N$: Using the binomial series, I (contradictorily) get $\sqrt[3]N=\sum_{k=0}^\infty\binom{1/3}k\delta^kq^{1-2k}$, which also happens to converge even faster than yours: In fact, for $\lvert\delta\rvert<q$, we already have $q=\operatorname{round}(\sqrt[3]N)$. (To prove this, observe $\lvert\binom{1/3}k\rvert\leq\frac13$ for $k\geq1$ and derive the upper bound $\frac q{3(q-1)}<\frac12$ for the approximation error $\lvert\sum_{k=1}^\infty\binom{1/3}k\delta^kq^{1-2k}\rvert$ using the geometric series.) $\endgroup$
    – yyyyyyy
    Nov 2, 2016 at 2:37
  • $\begingroup$ @yyyyyyy: You're absolutely right, I screwed up that series somehow (by introducing an extra factor of $q$ somewhere, I think). Fixing that simplifies the answer considerably, too. $\endgroup$
    – Ilmari Karonen
    Nov 2, 2016 at 13:57
4
$\begingroup$

Note: Ilmari Karonen's method is superior to mine regarding just about every aspect: It generalizes nicely to much larger $\lvert q^2-p\rvert$, it is easier to implement (no polynomial factorization), and it is very lightweight in terms of computational effort.

Let $p=q^2+\delta$, such that $\lvert\delta\rvert\leq 2^8$. Thus, $$N=pq=(q^2+\delta)q=q^3+\delta q \text.$$ Therefore $q$ is a root of the polynomial $f:=X^3+\delta X-N\in\mathbb Z[X]$, and since $\delta$ is chosen from the small set $\{-2^8,\dots,2^8\}$ you can iterate over all possible values of $\delta$ and try to factor $f$ until you find $q$. For example, in sage, you can use the following code:

R.<X> = ZZ[]
for d in range(-2**8, 2**8+1):
    xs = factor(X ** 3 + d * X - N)
    if xs[0][0].degree() == 1 and not N % xs[0][0][0]:
        print('q = {}'.format(-xs[0][0][0]))
        break
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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