howpublished = "\url{http://ieeexplore.ieee.org/xpl/articleDetails.jsp?reload=true&arnumber=6178001}"
}
+@misc {Lee-Choi-Koren-Dooho-improved-shamirs-crt-rsa,
+ author = "Lee, Seungkwang and Choi, Dooho and Choi, Yongjae",
+ title = "Improved Shamir's CRT-RSA Algorithm: A Revisit with the Modulus Chaining Method",
+ year = "2013",
+ howpublished = "\url{http://dx.doi.org/10.4218/etrij.14.0113.0317}"
+}
+
@misc {wiki-rsa,
author = "Wikipedia",
title = "RSA (cryptosystem) --- {W}ikipedia{,} The Free Encyclopedia",
year = "2014",
howpublished = "\url{http://en.wikipedia.org/wiki/RSA_%28cryptosystem%29}"
- }
-
\ No newline at end of file
+ }
\ No newline at end of file
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
+Le but de ce laboratoire et de mettre en œuvre l'attaque \emph{Boneh-DeMillo-Lipton} sur notre propre implémentation de \emph{RSA-CRT}~\footnote{\emph{Chinese remainder theorem}}. Puis de décrire et d'implémenter le \flqq truc\frqq\ de \emph{Shamir} afin de prévenir ce type d'attaque.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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}}.
+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 le 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}}.
+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).
+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 :
\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.
+La génération de signatures 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} ?}
+\subsubsection*{Question 1.3 : Quelles sont les valeurs que l'on peut pré-calculer et 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.
+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}
+{\setlength{\abovedisplayskip}{0pt}
\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) \\
+ n &= p \cdot q \\
+ \varphi(n) &= (p - 1) \cdot (q - 1) \\
d &= e^{-1} ~(mod ~\varphi(n)) \\
\mathbf{d_p} &= d ~(mod ~p - 1) \\
\mathbf{d_q} &= d ~(mod ~q - 1) \\
La signature $sig$ du message $m$ peut être ensuite calculée comme suit.
-{\setlength{\abovedisplayskip}{-4pt}
+{\setlength{\abovedisplayskip}{0pt}
\begin{flalign*}
s_p &= m^{d_p} ~(mod ~p) &\\
s_q &= m^{d_q} ~(mod ~q) \\
\subsection{Fonctionnement}
-D'après le document \cite{Boneh-DeMillo-Lipton-attack} :
+D'après le document \flqq On the Importance of Eliminating Errors in Cryptographic Computations\frqq~\cite{Boneh-DeMillo-Lipton-attack} $q$ peut être retrouvé comme suit :
-{\setlength{\abovedisplayskip}{-4pt}
+{\setlength{\abovedisplayskip}{0pt}
\begin{flalign*}
- q &= gcd(m - sign'^e, n) &
+ q &= gcd(m - sig'^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é.
+ \item $m$ : le message signé avec $sig'$.
+ \item $sig'$ : la signature calculée avec un $p$ altéré.
+ \item $e$ : l'exposant public.
+ \item $n$ : le module public.
\end{itemize}
Nous pouvons alors facilement retrouver $p$:
-{\setlength{\abovedisplayskip}{-4pt}
+{\setlength{\abovedisplayskip}{0pt}
\begin{flalign*}
p &= n / q &
\end{flalign*}
\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} :
+Voici une liste de techniques issues du document \flqq Fault Injection Attacks on Cryptographic Devices: Theory, Practice and Countermeasures\frqq~\cite{Barenghi-Breveglieri-Koren-Naccache-fault-injection} :
\begin{itemize}
\item Variation du niveau de voltage de l'alimentation électrique ;
\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.
+Il faut aussi ajouter qu'il est également possible d'utiliser des failles logicielles afin d'introduire des anomalies dans les calculs.
\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 :
+Oui, il est possible de récupérer $p$ ou $q$ si l'on possède une signature valide mais pas le message original :
-{\setlength{\abovedisplayskip}{-4pt}
+{\setlength{\abovedisplayskip}{0pt}
\begin{flalign*}
- q &= gcd(sign - sign'^e, n) &
+ q &= gcd(sig - sig'^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é.
+ \item $sig$ : la signature correctement calculée.
+ \item $sig'$ : la signature calculée avec un $p$ altéré.
\end{itemize}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\section{Le \flqq truc \frqq de \emph{Shamir}}
+\section{Le \flqq truc\frqq\ de \emph{Shamir}}
\subsection{Fonctionnement}
+Le principe consiste à introduire un nombre généré aléatoirement $r$ dans le calcul de $s_p$ et $s_q$ puis de vérifier que ces deux parties congrues modulo $r$.
+Voici ce qui a été implémenté :
+{\setlength{\abovedisplayskip}{0pt}
+\begin{flalign*}
+ \mathbf{r} &&\text{un nombre premier aléatoire de 64 bits} \\
+ exp &= d ~mod ~\varphi(p \cdot \mathbf{r}) \\
+ s_{pr} &= m^{exp} ~mod ~p \cdot \mathbf{r} \\
+ s_{qr} &= m^{exp} ~mod ~q \cdot \mathbf{r}
+\end{flalign*}
+Il faut alors vérifier cette égalité :
+{\setlength{\abovedisplayskip}{0pt}
+\begin{flalign*}
+ s_{pr} ~mod ~\mathbf{r} &= s_{qr} ~mod ~\mathbf{r} &
+\end{flalign*}
+Si celle ci est correcte alors on calcul $s_p$ et $s_q$ de la manière suivante, la signature est alors calculée de la même façon que montrée à la question 1.3. Si l'égalité n'est pas correct alors un message d'erreur est renvoyé.
+
+{\setlength{\abovedisplayskip}{0pt}
+\begin{flalign*}
+ s_p &= s_{pr} ~mod ~p \\
+ s_q &= s_{qr} ~mod ~q &
+\end{flalign*}
+
+Une explication complète est fournit par le document \flqq Improved Shamir's CRT-RSA Algorithm: A Revisit with the Modulus Chaining Method\frqq~\cite{Lee-Choi-Koren-Dooho-improved-shamirs-crt-rsa}.
+
+
+\subsection{Implémentation}
+
+Une tentative d'attaque sur un code utilisant le \flqq truc\frqq\ de \emph{Shamir} est illustrée dans la fonction \texttt{Tests::doAttackFixed()}. Pour tester cette attaque :
+
+\begin{verbatim}
+qbs run -- attack-fixed
+\end{verbatim}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conclusion}
+L'implémentation de RSA à l'aide des restes chinois permet de gagner du temps \emph{CPU} lors de la signature. Un facteur 3.25 a été observé. Cette implémentation étant vulnérable à l'attaque \emph{Boneh-DeMillo-Lipton}, l'implémentation du \flqq truc\frqq\ de \emph{Shamir} a permis de prévenir cette attaque tout en étant 2.46 fois plus rapide que l'implémentation standard de \emph{RSA}.
+
+Il faut bien garder à l'esprit que l'implémentation réalisée ici est de type \emph{textbook} et ne doit pas être utilisée telle quelle en pratique. Il manque notamment l'ajout de bourrage tel que \emph{OAEP}.
+
\bibliographystyle{plain}
\bibliography{main}
mpz_class RsaCrt::sign(const mpz_class& m, const KeyPriv& kPriv)
{
- mpz_class sp, sq;
-
- mpz_powm_sec(sp.get_mpz_t(), m.get_mpz_t(), kPriv.dp.get_mpz_t(), kPriv.p.get_mpz_t());
- mpz_powm_sec(sq.get_mpz_t(), m.get_mpz_t(), kPriv.dq.get_mpz_t(), kPriv.q.get_mpz_t());
-
- return sq + ((kPriv.qInv * (sp - sq)) % kPriv.p) * kPriv.q;
+ return sign(m, kPriv, false);
}
mpz_class RsaCrt::signWithFaultySp(const mpz_class& m, const KeyPriv& kPriv)
+{
+ return sign(m, kPriv, true);
+}
+
+mpz_class RsaCrt::sign(const mpz_class& m, const KeyPriv& kPriv, bool withError)
{
mpz_class sp, sq;
mpz_powm_sec(sp.get_mpz_t(), m.get_mpz_t(), kPriv.dp.get_mpz_t(), kPriv.p.get_mpz_t());
mpz_powm_sec(sq.get_mpz_t(), m.get_mpz_t(), kPriv.dq.get_mpz_t(), kPriv.q.get_mpz_t());
- mpz_combit(sp.get_mpz_t(), 42); // Flip the fourty second bit.
+ if (withError)
+ mpz_combit(sp.get_mpz_t(), 42); // Flip the fourty second bit.
return sq + ((kPriv.qInv * (sp - sq)) % kPriv.p) * kPriv.q;
}
* @param m the message to sign. No padding is used.
*/
static mpz_class signWithFaultySp(const mpz_class& m, const KeyPriv& kPriv);
+
+private:
+ static mpz_class sign(const mpz_class& m, const KeyPriv& kPriv, bool withError);
};
#endif
}
mpz_class RsaCrtShamirsTrick::sign(const mpz_class& m, const KeyPriv& kPriv)
+{
+ return sign(m, kPriv, false);
+}
+
+mpz_class RsaCrtShamirsTrick::signWithFaultySp(const mpz_class& m, const KeyPriv& kPriv)
+{
+ return sign(m, kPriv, true);
+}
+
+mpz_class RsaCrtShamirsTrick::sign(const mpz_class& m, const KeyPriv& kPriv, bool withError)
{
const mpz_class r = Rand::randPrime(64);
const mpz_class sqExponent = kPriv.d % ((kPriv.q - 1) * (r - 1)); // d mod phi(q * r).
mpz_class spr, sqr;
- mpz_powm(spr.get_mpz_t(), m.get_mpz_t(), spExponent.get_mpz_t(), pr.get_mpz_t());
- mpz_powm(sqr.get_mpz_t(), m.get_mpz_t(), sqExponent.get_mpz_t(), qr.get_mpz_t());
+ mpz_powm(spr.get_mpz_t(), m.get_mpz_t(), spExponent.get_mpz_t(), pr.get_mpz_t()); // spr = m^exp mod p*r.
+ mpz_powm(sqr.get_mpz_t(), m.get_mpz_t(), sqExponent.get_mpz_t(), qr.get_mpz_t()); // sqr = m^exp mod q*r.
+
+ if (withError)
+ mpz_combit(spr.get_mpz_t(), 42); // Flip the fourty second bit.
if (spr % r != sqr % r)
throw UnableToSignWithShamirsTrick();
return sq + ((kPriv.qInv * (sp - sq)) % kPriv.p) * kPriv.q;
}
-
-mpz_class RsaCrtShamirsTrick::signWithFaultySp(const mpz_class& m, const KeyPriv& kPriv)
-{
- mpz_class sp, sq;/*
-
- mpz_powm_sec(sp.get_mpz_t(), m.get_mpz_t(), kPriv.dp.get_mpz_t(), kPriv.p.get_mpz_t());
- mpz_powm_sec(sq.get_mpz_t(), m.get_mpz_t(), kPriv.dq.get_mpz_t(), kPriv.q.get_mpz_t());
-
- mpz_combit(sp.get_mpz_t(), 42); // Flip the fourty second bit.
-
- return sq + ((kPriv.qInv * (sp - sq)) % kPriv.p) * kPriv.q;*/
- return sp;
-}
* @param m the message to sign. No padding is used.
*/
static mpz_class signWithFaultySp(const mpz_class& m, const KeyPriv& kPriv);
+
+private:
+ static mpz_class sign(const mpz_class& m, const KeyPriv& kPriv, bool withError);
};
#endif
void Tests::runTests()
{
- if (this->rsaStandard())
- cout << "RSA standard OK" << endl;
- else
- cout << "RSA standard failed!" << endl;
+ cout << "Tests::runTests() ..." << endl;
- if (this->rsaCrt())
- cout << "RSA CRT OK" << endl;
- else
- cout << "RSA CRT failed!" << endl;
+ cout << "RSA standard: " << (this->rsaStandard() ? "OK" : "failed!") << endl;
+ cout << "RSA CRT: " << (this->rsaCrt() ? "OK" : "failed!") << endl;
}
void Tests::runTestsWithShamirsTrick()
{
- if (this->rsaCrtWithShamirsTrick())
- cout << "RSA CRT with shamir's trick OK" << endl;
- else
- cout << "RSA CRT with shamir's trick failed!" << endl;
+ cout << "Tests::runTestsWithShamirsTrick() ..." << endl;
+
+ cout << "RSA CRT with Shamir's trick: " << (this->rsaCrtWithShamirsTrick() ? "OK" : "failed!") << endl;
}
void Tests::runTimeMeasures()
{
+ cout << "Tests::runTimeMeasures() ..." << endl;
+
const int N = 1000;
const int nbKeys = 20; // Number of different generated key.
cout << N * nbKeys << " x RSA CRT: " << timeRsaCRT << " ms" << endl;
cout << N * nbKeys << " x RSA CRT Shamir's trick: " << timeRsaCRTShamirsTrick << " ms" << endl;
cout << "Speedup for CRT: " << (double(timeRsaStd) / double(timeRsaCRT)) << endl;
- cout << "Speedup for CRT with Shamir's trick: " << (double(timeRsaStd) / double(timeRsaCRT)) << endl;
+ cout << "Speedup for CRT with Shamir's trick: " << (double(timeRsaStd) / double(timeRsaCRTShamirsTrick)) << endl;
}
void Tests::doAttack()
{
+ cout << "Tests::doAttack() ..." << endl;
+
const auto& keys = RsaCrt::generateRSAKeys(RSA_PUBLIC_EXPONENT, KEY_SIZE_BITS);
const auto& kPub = keys.first;
const auto& kPriv = keys.second;
attackSuccessful = attackSuccessful && kPriv.p == p && kPriv.q == q; // With p and q we can recreate the original private key.
}
- // Try the attack with a correct signature.
+ // Try the attack with a correct signature (p and q shouldn't be found).
{
mpz_class correctSignaturePowerE;
mpz_pow_ui(correctSignaturePowerE.get_mpz_t(), correctSignature.get_mpz_t(), RSA_PUBLIC_EXPONENT);
void Tests::doAttackFixed()
{
- const auto& keys = RsaCrt::generateRSAKeys(RSA_PUBLIC_EXPONENT, KEY_SIZE_BITS);
- const auto& kPub = keys.first;
+ cout << "Tests::doAttackFixed() ..." << endl;
+
+ const auto& keys = RsaCrtShamirsTrick::generateRSAKeys(RSA_PUBLIC_EXPONENT, KEY_SIZE_BITS);
const auto& kPriv = keys.second;
+
+ mpz_class message = Rand::randSize(128);
+
+ try
+ {
+ RsaCrtShamirsTrick::signWithFaultySp(message, kPriv);
+ cout << "Attack successful -> incorrect" << endl;
+ }
+ catch (const RsaCrtShamirsTrick::UnableToSignWithShamirsTrick& e)
+ {
+ cout << "Attack failed -> correct" << endl;
+ }
}
bool Tests::rsaStandard()
projects / crypto_lab3.git / commitdiff