bachelor/book/wiener.tex

\chapter{Wiener's cryptanalysis method \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} \sqrt[4]{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 9 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{Background on Continued Fractions \label{sec:wiener:cf}}

Let us call \emph{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*}
Consider now any \emph{finite continued fraction}, conveniently represented with
the sequence
$\angular{a_0, a_1, a_2, a_3,  \ \ldots, a_n}$.
Any number $x \in \mathbb{Q}$ can be represented as a finite continued fraction,
and for each $i < n$ there exists a fraction $\rfrac{h}{k}$ approximating
$x$.
By definition, each new approximation
$$
\begin{bmatrix}
  h_i \\ k_i
\end{bmatrix}
=
\angular{a_0, a_1, \ \ldots, a_i}
$$
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}

Among the prolific properties of such objects, Legendre in 1768 discovered that,
if a continued fraction $f' = \frac{\theta'}{\kappa'}$ is
an underestimate of another one $f = \frac{\theta}{\kappa}$, i.e.
\begin{align}
  \abs{f - f'} = \delta
\end{align}
then for a $\delta$ sufficiently small, $f'$ is \emph{equal} to the $n$-th
continued fraction expansion of $f$, for some $n \geq 0$ (\cite{smeets} \S 2).
Formally,

\begin{theorem*}[Legendre]
  If $f = \frac{\theta}{\kappa}$,  $f' = \frac{\theta'}{\kappa'}$ and
  $\gcd(\theta, \kappa) = 1$, then
  \begin{align}
  \label{eq:wiener:cf_approx}
    \abs{f' - \frac{\theta}{\kappa}} < \delta = \frac{1}{2\kappa^2}
    \quad
    \text{ implies that }
    \quad
    \begin{bmatrix}
      \theta' \\ \kappa'
    \end{bmatrix}
    =
    \begin{bmatrix}
      \theta_n \\ \kappa_n
    \end{bmatrix},
    \quad
    \text{ for some } n \geq 0
  \end{align}
\end{theorem*}

Two centuries later, first Wiener \cite{wiener} and later Dan Boneh
\cite{20years} leveraged this theorem in order to produce an algorithm able to
recover $f$, having $f'$.
The \emph{continued fraction algorithm}  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{Continued Fraction Algorithm applied to RSA}

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{eq:wiener:cf_approx}:
\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}\sqrt[4]{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}\ \sqrt[4]{N})}{d\sqrt{N}}
  = \frac{1}{d\sqrt[4]{N}} < \frac{1}{2d^2}
\end{align*}

This demonstrates that the hypotesis of ~\ref{eq:wiener:cf_approx} is satisfied,
and allows us to proceed with the continued fraction algorithm to converge to a
solution ~\cite{20years}.

\paragraph{}
We start by generating the $\log N$ continued fraction expansions of
$\frac{e}{N}$, and for each convergent $\frac{k}{d}$,
%% XXX. verify this
which by contruction is already at the lowest terms, we verify if it produces a
factorization of $N$.
First we check that $\eulerphi{N} = \frac{ed-1}{k}$ is
an integer. Then we solve ~\ref{eq:wiener:pq} in $x$ in order to find $p, q$:
\begin{align}
  \label{eq:wiener:pq}
  x^2 - (N - \eulerphi{N} + 1)x + N = 0
\end{align}
The above equation is constructed so that the $x$ coefficient is the sum of the
two primes, while the constant term $N$ is the product of the two. Therefore, if
$\eulerphi{N}$ has been correctly guessed, the two roots will be $p$ and $q$.

\section{An Implementation Perspective}

The algorithm is pretty straightforward by itself: we just need to apply the
definitions provided in ~\ref{eq:wiener:cf} and test each convergent until
$\log N$ iterations have been reached.
%% XXX. questo viene da 20 years, ma non e` spiegato perche`.
A Continued fraction structure may look like this:

\begin{minted}{c}
  typedef struct cf {
    bigfraction_t fs[3];  /* holding h_i/k_i, h_i-1/k_i-1, h_i-2/k_i-2 */
    short i;              /* cycling in range(0, 3) */
    bigfraction_t x;      /* pointer to the i-th fraction in fs */
    BIGNUM* a;            /* current a_i */
    BN_CTX* ctx;
  } cf_t;
\end{minted}
where \texttt{bigfraction\_t} is just a pair of \texttt{BIGNUM} \!s
$\angular{h_i, k_i}$. Whenever we need to produce a new convergent, we increment
$i \pmod{3}$ and apply the given definitions. The fresh convergent must be
tested with very simple algebraic operations. It is worth noting here that
\ref{eq:wiener:pq} can be solved using the reduced discriminant formula, as
$p, q$ are odd primes:
\begin{align*}
\Delta = \left( \frac{N-\eulerphi{N} + 1}{2} \right)^2 - N \\
x_{\angular{p , q}} = - \frac{N - \eulerphi{N} + 1}{2} \pm \sqrt{\Delta}
\end{align*}
Assuming the existence of the procedures \texttt{cf\_init}, initializing a
continued fraction structure, and \texttt{cf\_next} producing the next
convergent, we provide an algorithm for attacking the RSA cipher via Wiener:

\begin{algorithm}[H]
  \caption{Wiener's Attack}
  \label{alg:wiener}
  \begin{algorithmic}[1]
    \Function{wiener}{\PKArg}
    \State $f \gets  \texttt{cf\_init}(e, N)$
    \For{$\ceil{\log N} \strong{ times }$}
      \State $k, d \gets \texttt{cf\_next}(f)$
      \If{$k \nmid ed-1$} \strong{continue} \EndIf
      \State $\eulerphi{N} \gets (ed - 1)\ //\ k$
      \If{$\eulerphi{N}$ is odd} \strong{continue} \EndIf
%% XXX. it could be that calling 'b' b/2 and 'delta' sqrt(delta/4) is
%% misleading.
      \State $b \gets (N - \eulerphi{N} + 1) \gg 1$
      \State $\Delta, r \gets \dsqrt{b^2 - N}$
      \If{$r \neq 0$} \strong{continue} \EndIf
      \State $p \gets b + \Delta$
      \State $q \gets b - \Delta$
      \State \strong{break}
    \EndFor
    \State \Return $p, q$
    \EndFunction
  \end{algorithmic}
\end{algorithm}

\paragraph{Parallelism}
Parallel implementation of this specific version of Wiener's Attack is
difficult, because the inner loop is inherently serial. At best, parallelism
could be employed to split the task into a \emph{constructor} process, building
the $f_n$ convergents, and many \emph{consumers} receiving each convergent to be
processed seperatedly.
The first one arriving to a solution, broadcasts a stop message to the others.

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