src/RsaCrtShamirsTrick.cpp

   1 #include "RsaCrtShamirsTrick.h"
   2
   3 using namespace std;
   4
   5 #include "Rand.h"
   6 #include "Utils.h"
   7
   8 pair<Rsa::KeyPub, RsaCrtShamirsTrick::KeyPriv> RsaCrtShamirsTrick::generateRSAKeys(uint exponent, uint keySizeBits)
   9 {
  10    mpz_class phi;
  11    Rsa::KeyPub kPub;
  12    KeyPriv kPriv;
  13
  14    do
  15    {
  16       kPub.e = exponent;
  17       kPriv.p = Rand::randPrime(keySizeBits / 2);
  18       kPriv.q = Rand::randPrime(keySizeBits / 2);
  19
  20       kPub.n = kPriv.p * kPriv.q;
  21       phi = (kPriv.p - 1) * (kPriv.q - 1);
  22
  23    // d = e^-1 (mode phi).
  24    } while (mpz_invert(kPriv.d.get_mpz_t(), kPub.e.get_mpz_t(), phi.get_mpz_t()) == 0);
  25
  26    // qInv = q^-1 (mod p)
  27    mpz_invert(kPriv.qInv.get_mpz_t(), kPriv.q.get_mpz_t(), kPriv.p.get_mpz_t());
  28
  29    return make_pair(kPub, kPriv);
  30 }
  31
  32 mpz_class RsaCrtShamirsTrick::sign(const mpz_class& m, const KeyPriv& kPriv)
  33 {
  34    return sign(m, kPriv, false);
  35 }
  36
  37 mpz_class RsaCrtShamirsTrick::signWithFaultySp(const mpz_class& m, const KeyPriv& kPriv)
  38 {
  39    return sign(m, kPriv, true);
  40 }
  41
  42 mpz_class RsaCrtShamirsTrick::sign(const mpz_class& m, const KeyPriv& kPriv, bool withError)
  43 {
  44    const mpz_class r = Rand::randPrime(64);
  45
  46    const mpz_class pr = kPriv.p * r;
  47    const mpz_class qr = kPriv.q * r;
  48
  49    const mpz_class spExponent = kPriv.d % ((kPriv.p - 1) * (r - 1)); // d mod phi(p * r).
  50    const mpz_class sqExponent = kPriv.d % ((kPriv.q - 1) * (r - 1)); // d mod phi(q * r).
  51
  52    mpz_class spr, sqr;
  53    mpz_powm(spr.get_mpz_t(), m.get_mpz_t(), spExponent.get_mpz_t(), pr.get_mpz_t()); // spr = m^exp mod p*r.
  54    mpz_powm(sqr.get_mpz_t(), m.get_mpz_t(), sqExponent.get_mpz_t(), qr.get_mpz_t()); // sqr = m^exp mod q*r.
  55
  56    if (withError)
  57       mpz_combit(spr.get_mpz_t(), 42); // Flip the fourty second bit.
  58
  59    if (spr % r != sqr % r)
  60       throw UnableToSignWithShamirsTrick();
  61
  62    mpz_class sp = spr % kPriv.p;
  63    mpz_class sq = sqr % kPriv.q;
  64
  65    return sq + ((kPriv.qInv * (sp - sq)) % kPriv.p) * kPriv.q;
  66 }