selgamal.cpp

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

  // we can take its address below
  byte msglen = (byte)data.getDataLen();
  xassert(data.getDataLen() <= 0xFF);

  // length of random bytes and real message bytes = maxlen
  int maxlen = maxInputSize();
  xassert(msglen <= maxlen);

  // TODO: I fear that we are exposing internal state bits of our
  // RNG here.  I think we should be hashing the output of the RNG,
  // rather than using it directly.  Ideally, we can make a new
  // RNG that always does that.

  // message (M) format:
  //   [ 0 ][ random bytes ][ message ][ 1-byte message length ]
  // the leading 0 ensures M will be less than p, and the random
  // bytes prevent small messages from weakening the crypto strength
  DataBlock message =
    concat( DataBlock("\0", 1),
    concat( randomDataBlock(rng, maxlen - data.getDataLen()),
    concat( data,
            DataBlock(&msglen, 1)  )));
  Integer M = dataBlock2Integer(message);

  // encrypt M
  Integer a, b;
  ElGamal_encrypt(
    a, b,   // output ciphertext
    p, g,   // parameters
    y,      // public key
    M,      // message < p
    rng);   // for choosing k

  // ciphertext format:
  //   [ a ][ b ]  (each is length p.ByteCount())
  int modulusLen = sizeAsDataBlock(p);
  data = concat(integer2DataBlock(a, modulusLen),
                integer2DataBlock(b, modulusLen));
}


// ------------------- ElGamalPrivateKey -----------------------------
ElGamalPrivateKey::ElGamalPrivateKey(ElGamalPrivateKey const &obj)
  : ElGamalPublicKey(obj), x(obj.x)
{}

ElGamalPrivateKey::ElGamalPrivateKey(
  Integer const &P, Integer const &G,
  Integer const &Y, Integer const &X)
  : ElGamalPublicKey(P, G, Y), x(X)
{}

ElGamalPrivateKey::ElGamalPrivateKey(
  ElGamalPublicKey const &pubkey, Integer const &X)
  : ElGamalPublicKey(pubkey), x(X)
{}

ElGamalPrivateKey::ElGamalPrivateKey(
  ElGamalParameters const &params,
  RandomNumberGenerator &rng)
  : ElGamalPublicKey(params, Integer(1) /*y*/)
{
  ElGamal_keygen(
    x, y,         // output keys
    p, g,         // parameters
    rng);         // randomness
}


ElGamalPrivateKey::~ElGamalPrivateKey()
{}


void ElGamalPrivateKey::encode(DataBlock &stream) const
{
  // format:
  //   [ encoded x ][ encoded public key ]
  appendInteger(stream, x);
  ElGamalPublicKey::encode(stream);
}

ElGamalPrivateKey::ElGamalPrivateKey(DataBlock &stream)
  : ElGamalPublicKey(stream)
{
  x = removeInteger(stream);
}


// --------------------- ElGamalDecryptor --------------------------
ElGamalDecryptor::ElGamalDecryptor(
  Integer const &P, Integer const &G,
  Integer const &Y, Integer const &X)
  : ElGamalPrivateKey(P, G, Y, X)
{}

ElGamalDecryptor::ElGamalDecryptor(ElGamalPrivateKey const &privkey)
  : ElGamalPrivateKey(privkey)
{}

ElGamalDecryptor::~ElGamalDecryptor()
{}


ElGamalDecryptor::ElGamalDecryptor(DataBlock &stream)
  : ElGamalPrivateKey(stream)
{}


int ElGamalDecryptor::minInputSize() const
{
  // ciphertext is always twice as big as p
  return sizeAsDataBlock(p) * 2;
}

int ElGamalDecryptor::maxInputSize() const
{
  return minInputSize();
}


int ElGamalDecryptor::minOutputSize(int /*inputSize*/) const
{
  return 0;
}

int ElGamalDecryptor::maxOutputSize(int /*inputSize*/) const
{
  // max plaintext leaves a byte for the length and another for M < p
  return sizeAsDataBlock(p) - 2;
}


void ElGamalDecryptor::trans(DataBlock &data)
{
  // refer to ElGamalEncryptor::trans for formats

  // decode ciphertext
  int modulusLen = sizeAsDataBlock(p);
  Integer a = dataBlock2Integer(Left(modulusLen, data));
  Integer b = dataBlock2Integer(Right(modulusLen, data));

  // decrypt
  Integer M;
  ElGamal_decrypt(
    M,      // output plaintext
    p, g,   // parameters
    x,      // private key
    a, b);  // ciphertext

  // decode plaintext
  DataBlock text = integer2DataBlock(M);
  byte msglen = text.getDataC()[ text.getDataLen() - 1 ];
  data.setFromBlock(text.getDataC()          // plaintext bytes
                     + text.getDataLen()-1   // one past last message byte
                     - msglen,               // first message byte
                    msglen);                 // length of message
}


// ======================= test code ================================
#ifdef TEST_SELGAMAL

#include "rng.h"       // LC_RNG
#include <string.h>    // strlen
#include <ctype.h>     // isprint

// use a simple, insecure generator for testing
LC_RNG rng(1);


bool objectInterfaceTest(char const * const params_array[2])
{
  ElGamalParameters params(params_array);

  // create a private key at random
  ElGamalPrivateKey privKey(params, rng);

  // store public and private keys in intermediate
  // structures, to test what will be saving and
  // loading from disk
  DataBlock pubKeyBlock;
  privKey.ElGamalPublicKey::encode(pubKeyBlock);

  DataBlock privKeyBlock;
  privKey.encode(privKeyBlock);

  // create encryptor and decryptor objects from the
  // "saved" keys
  ElGamalEncryptor enc(pubKeyBlock, rng);
  ElGamalDecryptor dec(privKeyBlock);

  // test that the composition is identity
  TransPair pair(enc, dec);
  return pair.test(2 /*iters*/, false /*echo*/);
}


inline bool IsPrime(Integer const &v)
  { return probablyPrime(v, 10 /*iters*/); }

bool testWithParams(char const * const params[2])
{
  bool ok = true;

  // get system parameters
  Integer const p(params[0], 10);
  Integer const g(params[1], 10);

  // make up a private key
  Integer x, y;
  {
    TimedSection ts("keygen");
    ElGamal_keygen(x, y, p, g, rng);
  }

  // see what we've got
  //PVAL(p);
  //PVAL(g);
  PVAL(x);
  PVAL(y);

  // verify properties
  {
    TimedSection ts("parameter verification");
    PVAL(IsPrime(p));
    PVAL(g < p);
    PVAL(x < p);
    PVAL(y == a_exp_b_mod_c(g, x, p));
  }

  // message to encrypt
  byte const *message = (byte const*)"Microsoft sucks!";
  DataBlock block(message, strlen((char const*)message)+1);    // include null terminator
  Integer const M(dataBlock2Integer(block));

  // encrypt
  Integer a, b;    // ciphertext
  {
    TimedSection ts("encryption");
    ElGamal_encrypt(
      a, b,          // output
      p, g,          // system parameters
      y,             // public key
      M,             // message
      rng);          // random generator
  }

  // print ciphertext
  PVAL(a);
  PVAL(b);

  // decrypt
  Integer M2;      // decrypted plaintext
  {
    TimedSection ts("decryption");
    ElGamal_decrypt(
      M2,            // output
      p, g,          // system parameters
      x,             // private key
      a, b);         // ciphertext
  }

  PVAL(M == M2);
  ok = (M == M2) && ok;

  // print as text
  DataBlock block2(integer2DataBlock(M2));
  block2.print("decrypted message");

  // decrypt wrongly
  {
    TimedSection ts("wrong decryption");
    ElGamal_decrypt(
      M2,            // output
      p, g,          // system parameters
      x+1,           // wrong private key
      a, b);         // ciphertext
  }

  cout << "should not match: ";
  PVAL(M == M2);
  ok = (M != M2) && ok;

  return ok;
}


void doit()
{
  bool ok = true;

  ok = objectInterfaceTest(ElGamal_512bit_parameters) && ok;

  //ok = testWithParams(ElGamal_512bit_parameters) && ok;
  //ok = testWithParams(ElGamal_1024bit_parameters) && ok;
  //ok = testWithParams(ElGamal_1536bit_parameters) && ok;
  //ok = testWithParams(ElGamal_2048bit_parameters) && ok;

  if (ok) {
    cout << "all tests succeeded\n";
  }
  else {
    cout << "at least one test failed\n";
  }
}


int main()
{
  try {
    doit();
    return 0;
  }
  catch (xBase &x) {
    cout << "exception caught: " << x << endl;
    return 4;
  }
}

#endif // TEST_SELGAMAL