pgpkeyset.c

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

/*
 * pgpKeySet.c -- PGPKeySet implementation
 *
 * Copyright (C) 1996,1997 Pretty Good Privacy, Inc.  All rights reserved.
 *
 * $Id: pgpKeySet.c,v 1.46.2.2.2.1 1997/07/15 21:26:27 quark Exp $
 */

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

#ifdef HAVE_STDLIB_H
#include <stdlib.h>
#endif

#include <string.h>
#include <ctype.h>

#include "pgpKDBint.h"
#include "pgpTypes.h"
#include "pgpDebug.h"
#include "pgpMem.h"
#include "pgpTimeDate.h"
#include "pgpUsuals.h"
#include "pgpMemPool.h"
#include "pgpRngMnt.h"
#include "pgpRngPub.h"

static int
compareKeyIDs(uchar const *keyIDA, uchar const *keyIDB)
{
	int				i;

	for (i = 4; i < 8; i++)
	{
		if (keyIDA[i] > keyIDB[i])
			return 1;
		else if (keyIDA[i] < keyIDB[i])
			return -1;
	}
	for (i = 0; i < 4; i++)
	{
		if (keyIDA[i] > keyIDB[i])
			return 1;
		else if (keyIDA[i] < keyIDB[i])
			return -1;
	}
	return 0;
}

static int
keyCompareByKeyID(void const *a, void const *b)
{
	PGPKey *		keyA = *(PGPKey **)a;
	PGPKey *		keyB = *(PGPKey **)b;
	
	uchar	 		 keyIDA[8];
	uchar	 		 keyIDB[8];
	
	size_t			len;
	PGPError		result;

	len = sizeof(keyIDA);
	result = pgpGetKeyString(keyA, kPGPKeyPropKeyId, (char *)keyIDA, &len);
	pgpAssert(result == PGPERR_OK);

	len = sizeof(keyIDB);
	result = pgpGetKeyString(keyB, kPGPKeyPropKeyId, (char *)keyIDB, &len);
	pgpAssert(result == PGPERR_OK);

	return compareKeyIDs(keyIDA, keyIDB);
}

static int
keyCompareByReverseKeyID(void const *a, void const *b)
{
	return -keyCompareByKeyID(a, b);
}

int
pgpUserIDStrCompare(char const *a, char const *b)
{
	for (;;)
	{
		while (*a && tolower(*a) == tolower(*b))
			a++, b++;
		while (*a && !isalnum(*a))
			a++;
		while (*b && !isalnum(*b))
			b++;
		if (!*a || tolower(*a) != tolower(*b))
			break;
		a++;
		b++;
	}
	return (uchar)tolower(*a) - (uchar)tolower(*b);
}

static int
keyCompareByUserID(void const *a, void const *b)
{
	PGPKey *		keyA = *(PGPKey **)a;
	PGPKey *		keyB = *(PGPKey **)b;

	char			nameA[256];	/* XXX What's the maximum userID size? */
	char			nameB[256];
	size_t			len;
	int				compareResult;
	PGPError		result;

	len = sizeof(nameA) - 1;
	result = pgpGetPrimaryUserIDName(keyA, nameA, &len);
	pgpAssert(result == PGPERR_OK);
	nameA[len] = '\0';

	len = sizeof(nameB) - 1;
	result = pgpGetPrimaryUserIDName(keyB, nameB, &len);
	pgpAssert(result == PGPERR_OK);
	nameB[len] = '\0';

	compareResult = pgpUserIDStrCompare(nameA, nameB);
	return (compareResult!=0) ? compareResult :
			keyCompareByKeyID(a, b);
}

static int
keyCompareByReverseUserID(void const *a, void const *b)
{
	return -keyCompareByUserID(a, b);
}

static int
keyCompareByValidity(void const *a, void const *b)
{
	PGPKey *		keyA = *(PGPKey **)a;
	PGPKey *		keyB = *(PGPKey **)b;

	long			validityA;
	long			validityB;
	PGPError		result;
	
	result = pgpGetPrimaryUserIDValidity(keyA, &validityA);
	pgpAssert(result == PGPERR_OK);
	result = pgpGetPrimaryUserIDValidity(keyB, &validityB);
	pgpAssert(result == PGPERR_OK);

	if (validityA < validityB)
		return 1;
	else if (validityA > validityB)
		return -1;
	else
		return keyCompareByKeyID(a, b);
}

static int
keyCompareByReverseValidity(void const *a, void const *b)
{
	return -keyCompareByValidity(a, b);
}

static int
keyCompareByTrust(void const *a, void const *b)
{
	PGPKey *		keyA = *(PGPKey **)a;
	PGPKey *		keyB = *(PGPKey **)b;

	long			trustA;
	long			trustB;
	PGPError		result;
	
	result = pgpGetKeyNumber(keyA, kPGPKeyPropTrust, &trustA);
	pgpAssert(result == PGPERR_OK);
	result = pgpGetKeyNumber(keyB, kPGPKeyPropTrust, &trustB);
	pgpAssert(result == PGPERR_OK);

	if (trustA < trustB)
		return 1;
	else if (trustA > trustB)
		return -1;
	else
		return keyCompareByKeyID(a, b);
}

static int
keyCompareByReverseTrust(void const *a, void const *b)
{
	return -keyCompareByTrust(a, b);
}

static int
keyCompareByKeySize(void const *a, void const *b)
{
	PGPKey *		keyA = *(PGPKey **)a;
	PGPKey *		keyB = *(PGPKey **)b;

	long			keySizeA;
	long			keySizeB;
	PGPError		result;
	
	result = pgpGetKeyNumber(keyA, kPGPKeyPropBits, &keySizeA);
	pgpAssert(result == PGPERR_OK);
	result = pgpGetKeyNumber(keyB, kPGPKeyPropBits, &keySizeB);
	pgpAssert(result == PGPERR_OK);

	if (keySizeA < keySizeB)
		return 1;
	else if (keySizeA > keySizeB)
		return -1;
	else
		return keyCompareByKeyID(a, b);
}

static int
keyCompareByReverseKeySize(void const *a, void const *b)
{
	return -keyCompareByKeySize(a, b);
}

static int
keyCompareByCreation(void const *a, void const *b)
{
	PGPKey *		keyA = *(PGPKey **)a;
	PGPKey *		keyB = *(PGPKey **)b;

	PGPTime			creationA;
	PGPTime			creationB;
	PGPError		result;
	
	result = pgpGetKeyTime(keyA, kPGPKeyPropCreation, &creationA);
	pgpAssert(result == PGPERR_OK);
	result = pgpGetKeyTime(keyB, kPGPKeyPropCreation, &creationB);
	pgpAssert(result == PGPERR_OK);

	if (creationA < creationB)
		return 1;
	else if (creationA > creationB)
		return -1;
	else
		return keyCompareByKeyID(a, b);
}

static int
keyCompareByReverseCreation(void const *a, void const *b)
{
	return -keyCompareByCreation(a, b);
}

/*
* The compare functions must all return non-ambiguous answers (>0,<0)
* because the add-key functionality uses a binary search to install
* new keys. If things are ambiguous then the order can change if some
* keys are tied under the main search. This is accomplished by doing
* a secondary search on keyid if there is a tie on the main search
* field.
*/

static int (*compareFunc[])(void const *, void const *) = {
	NULL,
	NULL,
	keyCompareByUserID,
	keyCompareByReverseUserID,
	keyCompareByKeyID,
	keyCompareByReverseKeyID,
	keyCompareByValidity,
	keyCompareByReverseValidity,
	keyCompareByTrust,
	keyCompareByReverseTrust,
	keyCompareByKeySize,
	keyCompareByReverseKeySize,
	keyCompareByCreation,
	keyCompareByReverseCreation };
static uint numCompareFuncs = sizeof(compareFunc) / sizeof(compareFunc[0]);

int
pgpCompareKeys(PGPKey *a, PGPKey *b, PGPKeyOrdering order)
{
	pgpa((
		pgpaPGPKeyValid(a),
		pgpaPGPKeyValid(b),
		pgpaAssert(order > 0 && order < numCompareFuncs
					&& order != kPGPAnyOrdering)));

	return (*compareFunc[order])(&a, &b);
}

static void
sortKeyList(PGPKeyList *list)
{
	pgpa((
		pgpaPGPKeyListValid(list),
		pgpaAssert(list->order > 0 && list->order < numCompareFuncs)));

	if (list->order != kPGPAnyOrdering)
		qsort(list->keys, list->keyCount, sizeof(list->keys[0]),
				compareFunc[list->order]);
}

/*
* Keep in mind that the comparison functions are not guaranteed to
* be total orderings, and so even if an element of the list has a
* perfect match with <key>, the index returned might not contain a
* perfect match.
*/
static long
binarySearchKeyList(PGPKeyList *list, PGPKey *key)
{
	long		lo;
	long		hi;
	long		i;
	int			result;
	int			(*compare)(void const *, void const *);

	pgpa((
		pgpaPGPKeyListValid(list),
		pgpaPGPKeyValid(key),
		pgpaAssert(list->order > 0 && list->order < numCompareFuncs)));

	if (list->order == kPGPAnyOrdering)
		return list->keyCount;

	compare = compareFunc[list->order];

	lo = 0;
	hi = list->keyCount;

	while (lo < hi)
	{
		i = (lo + hi) / 2;
		result = (*compare)(&key, &list->keys[i]);
		if (result > 0)
			lo = i + 1;
		else if (result < 0)
			hi = i;
		else
			return i;
	}
	return lo;
}


/* Creates a new empty key database */
PGPKeyDB *
pgpKeyDBCreateInternal(void)
{
	PGPKeyDB *	db;

	/* VC++ doesn't like the following macro */
/*	db = pgpNew(PGPKeyDB); */
	db = (PGPKeyDB *)pgpAlloc(sizeof(PGPKeyDB));
	if (db == NULL)
		return NULL;
	
	memset(db, 0, sizeof(*db));

	db->private = NULL;
	db->refCount = 1;
	db->firstSetInDB = NULL;

	memPoolInit(&db->keyPool);
	db->numKeys = 0;
	db->firstKeyInDB = NULL;
	db->firstFreeKey = NULL;
	db->firstFreeUserID = NULL;
	db->firstFreeCert = NULL;
	db->keysByKeyID = NULL;

	return db;
}

/* Does any additional initialization necessary after DB is fully created */
void
pgpKeyDBInitInternal(PGPKeyDB *db)
{
	/* Nothing for now */
	(void)db;
}

/* Does the final destruction of a key database structure */
void
pgpKeyDBDestroyInternal(PGPKeyDB *db)
{
	memPoolEmpty (&db->keyPool);
	memset (db, 0, sizeof(*db));
	pgpMemFree (db);
}

static PGPKey *
allocKey(PGPKeyDB *db)
{
	PGPKey *	key;

	pgpa(pgpaPGPKeyDBValid(db));

	if (db->firstFreeKey != NULL)
	{
		key = db->firstFreeKey;
		db->firstFreeKey = key->nextKeyInDB;
	}
	else
		key = memPoolNew(&db->keyPool, PGPKey);
	
	pgpClearMemory(key, sizeof(*key));

	return key;
}

static void
deallocKey(PGPKeyDB *db, PGPKey *key)
{
	pgpa((
		pgpaPGPKeyDBValid(db),
		pgpaAssert(db == key->keyDB)));

	key->nextKeyInDB = db->firstFreeKey;
	db->firstFreeKey = key;
}

static PGPError
addKeyToList(PGPKeyList *list, PGPKey *key)
{
	long			i;
	long			newKeyCount;
	PGPKey **	 	newKeys;
	
	pgpa(pgpaPGPKeyListValid(list));

	i = binarySearchKeyList(list, key);

	newKeyCount = list->keyCount + 1;
	newKeys = pgpAlloc(newKeyCount * sizeof(PGPKey *));
	if (!newKeys)
		return PGPERR_NOMEM;

	pgpCopyMemory(list->keys, newKeys, i * sizeof(PGPKey *));
	pgpCopyMemory(list->keys + i, newKeys + i + 1,
					(list->keyCount - i) * sizeof(PGPKey *));
	pgpFree(list->keys);

	list->keys = newKeys;
	list->keyCount = newKeyCount;

	newKeys[i] = key;
	pgpKeyIterAddKey(list, i);
	
	return PGPERR_OK;
}

static PGPError
addKeyToLists(PGPKeyDB *db, PGPKey *key)
{
	PGPKeySet *		set;
	PGPKeyList *	list;
	PGPError		result;

	pgpa(pgpaPGPKeyDBValid(db));

	for (set = db->firstSetInDB; set; set = set->nextSetInDB)
	{
		pgpa(pgpaPGPKeySetValid(set));

		if (pgpKeySetMember(set, key))
			for (list = set->firstListInSet; list; list = list->nextListInSet)
				if ((result = addKeyToList(list, key)) != PGPERR_OK)
					return result;
	}
	return PGPERR_OK;
}

static PGPError
removeKeyFromList(PGPKeyList *list, PGPKey *key)
{
	long			i;

	pgpa(pgpaPGPKeyListValid(list));

	for (i = 0; i < list->keyCount; i++)
		if (list->keys[i] == key)
			break;
	
	if (i < list->keyCount)
	{
		pgpCopyMemory(list->keys + i + 1, list->keys + i,
						(list->keyCount - i - 1) * sizeof(PGPKey *));

		list->keyCount--;
		pgpRealloc((void **)&list->keys, list->keyCount * sizeof(PGPKey *));

		pgpKeyIterRemoveKey(list, i);
	}
	
	return PGPERR_OK;
}

static PGPError
removeKeyFromLists(PGPKeyDB *db, PGPKey *key)
{
	PGPKeySet *		set;
	PGPKeyList *	list;
	PGPError		result;

	pgpa(pgpaPGPKeyDBValid(db));

	for (set = db->firstSetInDB; set; set = set->nextSetInDB)
{
		pgpa(pgpaPGPKeySetValid(set));

		for (list = set->firstListInSet; list; list = list->nextListInSet)
			if ((result = removeKeyFromList(list, key)) != PGPERR_OK)
				return result;
	}
	return PGPERR_OK;
}

PGPError
pgpReSortKeys(PGPKeyDB *db, RingSet *changed)
{
	PGPKeySet *		set;
	PGPKeyList *	list;
	PGPKey *		key;
	PGPKey **	 	movedKeys = NULL;
	long			numMovedKeys;
	long			movedKeysAlloc;
	long			i;
	int				(*compare)(void const *, void const *);
	PGPError		result = PGPERR_OK;

	pgpa(pgpaPGPKeyDBValid(db));

	movedKeysAlloc = 8;
	movedKeys = pgpAlloc(movedKeysAlloc * sizeof(PGPKey *));
	if (!movedKeys)
	{
		result = PGPERR_NOMEM;
		goto done;
	}
	for (set = db->firstSetInDB; set; set = set->nextSetInDB)
	{
		pgpa(pgpaPGPKeySetValid(set));

		for (list = set->firstListInSet; list; list = list->nextListInSet)
		{
			pgpa((
				pgpaPGPKeyListValid(list),
				pgpaAssert(list->order > 0 && list->order < numCompareFuncs)));

			if (list->order != kPGPAnyOrdering)
			{
				compare = compareFunc[list->order];
				numMovedKeys = 0;
				for (i = 0; i < list->keyCount; i++)
					if (ringSetIsMember(changed, list->keys[i]->key))
					{
						if (numMovedKeys >= movedKeysAlloc)
						{
							movedKeysAlloc *= 2;
							result = pgpRealloc((void **)&movedKeys,
													movedKeysAlloc
														* sizeof(PGPKey *));
							if (result)
								goto done;
						}
						key = movedKeys[numMovedKeys++] = list->keys[i];
						result = removeKeyFromList(list, key);
						if (result)
							goto done;
						i--;
					}
				for (i = 0; i < numMovedKeys; i++)
				{
					result = addKeyToList(list, movedKeys[i]);
					if (result)
						goto done;
								}
						}
				}
		}
	done:
	if (movedKeys != NULL)
		pgpFree(movedKeys);
	return result;
}

/*
* buildKeyPool can be used to either add keys or remove keys, but not both.
* If you are removing keys, pass TRUE for <deleteFlag>, but if so there
* better not be any new keys or else it'll do the wrong thing. Likewise,
* if you pass FALSE for <deleteFlag>, there better not be any keys missing.
*/
PGPError
pgpBuildKeyPool(PGPKeyDB *db, Boolean deleteFlag)
{
	RingIterator *	iter;
	RingObject *	obj;
	PGPKey *		key;
	PGPKey **	 	prevPtr;
	PGPError		result = PGPERR_OK;

	iter = ringIterCreate(pgpKeyDBRingSet(db));
	if (iter == NULL)
		return PGPERR_NOMEM;
	
	prevPtr = &db->firstKeyInDB;
	
	while (ringIterNextObject(iter, 1) > 0)
	{
		obj = ringIterCurrentObject(iter, 1);
		pgpAssertAddrValid(obj, VoidAlign);	/* XXX use better align check */

		key = *prevPtr;

		if (deleteFlag && key)
			while (key->key != obj)
			{
				pgpa(pgpaPGPKeyValid(key));

				removeKeyFromLists(db, key);

				*prevPtr = key->nextKeyInDB;
				pgpFreeKey(key);
				key = *prevPtr;

				pgpAssert(db->numKeys > 0);
				db->numKeys--;
			}

		if ((!key || key->key != obj) && !deleteFlag)
		{
			key = allocKey(db);
			if (key == NULL)
			{
				result = PGPERR_NOMEM;
				break;
			}

			key->refCount = 0;
			key->keyDB = db;
			key->key = obj;
			key->userVal = 0;
			key->subKeys.next = &key->subKeys;
			key->subKeys.prev = key->subKeys.next;
			key->userIDs.next = &key->userIDs;
			key->userIDs.prev = key->userIDs.next;
			key->nextKeyInDB = *prevPtr;
			pgpIncKeyRefCount (key);
			*prevPtr = key;

			db->numKeys++;

			addKeyToLists(db, key);
		}
		prevPtr = &key->nextKeyInDB;
	}

	/* Reached end of RingSet. If we're in delete mode, there
		may still be trailing PGPKey objects that need to be
		freed. */
	
	if (deleteFlag) {
	key = *prevPtr;
		while (key != NULL) {
		pgpa(pgpaPGPKeyValid(key));
			removeKeyFromLists(db, key);
			*prevPtr = key->nextKeyInDB;
			pgpFreeKey(key);
			key = *prevPtr;
			pgpAssert(db->numKeys > 0);
			db->numKeys--;
		}
	}

	*prevPtr = NULL;
	ringIterDestroy(iter);

	return result;
}

void
pgpIncKeyDBRefCount(PGPKeyDB *db)
{
	pgpa(pgpaPGPKeyDBValid(db));

	db->refCount++;
}

void
pgpFreeKeyDB(PGPKeyDB *db)
{
	pgpa(pgpaPGPKeyDBValid(db));

	db->refCount--;
	if (db->refCount <= 0)
	{
		if (db->keysByKeyID != NULL)
		{
			/*
			* Move the refCount up by 2 while we destroy the keyList,
			* so when pgpFreeKeyDB is called from pgpFreeKeySet from
			* pgpFreeKeyList below, it does nothing but decrement the
			* refCount. Unfortunately this is more of a hack than I'd
			* like. refCounts don't work all that well with cycles.
				*/
			db->refCount += 2;
			pgpFreeKeyList(db->keysByKeyID);
			db->refCount--;