vmbigintegersclass.cpp

TOOL (Tiny Object Oriented Language) is an easily-embedded, object-oriented, C++-like-language inter

	VM_DIGIT_T k, t[2];
	unsigned int i;

	if (q == 0)	/* No change */
		return wn;

	k = 0;

	for (i = 0; i < n; i++)
	{
		spMultiply(t, q, v[i]);
		w[i] -= k;
		if (w[i] > VM_MAX_DIGIT - k)
			k = 1;
		else
			k = 0;
		w[i] -= t[0];
		if (w[i] > VM_MAX_DIGIT - t[0])
			k++;
		k += t[1];
	}

	/* Cope with Wn not stored in array w[0..n-1] */
	wn -= k;

	return wn;
}

int VMBigIntegers::QhatTooBig(VM_DIGIT_T qhat, VM_DIGIT_T rhat,
					  VM_DIGIT_T vn2, VM_DIGIT_T ujn2)
{	/*	Returns true if Qhat is too big
		i.e. if (Qhat * Vn-2) > (b.Rhat + Uj+n-2)
	*/
	VM_DIGIT_T t[2];

	spMultiply(t, qhat, vn2);
	if (t[1] < rhat)
		return 0;
	else if (t[1] > rhat)
		return 1;
	else if (t[0] > ujn2)
		return 1;

	return 0;
}


int VMBigIntegers::mpCompare(VM_DIGIT_T a[], VM_DIGIT_T b[], unsigned int ndigits)
{
	/*	Returns sign of (a - b)
	*/

	if (ndigits == 0) return 0;

	while (ndigits--)
	{
		if (a[ndigits] > b[ndigits])
			return 1;	/* GT */
		if (a[ndigits] < b[ndigits])
			return -1;	/* LT */
	}

	return 0;	/* EQ */
}


VM_DIGIT_T VMBigIntegers::mpAdd(VM_DIGIT_T w[], VM_DIGIT_T u[], VM_DIGIT_T v[], 
			   unsigned int ndigits)
{
	/*	Calculates w = u + v
		where w, u, v are multiprecision integers of ndigits each
		Returns carry if overflow. Carry = 0 or 1.

		Ref: Knuth Vol 2 Ch 4.3.1 p 266 Algorithm A.
	*/

	VM_DIGIT_T k;
	unsigned int j;

	/* Step A1. Initialise */
	k = 0;

	for (j = 0; j < ndigits; j++)
	{
		/*	Step A2. Add digits w_j = (u_j + v_j + k)
			Set k = 1 if carry (overflow) occurs
		*/
		w[j] = u[j] + k;
		if (w[j] < k)
			k = 1;
		else
			k = 0;
		
		w[j] += v[j];
		if (w[j] < v[j])
			k++;

	}	/* Step A3. Loop on j */

	return k;	/* w_n = k */
}


int VMBigIntegers::bpSubtract(BIGD_T *w, BIGD_T *u, BIGD_T *v)
{
	/* Compute w = u - v 
	   with full memory management */

	unsigned int dig_size;
	unsigned int nu, nv, nw;
	VM_DIGIT_T borrow;

	nu = u->ndigits;
	nv = v->ndigits;
	nw = w->ndigits;
	/* Make sure u and v are the same size */
	if (nu > nv)
	{
		bpResize(v, nu);
		dig_size = nu;
	}
	else if (nv > nu)
	{
		bpResize(u, nv);
		dig_size = nv;
	}
	else
		dig_size = nu;

	/* Now make sure w is big enough */
	if (nw < dig_size)
	{
		bpResize(w, dig_size);
	}

	/* Finally, do the business */
	borrow = mpSubtract(w->digits, u->digits, v->digits, dig_size);

	/* Make sure we've set the right size for w */
	w->ndigits = mpSizeof(w->digits, w->maxdigits);

	return borrow;
}


BIGD_T* VMBigIntegers::bpResize(BIGD_T *b, unsigned int newsize)
{
	/* Return ptr to re-sized BIGD structure 
	   with newsize digits */

	unsigned int i;

	/* Check just in case NULL */
	if (b == NULL)
		return bpInit(b, newsize);

	/* Increase (we assume) size of digit array */
	b->digits = (VM_DIGIT_T *)realloc(b->digits, newsize * sizeof(VM_DIGIT_T));
	
	/* Check for failure */
	if (!b->digits)
		return NULL;

	b->maxdigits = newsize;	/* Remember new max */

	/* Make sure new digits are zero */
	for (i = b->ndigits; i < newsize; i++)
		b->digits[i] = 0;

	return b;
}


BIGD_T * VMBigIntegers::bpInit(BIGD_T *b, unsigned int precision)
{
	/* Return ptr to initialised BIGD structure 
	   with precision digits */

	/* Allocate required memory */
	b->digits = (VM_DIGIT_T *)calloc(precision, sizeof(VM_DIGIT_T));
	/* Check for failure */
	if (!b->digits)
		return NULL;
	b->ndigits = 0;	/* Nothing set yet */
	b->maxdigits = precision;	/* Remember max allocated */
	return b;
}


void VMBigIntegers::bpFinal(BIGD_T *b)
{
	/* Zeroise and free memory */
	unsigned int i;

	if (b == NULL) return;

	/* Zeroise them all, just in case */
	for (i = 0; i < b->maxdigits; i++)
		b->digits[i] = 0;

	free(b->digits);
	b->maxdigits = 0;
	b->ndigits = 0;
}


int VMBigIntegers::bpEqual(BIGD_T *a, BIGD_T *b)
{
	/*	Returns true if a == b, else false
	*/
	unsigned int n;

	if (a->ndigits == 0 || b->ndigits == 0) return -1;

	n = (a->ndigits > b->ndigits ? a->ndigits : b->ndigits);

	while (n--)
	{
		if (a->digits[n] != b->digits[n])
			return 0;	/* False */
	}

	return (!0);	/* True */
}


int VMBigIntegers::bpAdd(BIGD_T *w, BIGD_T *u, BIGD_T *v)
{
	/* Compute w = u + v 
	   with full memory management */

	unsigned int dig_size;
	unsigned int nu, nv, nw;
	VM_DIGIT_T carry;

	nu = u->ndigits;
	nv = v->ndigits;
	nw = w->ndigits;
	/* Make sure u and v are the same size */
	if (nu > nv)
	{
		bpResize(v, nu);
		dig_size = nu;
	}
	else if (nv > nu)
	{
		bpResize(u, nv);
		dig_size = nv;
	}
	else
		dig_size = nu;

	/* Now make sure w is big enough for sum (incl carry) */
	if (nw <= dig_size)
	{
		bpResize(w, dig_size + 1);
	}

	/* Finally, do the business using those nasty pointers */
	carry = mpAdd(w->digits, u->digits, v->digits, dig_size);

	/* Make sure we've set the right size for w */
	if (carry)
	{
		w->digits[dig_size] = carry;
		w->ndigits = dig_size + 1;
	}
	else
		w->ndigits = dig_size;

	return 0;
}


void VMBigIntegers::mpPrint(VM_DIGIT_T *p, unsigned int len)
{
	while (len--)
	{
		printf("%08lx ", p[len]);
	}
}

void VMBigIntegers::mpPrintNL(VM_DIGIT_T *p, unsigned int len)
{
	unsigned int i = 0;

	while (len--)
	{
		if ((i % 8) == 0 && i)
			printf("\n");
		printf("%08lx ", p[len]);
		i++;
	}
	printf("\n");
}

void VMBigIntegers::mpPrintTrim(VM_DIGIT_T *p, unsigned int len)
{
	/* Trim leading zeroes */
	while (len--)
	{
		if (p[len] != 0)
			break;
	}
	len++;
	while (len--)
	{
		printf("%08lx ", p[len]);
	}
}

void VMBigIntegers::mpPrintTrimNL(VM_DIGIT_T *p, unsigned int len)
{
	unsigned int i = 0;

	/* Trim leading zeroes */
	while (len--)
	{
		if (p[len] != 0)
			break;
	}
	len++;
	while (len--)
	{
		if ((i % 8) == 0 && i)
			printf("\n");
		printf("%08lx ", p[len]);
		i++;
	}
	printf("\n");
}

/* Print functions for BigDigit structures */

void VMBigIntegers::bpPrint(BIGD_T *p)
{
	unsigned int i = p->ndigits;
	while (i--)
	{
		printf("%08lx ", p->digits[i]);
	}
}


///////////////////////////////////////////////////////////////////////////////
//
// the following are extensions to the big digits library for performing
// diffie hellman key exchange protocols
//

// set up a couple of unique numbers for the equation co-efficients
//
VM_DIGIT_T VMoA[ VM_MAX_DIG_LEN ]; 
VM_DIGIT_T VMoQ[ VM_MAX_DIG_LEN ];

///////////////////////////////////////////////////////////////////////////////
//
// a large crypto safe prime
//
unsigned long VMalQ[] = { 9,7,2,7,5,9,5,1,8,8,5,1,6,8,5,9,9,1,4,0,2,3,8,0,3,8,1,2,0,7,8,7,6,9,3,4,4,9,1,2,1,0,9,0,2,4,3,2,6,5,1,4,0,9,9,7,9,4,2,7,7,7,3,9,8,0,3,0,6,9,9,9,2,8,0,3,1 };



/*****************************************************************************/
/*

     FUNCTION NAME:  VMDiffieHellman::mpTrimToBuffer

       DESCRIPTION:  This function converts a big integer value into a character
                     buffer so as to transfer the results of the dh equations into
                     a char buffer for use as a key

             INPUT:  p - pointer to the digit to convert
                     iDigitLength - the size of the digit object
                     pchKeyOutput - pointer to key buffer
                     iKeyLength - length of the key buffer
            OUTPUT:  

           RETURNS:  void 
*/
void VMDiffieHellman::mpTrimToBuffer( VM_DIGIT_T* p, int iDigitLength, char* pchKeyOutput, int iKeyLength )
{
  while ( iDigitLength-- )
  {
    if ( p[ iDigitLength ] != 0 )
      break;
  }
  iDigitLength++;
  int iPrinted = 0;
  while ( iDigitLength-- && iPrinted < iKeyLength )
  {
    char achPart[ 50 ];
    sprintf( achPart,  "%x", p[ iDigitLength ] );
    strncpy( pchKeyOutput + iPrinted, achPart, iKeyLength - iPrinted );
    iPrinted = strlen( pchKeyOutput );
  }
}
/* End of function "VMDiffieHellman::mpTrimToBuffer"
/*****************************************************************************/


/*****************************************************************************/
/*

     FUNCTION NAME:  VMDiffieHellman::GetUniqueSessionKey

       DESCRIPTION:  The real purpose for this class. Allows a unique session
                     key to be set up according to a pair of values exchanged
                     between two sides of a data exchange channel. 

             INPUT:  pchKeyOutput - pointer to buffer where the key will be
                                    output
                     iKeyLength - length of the output key buffer
                     lLocalIPAddress -  local value used in the generation of
                                        the session key
                     lRemoteIPAddress - remote alue used in the generation of
                                        the session key
            OUTPUT:  

           RETURNS:  void
*/
void VMDiffieHellman::GetUniqueSessionKey( char*         pchKeyOutput, 
                                          int           iKeyLength, 
                                          unsigned long lLocalIPAddress, 
                                          unsigned long lRemoteIPAddress )
{
  // go for a 2Gig keyspace comprised of a 65K by 65K 'square' of possible keys
  //
  lLocalIPAddress  = 0x0000ffff & lLocalIPAddress;
  lRemoteIPAddress = 0x0000ffff & lRemoteIPAddress;

  if ( 0 == lLocalIPAddress )  lLocalIPAddress  = 1;
  if ( 0 == lRemoteIPAddress ) lRemoteIPAddress = 1;

  VM_DIGIT_T oMyIP[ VM_MAX_DIG_LEN ]; 
  VM_DIGIT_T oHisIP[ VM_MAX_DIG_LEN ];

  // the following code is the diffie-hellman key exchange protocol expressed
  // in terms of the functions in the big integer library
  //
  mpSetDigit(oMyIP,  lLocalIPAddress,  VM_MAX_DIG_LEN );
  mpSetDigit(oHisIP, lRemoteIPAddress, VM_MAX_DIG_LEN );

  VM_DIGIT_T oMyY[ VM_MAX_DIG_LEN ]; 
  VM_DIGIT_T oHisY[ VM_MAX_DIG_LEN ];

  mpModExp( oMyY,  VMoA, oMyIP,  VMoQ, VM_MAX_DIG_LEN );
  mpModExp( oHisY, VMoA, oHisIP, VMoQ, VM_MAX_DIG_LEN );

  VM_DIGIT_T oMyZ[ VM_MAX_DIG_LEN ];
  mpModExp( oMyZ, oHisY, oMyIP, VMoQ, VM_MAX_DIG_LEN );

  VM_DIGIT_T oKey[ VM_MAX_DIG_LEN ];
  mpModulo( oKey, oMyZ, VM_MAX_DIG_LEN, VMoQ, VM_MAX_DIG_LEN );

  mpTrimToBuffer( oKey, VM_MAX_DIG_LEN, pchKeyOutput, iKeyLength );
}
/* End of function "VMDiffieHellman::GetUniqueSessionKey"
/*****************************************************************************/


/*****************************************************************************/
/*

     FUNCTION NAME:  VMDiffieHellman::GetInstance

       DESCRIPTION:  singleton accessor to the key exchange / generator

             INPUT:  void  
            OUTPUT:  none

           RETURNS:  pointer to the key exchange generator
*/
VMDiffieHellman* VMDiffieHellman::GetInstance( void )
{
  static VMDiffieHellman oInstance;
  return( &oInstance );
}
/* End of function "VMDiffieHellman::GetInstance"
/*****************************************************************************/


/*****************************************************************************/
/*

     FUNCTION NAME:  VMDiffieHellman::VMDiffieHellman

       DESCRIPTION:  ctor. sets up the A and Q equation factors for all users

             INPUT:  void  
            OUTPUT:  none

           RETURNS:  none
*/
VMDiffieHellman::VMDiffieHellman( void )
{
  mpSetEqual( VMoQ, VMalQ, VM_MAX_DIG_LEN );
  mpSetDigit( VMoA,     3, VM_MAX_DIG_LEN );
}
/* End of function "VMDiffieHellman::VMDiffieHellman"
/*****************************************************************************/



/*****************************************************************************/
/* Check-in history */
/*
 *$Log:   $
*/
/*****************************************************************************/