pgpelgkey.c

著名的加密软件的应用于电子邮件中

/*
 * pgpElGKey.c -- ElGamal encryption
 *
 * Copyright (C) 1996,1997 Pretty Good Privacy, Inc.  All rights reserved.
 *
 * $Id: pgpElGKey.c,v 1.9.2.3 1997/06/07 09:51:25 mhw Exp $
 */

/* Experiment with El Gamal signatures */
#undef ELGSIGS

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include "pgpDebug.h"
#include "pgpElGKey.h"
#include "pgpKeyMisc.h"
#include "bn.h"
#include "bnprime.h"
#include "pgpCFB.h"
#include "pgpCipher.h"
#include "pgpFixedKey.h"
#include "bngermain.h"
#include "pgpHash.h"
#include "pgpMem.h"
#include "pgpErr.h"
#include "bnprime.h"
#include "pgpPubKey.h"
#include "pgpRndom.h"
#include "pgpStr2Key.h"
#include "pgpUsuals.h"

#ifndef NULL
#define NULL 0
#endif

#define ASSERTELG(alg) pgpAssert((ALGMASK(alg))==PGP_PKALG_ELGAMAL)

struct ELGpub {
	struct BigNum p;		/* Public prime */
	struct BigNum g;		/* Public generator */
	struct BigNum y;		/* Public key, g**x mod p */
};

struct ELGsec {
	struct BigNum p;		/* Copy of public parameters */
	struct BigNum g;
	struct BigNum y;
	struct BigNum x;		/* Secret key, discrete log of y */
};

/* A PgpSecKey's priv points to this, an ELGsec plus the encrypted form... */
struct ELGsecPlus {
	struct ELGsec s;
	byte *cryptkey;
	size_t ckalloc, cklen;
	int locked;
};

/** Public key functions **/

static void
elgPubDestroy(struct PgpPubKey *pubkey)
{
	struct ELGpub *pub = (struct ELGpub *)pubkey->priv;

	ASSERTELG(pubkey->pkAlg);
	
	bnEnd(&pub->p);
	bnEnd(&pub->g);
	bnEnd(&pub->y);
	memset(pub, 0, sizeof(pub));
	pgpMemFree(pub);
	memset(pubkey, 0, sizeof(pubkey));
	pgpMemFree(pubkey);
}

#if 0
static void
elgPubId8(struct PgpPubKey const *pubkey, byte *buf)
{
	pgpAssert(0);
	struct ELGpub const *pub = (struct ELGpub *)pubkey->priv;
	byte *keybuf;
	size_t keybuflen;
	struct PgpHash const *h;
	struct PgpHashContext *hc;

	pgpAssert (pubkey->pkAlg == PGP_PKALG_ELG);

	/* Unfortunately we have no way of indicating failure */
	h = pgpHashByNumber (PGP_HASH_SHA);
	pgpAssert(h);
	hc = pgpHashCreate(h);
	pgpAssert(hc);

	keybuflen = elgPubBufferLength(pubkey);
	keybuf = pgpMemAlloc(keybuflen);
	pgpAssert(keybuf);
	elgPubToBuffer(pubkey, keybuf);

	pgpHashUpdate(hc, keybuf, keybuflen);
	memcpy (buf, pgpHashFinal(hc), 8);
	pgpHashDestroy(hc);
}
#endif

/*
 * Return the largest possible PgpESK size for a given key.
 * Must hold two numbers up to p in size.
 */
static size_t
elgMaxesk(struct PgpPubKey const *pubkey, PgpVersion version)
{
	struct ELGpub const *pub = (struct ELGpub *)pubkey->priv;

	(void)version;
	ASSERTELG(pubkey->pkAlg);
	return 2*(2 + (bnBits(&pub->p)+7)/8);
}


#if 0
/*
 * Heuristic algorithm to estimate the size of the random exponent chosen
 * for El Gamal encryption.
 * slowfactor is ln(ln(n))**(2/3).
 * Formula for work factor is exp(2.08*(ln n)**(1/3)*slowfactor), where
 * that 2.08 is sensitive to the algorithm.  This assumes some pretty good
 * version of NFS.
 * Change to use base 2 and we get:
 * 2**(2.656*(log2 n)**(1/3)*slowfactor).
 * We assume a DH exponent of 160 is about right for n of about 2**1000.
 * When we change the DH exponent by n bits we get 2**(n/2) increase in
 * work factor, so to find out how much we should change it, take the
 * power of 2 in the formula above, double it, and subtract the value
 * for n=1000, then add 160.  This leads to 5.3 * slowfactor * (log2
 * n)**(1/3) all minus 25 (-185.5+160).
 *
 * A simpler approximation holds slowfactor constant.  Varies from 3.5 at
 * bitsize of 1000 to 4.0 at 4000 bits, so I found that 4.5 made a good
 * conservative approximation for values in this range.  Then heuristic
 * formula becomes cube root of size of prime in bits, times 24, minus 80.
 * This can be calculated pretty well in int arithmetic if we want to.
 */
static unsigned
elgExpBits (unsigned primebits)
{
	unsigned size;
	double slowfactor;
	double logbits;
	
	logbits = log((double)primebits);
	slowfactor = exp((2./3.)*log(-.366 + logbits));
	size = 5.3 * slowfactor * exp(logbits/3.) - 25;

	return size >= 160 ? size : 160;
}
#endif

/*
 * Given a buffer of at least "maxesk" bytes, make an PgpESK
 * into it and return the size of the PgpESK, or <0.
 *
 * ElGamal encryption is a simple variant on non-interactove
 * Diffie-Hellman.  The recipient publishes g, p, and y = g**x mod p.
 * the sender picks a random xx, computes yy = g**xx mod p, and
 * the shared secret z = y**xx mod p = yy**x mod p = g**(x*xx) mod p, then
 * then sends z*m, where m is the message.  (Padded in the usual
 * PKCS manner.)
 */
static int
elgEncrypt(struct PgpPubKey const *pubkey, byte const *key,
           size_t keylen, byte *esk, size_t *esklen,
           struct PgpRandomContext const *rc, PgpVersion version)
{
	struct ELGpub const *pub = (struct ELGpub *)pubkey->priv;
	struct BigNum xx;		/* Random exponent */
	struct BigNum yy;		/* g**xx mod p */
	struct BigNum z;		/* y**xx mod p */
	unsigned t;
	unsigned xxbits, pbytes;
	int i;

	/* We don't need this argument, although other algorithms may... */
	(void)version;
	
	bnBegin(&xx);
	bnBegin(&yy);
	bnBegin(&z);

	ASSERTELG(pubkey->pkAlg);
	t = bnBits(&pub->p);
	if (t > 0xffff)
		return PGPERR_PUBKEY_TOOBIG;
	pbytes = (t + 7) / 8;
	if (keylen > pbytes)
		return PGPERR_PUBKEY_TOOSMALL; /* data too big for pubkey */

	/* Add checksum to key, place temporarily in esk buffer */
	t = 0;
	esk[0] = key[0];
	for (i = 1; i < (int)keylen; i++)
		t += esk[i] = key[i];
	esk[keylen] = (byte)(t >> 8 & 255);
	esk[keylen+1] = (byte)(t & 255);

	/* Choose the random xx value to be used for this encryption */
	xxbits = pgpDiscreteLogExponentBits(bnBits(&pub->p))*3/2;
	if (pgpBnGenRand(&xx, rc, xxbits, 0, 0, xxbits) < 0)
		goto nomem;

	/* Do the two exponentiations necessary to compute yy and z */
	if (bnExpMod(&yy, &pub->g, &xx, &pub->p) < 0 ||
	    bnExpMod(&z,  &pub->y, &xx, &pub->p) < 0)
		goto nomem;

	/* Re-use xx to hold the PKCS-padded conventional key */
	if (pgpPKCSPack(&xx, esk, keylen+2, PKCS_PAD_ENCRYPTED, pbytes, rc)<0)
		goto nomem;
	pgpAssert (bnCmp(&xx, &pub->p) < 0);

	/* Compute xx*z mod p, the encrypted session key we will transmit */
	if (bnMul(&z, &z, &xx) < 0 ||
	    bnMod(&z, &z, &pub->p) < 0)
		goto nomem;

	/* Pack the two values into the esk, first yy and then k*z */
	t  = pgpBnPutPlain(&yy, esk);
	t += pgpBnPutPlain(&z, esk+t);
	if (esklen)
		*esklen = (size_t)t;
	
	i = 0;
	goto done;
nomem:
	i = PGPERR_NOMEM;
done:
	bnEnd(&z);
	bnEnd(&yy);
	bnEnd(&xx);
	return i;
}

#ifdef ELGSIGS
/*
 * Helper routine to pack a hash into a buffer with DER prefix
 * Return size of packed data
 */
static unsigned
elgPack (byte *buf, unsigned buflen, struct PgpHash const *h, byte const *hash)
{
	unsigned t = h->DERprefixsize + h->hashsize;
	pgpAssert (t <= buflen);
	memcpy(buf, h->DERprefix, h->DERprefixsize);
	memcpy(buf+h->DERprefixsize, hash, h->hashsize);
	return t;
}
#endif

/*
 * Return 1 if (sig,siglen) is a valid MPI which signs
 * (hash, hashlen).
 * Not implementing ElGamal signatures, using DSS.
 */
static int
elgVerify(struct PgpPubKey const *pubkey, int sigtype, byte const *sig,
	size_t siglen, struct PgpHash const *h, byte const *hash)
{
#ifndef ELGSIGS
	(void)pubkey;
	(void)sigtype;
	(void)sig;
	(void)siglen;
	(void)h;
	(void)hash;
	return PGPERR_PUBKEY_UNIMP;
#else
	/* Check an El Gamal signature */
	struct ELGpub const *pub = (struct ELGpub *)pubkey->priv;
	struct BigNum a,b,yaab;
	byte buf[64];	/* largest hash size + DER prefix */
	int i;
	size_t off;
	unsigned t;

	(void)sigtype;

	bnBegin(&a);
	bnBegin(&b);
	bnBegin(&yaab);

	ASSERTELG(pubkey->pkAlg);

	/* sig holds two values.  Get first, a, from sig. */
	off = 0;
	i = pgpBnGetPlain(&a, sig+off, siglen-off);
	if (i <= 0)
		goto fail;
	/* Get 2nd value, b, from SIG */
	off += i;
	i = pgpBnGetPlain(&b, sig+off, siglen-off);
	if (i <= 0)
		goto fail;
	off += i;
	if (off != siglen) {
		i = PGPERR_SIG_TOOLONG;
		goto done;
	}
	
	/* Compute y**a * a**b, put in a */
	if (bnExpMod(&yaab, &pub->y, &a, &pub->p) < 0 ||
	    bnExpMod(&a, &a, &b, &pub->p)         < 0 ||
	    bnMul(&yaab, &a, &yaab)               < 0 ||
	    bnMod(&yaab, &yaab, &pub->p)          < 0)
		goto nomem;

	/* Reconstruct PKCS packed hash as b */
	t = elgPack(buf, sizeof(buf), h, hash);
	i = pgpPKCSPack(&b, buf, t, PKCS_PAD_SIGNED, (bnBits(&pub->p)+7)/8,
			(struct PgpRandomContext const *)NULL);
	memset(buf, 0, t);
	if (i < 0)
		goto nomem;

	/* Calculate g**M, leave in a */
	if (bnExpMod(&a, &pub->g, &b, &pub->p) < 0)
		goto nomem;

	/* Compare y**a * a**b with g**M, should be equal */
	i = bnCmp(&a, &yaab) == 0;
	goto done;
nomem:
	i = PGPERR_NOMEM;
	goto done;
fail:
	if (!i)
		i = PGPERR_SIG_TOOSHORT;
	goto done;
done:
	bnEnd(&yaab);
	bnEnd(&b);
	bnEnd(&a);

	return i;
#endif
}

/*
 * Turn a PgpPubKey into the algorithm-specific parts of a public key.
 * A public key's ELG-specific part is:
 *
 *  0      2+i  MPI for prime
 * 2+i     2+t  MPI for generator
 * 4+i+t   2+u	MPI for public key
 * 6+i+t+u
 */
static size_t
elgPubBufferLength(struct PgpPubKey const *pubkey)
{
	struct ELGpub const *pub = (struct ELGpub *)pubkey->priv;

	return 6 + (bnBits(&pub->p)+7)/8 + (bnBits(&pub->g)+7)/8 +
		(bnBits(&pub->y)+7)/8;
}

static void
elgPubToBuffer(struct PgpPubKey const *pubkey, byte *buf)
{
	struct ELGpub const *pub = (struct ELGpub *)pubkey->priv;
	unsigned off;

	off = 0;
	off += pgpBnPutPlain(&pub->p, buf+off);
	off += pgpBnPutPlain(&pub->g, buf+off);
	off += pgpBnPutPlain(&pub->y, buf+off);
}


/* A little helper function that's used twice */
static void
elgFillPubkey(struct PgpPubKey *pubkey, struct ELGpub *pub)
{
	pubkey->next	 = NULL;
	pubkey->pkAlg	 = PGP_PKALG_ELGAMAL;
	pubkey->priv	 = pub;
	pubkey->destroy  = elgPubDestroy;
#if 0
	pubkey->id8      = elgPubId8;
#endif
	pubkey->maxesk   = elgMaxesk;
	pubkey->encrypt  = elgEncrypt;
	pubkey->verify   = elgVerify;
	pubkey->bufferLength  = elgPubBufferLength;
	pubkey->toBuffer = elgPubToBuffer;
}


/*
 * Turn the algorithm-specific parts of a public key into a PgpPubKey
 * structure.  A public key's ELG-specific part is:
 *
 *  0      2+i  MPI for prime
 * 2+i     2+t  MPI for generator
 * 4+i+t   2+u	MPI for public key
 * 6+i+t+u
 */
struct PgpPubKey *
elgPubFromBuf(byte const *buf, size_t size, int *error)
{
	struct PgpPubKey *pubkey;
	struct ELGpub *pub;
	unsigned i, t, u;
	int v;

	bnInit();

	v = pgpBnParse(buf, size, 3, &i, &t, &u);
	if (v < 0) {
		*error = v;
		return NULL;
	}
	if ((buf[t-1] & 1) == 0) {	/* Too small or even prime p */
		*error = PGPERR_KEY_MPI;
		return NULL;
	}

	pub = (struct ELGpub *)pgpMemAlloc(sizeof(*pub));
	if (pub) {
		pubkey = (struct PgpPubKey *)pgpMemAlloc(sizeof(*pubkey));
		if (pubkey) {
			bnBegin(&pub->p);
			bnBegin(&pub->g);
			bnBegin(&pub->y);
			if (bnInsertBigBytes(&pub->p, buf+i+2, 0, t-i-2) >= 0
			    && bnInsertBigBytes(&pub->g, buf+t+2, 0,
						u-t-2) >= 0
			    && bnInsertBigBytes(&pub->y, buf+u+2, 0,
						v-u-2) >= 0)
			{
				elgFillPubkey(pubkey, pub);

				*error = 0;
				return pubkey;
			}
			/* Failed = clean up and return NULL */
			bnEnd(&pub->p);
			bnEnd(&pub->g);
			bnEnd(&pub->y);
			pgpMemFree(pubkey);
		}
		pgpMemFree(pub);
	}
	*error = PGPERR_NOMEM;
	return NULL;
}

/*
 * Return the size of the public portion of a key buffer.
 */
int
elgPubKeyPrefixSize(byte const *buf, size_t size)
{
	return pgpBnParse(buf, size, 3, NULL, NULL, NULL);
}