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. |-------------------------|
$$
a_0 + \frac{1}{a_1
    + \frac{1}{a_2
    + \frac{1}{a_3
    + \frac{1}{a_4 + \ldots}}}}
$$
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:
$$

  a_{-1} = 0 \quad
  a_i = h_i // k_i

  h_{-1} = 1 \quad h_{-2} = 0 \quad
  h_i = a_i h_{i-1} + h_{i-2}

  k_{-1} = 0  \quad k_{-2} = 1 \quad
  k_i = a_i k_{i-1} + k_{i-2}
$$


\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*}

\section{Again on the engine™}

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