src/Tests.cpp

   1 #include "Tests.h"
   2
   3 #include <iostream>
   4 using namespace std;
   5
   6 #include <gmpxx.h>
   7
   8 #include "Rand.h"
   9 #include "RsaStd.h"
  10 #include "RsaCrt.h"
  11
  12 Tests::Tests(uint keySizeBits, uint rsaPublicExponent) :
  13    KEY_SIZE_BITS(keySizeBits),
  14    RSA_PUBLIC_EXPONENT(rsaPublicExponent)
  15 {
  16 }
  17
  18 void Tests::runTests()
  19 {
  20    if (this->rsaStandard())
  21       cout << "RSA standard OK" << endl;
  22    else
  23       cout << "RSA standard failed!" << endl;
  24
  25    if (this->rsaCrt())
  26       cout << "RSA CRT OK" << endl;
  27    else
  28       cout << "RSA CRT failed!" << endl;
  29 }
  30
  31 void Tests::runTimeMeasures()
  32 {
  33    const int N = 1000;
  34    const int nbKeys = 20; // Number of different generated key.
  35
  36    int timeRsaStd = 0;
  37    int timeRsaCRT = 0;
  38
  39    for (int k = 0; k < nbKeys; ++k)
  40    {
  41       timeRsaStd += timeSignRsaStd(N);
  42       timeRsaCRT += timeSignRsaCRT(N);
  43    }
  44
  45    cout << N * nbKeys << " x RSA standard: " << timeRsaStd << " ms" << endl;
  46    cout << N * nbKeys << " x RSA CRT: " << timeRsaCRT << " ms" << endl;
  47    cout << "Speedup: " << (double(timeRsaStd) / double(timeRsaCRT)) << endl;
  48 }
  49
  50 void Tests::doAttack()
  51 {
  52    const auto& keys = RsaCrt::generateRSAKeys(RSA_PUBLIC_EXPONENT, KEY_SIZE_BITS);
  53    const auto& kPub = keys.first;
  54    const auto& kPriv = keys.second;
  55    mpz_class message = Rand::randSize(128);
  56    mpz_class faultySignature = RsaCrt::signWithFaultySp(message, kPriv);
  57    mpz_class correctSignature = RsaCrt::sign(message, kPriv);
  58
  59    bool attackOK = true;
  60
  61    cout << "Original:" << endl;
  62    cout << " p = " << kPriv.p << endl;
  63    cout << " q = " << kPriv.q << endl;
  64
  65    // At this point the attacker doesn't know the private key but he has intercepted the message and the faulty signature.
  66    {
  67       mpz_class faultySignaturePowerE;
  68       mpz_pow_ui(faultySignaturePowerE.get_mpz_t(), faultySignature.get_mpz_t(), RSA_PUBLIC_EXPONENT);
  69       mpz_class messageMinuxFaultySignaturePowerE = message - faultySignaturePowerE;
  70       mpz_class q;
  71       mpz_gcd(q.get_mpz_t(), messageMinuxFaultySignaturePowerE.get_mpz_t(), kPub.n.get_mpz_t());
  72       mpz_class p = kPub.n / q;
  73
  74       cout << "Found with a faulty signature:" << endl;
  75       cout << " p = " << p << endl;
  76       cout << " q = " << q << endl;
  77
  78       attackOK = attackOK && kPriv.p == p && kPriv.q == q; // With p and q we can recreate the original private key.
  79    }
  80
  81    // Try the attack with a correct signature.
  82    {
  83       mpz_class correctSignaturePowerE;
  84       mpz_pow_ui(correctSignaturePowerE.get_mpz_t(), correctSignature.get_mpz_t(), RSA_PUBLIC_EXPONENT);
  85       mpz_class messageMinuxCorrectSignaturePowerE = message - correctSignaturePowerE;
  86       mpz_class q;
  87       mpz_gcd(q.get_mpz_t(), messageMinuxCorrectSignaturePowerE.get_mpz_t(), kPub.n.get_mpz_t());
  88       mpz_class p = kPub.n / q;
  89
  90       cout << "Found with a correct signature:" << endl;
  91       cout << " p = " << p << endl; // Equal to 1.
  92       cout << " q = " << q << endl; // Equal to n.
  93
  94       attackOK = attackOK && kPriv.p != p && kPriv.q != q;
  95    }
  96
  97    if (attackOK)
  98       cout << "Attack successful" << endl;
  99    else
 100       cout << "Attack failed" << endl;
 101 }
 102
 103 bool Tests::rsaStandard()
 104 {
 105    const auto& keys = RsaStd::generateRSAKeys(RSA_PUBLIC_EXPONENT, KEY_SIZE_BITS);
 106    const auto& kPub = keys.first;
 107    const auto& kPriv = keys.second;
 108
 109    {
 110       mpz_class message = kPriv.n;
 111       mpz_class signature = RsaStd::sign(message, kPriv);
 112       if (Rsa::verifySignature(message, signature, kPub)) // Must not be able to signe message greater than kPriv.n.
 113          return false;
 114    }
 115
 116    {
 117       mpz_class message = kPriv.n - 1;
 118       mpz_class signature = RsaStd::sign(message, kPriv);
 119       if (!Rsa::verifySignature(message, signature, kPub) || Rsa::verifySignature(message + 1, signature, kPub))
 120          return false;
 121    }
 122
 123    {
 124       mpz_class message = kPriv.n / 2;
 125       mpz_class signature = RsaStd::sign(message, kPriv);
 126       if (!Rsa::verifySignature(message, signature, kPub) || Rsa::verifySignature(message + 1, signature, kPub))
 127          return false;
 128    }
 129
 130    return true;
 131 }
 132
 133 bool Tests::rsaCrt()
 134 {
 135    const auto& keys = RsaCrt::generateRSAKeys(RSA_PUBLIC_EXPONENT, KEY_SIZE_BITS);
 136    const auto& kPub = keys.first;
 137    const auto& kPriv = keys.second;
 138
 139    {
 140       mpz_class message = kPub.n;
 141       mpz_class signature = RsaCrt::sign(message, kPriv);
 142       if (Rsa::verifySignature(message, signature, kPub)) // Must not be able to signe message greater than kPub.n.
 143          return false;
 144    }
 145
 146    {
 147       mpz_class message = kPub.n - 1;
 148       mpz_class signature = RsaCrt::sign(message, kPriv);
 149       if (!Rsa::verifySignature(message, signature, kPub) || Rsa::verifySignature(message + 1, signature, kPub))
 150          return false;
 151    }
 152
 153    {
 154       mpz_class message = kPub.n / 2;
 155       mpz_class signature = RsaCrt::sign(message, kPriv);
 156       if (!Rsa::verifySignature(message, signature, kPub) || Rsa::verifySignature(message + 1, signature, kPub))
 157          return false;
 158    }
 159
 160    return true;
 161 }
 162
 163 int Tests::timeSignRsaStd(int N)
 164 {
 165    Timer timer;
 166    const auto& keys = RsaStd::generateRSAKeys(RSA_PUBLIC_EXPONENT, KEY_SIZE_BITS);
 167
 168    mpz_class message = Rand::randSize(KEY_SIZE_BITS / 2);
 169    for (int i = 0; i < N; i++)
 170       RsaStd::sign(message, keys.second);
 171
 172    return timer.ms();
 173 }
 174
 175 int Tests::timeSignRsaCRT(int N)
 176 {
 177    Timer timer;
 178    const auto& keys = RsaCrt::generateRSAKeys(RSA_PUBLIC_EXPONENT, KEY_SIZE_BITS);
 179
 180    mpz_class message = Rand::randSize(KEY_SIZE_BITS / 2);
 181    for (int i = 0; i < N; i++)
 182       RsaCrt::sign(message, keys.second);
 183
 184    return timer.ms();
 185 }