1 \documentclass[a4paper,
10pt
]{article
}
3 \usepackage[francais
]{babel
}
4 \usepackage[utf8
]{inputenc}
5 \usepackage[T1]{fontenc}
8 \usepackage{amssymb,amsmath,amsthm
}
15 \usepackage[usenames,dvipsnames
]{xcolor
}
17 \title{ICR - Labo \
#3 :
\textit{Attaque par faute contre RSA-CRT
}}
28 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
29 \section{Introduction
}
33 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
36 \subsection{Implémentation
}
38 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
}}.
40 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
}}.
43 \subsubsection*
{Question
1.1 : Comment s'assure-t-on que les routines implémentées fonctionnent correctement ?
}
45 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).
47 Les tests peuvent être lancés avec la commande suivante :
54 \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 ?
}
56 Les mesures sont réalisées en générant $
20'
000$ signatures. Vingt paires de clefs différentes sont utilisées.
58 Les temps sont mesurés à l'aide de la commande suivante :
61 qbs run release -- time-measures
65 \item \emph{RSA
} standard : $
14'
800\, ms$ ($
740\,
\mu s$ par signature).
66 \item \emph{RSA CRT
} : $
4'
466\, ms$ ($
223,
\mu s$ par signature).
69 La génération de signature avec
\emph{RSA CRT
} est en moyenne
3.25 fois plus rapide.
72 \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
} ?
}
74 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.
78 \mathbf{p, q
} &&
\text{deux nombres premiers de
512 bits choisis de manière aléatoire
} \\
80 \varphi(n) &= (p -
1) * (q -
1) \\
81 d &= e^
{-
1} ~(mod ~
\varphi(n)) \\
82 \mathbf{d_p
} &= d ~(mod ~p -
1) \\
83 \mathbf{d_q
} &= d ~(mod ~q -
1) \\
84 \mathbf{q_
{inv
}} &= q^
{-
1} ~(mod p)
88 La signature $sig$ du message $m$ peut être ensuite calculée comme suit.
91 s_p &= m^
{d_p
} ~(mod ~p) &\\
92 s_q &= m^
{d_q
} ~(mod ~q) \\
93 \mathbf{sig
} &= s_q + ((q_
{inv
} \cdot (s_p - s_q)) ~mod ~p)
\cdot q
97 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
98 \section{L'attaque de
\emph{Boneh-DeMillo-Lipton
}}
100 \subsection{Fonctionnement
}
102 D'après le
document \cite{Boneh-DeMillo-Lipton-attack
} :
105 q &= gcd(m - sign'^e, n) &
111 \item $m$ : le message signé avec $sign'$
112 \item $sign'$ : la signature calculé avec un $p$ altéré.
116 Nous pouvons alors facilement retrouver $p$:
122 Il est alors trivial de reconstituer la clef privée à partir de $p$ et $q$.
124 \subsubsection*
{Question
2.1 : En pratique, comment est-il possible d'introduire des fautes dans l'implémentation d'un algorithme cryptographique ?
}
126 Voici une liste de techniques issues du
document \cite{Barenghi-Breveglieri-Koren-Naccache-fault-injection
} :
129 \item Variation du niveau de voltage de l'alimentation électrique ;
130 \item Injection d’irrégularités dans le
\emph{clock
} de l'horloge ;
131 \item Champs magnétique ;
132 \item Émission de radiations ;
133 \item Surchauffe de l'appareil ;
134 \item Exposition à une lumière intense.
138 \subsubsection*
{Est-ce que cette attaque fonctionne dans le cas d'un bourrage non déterministe ?
}
143 \subsection{Implémentation
}
145 Cette attaque est illustrée dans la fonction
\texttt{Tests::doAttack()
}. Pour tester cette attaque :
152 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
153 \section{Le
\flqq truc
\frqq de
\emph{Shamir
}}
155 \subsection{Fonctionnement
}
159 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
164 % Fault Injection Attacks on Cryptographic Devices: Theory, Practice and Countermeasures
167 \bibliographystyle{plain
}