CryptoBook

Search…

Fundamentals

Number Theory

Abstract algebra

Elliptic Curves

Lattices

Asymmetric Cryptography

Symmetric Cryptography

Isogeny Based Cryptography

Appendices

Powered By GitBook

Boneh-Durfee Attack

What is Boneh-Durfee Attack

Boneh-Durfee attack is an extension of Wiener's attack. That is, it also attacks on low private component

$d$

with a further relaxed condition. If $d$

satisfies:$d < N^{0.292}$

Then we can use Boneh-Durfee attack to retrive

$d$

this, using a graphical directed point of view, can be seen as:

$\{E, n\} \xrightarrow[d < N^{0.292}]{P} \{d\}$

Consider

$d < N^{i}$

for first, see that$1=ed + \frac{k \phi(N)}{2}\\$

As stated above, the RSA's totient function can be espressed as:

$\phi(N) = (p-1)(q-1) = N-q-p+1$

continuing with the equation, we see that

$1 = ed + k(\frac{N+1}{2}-\frac{p+q}{2} )$

and if we decide to consider

$x = \frac{N+1}{2}$

and $y = \frac{p+q}{2}$

, we will have:$1 = ed + k(x+y)$

At this point, finding

$d$

is equivalent to find the 2 small solutions $x$

and $y$

to the congruence$f(x,y) \equiv k(x+y) \equiv 1 \space (mod \space e) \\
k(x + y) \equiv 1 (\space mod \space e)$

now let

$s = -\frac{p+q}{2}$

and $A = \frac{N+1}{2}$

this will preserve the scomposed $\phi(N)$

subtraction$k(A+s) \equiv 1 (\space mod \space e)$

consider

$e=N^{\alpha}$

(with any $\alpha$

), we deduct that $\alpha$

must be really closed to $1$

because $e$

is in the same order of the length of $N$

(so $e=N^{\sim 1^{-}}$

), we will get$| s | < 2\sqrt{N} = \\
\frac{p+q}{2} < 2\sqrt{N} =2e^{\frac{1}{2\alpha}} \sim \sqrt{e} \\
|k| < \frac{2ed}{\phi{(N)}} \leq\frac{3ed}{N}< 3e^{1+\frac{\alpha+1}{\alpha}} < e^{i}$

1

Copied!

Sage Implementation

RSA-and-LLL-attacks/boneh_durfee.sage at master · mimoo/RSA-and-LLL-attacks

GitHub

Boneh-Durfee attack Sage implementation

Last modified 4mo ago

Export as PDF

Copy link