tsint.cpp

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

// tsint.cc
// test an sint implementation
// copyright SafeTP Development Group, Inc., 2000  Terms of use are as specified in license.txt

#include "sint.h"       // interface to test
#include <iostream.h>   // cout, etc.
#include <stdlib.h>     // rand

#define PVAL(var) \
  cout << #var " = " << var << endl


// +, -, *, /, %
typedef int (*Small2Op)(int a, int b);

#define ARITHOP(op, name) \
  int name(int a, int b) { return a op b; }
ARITHOP(+, plus)
ARITHOP(-, minus)
ARITHOP(*, times)
ARITHOP(/, divide)
ARITHOP(%, mod)
#undef ARITHOP

typedef Integer (Integer::*Integer2Op)(Integer const &arg2) const;

struct Simple2Op {
  Small2Op smallOp;
  Integer2Op integerOp;
  char const *name;
};

static Simple2Op const simple2Ops[] = {
  { plus, &Integer::operator+, "+" },
  { minus, &Integer::operator-, "-" },
  { times, &Integer::operator*, "*" },
  { divide, &Integer::operator/, "/" },
  { mod, &Integer::operator%, "%" },
};

// returns 0 for ok
int testSmallIntOp(int arg1, int arg2, Simple2Op const &op)
{
  if (arg2 == 0 &&
      (op.smallOp == divide || op.smallOp == mod)) {
    // don't test division by 0
    return 0;
  }

  // compute correct result
  int correct = op.smallOp(arg1, arg2);

  // compute Integer result
  Integer intArg1(arg1);
  Integer intArg2(arg2);
  Integer intResult = (intArg1.*(op.integerOp))(arg2);

  // compare
  if (intResult != correct) {
    cout << "MISMATCH for " << op.name << ":\n";
    cout << "  as int: " << arg1 << " " << op.name
         << " " << arg2 << " = " << correct << endl;
    cout << "  as Integer: " << intArg1 << " " << op.name
         << " " << intArg2 << " = " << intResult << endl;
    return 1;
  }
  else {
    return 0;
  }
}


int randomInt(int top)
{
  return rand()%top;
}


// test arithmetic we can easily check
// returns # of errors
int smallIntTests()
{
  int errCt = 0;
  int const maxShort = 0x7fff;

  for (int i=0; i<100; i++) {
    // choose two random arguments small enough to ensure
    // the result will not overflow an 'int'

    int arg1 = randomInt(2*maxShort) - maxShort;
    int arg2 = randomInt(2*maxShort) - maxShort;

    for (int j=0; j<TABLESIZE(simple2Ops); j++) {
      errCt += testSmallIntOp(arg1, arg2, simple2Ops[j]);
    }
  }

  return errCt;
}


#if 0
typedef Integer (*IntFunc)(Integer const &arg1, Integer const &arg2,
                           Integer const &arg3);

struct FuncTest {
  IntFunc func;         // function to test
  char const *arg1;     // arguments..
  char const *arg2;
  char const *arg3;
  char const *result;   // expected result
};

FuncTest tests[] = {
  {

#endif // 0





struct GxpyTest {
  char const *g;  // base
  char const *x;  // exponent
  char const *p;  // modulus
  char const *y;  // expected g^x mod p
};

GxpyTest gxpyTests[] = {
  // a really small one
  {
    "2",   // g
    "4325425",   // x
    "1928657",   // p
    "447317"   // y
  },

  {
    "2",   // g
    "43254256442654",   // x
    "19286576364324",   // p
    "17272939509748"   // y
  },

  {
    "2",  // g
    "548948432849025",   // x
    "57899472189473",   // p
    "18644986069323"    // y
  },

  {
    "2",  // g
    "5489050948432849025",   // x
    "578924051789472189473",   // p
    "521179290064220127159"    // y
  },

  {
    "2",  // g
    "54890532848490210948432849025",   // x
    "5789247395389051789472189473",   // p
    "5317481790950600669453583956"    // y
  },

  // here's a smaller one I hope will still reveal the failure I'm
  // trying to track down
  {
    "2",  // g
    "548905328940328904328490210948432849025",   // x
    "578924739439055099065389051789472189473",   // p
    "486125552760568987057205453338446435881"    // y
  },

  // this is the big test..
  {
    "2",   // g
    // x:
    "39563373040557589371350852273858144327475138920318"
    "344860899660977339743162586334923039800008217242111"
    "257816070260550822158766999631179188059334733205868"
    "838582946794289203165146251986658756944574740704726"
    "456215049637616740384401985354145771798930433587364"
    "398448869792000267186031388262516111995763646171566"
    "167",
    // p:
    "97749600539612737120134139109009276164027148888140"
    "905562113202728825770378041021047366472221660289420"
    "424375568181773045389480995405707021083361824609543"
    "952665907444428562432136856581817529236824077820655"
    "698978818701263352430661286304886226166640126138272"
    "956149821755694098296575213484673715447084206451288"
    "983",
    // y:
    "47246592549183276087376250244263510504154502942745"
    "386047173756386254074223247337987446412782358107054"
    "855564144398512256664585175682678112808068074706517"
    "787494763578216165677956350521857529811736793983813"
    "027784439488336376469139328778349170113370927945390"
    "588291609282637210809293720197758682429154651702537"
    "604" },
};


// test a particular operation that's been causing linux sww to segfault
bool testGxpy()
{
  cout << "testing g^x mod p...\n";

  bool ok = true;

  for (int i=0; i<TABLESIZE(gxpyTests); i++) {
    Integer const g(gxpyTests[i].g, 10);
    Integer const x(gxpyTests[i].x, 10);
    Integer const p(gxpyTests[i].p, 10);
    Integer const y(gxpyTests[i].y, 10);

    cout << "computing g^x mod p, where\n"
            "  g = " << g << "\n"
            "  x = " << x << "\n"
            "  p = " << p << "\n";
    Integer result = g.expMod(x, p);
    cout << "result = " << result << endl;

    if (result != y) {
      cout << "ERROR: result failed to equal y:\n"
              "  y = " << y << "\n";
      ok = false;
      return ok;   // for now, don't show any more
    }
  }

  return ok;
}


class SimpleRand : public Integer::RandomSource {
public:
  virtual void getRandomBytes(byte *dest, int numBytes);
};

void SimpleRand::getRandomBytes(byte *dest, int numBytes)
{
  for (int i=0; i<numBytes; i++) {
    dest[i] = (byte)rand();
  }
}


void printSomeRandoms()
{
  cout << "printing some randoms...\n";

  SimpleRand src;
  char const *nums[] = {
    "1", "2", "10", "100", "1000", "1000000",
    "874135748654531", "7864894188795611681768789719413565"
  };
  for (int i=0; i<TABLESIZE(nums); i++) {
    cout << nums[i] << ": ";
    cout << random(src, Integer(nums[i], 10)) << endl;
  }
}


void testInverses()
{
  cout << "testing modular inverses...\n";

  static struct {
    char const *a;
    char const *modulus;
  } const arr[] = {
    { "3", "5" },
    { "5", "17" },
    { "51", "100" },
    { "53", "100" },
    { "1234886434615313", "48911894131684186486" },
  };

  for (int i=0; i<TABLESIZE(arr); i++) {
    Integer a(arr[i].a, 10);
    Integer m(arr[i].modulus, 10);

    Integer b = a.inverseMod(m);
    cout << "inverse of " << a << " mod " << m
         << " is " << b << endl;

    Integer one = (a*b) % m;
    if (one != 1) {
      cout << "WRONG!!  a*b % m is " << one << endl;
    }
  }
}


#define check(cond)                                                          \
  if (!(cond)) {                                                               \
    cout << "FAILED: " #cond ", line " << __LINE__ << ", file " __FILE__ "\n"; \
    errCt++;                                                                 \
  } else {                          \
    /*cout << "ok: " #cond "\n";*/  \
  }


int testBitOps()
{
  cout << "testing bitwise ops...\n";

  int errCt = 0;

  // numBits
  check(Integer(0).numBits() == 1);
  check(Integer(1).numBits() == 1);
  check(Integer(2).numBits() == 2);
  check(Integer(255).numBits() == 8);
  check(Integer(256).numBits() == 9);

  // leastSigByte
  check(Integer(0).leastSigByte() == 0);
  check(Integer(1).leastSigByte() == 1);
  check(Integer(2).leastSigByte() == 2);
  check(Integer(255).leastSigByte() == 255);
  check(Integer(256).leastSigByte() == 0);
  check(Integer(257).leastSigByte() == 1);
  check(Integer("123456789abcdef", 16).leastSigByte() == 0xef);

  // shifting ops
  static struct {
    char const *in;      // input, in hex
    char const *out;     // output
    int leftShiftAmt;    // negative for right shift
  } const arr[] = {
    { "4", "1", -2 },
    { "3", "0", -2 },
    { "5", "1", -2 },
    { "1", "4", 2 },
    { "4", "4", 0 },
    { "123456", "1234560", 4 },
    { "123456", "12345", -4 },
  };

  loopi(TABLESIZE(arr)) {
    Integer in(arr[i].in, 16);
    Integer out(arr[i].out, 16);
    int shamt = arr[i].leftShiftAmt;

    if (shamt >= 0) {     // left shift
      check((in << shamt) == out);
      in <<= shamt;
      check(in == out);
    }
    else {                // right shift
      shamt *= -1;
      check((in >> shamt) == out);
      in >>= shamt;
      check(in == out);
    }
  }

  return errCt;
}


int main()
{
  Integer a(5);
  Integer b(7);
  Integer c = a*b;

  PVAL(a);
  PVAL(b);
  PVAL(c);

  Integer big("12345678901234567890123456789012345678901234567890", 10);
  PVAL(big);

  int errCt = 0;

  //testGxpy();
  errCt += smallIntTests();

  printSomeRandoms();

  testInverses();

  errCt += testBitOps();

  if (errCt != 0) {
    cout << "tsint: " << errCt << " error(s)!\n";
  }
  else {
    cout << "tsint: success\n";
  }

  return 0;
}