From: Ummon <greg.burri@gmail.com>
Date: Mon, 15 Dec 2014 22:59:55 +0000 (+0100)
Subject: First part: RSA CRT versus RSA std.
X-Git-Url: http://git.euphorik.ch/?p=crypto_lab3.git;a=commitdiff_plain;h=91989c2627abc2cdf511f17169e4f862dc55e838

First part: RSA CRT versus RSA std.
---

diff --git a/rapport/main.tex b/rapport/main.tex
index 19a579f..b9ab258 100644
--- a/rapport/main.tex
+++ b/rapport/main.tex
@@ -34,6 +34,7 @@
 \section{Conclusion}
 
 
+% http://en.wikipedia.org/wiki/RSA_%28cryptosystem%29
 %\bibliographystyle{plain}
 %\bibliography{main}
 
diff --git a/src/Rand.h b/src/Rand.h
index 2ee12a1..cfeb067 100644
--- a/src/Rand.h
+++ b/src/Rand.h
@@ -3,6 +3,9 @@
 
 #include <gmpxx.h>
 
+/**
+ * All random functions uses "/dev/urandom".
+ */
 class Rand
 {
 public:
diff --git a/src/Rsa.cpp b/src/Rsa.cpp
index be21998..23db34c 100644
--- a/src/Rsa.cpp
+++ b/src/Rsa.cpp
@@ -1,47 +1,11 @@
 #include "Rsa.h"
 
+#include <iostream>
 using namespace std;
 
-#include "Rand.h"
-#include "Utils.h"
-
-pair<Rsa::KeyPub, Rsa::KeyPriv> Rsa::generateRSAKeys(uint exponent, uint keySizeBits)
-{
-   mpz_class p, q, phi;
-   KeyPub kPub;
-   KeyPriv kPriv;
-
-   do
-   {
-      kPub.e = exponent;
-      p = Rand::randPrime(keySizeBits / 2);
-      q = Rand::randPrime(keySizeBits / 2);
-
-      kPriv.n = kPub.n = p * q;
-      phi = (p - 1) * (q - 1);
-
-   } while (mpz_invert(kPriv.d.get_mpz_t(), kPub.e.get_mpz_t(), phi.get_mpz_t()) == 0);
-
-// For debugging purpose.
-//   print("p", p);
-//   print("q", q);
-//   print("n", kPub.n);
-//   print("phi", phi);
-//   print("d", kPriv.d);
-
-   return make_pair(kPub, kPriv);
-}
-
-mpz_class Rsa::sign(const mpz_class& m, const KeyPriv& kPriv)
-{
-   mpz_class result;
-   mpz_powm_sec(result.get_mpz_t(), m.get_mpz_t(), kPriv.d.get_mpz_t(), kPriv.n.get_mpz_t());
-   return result;
-}
-
 bool Rsa::verifySignature(const mpz_class& m, const mpz_class& sig, const KeyPub& kPub)
 {
-   mpz_class mPrime;
-   mpz_powm_sec(mPrime.get_mpz_t(), sig.get_mpz_t(), kPub.e.get_mpz_t(), kPub.n.get_mpz_t());
-   return m == mPrime;
+   mpz_class m2;
+   mpz_powm_sec(m2.get_mpz_t(), sig.get_mpz_t(), kPub.e.get_mpz_t(), kPub.n.get_mpz_t());
+   return m == m2;
 }
diff --git a/src/Rsa.h b/src/Rsa.h
index cbc3676..85b61bc 100644
--- a/src/Rsa.h
+++ b/src/Rsa.h
@@ -1,26 +1,16 @@
 #ifndef RSA_H
 #define RSA_H
 
-#include <utility>
 #include <gmpxx.h>
 
 class Rsa
 {
 public:
    struct KeyPub {
-      mpz_class n;
-      mpz_class e;
+      mpz_class n; // Modulus.
+      mpz_class e; // Exponent.
    };
 
-   struct KeyPriv {
-      mpz_class n;
-      mpz_class d;
-   };
-
-   static std::pair<KeyPub, KeyPriv> generateRSAKeys(uint exponent, uint keySizeBits);
-
-   static mpz_class sign(const mpz_class& m, const KeyPriv& kPriv);
-
    static bool verifySignature(const mpz_class& m, const mpz_class& sig, const KeyPub& kPub);
 };
 
diff --git a/src/RsaCrt.cpp b/src/RsaCrt.cpp
index 43f0b97..9e2c3c9 100644
--- a/src/RsaCrt.cpp
+++ b/src/RsaCrt.cpp
@@ -1 +1,41 @@
 #include "RsaCrt.h"
+
+using namespace std;
+
+#include "Rand.h"
+#include "Utils.h"
+
+pair<Rsa::KeyPub, RsaCrt::KeyPriv> RsaCrt::generateRSAKeys(uint exponent, uint keySizeBits)
+{
+   mpz_class phi;
+   Rsa::KeyPub kPub;
+   KeyPriv kPriv;
+
+   do
+   {
+      kPub.e = kPriv.e = exponent;
+      kPriv.p = Rand::randPrime(keySizeBits / 2);
+      kPriv.q = Rand::randPrime(keySizeBits / 2);
+
+      kPriv.n = kPub.n = kPriv.p * kPriv.q;
+      phi = (kPriv.p - 1) * (kPriv.q - 1);
+
+   } while (mpz_invert(kPriv.d.get_mpz_t(), kPub.e.get_mpz_t(), phi.get_mpz_t()) == 0);
+
+   kPriv.dp = kPriv.d % (kPriv.p - 1);
+   kPriv.dq = kPriv.d % (kPriv.q - 1);
+
+   mpz_invert(kPriv.qInv.get_mpz_t(), kPriv.q.get_mpz_t(), kPriv.p.get_mpz_t());
+
+   return make_pair(kPub, kPriv);
+}
+
+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;
+}
diff --git a/src/RsaCrt.h b/src/RsaCrt.h
index 29bc4b9..87f9a11 100644
--- a/src/RsaCrt.h
+++ b/src/RsaCrt.h
@@ -1,20 +1,30 @@
 #ifndef RSACRT_H
 #define RSACRT_H
 
+#include <utility>
+
 #include <gmpxx.h>
 
+#include "Rsa.h"
+
 class RsaCrt
 {
 public:
-   RsaCrt();
+   struct KeyPriv {
+      mpz_class n; // Modulus.
+      uint e; // Exponent.
 
-   struct KeyPrivCRT {
       mpz_class p;
       mpz_class q;
       mpz_class dp;
       mpz_class dq;
       mpz_class qInv;
+      mpz_class d;
    };
+
+   static std::pair<Rsa::KeyPub, KeyPriv> generateRSAKeys(uint exponent, uint keySizeBits);
+
+   static mpz_class sign(const mpz_class& m, const KeyPriv& kPriv);
 };
 
 #endif
diff --git a/src/RsaStd.cpp b/src/RsaStd.cpp
new file mode 100644
index 0000000..17c2345
--- /dev/null
+++ b/src/RsaStd.cpp
@@ -0,0 +1,40 @@
+#include "RsaStd.h"
+
+using namespace std;
+
+#include "Rand.h"
+#include "Utils.h"
+
+pair<Rsa::KeyPub, RsaStd::KeyPriv> RsaStd::generateRSAKeys(uint exponent, uint keySizeBits)
+{
+   mpz_class p, q, phi;
+   Rsa::KeyPub kPub;
+   KeyPriv kPriv;
+
+   do
+   {
+      kPub.e = exponent;
+      p = Rand::randPrime(keySizeBits / 2);
+      q = Rand::randPrime(keySizeBits / 2);
+
+      kPriv.n = kPub.n = p * q;
+      phi = (p - 1) * (q - 1);
+
+   } while (mpz_invert(kPriv.d.get_mpz_t(), kPub.e.get_mpz_t(), phi.get_mpz_t()) == 0); // If 'd' is not invertible we try another primes.
+
+// For debugging purpose.
+//   Utils::print("p", p);
+//   Utils::print("q", q);
+//   Utils::print("n", kPub.n);
+//   Utils::print("phi", phi);
+//   Utils::print("d", kPriv.d);
+
+   return make_pair(kPub, kPriv);
+}
+
+mpz_class RsaStd::sign(const mpz_class& m, const KeyPriv& kPriv)
+{
+   mpz_class result;
+   mpz_powm_sec(result.get_mpz_t(), m.get_mpz_t(), kPriv.d.get_mpz_t(), kPriv.n.get_mpz_t());
+   return result;
+}
diff --git a/src/RsaStd.h b/src/RsaStd.h
new file mode 100644
index 0000000..ea348bf
--- /dev/null
+++ b/src/RsaStd.h
@@ -0,0 +1,22 @@
+#ifndef RSASTD_H
+#define RSASTD_H
+
+#include <utility>
+#include <gmpxx.h>
+
+#include "Rsa.h"
+
+class RsaStd
+{
+public:
+   struct KeyPriv {
+      mpz_class n;
+      mpz_class d;
+   };
+
+   static std::pair<Rsa::KeyPub, KeyPriv> generateRSAKeys(uint exponent, uint keySizeBits);
+
+   static mpz_class sign(const mpz_class& m, const KeyPriv& kPriv);
+};
+
+#endif
diff --git a/src/Utils.cpp b/src/Utils.cpp
index b60be50..0bae372 100644
--- a/src/Utils.cpp
+++ b/src/Utils.cpp
@@ -17,6 +17,11 @@ int Timer::ms() const
    return chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - this->time).count();
 }
 
+void Timer::reset()
+{
+   this->time = chrono::high_resolution_clock::now();
+}
+
 ostream& operator<<(ostream& os, const Timer& t)
 {
    os << t.ms() << " ms";
diff --git a/src/Utils.h b/src/Utils.h
index d765da0..3507763 100644
--- a/src/Utils.h
+++ b/src/Utils.h
@@ -18,6 +18,7 @@ class Timer
 public:
    Timer();
    int ms() const;
+   void reset();
    friend std::ostream& operator<<(std::ostream& os, const Timer& t);
 
 private:
diff --git a/src/lab3.qbs b/src/lab3.qbs
index 2117c09..47e20ae 100644
--- a/src/lab3.qbs
+++ b/src/lab3.qbs
@@ -4,9 +4,9 @@ Product {
    name: "lab3"
    type: "application"
 
-   files: ["main.cpp", "Rand.h", "Rand.cpp", "Rsa.h", "Rsa.cpp", "RsaCrt.h", "RsaCrt.cpp", "Utils.h", "Utils.cpp"]
+   files: ["main.cpp", "Rand.h", "Rand.cpp", "Rsa.h", "Rsa.cpp", "RsaStd.h", "RsaStd.cpp", "RsaCrt.h", "RsaCrt.cpp", "Utils.h", "Utils.cpp"]
 
-   cpp.commonCompilerFlags: ["-std=c++11"]
+   cpp.commonCompilerFlags: ["-std=c++14"]
    cpp.staticLibraries: ["gmp", "gmpxx"]
 
    Properties {
diff --git a/src/main.cpp b/src/main.cpp
index ac75df1..9324bfc 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -11,30 +11,91 @@ using namespace std;
 
 #include <gmpxx.h>
 
+#include "Utils.h"
+#include "Rand.h"
 #include "Rsa.h"
+#include "RsaStd.h"
 #include "RsaCrt.h"
 
 const uint KEY_SIZE_BITS = 1024;
 const uint RSA_PUBLIC_EXPONENT = 65537;
 
+bool testRsaStandard()
+{
+   const auto& keys = RsaStd::generateRSAKeys(RSA_PUBLIC_EXPONENT, KEY_SIZE_BITS);
+   const auto& kPub = keys.first;
+   const auto& kPriv = keys.second;
+
+   mpz_class message = Rand::randSize(KEY_SIZE_BITS / 2);
+   mpz_class signature = RsaStd::sign(message, kPriv);
+
+   return Rsa::verifySignature(message, signature, kPub) && !Rsa::verifySignature(message + 1, signature, kPub);
+}
+
+bool testRsaCrt()
+{
+   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(KEY_SIZE_BITS / 2);
+   mpz_class signature = RsaCrt::sign(message, kPriv);
+
+   return Rsa::verifySignature(message, signature, kPub) && !Rsa::verifySignature(message + 1, signature, kPub);
+}
+
+int timeSignRsaStd(int N)
+{
+   Timer timer;
+   const auto& keys = RsaStd::generateRSAKeys(RSA_PUBLIC_EXPONENT, KEY_SIZE_BITS);
+
+   for (int i = 0; i < N; i++)
+   {
+      mpz_class message = Rand::randSize(KEY_SIZE_BITS / 2);
+      RsaStd::sign(message, keys.second);
+   }
+
+   return timer.ms();
+}
+
+int timeSignRsaCRT(int N)
+{
+   Timer timer;
+   const auto& keys = RsaCrt::generateRSAKeys(RSA_PUBLIC_EXPONENT, KEY_SIZE_BITS);
+
+   for (int i = 0; i < N; i++)
+   {
+      mpz_class message = Rand::randSize(KEY_SIZE_BITS / 2);
+      RsaCrt::sign(message, keys.second);
+   }
+
+   return timer.ms();
+}
+
+void measuresRsaDurations()
+{
+   const int N = 10000;
+   int timeRsaStd = timeSignRsaStd(N);
+   int timeRsaCRT = timeSignRsaCRT(N);
+
+   cout << N << " x RSA standard: " << timeRsaStd << " ms" << endl;
+   cout << N << " x RSA CRT: " << timeRsaCRT << " ms" << endl;
+   cout << "Speedup: " << (double(timeRsaStd) / double(timeRsaCRT)) << endl;
+}
+
 int main(int argc, char** argv)
 {
    vector<string> args;
    for (int i = 0; i < argc; i++)
       args.push_back(string(argv[i]));
 
-   const auto& keys = Rsa::generateRSAKeys(RSA_PUBLIC_EXPONENT, KEY_SIZE_BITS);
-   const auto& kPub = keys.first;
-   const auto& kPriv = keys.second;
-
-   mpz_class message(42);
-   mpz_class signature = Rsa::sign(message, kPriv);
+   if (!testRsaStandard())
+      cout << "RSA standard failed!" << endl;
 
-   mpz_class message2(42);
-   cout << "verify: " << Rsa::verifySignature(message2, signature, kPub) << endl;
+   if (!testRsaCrt())
+      cout << "RSA CRT failed!" << endl;
 
-   mpz_class message3(43);
-   cout << "verify: " << Rsa::verifySignature(message3, signature, kPub) << endl;
+   measuresRsaDurations();
 
    return 0;
 }