Implementation of Shamir's trick (working in progress).

[crypto_lab3.git] / src / RsaCrtShamirsTrick.cpp

diff --git a/src/RsaCrtShamirsTrick.cpp b/src/RsaCrtShamirsTrick.cpp
new file mode 100644 (file)
index 0000000..0e01e4b
--- /dev/null
+++ b/src/RsaCrtShamirsTrick.cpp
@@ -0,0 +1,66 @@
+#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;
+}