sdsa.cpp

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

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

#include "sdsa.h"       // this module
#include "intutils.h"   // Integer, pickRandom
#include "test.h"       // PVAL, TimedSection
#include "ssha.h"       // SHA
#include "blokutil.h"   // {append,remove}Integer
#include <limits.h>     // INT_MAX
#include "security.h"   // xsecurity
#include "cryputil.h"   // Sha1
    

// versioning query
void knownDSAPublicKeyVersions(int &minimum, int &maximum)
{
  minimum = 1;
  maximum = CURRENT_KEY_VERSION;
}


// ================= hardcoded parameters =========================
// 512-bit DSA parameters
// source: crypto++ 2.3, dsa512.dat
char const * const DSA_512bit_parameters[3] = {
  // p
  "111069504852506684738965995531108649436427572104617740087"
  "010102382583967887464248112026431189693533601619506678772919"
  "35957547795677949604631005846095348727",

  // q
  "1016505658889014629900729618210002584918553821669",

  // g
  "937669537554082395912373116614058888326790768383028782879"
  "510193424544198913335030871248010586304857807601769996794739"
  "8476862891519953843058561832564670724"
};


// 1024-bit DSA parameters
// source: crypto++ 2.3, dsa1024.dat
char const * const DSA_1024bit_parameters[3] = {
  // p
  "171629036916192407361147247412175483450671498402446405223"
  "342604064452387805209164181295136779553127669451336481211712"
  "917750491598981405691054950293359650266312514414286663921893"
  "864577838305839983628863929138152663687521040045060496780614"
  "787770044292894669823416877055924792600628174937600765129051"
  "082207442941",

  // q
  "746033625008812031879812927329777431144614716731",

  // g
  "798202678537483113358766534194690096690685332380658047896"
  "340069711162620056883131332345178336960504579044367523866012"
  "598393547711784009310101304946046212829238038263655414010583"
  "864533379129406111831002000073623847642861180352452894005931"
  "928626555148449736469063236208052572078397705716414779937366"
  "47115377692"
};


// ==================== functional interface =====================

void DSA_sign(
  // output
  Integer &r, Integer &s,  // signature (two 160-bit values)

  // common parameters
  Integer const &p,        // 1024-bit prime number
  Integer const &q,        // 160-bit prime factor of p-1
  Integer const &g,        // g = h^((p-1)*q) mod p, where h is any
                           // number less than p-1 such that g > 1

  // private key
  Integer const &x,        // any number less than q

  // public key
  //Integer const &y,        // y = g^x mod p
  // (y can be computed from x, and isn't even used in the
  // computation below)

  // per-message input
  Integer const &digest,   // 160-bit SHA-1 of message to sign
  RandomNumberGenerator &rng)
{
  // compute random k < q (computation must be secure, and k must
  // remain secret, else private key will be compromised)
  // computes 2 <= k <= q-2
  Integer k = pickRandom(rng, 2 /*lo*/, q-2 /*hi*/);

  // compute signature
  r = a_exp_b_mod_c(g, k, p) % q;
  s = (k.inverseMod(q) * (digest + x*r)) % q;
}


bool DSA_verify(
  // common parameters
  Integer const &p,        // 1024-bit prime number
  Integer const &q,        // 160-bit prime factor of p-1
  Integer const &g,        // g = h^((p-1)*q) mod p, where h is any
                           // number less than p-1 such that g > 1

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

  // per-message input
  Integer const &r,        // signature
  Integer const &s,
  Integer const &digest)   // 160-bit SHA-1 of message to sign
{
  Integer w = s.inverseMod(q);

  Integer u1 = (digest * w) % q;

  Integer u2 = (r * w) % q;

  Integer v = ( (a_exp_b_mod_c(g, u1, p) *
                 a_exp_b_mod_c(y, u2, p)) % p)   % q;

  // I'm getting a report of some strange behavior from DSA validation
  #ifdef PRINT_DSA_PARAMS
    #define PNUM(n) "  " #n " = " << n << "\n"
    cout << "Verifying DSA signature:\n"
            PNUM(p)
            PNUM(q)
            PNUM(g)
            PNUM(y)
            PNUM(r)
            PNUM(s)
            PNUM(digest)
            PNUM(w)
            PNUM(u1)
            PNUM(u2)
            PNUM(v)
	    ;
    #undef PNUM
  #endif // DSA_PRINT_PARAMS

  // test
  return v == r;
}


void DSA_keygen(
  Integer &x, Integer &y,                // keys (x is private)
  Integer const &p, Integer const &q,
  Integer const &g,                      // parameters
  RandomNumberGenerator &rng)            // source of randomness
{
  // randomly choose the private key
  x = pickRandom(rng, 2 /*lo*/, q-2 /*hi*/);

  // compute public key
  y = a_exp_b_mod_c(g, x, p);
}
    
    
// ================== object interface ======================
// ---------------- DSAParameters -----------------------
DSAParameters::DSAParameters()
  : p((long)0), q((long)0), g((long)0)
{}

DSAParameters::DSAParameters(DSAParameters const &obj)
  : p(obj.p), q(obj.q), g(obj.g)
{}

DSAParameters::~DSAParameters()
{}


DSAParameters::DSAParameters(Integer const &P, Integer const &Q,
                             Integer const &G)
  : p(P), q(Q), g(G)
{}


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


DSAParameters& DSAParameters::operator=(DSAParameters const &obj)
{
  if (this != &obj) {
    p = obj.p;
    q = obj.q;
    g = obj.g;
  }
  return *this;
}


bool DSAParameters::operator==(DSAParameters const &obj) const
{
  return
    p == obj.p &&
    q == obj.q &&
    g == obj.g;
}


void DSAParameters::encode(DataBlock &stream) const
{
  // format:
  //   [ encoded p ][ encoded q ][ encoded g ]
  appendInteger(stream, p);
  appendInteger(stream, q);
  appendInteger(stream, g);
}
    
DSAParameters::DSAParameters(DataBlock &stream)
{
  g = removeInteger(stream);
  q = removeInteger(stream);
  p = removeInteger(stream);
}
    
    
// -------------------- DSAPublicKey -------------------------
DSAPublicKey::DSAPublicKey()
  : DSAParameters(), y((long)0)
{}

DSAPublicKey::DSAPublicKey(DSAPublicKey const &obj)
  : DSAParameters(obj), y(obj.y)
{}

DSAPublicKey::~DSAPublicKey()
{}


DSAPublicKey::DSAPublicKey(
  DSAParameters const &params, Integer const &Y)
  : DSAParameters(params), y(Y)
{}


DSAPublicKey& DSAPublicKey::operator=(DSAPublicKey const &obj)
{
  if (this != &obj) {
    DSAParameters::operator=(obj);
    y = obj.y;
  }
  return *this;
}


bool DSAPublicKey::operator==(DSAPublicKey const &obj) const
{
  return
    DSAParameters::operator==(obj) &&
    y == obj.y;
}


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

DSAPublicKey::DSAPublicKey(DataBlock &stream)
  : DSAParameters(stream)
{
  y = removeInteger(stream);
}


void DSAPublicKey::insertOstream(ostream &os) const
{
  os << "p: " << getP()
     << "\nq: " << getQ()
     << "\ng: " << getG()
     << "\ny: " << getY()
     << "\n";
}


// -------------------- DSASigner -------------------------
DSASigner::DSASigner(
  DSAPrivateKey const &key, RandomNumberGenerator &Rng)
  : DSAPrivateKey(key), rng(Rng)
{}
    
    
DSASigner::DSASigner(
  DataBlock &stream, RandomNumberGenerator &Rng)
  : DSAPrivateKey(stream), rng(Rng)
{}
    
DSASigner::~DSASigner()
{}
    
    
int DSASigner::minInputSize() const
{
  // at one point I had decided that signing small messages would
  // be a security weakness, but I now believe that's wrong
  return 0;
}

int DSASigner::maxInputSize() const
{
  // must leave room for signature
  return INT_MAX - DSA_SIGNATURE_LENGTH;
}


int DSASigner::minOutputSize(int inputSize) const
{
  return inputSize + DSA_SIGNATURE_LENGTH;
}

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

// compute the SHA of a message, return it as an Integer
// (will consider moving this into a general-purpose util
// module when a good one starts to coalesce)
static Integer intSha(DataBlock const &data)
{
  DataBlock digest(SHA::DIGESTSIZE);
  SHA sha;
  sha.CalculateDigest(digest.getData(), data.getDataC(), data.getDataLen());
  digest.setDataLen(SHA::DIGESTSIZE);
  return dataBlock2Integer(digest);
}


void DSASigner::sign(DataBlock const &data, DataBlock &signature)
{
  // hash the message
  Integer digest;
  {
    //TimedSection ts("sha (sign)");
    digest = intSha(data);
  }

  // compute a signature
  Integer r, s;
  {
    //TimedSection ts("sign");
    DSA_sign(
      r, s,              // signature
      p, q, g,           // parameters
      x,                 // private key
      digest, rng);      // per-message
  }

  //TimedSection ts("append sig");

  // append signature, format:
  //   [ r ][ s ]  (each q.ByteCount() bytes long)
  int modulusLen = sizeAsDataBlock(q);
  xassert(modulusLen*2 == DSA_SIGNATURE_LENGTH);
  appendBlock(signature, integer2DataBlock(r, modulusLen));
  appendBlock(signature, integer2DataBlock(s, modulusLen));
}


void DSASigner::trans(DataBlock &data)
{
  sign(data, data);
}


// ------------------- DSAPrivateKey -----------------------------
DSAPrivateKey::DSAPrivateKey(DSAPrivateKey const &obj)
  : DSAPublicKey(obj), x(obj.x)
{}

DSAPrivateKey::DSAPrivateKey(
  DSAPublicKey const &pubkey, Integer const &X)
  : DSAPublicKey(pubkey), x(X)
{}

DSAPrivateKey::DSAPrivateKey(
  DSAParameters const &params,
  RandomNumberGenerator &rng)
  : DSAPublicKey(params, Integer(1) /*y*/)
{
  DSA_keygen(
    x, y,         // output keys
    p, q, g,      // parameters
    rng);         // randomness
}


DSAPrivateKey::~DSAPrivateKey()
{}


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

DSAPrivateKey::DSAPrivateKey(DataBlock &stream)
  : DSAPublicKey(stream)
{
  x = removeInteger(stream);
}


// --------------------- DSAVerifier --------------------------
DSAVerifier::DSAVerifier(DSAPublicKey const &pubkey)
  : DSAPublicKey(pubkey)
{}

DSAVerifier::~DSAVerifier()
{}


DSAVerifier::DSAVerifier(DataBlock &stream)
  : DSAPublicKey(stream)
{}


int DSAVerifier::minInputSize() const
{
  // must be at least a signature to check
  return DSA_SIGNATURE_LENGTH;
}

int DSAVerifier::maxInputSize() const
{
  return INT_MAX;
}


int DSAVerifier::minOutputSize(int inputSize) const
{
  return inputSize - DSA_SIGNATURE_LENGTH;
}

int DSAVerifier::maxOutputSize(int inputSize) const
{
  return minOutputSize(inputSize);
}


void DSAVerifier::verify(DataBlock const &data, DataBlock &signature)
{
  // refer to DSASigner::sign for formats

  // decode signature
  Integer r, s;
  {
    //TimedSection ts("remove, decode sig");
    int modulusLen = sizeAsDataBlock(q);
    xassert(modulusLen*2 == DSA_SIGNATURE_LENGTH);
    s = dataBlock2Integer(removeBlock(signature, modulusLen));
    r = dataBlock2Integer(removeBlock(signature, modulusLen));
  }

  // compute SHA of message (without signature (if &data==&signature))
  Integer digest;   // g++ needed this separate anyway.. grr.
  {
    //TimedSection ts("sha (verify)");
    digest = intSha(data);
  }

  // verify signature
  bool ok;
  {
    //TimedSection ts("verify");
    ok = DSA_verify(
      p, q, g,         // parameters
      y,               // public key
      r, s,            // signature
      digest);         // message
  }