\documentclass[a4paper,10pt]{article}

\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}

\usepackage{amssymb,amsmath,amsthm}

\usepackage{graphicx}
\usepackage{listings}
\usepackage{url}
\usepackage{upquote} 
\usepackage{color}
\usepackage[usenames,dvipsnames]{xcolor}

\title{ICR - Labo \#3 : \textit{Attaque par faute contre RSA-CRT}}
\author{G.Burri}


\begin{document}

\nocite{*}

\maketitle


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{RSA-CRT}

\subsection{Implémentation}

L'implémentation utilise le langage \emph{C++11}, le compilateur \emph{GCC} 4.9.1, la \emph{library} \emph{GMP} 6.0.0 ainsi que la système de \emph{build} \emph{QBS}~\footnote{\url{http://qt-project.org/wiki/qbs}}.

Le fichier \emph{*.qbs} peut-être ouvert à l'aide de l'environnement de développement \emph{Qt Creator}~\footnote{\url{http://qt-project.org/wiki/Category:Tools::QtCreator}}.


\subsubsection*{Question 1.1 : Comment s'assure-t-on que les routines implémentées fonctionnent correctement ?}

Pour chaque version, standard et restes chinois, une paire de clefs est générée puis trois messages sont testés avec des valeurs différentes correspondantes à $n$, $n-1$ et $n / 2$. Pour le premier cas la vérification de la signature ne doit pas fonctionner car le \emph{plaintext} est trop grand, dans les deux autres cas, on vérifie la signature ainsi qu'une signature altérée (incrémentée de 1).

Les tests peuvent être lancés avec la commande suivante :

\begin{verbatim}
qbs run -- tests 
\end{verbatim}


\subsubsection*{Question 1.2 : Quel est le gain en terme de temps d'exécution lors de la création d'une signature avec \emph{RSA-CRT} par rapport à la version standard ?}

Les mesures sont réalisées en générant $20'000$ signatures. Vingt paires de clefs différentes sont utilisées.

Les temps sont mesurés à l'aide de la commande suivante :

\begin{verbatim}
qbs run release -- time-measures 
\end{verbatim}

\begin{itemize}
   \item \emph{RSA} standard : $14'800\, ms$ ($740\, \mu s$ par signature).
   \item \emph{RSA CRT} : $4'466\, ms$ ($223, \mu s$ par signature).
\end{itemize}

La génération de signature avec \emph{RSA CRT} est en moyenne 3.25 fois plus rapide.


\subsubsection*{Question 1.3 : Quels sont les valeurs que l'on peut pré-calculer est stocker hormis $n$ et $d$ afin d'améliorer la vitesse de calcul d'une signature avec \emph{RSA-CRT} ?}

Les valeurs de $p$, $q$, $d_p$, $d_q$ et $q_{inv}$ sont mémorisées en tant que clef privée. Celles ci sont calculées comme suit.

{\setlength{\abovedisplayskip}{-4pt}
\begin{flalign*}
   e &= 65537 \\
   \mathbf{p, q} &&\text{deux nombres premiers de 512 bits choisis de manière aléatoire} \\
   n &= p * q \\
   \varphi(n) &= (p - 1) * (q - 1) \\
   d &= e^{-1} ~(mod ~\varphi(n)) \\
   \mathbf{d_p} &= d ~(mod ~p - 1) \\
   \mathbf{d_q} &= d ~(mod ~q - 1) \\
   \mathbf{q_{inv}} &= q^{-1} ~(mod ~p)
\end{flalign*}


La signature $sig$ du message $m$ peut être ensuite calculée comme suit.

{\setlength{\abovedisplayskip}{-4pt}
\begin{flalign*}
   s_p &= m^{d_p} ~(mod ~p) &\\
   s_q &= m^{d_q} ~(mod ~q) \\
   \mathbf{sig} &= s_q + ((q_{inv} \cdot (s_p - s_q)) ~mod ~p) \cdot q
\end{flalign*}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{L'attaque de \emph{Boneh-DeMillo-Lipton}}

\subsection{Fonctionnement}

D'après le document \cite{Boneh-DeMillo-Lipton-attack} :

{\setlength{\abovedisplayskip}{-4pt}
\begin{flalign*}
   q &= gcd(m - sign'^e, n) &
\end{flalign*}

Où :

\begin{itemize}
   \item $m$ : le message signé avec $sign'$
   \item $sign'$ : la signature calculée avec un $p$ altéré.
\end{itemize}


Nous pouvons alors facilement retrouver $p$:

{\setlength{\abovedisplayskip}{-4pt}
\begin{flalign*}
   p &= n / q &
\end{flalign*}

Il est alors trivial de reconstituer la clef privée à partir de $p$ et $q$.

\subsubsection*{Question 2.1 : En pratique, comment est-il possible d'introduire des fautes dans l'implémentation d'un algorithme cryptographique ?}

Voici une liste de techniques issues du document \cite{Barenghi-Breveglieri-Koren-Naccache-fault-injection} :

\begin{itemize}
   \item Variation du niveau de voltage de l'alimentation électrique ;
   \item Injection d’irrégularités dans le \emph{clock} de l'horloge ;
   \item Champs magnétique ;
   \item Émission de radiations ;
   \item Surchauffe de l'appareil ;
   \item Exposition à une lumière intense.
\end{itemize}

Il faut aussi ajouté qu'il est également possible d'utiliser des failles logicielles afin d'introduire des anomalies.


\subsubsection*{Question 2.2 : Est-ce que cette attaque fonctionne dans le cas d'un bourrage non déterministe ?}

Oui, il est possible de récupérer $p$ ou $q$ s'il l'on possède une signature valide mais pas le message original :

{\setlength{\abovedisplayskip}{-4pt}
\begin{flalign*}
   q &= gcd(sign - sign'^e, n) &
\end{flalign*}

Où :

\begin{itemize}
   \item $sign$ : la signature correctement calculée. 
   \item $sign'$ : la signature calculée avec un $p$ altéré.
\end{itemize}



\subsection{Implémentation}

Cette attaque est illustrée dans la fonction \texttt{Tests::doAttack()}. Pour tester cette attaque :

\begin{verbatim}
qbs run -- attack 
\end{verbatim}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Le \flqq truc \frqq de \emph{Shamir}}

\subsection{Fonctionnement}









%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conclusion}


\bibliographystyle{plain}
\bibliography{main}

\end{document}
