pgpkeymisc.c

vc环境下的pgp源码

/*
 * pgpKeyMisc.c
 * Miscellaneous helper functions for public key modules.
 * Including packing and unpacking for PKCS compatibility.
 *
 * $Id: pgpKeyMisc.c,v 1.32 1999/04/22 00:37:43 hal Exp $
 */


#include "pgpConfig.h"
#include <string.h>

#include <stdarg.h>

#include "pgpDebug.h"
#include "pgpKeyMisc.h"
#include "bn.h"
#include "pgpCFBPriv.h"
#include "pgpSymmetricCipherPriv.h"
#include "pgpPublicKey.h"
#include "pgpHashPriv.h"
#include "pgpMem.h"
#include "pgpErrors.h"
#include "pgpPubKey.h"
#include "pgpRandomX9_17.h"
#include "pgpStr2Key.h"
#include "pgpUsuals.h"
#include "pgpUtilities.h"
#include "pgpEnv.h"

#ifndef PKCS_COMPAT
#define PKCS_COMPAT 1
#endif


/*
 * Given a number of bits in a modulus, compute the minimum exponent size
 * needed to provide equivalent security from small-exponent attacks.
 * Adding padding on top of this is not an entirely evil idea.
 *
 * This is based on a paper from Michael Wiener   | This extension to
 * on the difficulty of the two attacks, which    | the table is not
 * the following table:                           | part of the original.
 *                                                |
 *   Table 1: Subgroup Sizes to Match Field Sizes |   THIS FUNCTION
 *                                                |
 *  Size of p   Cost of each attack    Size of q  |  Output   Error
 *   (bits)     (instructions or        (bits)    |         (+ is safe)
 *               modular multiplies)              |
 *                                                |
 *     512           9 x 10^17           119      |   137      +18
 *     768           6 x 10^21           145      |   153      +8
 *    1024           7 x 10^24           165      |   169      +4
 *    1280           3 x 10^27           183      |   184      +1
 *    1536           7 x 10^29           198      |   198      +0
 *    1792           9 x 10^31           212      |   212      +0
 *    2048           8 x 10^33           225      |   225      +0
 *    2304           5 x 10^35           237      |   237      +0
 *    2560           3 x 10^37           249      |   249      +0
 *    2816           1 x 10^39           259      |   260      +1
 *    3072           3 x 10^40           269      |   270      +1
 *    3328           8 x 10^41           279      |   280      +1
 *    3584           2 x 10^43           288      |   289      +1
 *    3840           4 x 10^44           296      |   297      +1
 *    4096           7 x 10^45           305      |   305      +0
 *    4352           1 x 10^47           313      |   313      +0
 *    4608           2 x 10^48           320      |   321      +1
 *    4864           2 x 10^49           328      |   329      +1
 *    5120           3 x 10^50           335      |   337      +2
 *
 * This function fits a curve to this, which overestimates the size
 * of q required, but by a very small amount in the important 1000-4000
 * bit range.  It is a quadratic curve up to 3840 bits, and a linear
 * curve past that.  They are designed to be C(1) (have the same value
 * and the same slope) at the point where they meet.
 */
#define AN      1       /* a = -AN/AD/65536, the quadratic coefficient */
#define AD      3
#define M       8       /* Slope = M/256, i.e. 1/32 where linear starts */
#define TX      3840    /* X value at the slope point, where linear starts */
#define TY      297     /* Y value at the slope point, where linear starts */
/*
 * For a slope of M at the point (TX,TY), we only have one degree of
 * freedom left in a quadratic curve, so use the coefficient of x^2,
 * namely a, as that free parameter.
 *
 * y = -AN/AD*((x-TX)/256)^2 + M*(x-TX)/256 + TY
 *   = -AN*(x-TX)*(x-TX)/AD/256/256 + M*x/256 - M*TX/256 + TY
 *   = -AN*x*x/AD/256/256 + 2*AN*x*TX/AD/256/256 - AN*TX*TX/AD/256/256 \
 *      + M*x/256 - M*TX/256 + TY
 *   = -AN*(x/256)^2/AD + 2*AN*(TX/256)*(x/256)/AD + M*(x/256) \
 *      - AN*(TX/256)^2/AD - M*(TX/256) + TY
 *   = (AN*(2*TX/256 - x/256) + M*AD)*x/256/AD - (AN*(TX/256)/AD + M)*TX/256 \
 *      + TY
 *   = (AN*(2*TX/256 - x/256) + M*AD)*x/256/AD \
 *      - (AN*(TX/256) + M*AD)*TX/256/AD + TY
 *   =  ((M*AD + AN*(2*TX/256 - x/256))*x - (AN*(TX/256)+M*AD)*TX)/256/AD + TY
 *   =  ((M*AD + AN*(2*TX - x)/256)*x - (AN*(TX/256)+M*AD)*TX)/256/AD + TY
 *   =  ((M*AD + AN*(2*TX - x)/256)*x - (M*AD + AN*TX/256)*TX)/256/AD + TY
 *   =  (((256*M*AD+2*AN*TX-AN*x)/256)*x - (M*AD + AN*TX/256)*TX)/256/AD + TY
 *
 * Since this is for the range 0...TX, in order to avoid having any
 * intermediate results less than 0, we need one final rearrangement, and
 * a compiler can easily take the constant-folding from there...
 *
 *   =  TY + (((256*M*AD+2*AN*TX-AN*x)/256)*x - (M*AD + AN*TX/256)*TX)/256/AD
 *   =  TY - ((M*AD + AN*TX/256)*TX - ((256*M*AD+2*AN*TX-AN*x)/256)*x)/256/AD
 */

#define BITS(x) \
        TY - ((M*AD + AN*TX/256)*TX - ((256*M*AD+AN*2*TX-AN*x)/256)*x)/(AD*256)

unsigned
pgpDiscreteLogExponentBits(unsigned modbits)
{
	unsigned expbits;

	if (modbits > TX)
		expbits = M*modbits/256 - M*TX/256 + TY;    /* Linear */
	else
		expbits = BITS(modbits);       /* Quadratic */
	return expbits;
}

/* For the Q prime in the DSA, we round up to a multiple of 8 bits.
 * That way when we make the signature, we can bring our hash output over
 * in a multiple of bytes.
 */
unsigned
pgpDiscreteLogQBits(unsigned modbits)
{
	return ((pgpDiscreteLogExponentBits(modbits)+7)/8)*8;
}

#undef BITS
#undef TY
#undef TX
#undef M
#undef AD
#undef AN

/*
 * Fill the given bignum, from bytes high-1 through low (where 0 is
 * the least significant byte), with non-zero random data.
 */
static int
randomPad(PGPRandomContext const *rc, BigNum *bn,
	unsigned high, unsigned low)
{
	unsigned i, l;
	PGPByte padding[64];   /* This can be any size (>0) whatsoever */

	high -= low;
	while (high) {
		l = high < sizeof(padding) ? high : sizeof(padding);
		pgpRandomGetBytes(rc, padding, l);
                for (i = 0; i < l; i++) {       /* Replace all zero bytes */ 
                        while(padding[i] == 0)
				pgpRandomGetBytes(rc, padding+i, 1);
                }
		high -= l;
		if (bnInsertBigBytes(bn, padding, high+low, l) < 0)
			return kPGPError_OutOfMemory;
	}

	pgpClearMemory( padding,  sizeof(padding));
	return 0;
}

/*
 * Fill the given bignum, from bytes high-1 through low (where 0 is
 * the least significant byte), with all ones (0xFF) data.
 */
static int
onesPad(BigNum *bn, unsigned high, unsigned low)
{
	unsigned l;
	static PGPByte const padding[] = {
		255,255,255,255,255,255,255,255,
		255,255,255,255,255,255,255,255
	};

	high -= low;
	while (high) {
		l = high < sizeof(padding) ? high : sizeof(padding);
		high -= l;
		if (bnInsertBigBytes(bn, padding, high+low, l) < 0)
			return kPGPError_OutOfMemory;
	}
	return 0;
}


/*
 * The Basic Encoding Rules (of which the Distinguished Encoding Rules
 * are a simple minimal-sized subset) are supposed to be compact.  Humph.
 * Maybe they are, but the ASN.1 they're encoding is less than concise.
 * It's sequence(sequence(object_id(1.2.840.113549.2.5)),octet_string(...))
 */
static PGPByte const MD5_prefix[] = {
	0x30, /* Universal, Constructed, Sequence */
	0x20, /* Length 32 (bytes following) */
		0x30, /* Universal, Constructed, Sequence */
		0x0c, /* Length 12 */
			0x06, /* Universal, Primitive, object-identifier */
			0x08, /* Length 8 */
				0x2a, /* 42 = ISO(1)*40 + Member bodies(2) */
				0x86, 0x48, /* 840 = US (ANSI) */
				0x86, 0xF7, 0x0D, /* 113549 = RSADSI */
				0x02, /* 2 = Hash functions */
				0x05, /* 5 = MD5 */
			0x05, /* Universal, Primitive, NULL */
			0x00, /* Length 0 */
		0x04, /* Universal, Primitive, Octet string */
		0x10 /* Length 16 */
			/* 16 MD5 digest bytes go here */
};

/* This is the PGP 2.2 MD5 identification byte */
static PGPByte const pgp22_MD5_byte = 1;


/*
 * Wrap a PKCS wrapper around some data.
 * Type 1 is for signature, type 2 for encryption.
 *
 * Type 2 wrappers:
 *
 * If the modulus is n bytes long, with the most significant byte
 * being n-1 and the least significant, 0, the wrapper looks like:
 *
 * Position     Value   Function
 * n-1           0      This is needed to ensure that the padded number
 *                      is less than the modulus.
 * n-2           2      The padding type (non-zero random).
 * n-3..len+1   ???     Non-zero random padding bytes to "salt" the
 *                      output and prevent duplicate plaintext attacks.
 * len           0      Zero byte to mark the end of the padding
 * len-1..0     data    Supplied payload data.
 *
 *
 * In the case of PGP, the payload is a byte indicating the type of
 * conventional cipher, currently always set to 1 to indicate IDEA,
 * and a 16-byte IDEA key followed by a 16-bit checksum.
 *
 * Versions of PGP up to 2.2 generated a "broken" version of this format,
 * which had the components (except for the most significant zero byte)
 * in the opposite order.  This is controlled by PKCS_COMPAT.
 * There's no security difference, it's just nice if everyone does it
 * the same way.
 *
 * Position     Value
 * n-1           0
 * n-2..n-len-1 data    Supplied payload data.
 * n-len-2       0      Zero byte to mark the end of the padding
 * n-len-3..1   ???     Non-zero random padding bytes to "salt" the
 *                      output and prevent duplicate plaintext attacks.
 * 0             2      The padding type (non-zero random).
 *
 * On decryption, the fact that the first (most significant) byte of
 * payload data is 1 for the <= 2.2 format, and a padding type of 1
 * (fixed, all ones) is never used for public-key encryption lets
 * these be distinguished.
 *
 * There really should be several bytes of padding, although this
 * routine will not fail to encrypt unless it will not fit, even
 * with no padding bytes.
 *
 *
 * Type 1 padding:
 *
 *
 * The type is 1, and the padding is all 1's
 * (hex 0xFF).  In addition, if the data is a DER-padded MD5 hash, there's
 * an option for encoding it with the old PGP 2.2 format, in which case
 * that's all replaced by a 1 byte indicating MD5.
 *
 * When decrypting, distinguishing these is a bit trickier, since the
 * second most significant byte is 1 in both cases, but in general,
 * it could only cause confusion if the PGP hash were all 1's.
 *
 * To summarize, the formats are:
 *
 * Position     Value   Function
 * n-1           0      This is needed to ensure that the padded number
 *                      is less than the modulus.
 * n-2           1      The padding type (all ones).
 * n-3..len+1   255     All ones padding to ensure signatures are rare.
 * len           0      Zero byte to mark the end of the padding
 * len-1..x     ASN.1	The ASN.1 DER magic cookie (18 bytes)
 * x-1..0       data    The payload MD5 hash (16 bytes).
 *
 *
 * Position     Value
 * n-1           0
 * n-2           1	"This is MD5"
 * n-2..n-len-2 data    Supplied payload MD5 hash (len == 16).
 * n-len-2       0      Zero byte to mark the end of the padding
 * n-len-3..1   255     All ones padding.
 * 0             1      The padding type (all ones).
 *
 *
 * The reason for the all 1's padding is an extra consistency check.
 * A randomly invented signature will not decrypt to have the long
 * run of ones necessary for acceptance.
 *
 * Oh... the public key isn't needed to decrypt, but it's passed in
 * because a different glue library may need it for some reason.
 *
 * TODO: Have the caller put on the PKCS wrapper.  We can notice and
 * strip it off if we're trying to be compatible.
 */

int
pgpPKCSPack(BigNum *bn, PGPByte const *in, unsigned len, PGPByte padtype,
	unsigned bytes, PGPRandomContext const *rc)
{
	if (len+3 > bytes)
		return kPGPError_PublicKeyTooSmall;	/* data won't fit in pubkey! */

	/* Set the entire number to 0 to start */
	(void)bnSetQ(bn, 0);
	
	if (padtype == PKCS_PAD_ENCRYPTED) {
		/* Random padding */
		if (PKCS_COMPAT || in[0] != 1) {
			if (bnInsertBigBytes(bn, &padtype, bytes-2, 1) < 0 ||
			    randomPad(rc, bn, bytes-2, len+1) < 0 ||
			    bnInsertBigBytes(bn, in, 0, len) < 0)
				return kPGPError_OutOfMemory;
		} else {
			/* Old <= 2.2 broken format */
			if (bnInsertBigBytes(bn, in, bytes-len-1, len) < 0 ||
			    randomPad(rc, bn, bytes-len-2, 1) < 0 ||
			    bnInsertBigBytes(bn, &padtype, 0, 1) < 0)
				return kPGPError_OutOfMemory;
		}
	} else {
		pgpAssert (padtype == PKCS_PAD_SIGNED);
		/* Constant padding */
		if (PKCS_COMPAT
		    || len != sizeof(MD5_prefix)+16
		    || memcmp(in, MD5_prefix, sizeof(MD5_prefix)) != 0)
		{
			if (bnInsertBigBytes(bn, &padtype, bytes-2, 1) < 0 ||
			    onesPad(bn, bytes-2, len+1) < 0 ||
			    bnInsertBigBytes(bn, in, 0, len) < 0)