\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: