CryptoBook
Search…
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
dd
with a further relaxed condition. If
dd
satisfies:
d<N0.292d < N^{0.292}
Then we can use Boneh-Durfee attack to retrive
dd
this, using a graphical directed point of view, can be seen as:
{E,n}d<N0.292P{d}\{E, n\} \xrightarrow[d < N^{0.292}]{P} \{d\}
Consider
d<Nid < N^{i}
for first, see that
1=ed+kϕ(N)21=ed + \frac{k \phi(N)}{2}\\
As stated above, the RSA's totient function can be espressed as:
ϕ(N)=(p1)(q1)=Nqp+1 \phi(N) = (p-1)(q-1) = N-q-p+1
continuing with the equation, we see that
1=ed+k(N+12p+q2)1 = ed + k(\frac{N+1}{2}-\frac{p+q}{2} )
and if we decide to consider
x=N+12x = \frac{N+1}{2}
and
y=p+q2y = \frac{p+q}{2}
, we will have:
1=ed+k(x+y)1 = ed + k(x+y)
At this point, finding
dd
is equivalent to find the 2 small solutions
xx
and
yy
to the congruence
f(x,y)k(x+y)1 (mod e)k(x+y)1( mod e)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=p+q2s = -\frac{p+q}{2}
and
A=N+12A = \frac{N+1}{2}
this will preserve the scomposed
ϕ(N)\phi(N)
subtraction
k(A+s)1( mod e)k(A+s) \equiv 1 (\space mod \space e)
consider
e=Nαe=N^{\alpha}
(with any
α\alpha
), we deduct that
α\alpha
must be really closed to
11
because
ee
is in the same order of the length of
NN
(so
e=N1e=N^{\sim 1^{-}}
), we will get
s<2N=p+q2<2N=2e12αek<2edϕ(N)3edN<3e1+α+1α<ei| 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