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} \\
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)
+ \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) \\
D'après le document \cite{Boneh-DeMillo-Lipton-attack} :
+{\setlength{\abovedisplayskip}{-4pt}
\begin{flalign*}
q &= gcd(m - sign'^e, n) &
\end{flalign*}
\begin{itemize}
\item $m$ : le message signé avec $sign'$
- \item $sign'$ : la signature calculé avec un $p$ altéré.
+ \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*}
\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*{Est-ce que cette attaque fonctionne dans le cas d'un bourrage non déterministe ?}
+\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{Fonctionnement}
-(maths)
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\section{Conclusion}
-%
-% Fault Injection Attacks on Cryptographic Devices: Theory, Practice and Countermeasures
+
+
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\section{Conclusion}
\bibliographystyle{plain}
return sq + ((kPriv.qInv * (sp - sq)) % kPriv.p) * kPriv.q;
}
-
-
#define RSACRT_H
#include <utility>
+#include <exception>
#include <gmpxx.h>
/**
* m must not be greater or equal than kPriv.n.
+ * @param m the message to sign. No padding is used.
*/
static mpz_class sign(const mpz_class& m, const KeyPriv& kPriv);
+ /**
+ * Sp is altered by flipping its 42nd bit.
+ * @param m the message to sign. No padding is used.
+ */
static mpz_class signWithFaultySp(const mpz_class& m, const KeyPriv& kPriv);
};
--- /dev/null
+#include "RsaCrtShamirsTrick.h"
+
+using namespace std;
+
+#include "Rand.h"
+#include "Utils.h"
+
+pair<Rsa::KeyPub, RsaCrtShamirsTrick::KeyPriv> RsaCrtShamirsTrick::generateRSAKeys(uint exponent, uint keySizeBits)
+{
+ mpz_class phi;
+ Rsa::KeyPub kPub;
+ KeyPriv kPriv;
+
+ do
+ {
+ kPub.e = exponent;
+ kPriv.p = Rand::randPrime(keySizeBits / 2);
+ kPriv.q = Rand::randPrime(keySizeBits / 2);
+
+ kPub.n = kPriv.p * kPriv.q;
+ phi = (kPriv.p - 1) * (kPriv.q - 1);
+
+ // d = e^-1 (mode phi).
+ } while (mpz_invert(kPriv.d.get_mpz_t(), kPub.e.get_mpz_t(), phi.get_mpz_t()) == 0);
+
+ // qInv = q^-1 (mod p)
+ mpz_invert(kPriv.qInv.get_mpz_t(), kPriv.q.get_mpz_t(), kPriv.p.get_mpz_t());
+
+ return make_pair(kPub, kPriv);
+}
+
+mpz_class RsaCrtShamirsTrick::sign(const mpz_class& m, const KeyPriv& kPriv)
+{
+ const mpz_class r = Rand::randPrime(64);
+
+ const mpz_class pr = kPriv.p * r;
+ const mpz_class qr = kPriv.q * r;
+
+ const mpz_class spExponent = kPriv.d % ((kPriv.p - 1) * (r - 1)); // d mod phi(p * r).
+ 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());
+
+ if (spr % r != sqr % r)
+ throw UnableToSignWithShamirsTrick();
+
+ mpz_class sp = spr % kPriv.p;
+ mpz_class sq = sqr % kPriv.q;
+
+ 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;
+}
--- /dev/null
+#ifndef RSACRT_SHAMIRS_TRICK_H
+#define RSACRT_SHAMIRS_TRICK_H
+
+#include <utility>
+#include <exception>
+
+#include <gmpxx.h>
+
+#include "Rsa.h"
+
+class RsaCrtShamirsTrick
+{
+public:
+ class UnableToSignWithShamirsTrick : public std::exception {};
+
+ struct KeyPriv {
+ mpz_class p;
+ mpz_class q;
+ mpz_class d;
+ mpz_class qInv;
+ };
+
+ /**
+ * Generate a pair of keys (public, private).
+ */
+ static std::pair<Rsa::KeyPub, KeyPriv> generateRSAKeys(uint exponent, uint keySizeBits);
+
+ /**
+ * m must not be greater or equal than kPriv.n.
+ * Use the Shamir's trick to test if a fault has been created during the computation of Sp and Sq.
+ * If so it throws 'UnableToSignWithShamirsTrick'.
+ * @param m the message to sign. No padding is used.
+ */
+ static mpz_class sign(const mpz_class& m, const KeyPriv& kPriv);
+
+ /**
+ * Sp is altered by flipping its 42nd bit.
+ * @param m the message to sign. No padding is used.
+ */
+ static mpz_class signWithFaultySp(const mpz_class& m, const KeyPriv& kPriv);
+};
+
+#endif
#include "Rand.h"
#include "RsaStd.h"
#include "RsaCrt.h"
+#include "RsaCrtShamirsTrick.h"
Tests::Tests(uint keySizeBits, uint rsaPublicExponent) :
KEY_SIZE_BITS(keySizeBits),
cout << "RSA CRT 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;
+}
+
void Tests::runTimeMeasures()
{
const int N = 1000;
int timeRsaStd = 0;
int timeRsaCRT = 0;
+ int timeRsaCRTShamirsTrick = 0;
for (int k = 0; k < nbKeys; ++k)
{
timeRsaStd += timeSignRsaStd(N);
timeRsaCRT += timeSignRsaCRT(N);
+ timeRsaCRTShamirsTrick += timeSignRsaCRTShamirsTrick(N);
}
cout << N * nbKeys << " x RSA standard: " << timeRsaStd << " ms" << endl;
cout << N * nbKeys << " x RSA CRT: " << timeRsaCRT << " ms" << endl;
- cout << "Speedup: " << (double(timeRsaStd) / double(timeRsaCRT)) << 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;
}
void Tests::doAttack()
const auto& keys = RsaCrt::generateRSAKeys(RSA_PUBLIC_EXPONENT, KEY_SIZE_BITS);
const auto& kPub = keys.first;
const auto& kPriv = keys.second;
+
mpz_class message = Rand::randSize(128);
mpz_class faultySignature = RsaCrt::signWithFaultySp(message, kPriv);
mpz_class correctSignature = RsaCrt::sign(message, kPriv);
- bool attackOK = true;
+ bool attackSuccessful = true;
cout << "Original:" << endl;
cout << " p = " << kPriv.p << endl;
cout << " p = " << p << endl;
cout << " q = " << q << endl;
- attackOK = attackOK && kPriv.p == p && kPriv.q == q; // With p and q we can recreate the original private key.
+ 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.
cout << " p = " << p << endl; // Equal to 1.
cout << " q = " << q << endl; // Equal to n.
- attackOK = attackOK && kPriv.p != p && kPriv.q != q;
+ attackSuccessful = attackSuccessful && kPriv.p != p && kPriv.q != q;
}
- if (attackOK)
+ if (attackSuccessful)
cout << "Attack successful" << endl;
else
cout << "Attack failed" << endl;
}
+void Tests::doAttackFixed()
+{
+ const auto& keys = RsaCrt::generateRSAKeys(RSA_PUBLIC_EXPONENT, KEY_SIZE_BITS);
+ const auto& kPub = keys.first;
+ const auto& kPriv = keys.second;
+}
+
bool Tests::rsaStandard()
{
const auto& keys = RsaStd::generateRSAKeys(RSA_PUBLIC_EXPONENT, KEY_SIZE_BITS);
return true;
}
+bool Tests::rsaCrtWithShamirsTrick()
+{
+ const auto& keys = RsaCrtShamirsTrick::generateRSAKeys(RSA_PUBLIC_EXPONENT, KEY_SIZE_BITS);
+ const auto& kPub = keys.first;
+ const auto& kPriv = keys.second;
+
+ {
+ mpz_class message = kPub.n;
+ mpz_class signature = RsaCrtShamirsTrick::sign(message, kPriv);
+ if (Rsa::verifySignature(message, signature, kPub)) // Must not be able to signe message greater than kPub.n.
+ return false;
+ }
+
+ {
+ mpz_class message = kPub.n - 1;
+ mpz_class signature = RsaCrtShamirsTrick::sign(message, kPriv);
+ if (!Rsa::verifySignature(message, signature, kPub) || Rsa::verifySignature(message + 1, signature, kPub))
+ return false;
+ }
+
+ {
+ mpz_class message = kPub.n / 2;
+ mpz_class signature = RsaCrtShamirsTrick::sign(message, kPriv);
+ if (!Rsa::verifySignature(message, signature, kPub) || Rsa::verifySignature(message + 1, signature, kPub))
+ return false;
+ }
+
+ return true;
+}
+
int Tests::timeSignRsaStd(int N)
{
Timer timer;
return timer.ms();
}
+
+int Tests::timeSignRsaCRTShamirsTrick(int N)
+{
+ Timer timer;
+ const auto& keys = RsaCrtShamirsTrick::generateRSAKeys(RSA_PUBLIC_EXPONENT, KEY_SIZE_BITS);
+
+ mpz_class message = Rand::randSize(KEY_SIZE_BITS / 2);
+ for (int i = 0; i < N; i++)
+ RsaCrtShamirsTrick::sign(message, keys.second);
+
+ return timer.ms();
+}
public:
Tests(uint keySizeBits, uint rsaPublicExponent);
- void runTests();
+ void runTests();
+ void runTestsWithShamirsTrick();
void runTimeMeasures();
+
void doAttack();
+ void doAttackFixed();
private:
bool rsaStandard();
bool rsaCrt();
+ bool rsaCrtWithShamirsTrick();
+ /**
+ * Return the time in [ms] required to sign N times with RSA standard.
+ * One key pair and a message is generated.
+ */
int timeSignRsaStd(int N);
+
+ /**
+ * Return the time in [ms] required to sign N times with RSA CRT.
+ * One key pair and a message is generated.
+ */
int timeSignRsaCRT(int N);
+ int timeSignRsaCRTShamirsTrick(int N);
+
const uint KEY_SIZE_BITS;
const uint RSA_PUBLIC_EXPONENT;
};
name: "lab3"
type: "application"
- files: ["main.cpp", "Rand.h", "Rand.cpp", "Rsa.h", "Rsa.cpp", "RsaStd.h", "RsaStd.cpp", "RsaCrt.h", "RsaCrt.cpp", "Utils.h", "Utils.cpp", "Tests.h", "Tests.cpp"]
+ files: ["main.cpp", "Rand.h", "Rand.cpp", "Rsa.h", "Rsa.cpp", "RsaStd.h", "RsaStd.cpp", "RsaCrt.h", "RsaCrt.cpp", "RsaCrtShamirsTrick.h", "RsaCrtShamirsTrick.cpp", "Utils.h", "Utils.cpp", "Tests.h", "Tests.cpp"]
cpp.commonCompilerFlags: ["-std=c++11"]
cpp.staticLibraries: ["gmp", "gmpxx"]
cout << "Usage: " << progName << " <command>" << endl;
cout << " <command> can be one of the following:" << endl;
cout << " * tests: Do some tests for RSA and RSA-CRT" << endl;
+ cout << " * tests-with-shamirs-trick: Do some tests for RSA-CRT with Shamir's trick" << endl;
cout << " * time-measures: Compute the ratio between RSA and RSA-CRT" << endl;
cout << " * attack: Simulate the Boneh-DeMillo-Lipton attack against RSA-CRT" << endl;
- cout << " * attack-fixed: [TODO]" << endl;
+ cout << " * attack-fixed: Try the attack with the Shamir's trick version" << endl;
}
int main(int argc, char** argv)
if (args.size() >= 2 && args[1] == "tests")
Tests(KEY_SIZE_BITS, RSA_PUBLIC_EXPONENT).runTests();
+ else if (args.size() >= 2 && args[1] == "tests-with-shamirs-trick")
+ Tests(KEY_SIZE_BITS, RSA_PUBLIC_EXPONENT).runTestsWithShamirsTrick();
else if (args.size() >= 2 && args[1] == "time-measures")
Tests(KEY_SIZE_BITS, RSA_PUBLIC_EXPONENT).runTimeMeasures();
else if (args.size() >= 2 && args[1] == "attack")
Tests(KEY_SIZE_BITS, RSA_PUBLIC_EXPONENT).doAttack();
+ else if (args.size() >= 2 && args[1] == "attack-fixed")
+ Tests(KEY_SIZE_BITS, RSA_PUBLIC_EXPONENT).doAttackFixed();
else
printUsage(args[0]);
projects / crypto_lab3.git / commitdiff