bachelor/book/wiener.tex

\chapter{Wiener's Attack \label{chap:wiener}}

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}$.

The scandalous implication behind Wiener's attack is that, even if there are
situations where having a small private exponent may be
particularly tempting with respect to performance (for example, a smart card
communication with a computer), they represent a threat to the security of the
cipher.
Fortunately, ~\cite{wiener} \S 6 presents a couple of precautions that make a
RSA key-pair immune to this attack, namely
(i) making $e > \sqrt{N}$ and
(ii) $gcd(p-1, q-1)$ large.

\section{Continued Fractions background \label{sec:wiener:cf}}

Let us call ``continued fraction'' any expression of the form:
%% why \cfrac sucks this much. |-------------------------|
\begin{align*}
a_0 + \frac{1}{a_1
    + \frac{1}{a_2
    + \frac{1}{a_3
    + \frac{1}{a_4 + \ldots}}}}
\end{align*}
hereby described as a series for convenience:
$\angular{a_0, a_1, a_2, a_3,  \ \ldots, a_n}$.
Any floating point number $x$ can be represented as a continued fraction, and
for each $i < n$ there exists fraction $\rfrac{h_i}{k_i}$ approximating $x$.
By definition, each new approximation is recursively defined as:

\begin{align}
  \label{eq:wiener:cf}
  \begin{cases}
    a_{-1} = 0 \\
    a_i = h_i // k_i \\
  \end{cases}
  \quad
  \begin{cases}
    h_{-2} = 0 \\
    h_{-1} = 1 \\
    h_i = a_i h_{i-1} + h_{i-2}
  \end{cases}
  \quad
  \begin{cases}
    k_{-2} = 1 \\
    k_{-1} = 0  \\
    k_i = a_i k_{i-1} + k_{i-2}
  \end{cases}
\end{align}

After a small digression into the properties of continued fractions, Wiener, in
~\cite{wiener}, shows that, if a continued fraction $f'$ is an underestimate of
another one $f$:
\begin{align}
  f' = f(1-\delta)
\end{align}

Then it is possible to recover $f$, having $f'$, if $\delta$ is small
enough, where small enough means:
\begin{align}
  \label{eq:wiener:cf_approx}
  \delta = 1 - \frac{f'}{f} < \frac{1}{\rfrac{3}{2}{h_1}{k_1}}
\end{align}
\\
The ``continued fraction algorithm'' allowing us to recover $f$ is the
following:
\begin{enumerate}[(i)]
  \setlength{\itemsep}{1pt}
  \setlength{\parskip}{0pt}
  \setlength{\parsep}{0pt}
  \item generate the next $a_i$ of the continued fraction expansion of $f'$;
  \item use ~\ref{eq:wiener:cf} to generate the next fraction $\rfrac{h_i}{k_i}$
    equal to $\angular{a_0, a_1, \ldots, a_{i-1}, a_i}$ %% non e` proprio cosi`
  \item check whether $\rfrac{h_i}{k_i}$ is equal to $f$
\end{enumerate}

\section{The actual attack}

As we saw in ~\ref{sec:preq:rsa}, by construction 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 formalized 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*}

This demonstrates the conditions of ~\ref{eq:wiener:cf_approx} and allows us to
proceed with the continued fraction algorithm to converge to a solution.
\section{Again on the engine™}

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