bachelor/book/wiener.tex

\chapter{Wiener's Attack}

Wiener's attack was first published in 1989 as a result of cryptanalysis on the
use of short RSA secret keys ~\cite{wiener}. It exploited the fact that it is
possible to find the private key in \emph{polynomial time} using continued fractions
expansions whenever a good estimate of the fraction $\frac{e}{N}$ is known.
More specifically, given $d < \frac{1}{3} ^{4}\sqrt{N}$ one can efficiently
recover $d$ only knowing $\angular{N, e}$.

\section{A small digression into continued fractions \label{sec:wiener:cf}}

\section{The actual attack}


As we saw in ~\ref{sec:preq:rsa}, by contruction the two exponents are such that
$ed \equiv 1 \pmod{\varphi(N)}$. This implies that there exists a
$k \in \naturalN \mid ed = k\varphi(N) + 1$. This can be formalized to be
the same problem we saw in ~\ref{sec:wiener:cf}:
\begin{align*}
  ed = k\varphi(N) + 1 \\
  \abs{\frac{ed - k\eulerphi{N}}{d\eulerphi{N}}} = \frac{1}{d\eulerphi{N}} \\
  \abs{\frac{e}{\eulerphi{N}} - \frac{k}{d}} = \frac{1}{d\eulerphi{N}} \\
\end{align*}

Now we proceed by substituting $\eulerphi{N}$ with $N$, since for large $N$, one
approximates the other. We consider also the difference of the two, limited by
$\abs{\cancel{N} + p + q - 1 - \cancel{N}} < 3\sqrt{N}$.
For the last step, remember that $k < d < \rfrac{1}{3} {}^4\sqrt{N}$:

\begin{align*}
  \abs{\frac{e}{N} - \frac{k}{d}} &= \abs{\frac{ed - kN}{Nd}} \\
  &= \abs{\frac{\cancel{ed} -kN - \cancel{k\eulerphi{N}} + k\eulerphi{N}}{Nd}} \\
  &= \abs{\frac{1-k(N-\eulerphi{N})}{Nd}} \\
  &\leq \abs{\frac{3k\sqrt{N}}{Nd}}
  = \frac{3k}{d\sqrt{N}}
  < \frac{3(\rfrac{1}{3} {}^4\sqrt{N})}{d\sqrt{N}}
  = \frac{1}{d{}^4\sqrt{N}}
\end{align*}

\section{Again on the engine™}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "question_authority"
%%% End: