6
$\begingroup$

I'm doing some research into attacks on the RSA cryptosystem and have stumbled across Wiener's attack. Within the proof there exists the statement "$p+q-1 < 3\sqrt{N}$".
No proof is given for this, and I can't seem to figure out why this statement holds. Could anyone help me figure this out or point me towards the relevant theorems?

$\endgroup$
9
$\begingroup$

There is likely an assumption on the sizes of $p$ and $q$ that you haven't listed in your question that exists in the description. For example, Boneh's description of Wiener's attack has that $q<p<2q$.

With that assumption, we can prove the inequality.

We know that

$$p+q < 2q+q$$ $$p+q < 3q$$

Furthermore, since $N=pq$ and $p>q$, we have that $\sqrt{N} > q$, or $3\sqrt{N} > 3q$. So

$$p+q < 3q < 3\sqrt{N}$$

In your inequality, you have $p+q-1$ which is clearly smaller than $p+q$, so everything works out, $p+q-1 < 3\sqrt{N}$.

$\endgroup$
  • 2
    $\begingroup$ To expand on the first sentence: An assumption on the sizes of $p$ and $q$ relative to each other is not only likely, but necessary: otherwise, $p=2$ and $q=17$ and similar highly "unbalanced" cases would provide a counterexample. $\endgroup$ – yyyyyyy Jan 8 '16 at 16:05
  • $\begingroup$ You are very much right! I'd gotten too focussed on one specific part to actually go back and read the attack specifications, thank you! $\endgroup$ – Jonathan Jan 8 '16 at 16:19
2
$\begingroup$

I'm thinking that is not true. Because if we have $p=67$ and $q=3$ then $N=201$ and $p+q-1=69$ and so we have inconsistence.

$\endgroup$
  • 2
    $\begingroup$ as noted by mike, you apparantly need to assume $q<p<2q$ (which is always the case with standard RSA keys) $\endgroup$ – SEJPM Jan 9 '16 at 19:36
  • 2
    $\begingroup$ Right, I just look the question. Sorry $\endgroup$ – Masoud Eskandari Jan 9 '16 at 19:45

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.