selgamal.cpp

伯克利做的SFTP安全文件传输协议

// selgamal.cc
// code for selgamal.h
// copyright SafeTP Development Group, Inc., 2000  Terms of use are as specified in license.txt

#include "selgamal.h"    // this module
#include "intutils.h"    // Integer, pickRandom
//#include "nbtheory.h"    // GCD (greatest common divisor)
#include "test.h"        // PVAL, TimedSection
#include "blokutil.h"    // {append,remove}Integer

#ifdef TEST_SELGAMAL
#  define DBG(  statement  ) statement
#else
#  define DBG(  statement  )
#endif

// --------------- hardcoded parameters ---------------------
// source: crypto++ 2.3, elgc512.dat
char const * const ElGamal_512bit_parameters[2] = {
  // p
  "119605128756320434943132008814524424060407620407400077853"
  "365103860003144936083867596027849971422189322492613650551460"
  "99647666757625666309250762353905741099",

  // g
  "3"
};                  


// source: crypto++ 2.3, elgc1024.dat
char const * const ElGamal_1024bit_parameters[2] = {
  // p
  "977496005396127371201341391090092761640271488881409055621"
  "132027288257703780410210473664722216602894204243755681817730"
  "453894809954057070210833618246095439526659074444285624321368"
  "565818175292368240778206556989788187012633524306612863048862"
  "261666401261382729561498217556940982965752134846737154470842"
  "06451288983",

  // g
  "2"
};


// source: Dan ran crypto++'s ElGamal parameter-generation process and
//         came up with these.  As a result, there is no easy way to
//         obtain the generating S and C...
char const * const ElGamal_1536bit_parameters[2] = {
  // p
  "142618907245886271279213602676359488049896630496857616"
  "794050092453543558817473977614067511177866789362588799706061"
  "531732404986822418118835593617527940161881354516511525122608"
  "731009643783413746761566159237020633313909432914608993695210"
  "824435819663719680859209032927538354827854508771895668378328"
  "358299960582102881193281380825488276517010382627590988370209"
  "595449467999338818817811436981425466110683855772567627502111"
  "0225440404436276758964952442164535720294212256759",

  // g
  "2"
};


// source: crypto++ 2.3, elgc2048.dat
char const * const ElGamal_2048bit_parameters[2] = {
  // p
  "205544021376723787805675029599271747699247034561572833450"
  "103059152527377261276254251091115239266847842467594552228166"
  "559391210735044770323943036112220870379439779345143884040433"
  "232087586943628325469720597007749668714948120540444631819798"
  "233042034716545572566752417222126838697084032284117601150870"
  "208146136069930444111439858502280670966562728991542346834576"
  "595909616618051766137511466323858166659411263563941078605293"
  "409134067236548944793943923432524157085473555110652782496771"
  "669101202164445067425911813434809908136744115698878944008780"
  "190972447186437751649112886009750445434305724443157680942824"
  "41072839637417646323",

  // g
  "3"
};


// -------------- functional interface ------------------
void ElGamal_encrypt(
  // output ciphertext
  Integer &a,                     // g^k mod p
  Integer &b,                     // (y^k)*M mod p

  // system parameters
  Integer const &p,               // prime number
  Integer const &g,               // g < p

  // public key
  Integer const &y,               // y = g^x mod p

  // per-message info
  Integer const &message,         // message < p
  RandomNumberGenerator &rng)     // for choosing k
{
  // test that the message isn't too long; it is caller's responsibility
  // to pad the message with random bits, and encode the actual length,
  // as necessary
  xassert(message < p);

  // choose k, which is less than p and relatively prime to p-1
  Integer k;
  do {
    k = pickRandom(rng, 3 /*min*/, p-2 /*max*/);
  } while (gcd(k, p-1) != 1);
  //PVAL(k);

  // encrypt
  a = a_exp_b_mod_c(g, k, p);
  b = (a_exp_b_mod_c(y, k, p) * message) % p;

// same code, but with some extra instrumentation
#if 0
  Integer k;
  {
    do {
      k.Randomize(rng, 3 /*min*/, p-2 /*max*/);
      DBG(  iters++;                )
      DBG(  if (iters % 10 == 0) {  )
      DBG(    cout << ".";          )
      DBG(  }                       )
    } while (GCD(k, p-1) != 1);
    DBG(  cout << "took " << iters << " iters to choose k\n";  )
    DBG(  PVAL(k);                                             )
  }

  // encrypt
  {
    TimedSection ts("compute a");
    a = a_exp_b_mod_c(g, k, p);
  }
  {
    TimedSection ts("compute b");
    b = (a_exp_b_mod_c(y, k, p) * message) % p;
  }
#endif // 0
}


void ElGamal_decrypt(
  // output plaintext
  Integer &message,               // message < p

  // system parameters
  Integer const &p,               // prime number
  Integer const &/*g*/,           // g < p (not used during decryption)

  // private key
  Integer const &x,               // x < p

  // per-message info
  Integer const &a,               // g^k mod p
  Integer const &b)               // (y^k)*M mod p
{
  // decrypt
  message = ((a_exp_b_mod_c(a, x, p).inverseMod(p)) * b) % p;
    // this is written in Schneier as b/(a^x) mod p
}


void ElGamal_keygen(
  // output keys
  Integer &x,          // private key: x < p
  Integer &y,          // public key:  y = g^x mod p

  // parameters
  Integer const &p, Integer const &g,

  // random generator; must be cryptographically strong!
  RandomNumberGenerator &rng)
{
  // randomly choose the private key
  x = pickRandom(rng, 2 /*min*/, p-2 /*max*/);

  // compute public key
  y = a_exp_b_mod_c(g, x, p);
}


// ================= object interface =======================
// ---------------- ElGamalParameters -----------------------
ElGamalParameters::ElGamalParameters(ElGamalParameters const &obj)
  : p(obj.p), g(obj.g)
{}

ElGamalParameters::~ElGamalParameters()
{}


ElGamalParameters::ElGamalParameters(Integer const &P, Integer const &G)
  : p(P), g(G)
{}


ElGamalParameters::ElGamalParameters(char const * const *params)
  : p(params[0], 10), g(params[1], 10)
{}


void ElGamalParameters::encode(DataBlock &stream) const
{
  // format:
  //   [ encoded p ][ encoded g]
  appendInteger(stream, p);
  appendInteger(stream, g);
}

ElGamalParameters::ElGamalParameters(DataBlock &stream)
{
  g = removeInteger(stream);
  p = removeInteger(stream);
}


// -------------------- ElGamalPublicKey -------------------------
ElGamalPublicKey::ElGamalPublicKey(ElGamalPublicKey const &obj)
  : ElGamalParameters(obj), y(obj.y)
{}

ElGamalPublicKey::~ElGamalPublicKey()
{}


ElGamalPublicKey::ElGamalPublicKey(
  Integer const &P, Integer const &G, Integer const &Y)
  : ElGamalParameters(P, G), y(Y)
{}

ElGamalPublicKey::ElGamalPublicKey(
  ElGamalParameters const &params, Integer const &Y)
  : ElGamalParameters(params), y(Y)
{}


void ElGamalPublicKey::encode(DataBlock &stream) const
{
  // format:
  //   [ encoded y ][ encoded parameters ]
  appendInteger(stream, y);
  ElGamalParameters::encode(stream);
}

ElGamalPublicKey::ElGamalPublicKey(DataBlock &stream)
  : ElGamalParameters(stream)
{
  y = removeInteger(stream);
}


// -------------------- ElGamalEncryptor -------------------------
ElGamalEncryptor::ElGamalEncryptor(
  Integer const &P, Integer const &G, Integer const &Y,
  RandomNumberGenerator &Rng)
  : ElGamalPublicKey(P, G, Y), rng(Rng)
{
  selfCheck();
}

ElGamalEncryptor::ElGamalEncryptor(
  ElGamalPublicKey const &key, RandomNumberGenerator &Rng)
  : ElGamalPublicKey(key), rng(Rng)
{
  selfCheck();
}


ElGamalEncryptor::ElGamalEncryptor(
  DataBlock &stream, RandomNumberGenerator &Rng)
  : ElGamalPublicKey(stream), rng(Rng)
{
  selfCheck();
}

ElGamalEncryptor::~ElGamalEncryptor()
{}


void ElGamalEncryptor::selfCheck()
{
  // Because we use just one byte in the message to encode the length,
  // we cannot encode messages larger than 255 characters, no matter
  // what the modulus length is.  However, this is not a problem, because
  // the largest modulus anyone is likely to use is 2048, which itself
  // imposes a 256-byte limit.
  xassert(maxInputSize() <= 0xFF);
}


int ElGamalEncryptor::minInputSize() const
{
  return 0;
}

int ElGamalEncryptor::maxInputSize() const
{
  // we lose one byte up front ensuring that M < p, and another at the
  // back to encode the message's actual length
  return sizeAsDataBlock(p) - 2;
}


int ElGamalEncryptor::minOutputSize(int /*inputSize*/) const
{
  // the ciphertext is always twice the size of the modulus
  return sizeAsDataBlock(p) * 2;
}

int ElGamalEncryptor::maxOutputSize(int inputSize) const
{
  // min and max sizes are the same
  return minOutputSize(inputSize);
}


// modelled on Wei Dai's elgamal.cc
void ElGamalEncryptor::trans(DataBlock &data)
{
  // compute message length, and store it in a 'byte' variable so