Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

Build your own cryptographically safe server/client protocol

, 21 Jun 2006 CPOL
This article presents all you need to implement your own secure protocol using variable keysize RSA encryption/decryption, digital signing, multi precision library, Diffie-Hellman key exchange, Rijndael, and more. Everything is converged into a secure IOCP client/server chat server.
// MyCryptLib.cpp: implementation of the MyCryptLib class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "SecureChat.h"
#include "MyCryptLib.h"

// For timeGetTime();timeBeginPeriod() timeEndPeriod()
#include  <Mmsystem.h>
#pragma comment( lib, "winmm" )


#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

MyCryptLib::MyCryptLib()
{
	m_mtIndex=0;
	m_bSeeded=FALSE;
}

MyCryptLib::~MyCryptLib()
{

}


// Used to Speed up prime nr generator. 
const DWORD MyCryptLib::SMALL_PRIMES[] =  {
	3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 
	47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 
	103, 107, 109, 113,127, 131, 137, 139, 149, 151, 
	157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 
	211, 223, 227, 229,233, 239, 241, 251, 257, 263, 
	269, 271, 277, 281,283, 293, 307, 311, 313, 317, 
	331, 337, 347, 349,353, 359, 367, 373, 379, 383, 
	389, 397, 401, 409,419, 421, 431, 433, 439, 443, 
	449, 457, 461, 463,467, 479, 487, 491, 499, 503, 
	509, 521, 523, 541,547, 557, 563, 569, 571, 577, 
	587, 593, 599, 601,607, 613, 617, 619, 631, 641, 
	643, 647, 653, 659,661, 673, 677, 683, 691, 701, 
	709, 719, 727, 733,739, 743, 751, 757, 761, 769, 
	773, 787, 797, 809,811, 821, 823, 827, 829, 839, 
	853, 857, 859, 863,877, 881, 883, 887, 907, 911, 
	919, 929, 937, 941,947, 953, 967, 971, 977, 983, 
	991, 997,
};

const UINT MyCryptLib::_NUMBEROFPRIMES_=sizeof(MyCryptLib::SMALL_PRIMES)/sizeof(DWORD);


// SHA konstants. 
#ifdef SYSTEM_LITTLE_ENDIAN
const UINT MyCryptLib::_SHA_MASK_[4]={0x00000000, 0x000000ff, 0x0000ffff, 0x00ffffff};
const UINT MyCryptLib::_SHA_BITS_[4]={0x00000080, 0x00008000, 0x00800000, 0x80000000};
#else
const UINT MyCryptLib::_SHA_MASK_[4]={0x00000000, 0xff000000, 0xffff0000, 0xffffff00};
const UINT MyCryptLib::_SHA_BITS_[4]={0x80000000, 0x00800000, 0x00008000, 0x00000080};
#endif

/*
*	Add(DWORD C[], DWORD A[], DWORD B[], UINT nSize)
-----------------------------------------------------
*  Addition for very big numbers A,B,C
*  Assumes that A, B and C, have the same size. 
*  nSize = number of bytes. 
*  Adds A & B and put the result in C. 
*  Reference  Knuth, Donald. 1968. The Art of Computer Programming
*  Returns 0 if success 1 if overflow. 
*/

DWORD MyCryptLib::BNAdd(DWORD C[], const DWORD A[], const DWORD B[], const UINT nSize)
{	
	DWORD k=0; // carry 
	for (UINT i = 0; i < nSize; i++)
	{
		C[i] = A[i] + k;
		if(C[i]>=k)// detect overflow and set k
			k=0;
		else
			k=1;

		C[i] += B[i];
		if (C[i] < B[i]) // Detect overflow again. 
			k++;	
	}
	return k;
}


// Returns ceil(x) as a non-negative integer or 0 if x < 0 
UINT MyCryptLib::BNUiceil(double x)
{
	UINT c;
	if (x < 0) return 0;
	c = (UINT)x;
	if ((x - c) > 0.0)
		c++;
	return c;
}



/*
*	SHA1 Implementation algoritm from, the algorith is taken from 
*	Federal Information
*	Processing Standards Publication 180-1, 1995 April 17
*  http://www.itl.nist.gov/fipspubs/fip180-1.htm
*  
*/


/*
* Sha1Hash(unsigned char *_pOutDigest, const unsigned char *_pData,UINT nSize)
*
*
* Computes SH1 hash given data (_pData) of size nSize.  	
*  
* _pOutDigest is an buffer of size SHA1_DIGEST_SIZE (20) which will be filled with 
* the digestvalue. 
*
*
*/

void MyCryptLib::SHA1Hash(unsigned char *_pOutDigest, const unsigned char *_pData,UINT nSize)
{

	// Be safe
	if ( !_pOutDigest || !_pData )
		return;

	SHA1_STATETYPE csha1;
	memset(&csha1,0,sizeof(csha1));
	SHA1_Start(&csha1);
	SHA1_Hash(_pData,nSize,&csha1);
	SHA1_Finish(_pOutDigest,&csha1);
}


void MyCryptLib::SHA1_Transform(SHA1_STATETYPE* _pcsha1)
{

	UINT   w[80], i, a, b, c, d, e, t;

	for (i = 0; i < SHA1_BLOCK_SIZE / 4; ++i)
		w[i] = SHA_BLOCK32(_pcsha1->wbuf[i]);

	for (i = SHA1_BLOCK_SIZE / 4; i < 80; ++i)
		w[i] = rotate32(w[i - 3] ^ w[i - 8] ^ w[i - 14] ^ w[i - 16], 1);

	a = _pcsha1->hash[0];
	b = _pcsha1->hash[1];
	c = _pcsha1->hash[2];
	d = _pcsha1->hash[3];
	e = _pcsha1->hash[4];

	for(i = 0; i < 20; ++i)
	{
		sha_round(F0to19, 0x5a827999);    
	}

	for(i = 20; i < 40; ++i)
	{
		sha_round(F20to39, 0x6ed9eba1);
	}

	for(i = 40; i < 60; ++i)
	{
		sha_round(F40to59, 0x8f1bbcdc);
	}

	for(i = 60; i < 80; ++i)
	{
		sha_round(F60to79, 0xca62c1d6);
	}

	_pcsha1->hash[0] += a; 
	_pcsha1->hash[1] += b; 
	_pcsha1->hash[2] += c; 
	_pcsha1->hash[3] += d; 
	_pcsha1->hash[4] += e;

}
void MyCryptLib::SHA1_Start(SHA1_STATETYPE *_pcsha1)
{

	_pcsha1->hash[0] = 0x67452301;
	_pcsha1->hash[1] = 0xefcdab89;
	_pcsha1->hash[2] = 0x98badcfe;
	_pcsha1->hash[3] = 0x10325476;
	_pcsha1->hash[4] = 0xc3d2e1f0;
	_pcsha1->count[0] = 0;
	_pcsha1->count[1] = 0;
}

void MyCryptLib::SHA1_Finish(unsigned char* _pShaValue, SHA1_STATETYPE* _pcsha1)
{
	UINT    i = (UINT)(_pcsha1->count[0] & (SHA1_BLOCK_SIZE - 1));
	_pcsha1->wbuf[i >> 2] = (_pcsha1->wbuf[i >> 2] & _SHA_MASK_[i & 3]) | _SHA_BITS_[i & 3];

	if(i > SHA1_BLOCK_SIZE - 9)
	{
		if(i < 60) _pcsha1->wbuf[15] = 0;
		SHA1_Transform(_pcsha1);
		i = 0;
	}
	else   
		i = (i >> 2) + 1;

	while(i < 14) 
		_pcsha1->wbuf[i++] = 0;


	_pcsha1->wbuf[14] = SHA_BLOCK32((_pcsha1->count[1] << 3) | (_pcsha1->count[0] >> 29));
	_pcsha1->wbuf[15] = SHA_BLOCK32(_pcsha1->count[0] << 3);

	SHA1_Transform(_pcsha1);


	for(i = 0; i < SHA1_DIGEST_SIZE; ++i)
		_pShaValue[i] = (unsigned char)(_pcsha1->hash[i >> 2] >> 8 * (~i & 3));
}


void MyCryptLib::SHA1_Hash(const unsigned char *_pData, unsigned int _iSize, SHA1_STATETYPE* _pcsha1)
{
	UINT ipos = (UINT)(_pcsha1->count[0] & (SHA1_BLOCK_SIZE - 1));
	UINT ispace = SHA1_BLOCK_SIZE - ipos;
	unsigned char *pData=(unsigned char *)_pData;
	if((_pcsha1->count[0] += _iSize) < _iSize)
		++(_pcsha1->count[1]);
	while(_iSize >= ispace)     
	{
		memcpy(((unsigned char*)_pcsha1->wbuf) + ipos, pData, ispace);
		ipos = 0; 
		_iSize -= ispace; 
		pData += ispace; 
		ispace = SHA1_BLOCK_SIZE; 
		SHA1_Transform(_pcsha1);
	}	
	memcpy(((unsigned char*)_pcsha1->wbuf) + ipos, pData, _iSize);
}



/*
*	BNAdddw(DWORD w[], const DWORD u[], DWORD v, UINT nSize)
-----------------------------------------------------
*  Addition for very big numbers w,u
*  w=u+v. 
*  nSize = number of bytes. 
*  Reference  Knuth, Donald. 1968. The Art of Computer Programming
*  Returns 0 if success 1 if overflow. 
*/
inline DWORD MyCryptLib::BNAdddw(DWORD w[], const DWORD u[], DWORD v, UINT nSize)
{
	DWORD k=0;
	w[0] = u[0] + v;
	k=(w[0] >= v) ? 0:1;	
	for (UINT j = 1; j < nSize; j++)
	{
		w[j] = u[j] + k;
		k=(w[j] >= k) ? 0:1;
	}
	return k;	
}

/*
*	BNSubtract(DWORD C[], DWORD A[], DWORD B[], UINT nSize)
-----------------------------------------------------
*  Subtraction  for very big numbers A,B,C
*  Assumes that A, B and C, have the same size. 
*  nSize = number of bytes. 
*  Calculates C = A - B where A >= B
*  Reference  Knuth, Donald. 1968. The Art of Computer Programming
*  Returns 0 if success 1 if overflow. 
*/

DWORD MyCryptLib::BNSubtract(DWORD C[], const DWORD A[], const DWORD B[],const UINT nSize)
{
	DWORD  k=0;
	for (UINT i = 0; i < nSize; i++)
	{
		C[i] = A[i] - k;
		if (C[i] > _MAXIMUMNR_ - k) // detect underflow (borrow) 
			k = 1;
		else
			k = 0;
		C[i] -= B[i];
		if (C[i] > _MAXIMUMNR_  - B[i])
			k++;
	}	
	return k;
}

/*
*	BNSubtract(DWORD w[], const DWORD u[], DWORD v, UINT nSize)
-----------------------------------------------------
*  Subtraction  for very big numbers u to an normal DWORD. 
*  Assumes that w,u, have the same size. 
*  nSize = number of bytes. 
*  Calculates w=u-v
*  Reference  Knuth, Donald. 1968. The Art of Computer Programming
*  Returns 0 if success 1 if overflow. 
*/



DWORD MyCryptLib::BNSubtractdw(DWORD w[], const DWORD u[], DWORD v, UINT nSize)
{
	DWORD k=0;
	w[0] = u[0] - v;
	if (w[0] > _MAXIMUMNR_- v)
		k = 1;
	else
		k = 0;
	for (UINT j = 1; j < nSize; j++)
	{
		w[j] = u[j] - k;
		if (w[j] > _MAXIMUMNR_ - k)
			k = 1;
		else
			k = 0;
	}	
	return k;	
}


CString MyCryptLib::BNPrint(const DWORD *p, UINT nSize)
{
	CString stmp="";
	CString sRet="";
	// Trim leading zeroes 
	while (nSize--)
	{
		if (p[nSize] != 0)
			break;
	}
	nSize++;

	// Catch empty len to show 0 
	if ( nSize==0 ) 
		nSize=1;

	while ( nSize-- )
	{

		stmp.Format("%08lx ", p[nSize]);
		sRet+=stmp;
	}

	return sRet;
}


CString MyCryptLib::BNPrintC(const DWORD *p, UINT nSize)
{
	CString stmp="";
	CString sRet;
	sRet.Format("[%i] = {\r\n",nSize);
	int iNrPrinted=0;
	for ( UINT i=0; i<nSize; i++ )
	{

		stmp.Format("0x%08lx, ", p[i]);
		iNrPrinted++;
		sRet+=stmp;
		if(iNrPrinted%6==0)
			sRet+="\r\n";
	}
	sRet+="};";
	return sRet;	
}

/*
*	Returns an CString version of the number
*
*/
CString MyCryptLib::BNToString(const DWORD *a, UINT nSize,UINT nBase)
{

	// Is the number is Zero 
	if ( BNIsZero(a, nSize) )
		return "0";

	CString sRet=""; // return String 

	const char DEC_DIGITS[] = "0123456789";
	const char HEX_DIGITS[] = "0123456789abcdef";
	const char *cdigits;
	double dFactor=0.0;

	// Setup the data according to nBase
	switch (nBase)
	{
	case 10:
		cdigits = DEC_DIGITS;
		dFactor = 2.40824;	/* log(256)/log(10)=2.40824 */
		break;
	case 16:
		cdigits = HEX_DIGITS;
		dFactor = 2.0;	/* log(256)/log(16)=2.0 */
		break;
	default:
		return "Base must be 10 or 16";
	}
	// Convert to 8 bits octtlets (is easier to handle)
	UINT nbytes = nSize * sizeof(DWORD);
	BYTE* pOct=NULL;
	pOct=new BYTE[nbytes];
	// be safe
	if ( pOct==NULL )
		return "Not enough memory: pOct=new BYTE[nbytes] Failed..";
	memset(pOct,0,nbytes);
	UINT NumberOfOctNeeded= BNToOctets(a,nSize,pOct,nbytes);

	// Create temporary place
	UINT NewOctLength=BNUiceil(NumberOfOctNeeded*dFactor);
	BYTE* pNewOct=new BYTE[NewOctLength];
	// Be safe 
	if ( pNewOct==NULL )
	{
		delete[] pOct;
		return "Not enough memory: pNewOct=new BYTE[NewOctLength] Failed..";
	}
	memset(pNewOct,0,NewOctLength);
	// Transform 
	UINT t=0;
	UINT i=0;
	for (i  = 0; i < nbytes; i++)
	{
		t = pOct[i];
		for (UINT j = NewOctLength; j > 0; j--)
		{
			t += (unsigned long)(pNewOct[j-1] * 256);
			pNewOct[j-1] = (unsigned char)(t % nBase);
			t /= nBase;
		}
	}

	// Find index of leading significant digit 
	UINT isig=0;
	for ( isig = 0; isig < NewOctLength; isig++ )
		if (pNewOct[isig])
			break;
	// number of charachters needed.. 	
	UINT nchars = NewOctLength - isig;

	for(i=0;i<nchars;i++)
		sRet+=cdigits[pNewOct[isig+i]];


	delete[] pOct;
	delete[] pNewOct;
	return sRet;
}



/*
*	Returns True if a == b else false
*/
int MyCryptLib::BNIsEqual(const DWORD a[], const DWORD b[], UINT nSize)
{
	if ( nSize <= 0 ) 
		return FALSE;

	while ( nSize-- )
	{
		if ( a[nSize] != b[nSize] )
			return FALSE;	
	}	
	return TRUE;
}

/*
*	Makes A=0
*/
void MyCryptLib::BNSetZero(DWORD A[], UINT nSize)
{
	while ( nSize-- )
		A[nSize] = 0;
}


/*
*	Return True if a==0
*/
int MyCryptLib::BNIsZero(const DWORD a[], UINT nSize)
{
	if (nSize == 0) 
		return FALSE;

	for (UINT i = 0; i < nSize; i++)	
	{
		if (a[i] != 0)
			return FALSE;	
	}

	return TRUE;
}

/*
*	Makes a=b
*/

void MyCryptLib::BNSetEqual(DWORD a[], const DWORD b[], UINT nSize)
{
	for (UINT i = 0; i < nSize; i++)
	{
		a[i] = b[i];
	}	
}

/*
* Makes a=d
* Where d is an normal DWORD. 
*/
void MyCryptLib::BNSetEqualdw(DWORD a[], const DWORD d, UINT nSize)
{
	if(nSize<=0)
		return;
	BNSetZero(a,nSize);
	a[0]=d;
}


int MyCryptLib::BNCompare(const DWORD a[], const DWORD b[], UINT nSize)
{
	if ( nSize <= 0 ) 
		return 0;
	while (nSize--)
	{
		if (a[nSize] > b[nSize])
			return 1;	// Grater than 
		if (a[nSize] < b[nSize])
			return -1;	// Less Than 
	}
	return 0;// equal 
}

/* Returns sign of (a - b) where b is an DWORD */
inline int MyCryptLib::BNComparedw(const DWORD a[], DWORD b, UINT nSize)
{

	// Be Safe 
	if (nSize == 0) return (b ? -1 : 0);

	for (UINT i = 1; i < nSize; i++)
	{
		if (a[i] != 0)
			return 1;	// Greater than 
	}

	if ( a[0] < b) 
		return -1;	// Less than 
	else if ( a[0] > b )
		return 1;		// Greater 

	return 0; //equal  	
}


/*  BNShiftLeft(DWORD a[], const DWORD *b, DWORD x, DWORD nSize)
*	Computes a = b << x 
*  returns carry 
*/
inline DWORD MyCryptLib::BNShiftLeft(DWORD a[], const DWORD *b, UINT x, UINT nSize)
{
	DWORD mask, carry, nextcarry;
	UINT i=0;

	if ( x >= sizeof(DWORD)*8 )
		return 0;

	mask = _HIBITMASK_;
	for (i = 1; i < x; i++)
	{
		mask = (mask >> 1) | mask;
	}
	if (x == 0) mask = 0x0;

	UINT y = (sizeof(DWORD)*8) - x;
	carry = 0;
	for (i = 0; i < nSize; i++)
	{
		nextcarry = (b[i] & mask) >> y;
		a[i] = b[i] << x | carry;
		carry = nextcarry;
	}

	return carry;
}


/* BNShiftRight(DWORD a[], const DWORD *b, DWORD x, DWORD nSize)
* Computes a = b >> x 
* returns carry 
*
*/
inline DWORD MyCryptLib::BNShiftRight(DWORD a[], const DWORD *b, DWORD x, DWORD nSize)
{

	DWORD mask, carry, nextcarry;
	UINT i=0;
	// be safe. 
	if ( x >= (sizeof(DWORD)*8) )
		return 0;

	// Create mask
	mask = 0x1;
	for (i = 1; i < x; i++)
	{
		mask = (mask << 1) | mask;
	}
	if (x == 0) mask = 0x0;

	UINT y = (sizeof(DWORD)*8) - x;
	carry = 0;
	i = nSize;
	while (i--)
	{
		nextcarry = (b[i] & mask) << y;
		a[i] = b[i] >> x | carry;
		carry = nextcarry;
	}

	return carry;	
}




/* BNDivdw(DWORD q[], const DWORD a[], DWORD b, UINT nSize)
*   Calculates quotient q = a div b
*   Returns remainder r = a mod b
*   a,q are big numbers of nSize
*	 r, a are normal DWORDS.
*
*/
inline DWORD MyCryptLib::BNDividedw(DWORD q[], const DWORD u[], DWORD v, UINT nSize)
{
	UINT j;
	DWORD t[2], r;
	UINT shift;
	DWORD bitmask, overflow, *uu;

	if (nSize == 0) return 0;
	if (v == 0)	return 0;

	bitmask = _HIBITMASK_;
	for (shift = 0; shift < (sizeof(DWORD)*8); shift++)
	{
		if (v & bitmask)
			break;
		bitmask >>= 1;
	}	
	v <<= shift;
	overflow = BNShiftLeft(q, u, shift, nSize);
	uu = q;
	r = overflow;	
	j = nSize;
	while (j--)
	{
		t[0] = uu[j];
		t[1] = r;
		overflow = BNDivideHelper(&q[j], &r, t, v);
	}
	r >>= shift;	
	return r;
}







/*
*	BNMultiply(DWORD C[], DWORD A[], DWORD B[], UINT nSize)
-----------------------------------------------------
*  Multiplication for very big numbers A,B,C
*  Assumes that A, B  have the same size, and C have the size of 2*nSize; 
*  nSize = number of bytes. 
*  Calculates C = A - B where A >= B
*  Reference  Knuth, Donald. 1968. The Art of Computer Programming
*  Returns 0 if success 1 if overflow. 
* v=B 
* u=A
*/

DWORD MyCryptLib::BNMultiply(DWORD C[], const DWORD A[], const DWORD B[], const UINT nSize)
{
	DWORD  k, tmp[2];
	UINT m, n;
	m = n = nSize;
	for ( UINT i = 0; i < 2 * m; i++)
		C[i] = 0;

	for ( UINT j = 0; j < n; j++)
	{
		if (B[j] == 0) // Zero multiplication ?
		{
			C[j + m] = 0;
		}
		else
		{
			k = 0;
			for (UINT i = 0; i < m; i++)
			{
				// Perform t = A[i] * B[i]+C[i+j] + k
				// use Help function for code cleaness. 
				BNMultiplyHelper(tmp, A[i], B[j]);
				tmp[0] += k;
				if (tmp[0] < k) // Overflow? 
					tmp[1]++;
				tmp[0] += C[i+j];
				if (tmp[0] < C[i+j])
					tmp[1]++;
				k = tmp[1];
				C[i+j] = tmp[0];

			}	
			C[j+m] = k;
		}
	}	
	return 0;
}

/*
*	w=u*v where u is an multipresition nr and v is an normal number. 
*/

DWORD MyCryptLib::BNMultiplydw(DWORD w[], const DWORD u[], DWORD v, UINT nSize)
{
	DWORD k, t[2];
	UINT j;
	if (v == 0) 
	{
		for (j = 0; j < nSize; j++)
			w[j] = 0;
		return 0;
	}
	k = 0;
	for (j = 0; j < nSize; j++)
	{
		BNMultiplyHelper(t, u[j], v);
		w[j] = t[0] + k;
		if (w[j] < k) // Overflow ? 
			t[1]++;
		k = t[1];
	}
	return k;	
}

/*
* Compute w = w - qv
* where w = (WnW[n-1]...W[0])
*  return modified Wn.
*/
inline DWORD MyCryptLib::BNMultSub(DWORD wn, DWORD w[], const DWORD v[], DWORD q, UINT n)
{
	DWORD k, t[2];
	UINT i;

	if ( q == 0 )	// Nothing to do 
		return wn;

	k = 0;

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

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

	return wn;	
}


/*
*	 Function Helper for numeric Multiplication 
*   Reference: Arbitrary Precision Computation
*	 http://numbers.computation.free.fr/Constants/constants.html
*   Splits the x,y to half and performin the multplication of each half. 
*/
inline int MyCryptLib::BNMultiplyHelper(DWORD p[2], const DWORD x, const DWORD y)
{
#ifdef _USEOPTIMIZEASM_
	__asm
	{
		mov eax, x
			xor edx, edx
			mul y
			; Product in edx:eax
			mov ebx, p
			mov dword ptr [ebx], eax
			mov dword ptr [ebx+4], edx
	}
#else 
	DWORD x0, y0, x1, y1;
	DWORD t, u, carry;
	x0 = LOHALF(x);
	x1 = HIHALF(x);
	y0 = LOHALF(y);
	y1 = HIHALF(y);
	p[0] = x0 * y0;
	t = x0 * y1;
	u = x1 * y0;
	t += u;
	if (t < u)
		carry = 1;
	else
		carry = 0;
	carry = TOHIGH(carry) + HIHALF(t);
	t = TOHIGH(t);
	p[0] += t;
	if (p[0] < t)
		carry++;
	p[1] = x1 * y1;
	p[1] += carry;

#endif
	return 0;
}
/*	
*  Function Helper 
* Compute uu = uu - q(v1v0) 
* 
*/
inline void MyCryptLib::BNMultSubHelper(DWORD uu[], DWORD qhat, DWORD v1, DWORD v0)
{
	DWORD p0, p1, t;
	p0 = qhat * v0;
	p1 = qhat * v1;
	t = p0 + TOHIGH(LOHALF(p1));
	uu[0] -= t;
	if (uu[0] > _MAXIMUMNR_ - t)
		uu[1]--;	// Borrow
	uu[1] -= HIHALF(p1);

}
/*	Help function for BNDivide (For code cleaness) 
* Returns true if Qhat is too big
* i.e. if (Qhat * Vn-2) > (b.Rhat + Uj+n-2)
* 
*/

inline int MyCryptLib::BNQhatTooBigHelper(DWORD qhat, DWORD rhat, DWORD vn2, DWORD ujn2)
{
	DWORD t[2];
	BNMultiplyHelper(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;	
}


/*
*	Function Helper for numeric Multiplication 
*  Computes quotient q = u / v, remainder r = u mod v
*  u an DWORD[2].
*  v,q,r are normal DWORDs. 
*  Assumes that v1>=b/2 where b is the size of half DWORD
*
*/

inline DWORD MyCryptLib::BNDivideHelper(DWORD *q, DWORD *r, const DWORD u[], DWORD v)
{
	DWORD q2;
	DWORD qhat, rhat, t, v0, v1, u0, u1, u2, u3;
	DWORD uu[2];
	DWORD B= _MAXHALFNR_+1;

	if (!(v & _HIBITMASK_))
	{	
		*q = *r = 0;
		return _MAXIMUMNR_;
	}

	v0 = LOHALF(v);
	v1 = HIHALF(v);
	u0 = LOHALF(u[0]);
	u1 = HIHALF(u[0]);
	u2 = LOHALF(u[1]);
	u3 = HIHALF(u[1]);
	qhat = (u3 < v1 ? 0 : 1);
	if (qhat > 0)
	{
		rhat = u3 - v1;
		t = TOHIGH(rhat) | u2;
		if (v0 > t)
			qhat--;
	}
	uu[0] = u[1];
	uu[1] = 0;		
	if (qhat > 0)
	{

		BNMultSubHelper(uu, qhat, v1, v0);
		if (HIHALF(uu[1]) != 0)
		{
			uu[0] += v;
			uu[1] = 0;
			qhat--;
		}
	}
	q2 = qhat;
	t = uu[0];
	qhat = t / v1;
	rhat = t - qhat * v1;
	t = TOHIGH(rhat) | u1;
	if ( (qhat == B) || (qhat * v0 > t) )
	{
		qhat--;
		rhat += v1;
		t = TOHIGH(rhat) | u1;
		if ((rhat < B) && (qhat * v0 > t))
			qhat--;
	}
	uu[1] = HIHALF(uu[0]);	
	uu[0] = TOHIGH(LOHALF(uu[0])) | u1;	
	BNMultSubHelper(uu, qhat, v1, v0);
	if ( HIHALF(uu[1]) != 0 )
	{	
		qhat--;
		uu[0] += v;
		uu[1] = 0;
	}
	*q = TOHIGH(qhat);
	t = uu[0];
	qhat = t / v1;
	rhat = t - qhat * v1;
	t = TOHIGH(rhat) | u0;
	if ( (qhat == B) || (qhat * v0 > t) )
	{
		qhat--;
		rhat += v1;
		t = TOHIGH(rhat) | u0;
		if ((rhat < B) && (qhat * v0 > t))
			qhat--;
	}
	uu[1] = HIHALF(uu[0]);
	uu[0] = TOHIGH(LOHALF(uu[0])) | u0;	
	BNMultSubHelper(uu, qhat, v1, v0);
	if (HIHALF(uu[1]) != 0)
	{	
		qhat--;
		uu[0] += v;
		uu[1] = 0;
	}
	*q |= LOHALF(qhat);
	*r = uu[0];
	return q2;
}


/*
*	BNDivide(DWORD q[], DWORD r[], const DWORD u[], UINT usize, DWORD v[], UINT vsize)
-----------------------------------------------------
*  Division for very big numbers 
*
* Computes quotient q = u / v and remainder r = u mod v
* where q, r, u are multiple precision digits
* all of udigits and the divisor v is vdigits.
*/
int MyCryptLib::BNDivide(DWORD q[], DWORD r[], const DWORD u[], UINT usize, DWORD v[], UINT vsize)
{
	UINT shift;
	int n, m, j;
	DWORD bitmask, overflow;
	DWORD qhat, rhat, t[2];
	DWORD *uu, *ww;
	int qhatOK, cmp;
	BNSetZero(q, usize);
	BNSetZero(r, usize);

	//  Work out exact sizes of u and v 
	n = (int)BNSizeof(v, vsize);
	m = (int)BNSizeof(u, usize);
	m -= n;

	// special cases 
	if ( n == 0 )
		return -1;	// divide by zero

	if ( n == 1 )
	{	// Short div is better 
		r[0] = BNDividedw(q, u, v[0], usize);
		return 0;
	}

	if ( m < 0 )
	{   // set r=u
		BNSetEqual(r, u, usize);
		return 0;
	}

	if ( m == 0 )
	{
		cmp = BNCompare(u, v, (UINT)n);
		if (cmp < 0)
		{
			BNSetEqual(r, u, usize);
			return 0;
		}
		else if (cmp == 0)
		{
			BNSetEqualdw(q, 1, usize);
			return 0;
		}
	}

	bitmask =  _HIBITMASK_;
	for ( shift = 0; shift < 32; shift++ )
	{
		if (v[n-1] & bitmask)
			break;
		bitmask >>= 1;
	}

	overflow = BNShiftLeft(v, v, shift, n);
	overflow = BNShiftLeft(r, u, shift, n + m);
	t[0] = overflow;	
	uu = r;	
	for ( j = m; j >= 0; j-- )
	{
		qhatOK = 0;
		t[1] = t[0];
		t[0] = uu[j+n-1];
		overflow = BNDivideHelper(&qhat, &rhat, t, v[n-1]);
		if ( overflow )
		{	
			rhat = uu[j+n-1];
			rhat += v[n-1];
			qhat = _MAXIMUMNR_;
			if (rhat < v[n-1])	
				qhatOK = 1;
		}
		if (qhat && !qhatOK && BNQhatTooBigHelper(qhat, rhat, v[n-2], uu[j+n-2]))
		{	
			rhat += v[n-1];
			qhat--;
			if (!(rhat < v[n-1]))
				if (BNQhatTooBigHelper(qhat, rhat, v[n-2], uu[j+n-2]))
					qhat--;
		}
		ww = &uu[j];
		overflow = BNMultSub(t[1], ww, v, qhat, (UINT)n);
		q[j] = qhat;
		if (overflow)
		{	
			q[j]--;
			overflow = BNAdd(ww, ww, v, (UINT)n);
		}
		t[0] = uu[j+n-1];	
	}	
	for (j = n; j < m+n; j++)
		uu[j] = 0;
	BNShiftRight(r, r, shift, n);
	BNShiftRight(v, v, shift, n);
	return 0;
}

inline DWORD MyCryptLib::BNModdw(DWORD a[], DWORD d, UINT nSize)
{
	DWORD *q=NULL;
	DWORD r = 0;
	// allocate temporary ultiprecision integer of nSize*2. 
	q = BNAlloc(nSize * 2);
	if(q!=NULL)
	{
		r = BNDividedw(q, a, d, nSize);
		BNFree(&q);
	}
	return r;
}

/*	
* BNMod(DWORD r[], const DWORD u[], UINT nUSize, DWORD v[], UINT nVSize)
* Computes r = u mod v
* where r, v are multiprecision integers of length vdigits
* and u is a multiprecision integer of length udigits.
* r may overlap v.
*/

DWORD MyCryptLib::BNMod(DWORD r[], const DWORD u[], UINT nUSize, DWORD v[], UINT nVSize)
{
	DWORD *qq, *rr;
	UINT nn = max(nUSize, nVSize);
	qq = BNAlloc(nUSize);
	rr = BNAlloc(nn);

	// rr[nn] = u mod v 
	BNDivide(qq, rr, u, nUSize, v, nVSize);
	// r=rr
	BNSetEqual(r, rr, nVSize);
	BNFree(&rr);
	BNFree(&qq);
	return 0;
}


/*	Computes a = (x * y) mod m */
DWORD MyCryptLib::BNModMult(DWORD a[], const DWORD x[], const DWORD y[], const DWORD m[], UINT nSize)
{
	DWORD *p;
	DWORD *tm;
	p = BNAlloc(nSize * 2);
	tm = BNAlloc(nSize);
	BNSetEqual(tm, m, nSize);
	BNMultiply(p, x, y, nSize);
	BNMod(a, p, nSize * 2, tm, nSize);
	BNFree(&p);
	BNFree(&tm);
	return 0;	
}




/* BNSizeof(const DWORD A[], UINT nSize)
*
* Returns size of significant digits in A.
*/

UINT MyCryptLib::BNSizeof(const DWORD A[], UINT nSize)
{
	while ( nSize-- )
	{
		if ( A[nSize] != 0 )
			return (++nSize);
	}
	return 0;
}


// Returns number of significant bits in d 
UINT MyCryptLib::BNBitLength(const DWORD *d, UINT nSize)
{
	UINT n, i, bits;
	DWORD mask;

	// be Safe 
	if ( !d || nSize == 0 )
		return 0;

	// Get The size of it 
	n = BNSizeof(d, nSize);
	if (0 == n) return 0;

	DWORD dwLastWord= d[n-1];
	DWORD dwDummY=0;
	mask =_HIBITMASK_;
	for (i = 0; mask > 0;i++)
	{
		if (dwLastWord & mask)
			break;
		mask >>= 1;
	}

	bits = n * (sizeof(DWORD)*8) - i;

	return bits;
}

/*
*	Alloc and free is made inside the class for future optimization 
*  e.g reusing allocated memory etc.. 
*/

inline DWORD * MyCryptLib::BNAlloc(UINT nSize)
{
	DWORD* p=NULL;
	if(nSize<=0)
		return NULL;

	p=(DWORD*)calloc(nSize, sizeof(DWORD));
	return p; 
}

inline void MyCryptLib::BNFree(DWORD **p)
{
	if (*p!=NULL)
	{
		free(*p);
		*p = NULL;
	}
}


/* 
* Creates an Big (multiprecision) Number from an nOctBytes octects array
* Returns actual number of digits set. 
* 
* This funcion is normaly used to import data from other sources (for test porpose) 
* 
*/
UINT MyCryptLib::BNFromOctets(DWORD a[], UINT nSize, const unsigned char *c, UINT nOctBytes)
{
	UINT i;
	int j, k;
	DWORD t;
	DWORD t2;
	BNSetZero(a, nSize);

	/* Read in octets, least significant first */
	/* i counts into big_d, j along c, and k is # bits to shift */
	for (i = 0, j = nOctBytes - 1; (i < nSize)&&(j >= 0); i++)
	{
		t = 0;
		for (k = 0; (j >= 0) && (k < (sizeof(DWORD)*8)); j--, k += 8)
		{
			t2=((DWORD)c[j]);
			t |= t2 << k;
		}
		a[i] = t;
	}

	return i;
}

/*
* Convert an big Number a into an array of octets, in big-endian order,
* padding to nbytes or truncating if necessary.
* Return number of octets required excluding leading zero bytes.
*/

UINT MyCryptLib::BNToOctets(const DWORD a[], UINT nSize, unsigned char *c, UINT nbytes)
{
	int j, k, len;
	DWORD t;
	UINT i, noctets, nbits;

	nbits = BNBitLength(a, nSize);
	noctets = (nbits + 7) / 8;

	len = (int)nbytes;

	for (i = 0, j = len - 1; i < nSize && j >= 0; i++)
	{
		t = a[i];
		for (k = 0; j >= 0 && k < (sizeof(DWORD)*8); j--, k += 8)
			c[j] = (unsigned char)(t >> k);
	}

	for ( ; j >= 0; j--)
		c[j] = 0;

	return noctets;	
}



UINT MyCryptLib::BNFromDecimal(DWORD a[], UINT nSize, const char *s,UINT nStringLength)
{


	BNSetZero(a, nSize);
	//  Create some temp storage for int values.
	UINT newlen = BNUiceil(nStringLength * 0.41524);	// log(10)/log(256)=0.41524 
	BYTE* ptmp=NULL;
	ptmp=new BYTE[newlen];

	memset(ptmp,0,newlen);
	if (ptmp==NULL) 
		return 0; //FAILED 

	// Go through zero-terminated string
	DWORD t=0;
	for (UINT i = 0; s[i]; i++)
	{
		t = s[i] - '0';
		if (t > 9 || t < 0) continue;
		for (UINT j = newlen; j > 0; j--)
		{
			t += (DWORD)(ptmp[j-1] * 10);
			ptmp[j-1] = (unsigned char)(t & 0xFF);
			t >>= 8;
		}
	}

	// now Convert bytes to big digits 
	UINT AcctualNumberofbytes = BNFromOctets(a, nSize, ptmp, newlen);

	// Clean up 
	delete[] ptmp;

	return AcctualNumberofbytes;
}

UINT MyCryptLib::BNFromHex(DWORD a[], UINT nSize, const char *s, UINT nStringLength)
{

	size_t newlen;
	BYTE  *newdigits;
	size_t n;
	unsigned long t;
	size_t i, j;

	BNSetZero(a, nSize);

	// temporary 
	n = strlen(s);
	newlen = BNUiceil(n * 0.5);	// log(16)/log(256)=0.5 
	newdigits = new BYTE[newlen];

	if (newdigits==NULL)
		return 0; 

	memset(newdigits,0,newlen);
	// Work through zero-terminated string 
	for ( i = 0; s[i]; i++ )
	{
		t = s[i];
		if ((t >= '0') && (t <= '9')) t = (t - '0');
		else if ((t >= 'a') && (t <= 'f')) t = (t - 'a' + 10);
		else if ((t >= 'A') && (t <= 'F')) t = (t - 'A' + 10);
		else continue;
		for (j = newlen; j > 0; j--)
		{
			t += (unsigned long)newdigits[j-1] << 4;
			newdigits[j-1] = (unsigned char)(t & 0xFF);
			t >>= 8;
		}
	}

	// Convert bytes to big digits 
	n = BNFromOctets(a, nSize, newdigits, newlen);

	// Clean up 
	delete[] newdigits;

	return n;


}


/*	Computes y = x^e mod m */
/*	Binary left-to-right method */
int MyCryptLib::BNModExp(DWORD yout[], const DWORD x[], const DWORD e[], const DWORD m[], UINT nSize)
{
	// Be safe
	if ( nSize <= 0 ) 
		return -1;

	DWORD mask;
	UINT n;
	DWORD *t1, *t2, *t3, *tm, *y; //temporary variables 

	// Create some temporary variables
	const UINT nn = nSize * 2;

	t1 = BNAlloc(nn);
	if(t1==NULL)
	{
		return -1;
	}
	t2 = BNAlloc(nn);
	if(t2==NULL)
	{
		BNFree(&t1);
		return -1;
	}
	t3 = BNAlloc(nn);
	if(t3==NULL)
	{
		BNFree(&t1);
		BNFree(&t2);
		return -1;
	}
	tm = BNAlloc(nSize);
	if(tm==NULL)
	{
		BNFree(&t1);
		BNFree(&t2);
		BNFree(&t3);
		return -1;
	}
	y = BNAlloc(nSize);
	if(y==NULL)
	{
		BNFree(&t1);
		BNFree(&t2);
		BNFree(&t3);
		BNFree(&tm);
		return -1;
	}

	BNSetEqual(tm, m, nSize);

	//  Find second-most significant bit in e 
	n = BNSizeof(e, nSize);
	for (mask = _HIBITMASK_; mask > 0; mask >>= 1)
	{
		if (e[n-1] & mask)
			break;
	}

	// next bitmask 
	if ( mask==1 )
	{
		mask=_HIBITMASK_;
		n--;
	}else
		mask >>=1; 

	BNSetEqual(y, x, nSize);

	while ( n )
	{

		BNModSquareTmp(y, y, tm, nSize, t1, t2, t3);	
		if (mask & e[n-1])
			BNMultTmp(y, y, x, tm, nSize, t1, t2, t3);

		// Move to next bit
		// next bitmask 
		if ( mask==1 )
		{
			mask=_HIBITMASK_;
			n--;
		}else
			mask >>=1; 
	}

	BNSetEqual(yout, y, nSize);

	BNFree(&t1);
	BNFree(&t2);
	BNFree(&t3);
	BNFree(&tm);
	BNFree(&y);
	return 0;
}
// helper function for code cleannesss. 
inline int MyCryptLib::BNMultTmp(DWORD a[], const DWORD x[], const DWORD y[], DWORD m[], UINT nSize, DWORD temp[], DWORD tqq[], DWORD trr[])
{
	BNMultiply(temp, x, y, nSize);
	BNModuloTmp(a, temp, nSize * 2, m, nSize, tqq, trr);
	return 0; 
}

inline int MyCryptLib::BNModuloTmp(DWORD r[], const DWORD u[], UINT nUSize, DWORD v[], UINT nVSize, DWORD tqq[], DWORD trr[])
{
	BNDivide(tqq, trr, u, nUSize, v, nVSize);
	BNSetEqual(r, trr, nVSize);	
	return 0;
}

inline int MyCryptLib::BNModSquareTmp(DWORD a[], const DWORD x[], DWORD m[], UINT nSize, DWORD temp[], DWORD tqq[], DWORD trr[])
{
	//x*x
	BNSquare(temp, x, nSize);

	// Then modulo m
	BNModuloTmp(a, temp, nSize * 2, m, nSize, tqq, trr);
	return 0;
}


/*	
* Computes sw = x * x
* where:
* 	x is a Big multiprecision Number
*	w is a Big multiprecision Number of 2*nSize
*	nSize is the size of the number in bytes. 
*/

inline int MyCryptLib::BNSquare(DWORD w[], const DWORD x[], UINT nSize)
{
	DWORD k, p[2], u[2], cbit, carry;
	UINT i, j, t, i2, cpos;
	t = nSize;

	i2 = t << 1;

	for (i = 0; i < i2; i++)
		w[i] = 0;

	carry = 0;
	cpos = i2-1;

	for (i = 0; i < t; i++)
	{

		i2 = i << 1; 
		BNMultiplyHelper(p, x[i], x[i]);
		p[0] += w[i2];

		if (p[0] < w[i2])
			p[1]++;
		k = 0;	
		if ( i2 == cpos && carry )
		{
			p[1] += carry;
			if (p[1] < carry)
				k++;
			carry = 0;
		}

		u[0] = p[1];
		u[1] = k;
		w[i2] = p[0];

		k = 0;
		for ( j = i+1; j < t; j++ )
		{
			BNMultiplyHelper(p, x[j], x[i]);
			cbit = (p[0] & _HIBITMASK_) != 0;
			k =  (p[1] & _HIBITMASK_) != 0;
			p[0] <<= 1;
			p[1] <<= 1;
			p[1] |= cbit;

			p[0] += u[0];
			if (p[0] < u[0])
			{
				p[1]++;
				if (p[1] == 0)
					k++;
			}
			p[1] += u[1];
			if (p[1] < u[1])
				k++;

			p[0] += w[i+j];
			if (p[0] < w[i+j])
			{
				p[1]++;
				if (p[1] == 0)
					k++;
			}
			if ((i+j) == cpos && carry)
			{
				p[1] += carry;
				if (p[1] < carry)
					k++;
				carry = 0;
			}
			u[0] = p[1];
			u[1] = k;
			w[i+j] = p[0];
		}

		carry = u[1];
		w[i+t] = u[0];
		cpos = i+t;
	}	
	return 0;
}

//	Computes inv = u^(-1) mod v 
//  This function is not 100% correct, I have to check it later. 
int MyCryptLib::BNModInv(DWORD inv[], const DWORD u[], const DWORD v[], UINT nSize)
{
	DWORD *u1, *u3, *v1, *v3, *t1, *t3, *q, *w;
	u1=u3=v1=v3=t1=t3=q=w=NULL;
	int bIterations;
	int result;

	// Allocate temp storage
	u1 = BNAlloc(nSize);
	if ( u1==NULL )
	{
		return -1;
	}
	u3 = BNAlloc(nSize);
	if ( u3==NULL )
	{
		BNFree(&u1);
		return -1;
	}
	v1 = BNAlloc(nSize);
	if ( v1==NULL )
	{
		BNFree(&u1);
		BNFree(&u3);
		return -1;
	}
	v3 = BNAlloc(nSize);
	if ( v3==NULL )
	{
		BNFree(&u1);
		BNFree(&u3);
		BNFree(&v1);
		return -1;
	}


	t1 = BNAlloc(nSize);

	if ( t1==NULL )
	{
		BNFree(&u1);
		BNFree(&u3);
		BNFree(&v1);
		BNFree(&v3);
		return -1;
	}

	t3 = BNAlloc(nSize);
	if ( t3==NULL )
	{
		BNFree(&u1);
		BNFree(&u3);
		BNFree(&v1);
		BNFree(&v3);
		BNFree(&t1);
		return -1;
	}

	q  = BNAlloc(nSize);
	if ( q==NULL )
	{
		BNFree(&u1);
		BNFree(&u3);
		BNFree(&v1);
		BNFree(&v3);
		BNFree(&t1);
		BNFree(&t3);
		return -1;
	}
	w  = BNAlloc(2 * nSize);
	if ( w==NULL )
	{
		BNFree(&u1);
		BNFree(&u3);
		BNFree(&v1);
		BNFree(&v3);
		BNFree(&t1);
		BNFree(&t3);
		BNFree(&q);
		return -1;
	}

	// Init 
	BNSetEqualdw(u1, 1, nSize);		 // u1 = 1 

	BNSetEqual(u3, u, nSize);		 // u3 = u 
	BNSetZero(v1, nSize);			 // v1 = 0 
	BNSetEqual(v3, v, nSize);		 // v3 = v 

	bIterations = 1;	
	while ( !BNIsZero(v3, nSize) )		
	{					
		BNDivide(q, t3, u3, nSize, v3, nSize);

		BNMultiply(w, q, v1, nSize);	

		// what if the real sizeof(w+u1)> nSize ???
		//ASSERT(BNSizeof(w,nSize*2)>nSize);

		BNAdd(t1, u1, w, nSize);		

		// Swap 
		BNSetEqual(u1, v1, nSize);
		BNSetEqual(v1, t1, nSize);
		BNSetEqual(u3, v3, nSize);
		BNSetEqual(v3, t3, nSize);
		bIterations = -bIterations;
	}

	if (bIterations < 0)
		BNSubtract(inv, v, u1, nSize);	
	else
		BNSetEqual(inv, u1, nSize);	


	if (BNComparedw(u3, 1, nSize) != 0)
	{
		result = 1;
		BNSetZero(inv, nSize);
	}
	else
		result = 0;

	// Free the memory 
	BNSetZero(u1, nSize);
	BNSetZero(v1, nSize);
	BNSetZero(t1, nSize);
	BNSetZero(u3, nSize);
	BNSetZero(v3, nSize);
	BNSetZero(t3, nSize);
	BNSetZero(q, nSize);
	BNSetZero(w, 2*nSize);
	BNFree(&u1);
	BNFree(&v1);
	BNFree(&t1);
	BNFree(&u3);
	BNFree(&v3);
	BNFree(&t3);
	BNFree(&q);
	BNFree(&w);
	return 0;

}

int MyCryptLib::BNGcd(DWORD g[], const DWORD x[], const DWORD y[], UINT nSize)
{
	DWORD *yy, *xx;	
	yy = BNAlloc(nSize);

	if( yy==NULL )
		return -1;

	xx = BNAlloc(nSize);

	if( xx==NULL )
	{
		BNFree(&yy);
		return -1;
	}

	BNSetZero(yy, nSize);
	BNSetZero(xx, nSize);
	BNSetEqual(xx, x, nSize);
	BNSetEqual(yy, y, nSize);
	BNSetEqual(g, yy, nSize);		

	while ( !BNIsZero(xx, nSize) )	
	{
		BNSetEqual(g, xx, nSize);
		BNMod(xx, yy, nSize, xx, nSize);	
		BNSetEqual(yy, g, nSize);	
	}
	BNSetZero(xx, nSize);
	BNSetZero(yy, nSize);
	BNFree(&xx);
	BNFree(&yy);

	return 0;	// gcd = g 
}


/*	Returns true if w is a probable prime using the
*  Rabin-Miller Probabilistic Primality Test.
*  Carries out t iterations specified by user.
*
* DSS Standard recommends using t >= 50
* Ferguson & Schneier recommend t = 64 for prob error < 2^-128
* In practice, most random composites are caught in the first
* round or two and so specifying a large t will only affect
* the final check.
*
*/


int MyCryptLib::BNRabinMiller(const DWORD w[], UINT nSize, UINT t)
{

	DWORD *m, *a, *b, *z, *w1, *j;
	DWORD maxrand;
	int failed;
	BOOL bisprime;
	UINT i;

	// Catch w <= 1 
	if (BNComparedw(w, 1, nSize) <= 0) 
		return 0;

	// Allocate temp storage..

	m = BNAlloc(nSize);
	if ( m==NULL ) 
	{
		return FALSE;
	}
	a = BNAlloc(nSize);
	if ( a==NULL )  
	{
		BNFree(&m);
		return FALSE;
	}
	b = BNAlloc(nSize);
	if ( b==NULL ) 
	{
		BNFree(&m);
		BNFree(&a);
		return FALSE;
	}
	z = BNAlloc(nSize);
	if ( z==NULL ) 
	{
		BNFree(&m);
		BNFree(&a);
		BNFree(&b);
		return FALSE;
	}
	w1 = BNAlloc(nSize);
	if ( w1==NULL ) 
	{
		BNFree(&m);
		BNFree(&a);
		BNFree(&b);
		BNFree(&z);
		return FALSE;
	}
	j = BNAlloc(nSize);
	if ( j==NULL ) 
	{
		BNFree(&m);
		BNFree(&a);
		BNFree(&b);
		BNFree(&z);
		BNFree(&w1);
		return FALSE;
	}

	// Rabin-Miller from FIPS-186-2 Appendix 2. 
	// Step 1. Set i = 1 [but do # tests requested by user].
	// Step 2. Find a and m where w = 1 + (2^a)m
	//	m is odd and 2^a is largest power of 2 dividing w - 1 

	BNSubtractdw(w1, w, 1, nSize);	
	BNSetEqual(m, w1, nSize);		

	for (BNSetZero(a, nSize); (!(m[0]&0x1));  BNAdddw(a, a, 1, nSize))
	{
		BNShiftRight(m, m, 1, nSize);
	}

	if ( BNSizeof(w, nSize) == 1 )
		maxrand = w[0] - 1;
	else
		maxrand = _MAXIMUMNR_;

	bisprime = TRUE;
	for (i = 0; i < t; i++)
	{
		failed = 1;
		//  Step 3. Generate random integer b, 1 < b < w 
		BNSetZero(b, nSize);
		do
		{
			b[0] = RandBetween(2, maxrand);
		} while (BNCompare(b, w, nSize) >= 0);


		// Step 4. Set j = 0 and z = b^m mod w 
		BNSetZero(j, nSize);
		BNModExp(z, b, m, w, nSize);
		do
		{
			// Step 5. If j = 0 and z = 1, or if z = w - 1 */
			if ((BNIsZero(j, nSize) && BNComparedw(z, 1, nSize) == 0) || (BNCompare(z, w1, nSize) == 0))
			{	// Passes on this loop  - go to Step 9 
				failed = 0;
				break;
			}

			// Step 6. If j > 0 and z = 1 */
			if ( !BNIsZero(j, nSize) && (BNComparedw(z, 1, nSize) == 0) )
			{	// Fails - go to Step 8 
				failed = 1;
				break;
			}

			//  Step 7. j = j + 1. If j < a set z = z^2 mod w 
			BNAdddw(j, j, 1, nSize);
			if ( BNCompare(j, a, nSize) < 0 )
				BNModMult(z, z, z, w, nSize);

			// if j < a go to Step 5 
		} while (BNCompare(j, a, nSize) < 0);

		if ( failed )
		{	// Step 8. Not a prime. 
			bisprime = FALSE;
			break;
		}
	}	

	BNSetZero(m, nSize);
	BNSetZero(a, nSize);
	BNSetZero(b, nSize);
	BNSetZero(z, nSize);
	BNSetZero(w1, nSize);
	BNSetZero(j, nSize);
	BNFree(&m);
	BNFree(&a);
	BNFree(&b);
	BNFree(&z);
	BNFree(&w1);
	BNFree(&j);	
	return bisprime;
}



/* The Mersenne Twister Random generator init
* The function inits the Random generator with pRandomPool and nSize 
* If the pRandomPool is not provided it uses the old dangerus srand() and rand() to
* init. 
*/
inline BOOL MyCryptLib::MTInit(BYTE *pRandomPool, UINT nSize)
{
	// If no Random pool is given use the Function MTCollectEntropy to 
	// get entopry from the HW (see the MTCollectEntropy) function. The acctual 
	// entropy we get is less than ~128 bits. It's a good idea to have a tenth 
	// to a fifth as much entropy as the length of the key othervise it 
	// is very dangerous. But hey FBI & CIA is no after oss right ? :=)
	if ( pRandomPool==NULL || nSize<624*4 ) 
	{
		if ( nSize>0&&pRandomPool )
		{
			memcpy(&m_mtbuffer,pRandomPool,nSize);	  
		}

		// If entropy is not given collect from HW. 
		if ( nSize<624*4 )
		{
			BYTE *pmtbuffer=(BYTE*)&m_mtbuffer;
			MTCollectEntropy(pmtbuffer+nSize,624*4-nSize);	
		}		

		m_bSeeded=TRUE;
	}
	m_mtIndex=624; // Start with performin the shuffel so the randomness is spread around. 
	return m_bSeeded;
}

/*
* MTCollectEntropy(BYTE *pRandomPool, UINT nSize)
*
* This function collects entropy (true randomness) from the Hardware
* Using different source namely: 
*  
* - System time 
* - Current process ID
* - Current thread ID 
* - Get clock ticks since system booted
* - The nr pages and memory allockated. 
*
* The entropies above are destilled to with SHA1 hash function to fill the 
* pRadomPool of size nSize. 
* 
* Observe! Warning!  
* - This function gives approximatly ~128 bit entropy destilled into
*   pRandomPool with nSize. 
* - The last 20 bytes may hold more entropie than the other in pRandomPool, Additional
*   destilling is needed.
*/
BOOL MyCryptLib::MTCollectEntropy(BYTE *pRandomPool, UINT nSize)
{
	SYSTEMTIME st;
	FILETIME ft;
	MEMORYSTATUS ms;
	SHA1_STATETYPE csha1;
	UINT nCollected = 0; 
	BYTE EntropyBucket[SHA1_DIGEST_SIZE];
	BYTE *pEntropyBucket=(BYTE*)EntropyBucket;
	DWORD dwRes=0;
	DWORD dwTick=0;
	ms.dwLength = sizeof(MEMORYSTATUS);
	memset(&csha1,0,sizeof(csha1));
	SHA1_Start(&csha1);

	while ( nSize-nCollected>0 )
	{	
		// Hash the previus entropy Bucket..
		SHA1_Hash(pEntropyBucket,SHA1_DIGEST_SIZE,&csha1);

		// Destill The process ID
		dwRes=GetCurrentProcessId();
		SHA1_Hash((BYTE*)&dwRes,sizeof(DWORD),&csha1);

		// Destill The thread ID	
		dwRes=GetCurrentThreadId();
		SHA1_Hash((BYTE*)&dwRes,sizeof(DWORD),&csha1);

		// Destill The system time. 
		GetSystemTime(&st);
		SystemTimeToFileTime(&st, &ft);
		SHA1_Hash((BYTE*)&ft,sizeof(FILETIME),&csha1);

		// Destill The processors tickcount. 
		dwTick = GetTickCount();
		SHA1_Hash((BYTE*)&dwTick,sizeof(DWORD),&csha1);

		// Destill The memory allocated
		GlobalMemoryStatus(&ms);
		SHA1_Hash((BYTE*)&ms, sizeof(MEMORYSTATUS),&csha1);

		// Put it inside the Bucket. 
		SHA1_Finish(EntropyBucket,&csha1);

		// Copy the Entropy to the pool
		if ( nSize-nCollected<SHA1_DIGEST_SIZE )
		{
			memcpy(pRandomPool+nCollected,pEntropyBucket,nSize-nCollected);
			nCollected+=nSize-nCollected;
		}
		else
		{
			memcpy(pRandomPool+nCollected,pEntropyBucket,SHA1_DIGEST_SIZE);
			nCollected+=SHA1_DIGEST_SIZE;
		}
	}
	return TRUE; 
}



/*
*	The Mersenne Twister is a new random number generator, 
*	discovered in 1996 by Matsumora and Nishimura. 
*  MT is a twisted GFSR(624,397), similar in spirit to R250 and R521 but faster. 
*  It takes up more space than R250 or R521, but less than the two combined. 
*	MT has an amazing period of 2^19937-1. Overall, and passes all the statistical tests. 
*  Assumes it is already initciaded. 	
*
* More info () ----------------------------------------
* The Mersenne Twister, a new variant of the twisted GFSR ("TGFSR") by Matsumoto and Nishimura, 
* sets new standards for the period, quality and speed of random number generators. The incredible 
* period is 219937 - 1, a number with about 6000 decimal digits; the 32-bit random numbers exhibit 
* best possible equidistribution properties in dimensions up to 623; and it's fast, very fast. 
* A paper on the Mersenne Twister has been submitted to ACM TOMACS. 
* 
* The Mersenne Twister generator passes all current statistical tests.
*/
inline DWORD MyCryptLib::MTRandom()
{
	if( !m_bSeeded )
		MTInit();

	if ( m_mtIndex >= 624 )
	{
		m_mtIndex = 0;
		int i = 0;
		int s;
		for (; i < 624 - 397; i++) {
			s = (m_mtbuffer[i] & 0x80000000) | (m_mtbuffer[i+1] & 0x7FFFFFFF);
			m_mtbuffer[i] = m_mtbuffer[i + 397] ^ (s >> 1) ^ ((s & 1) * 0x9908B0DF);
		}
		for (; i < 623; i++) {
			s = (m_mtbuffer[i] & 0x80000000) | (m_mtbuffer[i+1] & 0x7FFFFFFF);
			m_mtbuffer[i] = m_mtbuffer[i - (624 - 397)] ^ (s >> 1) ^ ((s & 1) * 0x9908B0DF);
		}

		s = (m_mtbuffer[623] & 0x80000000) | (m_mtbuffer[0] & 0x7FFFFFFF);
		m_mtbuffer[623] = m_mtbuffer[396] ^ (s >> 1) ^ ((s & 1) * 0x9908B0DF);
	}
	DWORD tmp=m_mtbuffer[m_mtIndex++];
	tmp  ^= (tmp >> 11);
	tmp ^= (tmp << 7) & 0x9D2C5680UL;
	tmp ^= (tmp << 15) & 0xEFC60000UL;
	return tmp ^ (tmp >> 18);
}
/*
*	Generates an Random nr between dwLower and dwUpper. 
*/
inline DWORD MyCryptLib::RandBetween(DWORD dwLower, DWORD dwUpper)
{

	DWORD d, range;
	unsigned char *bp;
	int i, nbits;
	DWORD mask;

	if ( dwUpper <= dwLower ) 
	{
		return dwLower;
	}
	range = dwUpper - dwLower;

	do
	{
		bp = (unsigned char *)&d;
		for (i = 0; i < sizeof(DWORD); i++)
		{
			bp[i] = BYTE(MTRandom() & 0xFF);
		}


		mask = _HIBITMASK_;
		for (nbits = sizeof(DWORD)*8; nbits > 0; nbits--, mask >>= 1)
		{
			if (range & mask)
				break;
		}
		if (nbits < sizeof(DWORD)*8)
		{
			mask <<= 1;
			mask--;
		}
		else
			mask = _MAXIMUMNR_;

		d &= mask;

	} while (d > range); 

	return (dwLower + d);
}




/*
*	Returns true if w > 2 is a probable prime
*  tryes some small nr primes and then uses 
*	the rabin Miller alghorim to detect the prime nr
*
*  nrRounds denotes the number of rounds to use when determine that 
*  the number is an primenumber or not. 
*/
int MyCryptLib::BNIsPrime(DWORD W[], UINT nSize, UINT nrRounds)
{

	// if the number is even then return FALSE;
	if ((!(W[0] & 0x1)))
		return 0;


	// if the number is bigger than the biggest prime nr..
	if (BNComparedw(W, SMALL_PRIMES[_NUMBEROFPRIMES_-1], nSize) > 0)
	{
		for (UINT i = 0; i < _NUMBEROFPRIMES_; i++)
		{
			if (BNModdw(W, SMALL_PRIMES[i], nSize) == 0) // if the number contain one of the small primes. 
				return FALSE;
		}
	}
	else //W < Biggest prime in the list so we are going to check it our self. 
	{	
		for (UINT i = 0; i < _NUMBEROFPRIMES_; i++)
		{
			if (BNComparedw(W, SMALL_PRIMES[i], nSize) == 0)
				return TRUE; // Is an small prime	
		}
		return FALSE; // Not an prime. 
	}
	// Use Rabin Miller now. 
	return BNRabinMiller(W, nSize, nrRounds);
}

/*
* Creates an prime nr.	
* Return number of signifikant bits if success, -1 if the functions did not sucess. 
* -------------------------------------------------------------------------------------------
* The prime nr is not completly  cryptographically secure because it relies on the   
* Mersenne Twister random generator, and Rabin Miller prime detection algorithm.  
* But if it is propetly seeded it is quite safe (se below).
* ------------------------ 
* The Mersenne Twister, a new variant of the twisted GFSR ("TGFSR") by Matsumoto and Nishimura, 
* sets new standards for the period, quality and speed of random number generators. The incredible 
* period is 2^(219937 - 1), a number with about 6000 decimal digits; the 32-bit random numbers exhibit 
* best possible equidistribution properties in dimensions up to 623; and it's fast, very fast. 
* A paper on the Mersenne Twister has been submitted to ACM TOMACS. 
* 
* The Mersenne Twister generator passes all current statistical tests.
*/
int MyCryptLib::BNMakePrime(DWORD p[], UINT nSize, PBYTE pEntropyPool, UINT nSizeEntropyPool)
{
	// if entropy is provided use it!
	if ( pEntropyPool )
	{
		MTInit(pEntropyPool,nSizeEntropyPool);
	}

	for ( UINT i = 0; i < nSize; i++ )
		p[i] = MTRandom();	

	// Make sure the highest and low bits are set, so we have an nice big odd nr. 
	p[nSize - 1] |= _HIBITMASK_;
	p[0] |= 0x1;

	// Check if prime 
	//  Why 10 rounds ? well
	// DSS Standard recommends using t >= 50
	// Ferguson & Schneier recommend t = 64 for prob error < 2^-128
	// But in practice the moste primes is found in round one or two so 10 is an nice
	// home made nr of rounds. 
	while (!BNIsPrime(p, nSize, 10) )
	{
		// Keep adding 2 until we find a prime 
		BNAdddw(p, p, 2, nSize);

		// Check for overflow 
		if (!(p[nSize - 1] & _HIBITMASK_))
			return -1;	// Failed to find a prime 
	}
	// return nr of significant bits.
	return BNBitLength(p,nSize);
}






/*
* BNMakeRSAPrime(DWORD p[], DWORD ee[], UINT nSize)
*	
* Return number of signifikant bits if success, -1 if the functions did not sucess. 
* -------------------------------------------------------------------------------------------
* The prime nr is not completly  cryptographically secure because it relies on the   
* Mersenne Twister random generator, and Rabin Miller prime detection algorithm.  
* But if it is propetly seeded it is quite safe (se below).
* ------------------------ 
* The Mersenne Twister, a new variant of the twisted GFSR ("TGFSR") by Matsumoto and Nishimura, 
* sets new standards for the period, quality and speed of random number generators. The incredible 
* period is 219937 - 1, a number with about 6000 decimal digits; the 32-bit random numbers exhibit 
* best possible equidistribution properties in dimensions up to 623; and it's fast, very fast. 
* A paper on the Mersenne Twister has been submitted to ACM TOMACS. 
* 
* The Mersenne Twister generator passes all current statistical tests.
*
* Important assumptions!:
*  - ee is an Fermat prime nr greater than 2.  
*
*/
int MyCryptLib::BNMakeRSAPrime(DWORD p[], DWORD ee, UINT nSize,UINT nMaximumRetry)
{
	UINT nRet=-1; 
	for ( UINT i=0; i<nMaximumRetry; i++ )
	{
		nRet=BNMakePrime(p,nSize);
		if(nRet>0&&BNModdw(p, ee,nSize)!=1)
			break;
	}
	return nRet;
}



/*
* Creates an random nr. 	
* 
* OBS!! not cryptographically secure!! why? 
* Well we do some homemade modification to the number. 
* 1) We fill it up to n (n also random) with random numbers  
* 2) We fill the rest with zeros. 
* 3) We mask the number n with an mask. 
*
* why? Because of practical resons, we do not whant numbers near owerflow and underflow.!
*/
UINT MyCryptLib::BNMakeRandomNr(DWORD a[], UINT nSize)
{
	UINT  i, n, bits;
	DWORD mask;

	n = (UINT)RandBetween(1, nSize);
	for ( i = 0; i < n; i++) 
		a[i] = MTRandom();
	for ( i = n; i < nSize; i++)
		a[i] = 0;
	// Mask it 50% chance 
	bits = (UINT)RandBetween(0, 16*sizeof(DWORD));

	if ( bits != 0 && bits < 8*sizeof(DWORD) )
	{	
		mask = _HIBITMASK_;
		for (i = 1; i < bits; i++)
		{
			mask |= (mask >> 1);
		}
		mask = ~mask;
		a[n-1] &= mask;
	}
	return n;	
}





/*
* Generates keys used for RSA Encryption/Decryption Algorithm 	
*
* n is the public key modulus..
* e is the public exponent encryption exponent.
* d is the secret exponent or decryption exponent.
* The  private key as a quintuple  (p, q, dP, dQ, and qInv), is used 
* for the Chinese Remainder Theorem (CRT) decryption. 
* The CRT method of decryption is four times faster overall 
* than calculating m = c^d mod n.
* p and q are prime factors of n.
* dP and dQ are known as the CRT exponents.
* qInv is the CRT coefficient. 
* 
* nPSize is the size of the prime nr P 
* nQSize is the size of the prime nr Q
*
* The key length is nPSize+nQSize
*
* nSize is the size of the input variables. 
* 
* Observe! nSize must be big enough (eg nSize>=max(nPSize,nQSize)*2) 
*
* In practice, common choices for e are 3, 17 and 65537 (2^16+1). These are Fermat primes and are chosen 
* because they make the modular exponentiation operation faster. 
* 
* Assumed that e is an primenumber greater than 2. 
*
* pSeedData is an pointer to an Random number pool of size nSeedData.
* This pool is used with the Mersenne Twister random nr generator to 
* if pSeedData is NULL then the Random number pool is seeded with 
* current time  since 1981 and time in ms since the computer started and the
* old srand() rand function. 
* if e is NULL then the the default nr 65537.
*/
int MyCryptLib::RSAGenerateKey(DWORD n[], DWORD d[], DWORD p[], DWORD q[], DWORD dP[], DWORD dQ[], DWORD qInv[], UINT nSize, UINT nPSize,UINT nQSize,DWORD e, BYTE* pSeedData,UINT nSeedData)
{

	// Make sure that nSize is big enough 	
	if( nSize<max(nPSize,nQSize)*2 )
		return -30;

	// The operation size of primes. (they are bigger than this nr) 
	UINT nPrimeSize=max(nPSize,nQSize);
	// The operation size of public key N. 
	UINT nNSize=0; 
	// The operation size of private key D. 
	UINT nDSize=0;


	// Create some temporary data. 
	DWORD *pG=BNAlloc(nSize);
	if ( pG==NULL )
	{
		return -1;
	}

	DWORD *pP1=BNAlloc(nSize);
	if ( pP1==NULL )
	{
		BNFree(&pG);
		return -2;
	}

	DWORD *pQ1=BNAlloc(nSize);
	if ( pQ1==NULL )
	{
		BNFree(&pG);
		BNFree(&pP1);
		return -3;
	}

	DWORD *pPhi=BNAlloc(nSize);
	if ( pPhi==NULL )
	{
		BNFree(&pG);
		BNFree(&pP1);
		BNFree(&pQ1);
		return -4;
	}

	DWORD *pE=BNAlloc(nSize);
	if ( pE==NULL )
	{
		BNFree(&pG);
		BNFree(&pP1);
		BNFree(&pQ1);
		BNFree(&pPhi);
		return -5;
	}	


	if ( pSeedData!=NULL && nSeedData>=0 ) 
		MTInit(pSeedData,nSeedData/2);
	else 
		MTInit();

	int nRet=BNMakeRSAPrime(p,e,nPSize);
	if ( nRet<=0 )
	{
		BNFree(&pG);
		BNFree(&pP1);
		BNFree(&pQ1);
		BNFree(&pPhi);
		BNFree(&pE);
		return -6;
	}

	if ( pSeedData!=NULL && nSeedData>=0)  
		MTInit(pSeedData+nSeedData/2,nSeedData/2);
	else 
		MTInit();

	nRet=BNMakeRSAPrime(q,e,nQSize);
	if ( nRet<=0 )
	{
		BNFree(&pG);
		BNFree(&pP1);
		BNFree(&pQ1);
		BNFree(&pPhi);
		BNFree(&pE);
		return -7;
	}

	// Check if the prime nr is ok 
	if ( BNIsEqual(p,q,nPrimeSize) )
	{
		BNFree(&pG);
		BNFree(&pP1);
		BNFree(&pQ1);
		BNFree(&pPhi);
		BNFree(&pE);
		return -8;
	}


	BNSetEqualdw(pE,e,nSize);

	// If q > p swap p and q so p > q 
	if ( BNCompare(p, q,nPrimeSize) < 1 )
	{	
		BNSetEqual(pG, p,nPrimeSize);
		BNSetEqual(p, q,nPrimeSize);
		BNSetEqual(q, pG,nPrimeSize);
	}


	if ( BNSubtractdw(pP1,p,1,nPrimeSize)!=0 )
	{
		BNFree(&pG);
		BNFree(&pP1);
		BNFree(&pQ1);
		BNFree(&pPhi);
		BNFree(&pE);
		return -8;
	}


	if ( BNSubtractdw(pQ1,q,1,nPrimeSize)!=0 )
	{
		BNFree(&pG);
		BNFree(&pP1);
		BNFree(&pQ1);
		BNFree(&pPhi);
		BNFree(&pE);
		return -8;
	}

	// Make sure that GCD(p-1,e)!=1 and GCD(q-1,e)!=1 

	BNGcd(pG, pP1, pE,nPrimeSize);

	if ( BNComparedw(pG,1,nPrimeSize)!=0 )
	{
		BNFree(&pG);
		BNFree(&pP1);
		BNFree(&pQ1);
		BNFree(&pPhi);
		BNFree(&pE);
		return -9;
	}



	BNGcd(pG, pQ1, pE,nPrimeSize);

	if ( BNComparedw(pG,1,nPrimeSize)!=0 )
	{
		BNFree(&pG);
		BNFree(&pP1);
		BNFree(&pQ1);
		BNFree(&pPhi);
		BNFree(&pE);
		return -9;
	}


	// n = pq 
	BNMultiply(n, p, q,nPrimeSize);

	nNSize=BNSizeof(n,nSize);

	if ( BNIsZero(n,nNSize)) 
	{
		BNFree(&pG);
		BNFree(&pP1);
		BNFree(&pQ1);
		BNFree(&pPhi);
		BNFree(&pE);
		return -11;
	}
	//
	// d = e^-1 mod (p-1)(q-1) 
	// 

	// pPhi = (p-1)(q-1) 
	BNMultiply(pPhi, pP1, pQ1,nPrimeSize);
	// pPhi have the operation size of nPrimeSize*2<=nSize

	if ( BNIsZero(pPhi,nSize))  
	{
		BNFree(&pG);
		BNFree(&pP1);
		BNFree(&pQ1);
		BNFree(&pPhi);
		BNFree(&pE);
		return -11;
	}

	nRet = BNModInv(d, pE, pPhi,nSize);

	nDSize=BNSizeof(d,nSize);


	if ( BNIsZero(d,nDSize) || nRet!=0 )
	{
		BNFree(&pG);
		BNFree(&pP1);
		BNFree(&pQ1);
		BNFree(&pPhi);
		BNFree(&pE);
		return -11;
	}

	// Check ed = 1 mod phi 
	BNSetZero(pG,nSize);
	//BNModMult(pG, pE, d, pPhi,nSize);
	BNModMult(pG, pE, d, pPhi,max(nDSize,nPrimeSize*2));


	if ( BNComparedw(pG,1,nSize)!=0 )
	{
		BNFree(&pG);
		BNFree(&pP1);
		BNFree(&pQ1);
		BNFree(&pPhi);
		BNFree(&pE);
		return -11;
	}

	if ( BNModInv(dP, pE, pP1,nPrimeSize)!=0 )
	{
		BNFree(&pG);
		BNFree(&pP1);
		BNFree(&pQ1);
		BNFree(&pPhi);
		BNFree(&pE);
		return -12;
	}

	if ( BNModInv(dQ, pE, pQ1,nPrimeSize)!=0 )
	{
		BNFree(&pG);
		BNFree(&pP1);
		BNFree(&pQ1);
		BNFree(&pPhi);
		BNFree(&pE);
		return -13;
	}

	if ( BNModInv(qInv, q, p,nSize)!=0 )
	{
		BNFree(&pG);
		BNFree(&pP1);
		BNFree(&pQ1);
		BNFree(&pPhi);
		BNFree(&pE);
		return -14;
	}

	BNFree(&pG);
	BNFree(&pP1);
	BNFree(&pQ1);
	BNFree(&pPhi);
	BNFree(&pE);
	return nNSize;	
}

#ifdef _MYCRYPTLIB_DEMOS_


void MyCryptLib::DemoDiffieHellman(CHistoryEdit *pLogg, UINT nSize)
{
	if(!pLogg) // be safe.. 
		return; 
	pLogg->AppendString("Diffie Hellman Key Exchange Test.. \r\n---------");

	CString stmp;
	// We need some variables. 
	UINT i=0;
	UINT j=0;
	DWORD dwStartTime=0;
	DWORD dwEndTime=0;
	DWORD dwTotalComputeBTime=0;
	DWORD dwTotalComputeATime=0;
	DWORD dwTotalComputeS1Time=0;
	DWORD dwTotalComputeS2Time=0;
	DWORD dwTotalComputePTime=0;

	// Allocate memory 
	DWORD* p=BNAlloc(nSize);


	UINT nKeySize=nSize/2;

	DWORD* g=BNAlloc(nKeySize);
	DWORD* A=BNAlloc(nKeySize);
	DWORD* B=BNAlloc(nKeySize);
	DWORD* a=BNAlloc(nKeySize);
	DWORD* b=BNAlloc(nKeySize);
	DWORD* S1=BNAlloc(nKeySize);
	DWORD* S2=BNAlloc(nKeySize);


	// be Safe.. 
	if( !p || !g || !A || !B || !a || !b || !S1 || !S2 )
	{
		BNFree(&p);
		BNFree(&g);
		BNFree(&A);
		BNFree(&B);
		BNFree(&a);
		BNFree(&b);
		BNFree(&S1);
		BNFree(&S2);
		return ;

	}



	// Make them all zero.. 

	BNSetZero(p,nSize);
	BNSetZero(g,nKeySize);
	BNSetZero(A,nKeySize);
	BNSetZero(B,nKeySize);
	BNSetZero(a,nKeySize);
	BNSetZero(b,nKeySize);
	BNSetZero(S1,nKeySize);
	BNSetZero(S2,nKeySize);


	// Compute how much time in sekonds it takes to generate the prime nrs. 
	// The Keygeneration is an socastic function with these estimated parameters. 
	double time=0.3518*exp(0.0016*nSize*8*4);

	stmp.Format("Exchanging a secure Session key of size %i bits.",nKeySize*4*8);
	pLogg->AppendString(stmp);

	// Generate prime number. 
	stmp.Format("Generating a ~ %i bit prime nr. This may take a while..\r\n",nSize*8*4);
	pLogg->AppendString(stmp);


	timeBeginPeriod(1);
	dwStartTime=timeGetTime();

	BNSetEqualdw(g,5,nKeySize);
	int iRet=BNMakePrime(p,nSize);

	if ( iRet <0 )
	{
		BNFree(&p);
		BNFree(&g);
		BNFree(&A);
		BNFree(&B);
		BNFree(&a);
		BNFree(&b);
		BNFree(&S1);
		BNFree(&S2);
		pLogg->AppendString("Failed to Generate Prime number..");
		return;
	}

	dwEndTime=timeGetTime();
	timeEndPeriod(1);
	dwTotalComputePTime=dwEndTime-dwStartTime;
	UINT nPsize=BNBitLength(p,nSize);

	stmp.Format("Using public key: Ppub (size %ibits) Gpub %i.",nPsize,5);
	pLogg->AppendString(stmp);

	for(i=0;i<10;i++)
	{

		stmp.Format("------ Test nr %i.\r\n",i+1);
		pLogg->AppendString(stmp);

		// Generate Random secret keys a,b
		// 16= 256bit + 256bit
		for (j = 0; j <nKeySize ; j++)
			a[j] = MTRandom();	

		for (j = 0; j <nKeySize ; j++)
			b[j] = MTRandom();	


		// Alice Computes A 
		timeBeginPeriod(1);
		dwStartTime=timeGetTime();
		BNModExp(A, g, a, p,nKeySize);
		dwEndTime=timeGetTime();
		dwTotalComputeATime+=dwEndTime-dwStartTime;
		pLogg->AppendString("const DWORD Apub"+BNPrintC(A,nKeySize));


		// Bob Computes B 
		timeBeginPeriod(1);
		dwStartTime=timeGetTime();
		BNModExp(B, g, b, p,nKeySize);
		dwEndTime=timeGetTime();
		dwTotalComputeBTime+=dwEndTime-dwStartTime;
		pLogg->AppendString("const DWORD Bpub"+BNPrintC(B,nKeySize));


		// Exchange A and B 
		pLogg->AppendString("Exchange A and B, and compute secret keys..");

		// Alice computes S1=B^a mod(p)
		timeBeginPeriod(1);
		dwStartTime=timeGetTime();
		BNModExp(S1, B, a, p,nKeySize);
		dwEndTime=timeGetTime();
		timeEndPeriod(1);
		dwTotalComputeS1Time+=(dwEndTime-dwStartTime);

		// Bob Computes S2=A^b mod(p)
		timeBeginPeriod(1);
		dwStartTime=timeGetTime();
		BNModExp(S2, B, a, p,nKeySize);
		dwEndTime=timeGetTime();
		timeEndPeriod(1);
		dwTotalComputeS2Time+=(dwEndTime-dwStartTime);


		if ( !BNIsEqual(S1,S2,nKeySize) )
		{
			pLogg->AppendString("Error Secret key S1 is not equal S2");
			BNFree(&p);
			BNFree(&g);
			BNFree(&A);
			BNFree(&B);
			BNFree(&a);
			BNFree(&b);
			BNFree(&S1);
			BNFree(&S2);
			return;
		}else
		{

			pLogg->AppendString("Exchanged: const DWORD S"+BNPrintC(S1,nKeySize));
		}

	}

	pLogg->AppendString("\r\n---------------------------\r\n");


	pLogg->AppendString("const DWORD Ppub"+BNPrintC(p,nSize));

	stmp.Format("\r\nconst DWORD Gpub = %i",5);
	pLogg->AppendString(stmp);


	stmp.Format("Prime number generation time: %ims, keysize: %i \r\n",dwTotalComputePTime,nPsize);
	pLogg->AppendString(stmp);

	stmp.Format("Mean A & B (A= g^ a mod(p)) computation time: %0.2fms.\r\n",(dwTotalComputeATime+dwTotalComputeBTime)/(double)(i*2));
	pLogg->AppendString(stmp);


	stmp.Format("Mean S1 & S2 computation time: %0.2fms.\r\n",(dwTotalComputeS1Time+dwTotalComputeS2Time)/(double)(i*2));
	pLogg->AppendString(stmp);


	double dTotal=((dwTotalComputeATime+dwTotalComputeBTime)/(double)(i*2)) +  ((dwTotalComputeS1Time+dwTotalComputeS2Time)/(double)(i*2));

	stmp.Format("Total mean key Exchange time: %0.2fms.\r\n",dTotal);
	pLogg->AppendString(stmp);

	BNFree(&p);
	BNFree(&g);
	BNFree(&A);
	BNFree(&B);
	BNFree(&a);
	BNFree(&b);
	BNFree(&S1);
	BNFree(&S2);
}

void MyCryptLib::DemoDSA(CHistoryEdit *pLogg, UINT nSize, BYTE* pEntropyPool,UINT nEntropySize)
{	
	// Be Safe.
	if ( !pLogg )
		return;


	// Compute the size of P,Q primes. 
	UINT nPSize=nSize/2;
	UINT nQSize=nSize-nPSize;

	// let nSize be big enough for operations. 
	nSize=max(nPSize,nQSize)*2;

	pLogg->AppendString("DSA Test.. \r\n---------");


	CString stmp;
	// We need some variables. 
	BOOL bTestOK=TRUE;
	UINT i=0;
	UINT j=0;
	DWORD dwStartTime=0;
	DWORD dwEndTime=0;
	DWORD dwTotalSignTime=0;
	DWORD dwTotalVerifyTime=0;
	DWORD dwTotalRSAKeyGenerationTime=0;
	DWORD dwOverFlow=0;

	// Allocate memory 
	DWORD* n=BNAlloc(nSize);
	DWORD* d=BNAlloc(nSize);
	DWORD* p=BNAlloc(nSize);
	DWORD* q=BNAlloc(nSize);	
	DWORD* dQ=BNAlloc(nSize);
	DWORD* dP=BNAlloc(nSize);
	DWORD* qInv=BNAlloc(nSize);
	DWORD* m=BNAlloc(nSize);
	DWORD* S=BNAlloc(nSize);
	DWORD* e=BNAlloc(nSize);

	// be Safe.. 
	if ( !n||!d||!p||!q||!dQ||!dP||!qInv||!m||!S||!e )
	{
		BNFree(&n);
		BNFree(&d);
		BNFree(&p);
		BNFree(&q);
		BNFree(&dQ);
		BNFree(&dP);
		BNFree(&qInv);
		BNFree(&m);
		BNFree(&S);
		BNFree(&e);
		return ;
	}



	// Make them all zero.. 

	BNSetZero(n,nSize);
	BNSetZero(d,nSize);
	BNSetZero(p,nSize);
	BNSetZero(q,nSize);
	BNSetZero(dP,nSize);
	BNSetZero(dQ,nSize);
	BNSetZero(qInv,nSize);
	BNSetZero(m,nSize);
	BNSetZero(S,nSize);

	// Compute how much time in sekonds it takes to generate the prime nrs. 
	// The Keygeneration is an socastic function with these estimated parameters. 
	double time=0.3518*exp(0.0016*nSize*8*4);

	stmp.Format("Generating a ~ %i bit RSA/DSA key. This may take approximately %0.1f seconds. \r\n",nSize*8*4,time);

	pLogg->AppendString(stmp);

	timeBeginPeriod(1);
	dwStartTime=timeGetTime();

	DWORD dwe=3;


	int iRet=RSAGenerateKey(n,d,p,q,dP,dQ,qInv,nSize,nPSize,nQSize,dwe,pEntropyPool,nEntropySize);
	if ( iRet<0 )
	{
		pLogg->AppendString("Failed to Generate RSA Keys..");
		return;
	}

	dwEndTime=timeGetTime();
	timeEndPeriod(1);

	dwTotalRSAKeyGenerationTime=dwEndTime-dwStartTime;

	UINT nNsize=BNBitLength(n,nSize);
	nSize=BNSizeof(d,nSize);

	pLogg->AppendString("-------------- DSA  test");
	for ( i=0  ; i<25 ; i++ )
	{

		stmp.Format("------ Test nr %i.\r\n",i+1);
		pLogg->AppendString(stmp);
		pLogg->AppendString("Generating a Random message m.");
		BNSetZero(m,nSize);
		for (j = 0; j <nSize-2; j++)
			m[j] = MTRandom();	




		timeBeginPeriod(1);
		dwStartTime=timeGetTime();
		// Sign the message.. 
		DigitalSignSHA1rDSA((unsigned char *)m,nSize*4,d,n,S,nSize);
		dwEndTime=timeGetTime();
		dwTotalSignTime+=dwEndTime-dwStartTime;

		// Send (m,S) to Client that already have and trust public keys (n,e)..

		// Verify.  
		pLogg->AppendString("Verify the signature..");
		timeBeginPeriod(1);
		dwStartTime=timeGetTime();
		bTestOK=DigitalVerifySHA1rDSA((unsigned char *)m,nSize*4,n,dwe,S,nSize);

		dwEndTime=timeGetTime();
		dwTotalVerifyTime +=dwEndTime-dwStartTime;

		if ( !bTestOK )
		{
			pLogg->AppendString("Verification failed fatal error");
			break;
		}


	}


	pLogg->AppendString("\r\n---------------------------\r\n");
	pLogg->AppendString("const DWORD SecureChatIOCP::m_DSAKeypubN"+BNPrintC(n,nSize));
	pLogg->AppendString("const DWORD SecureChatIOCP::m_DSAKeypubD"+BNPrintC(d,nSize));
	stmp.Format("const DWORD SecureChatIOCP::m_DSAKeypubE = %i;",dwe);
	pLogg->AppendString(stmp);

	if ( bTestOK )
	{

		pLogg->AppendString("\r\n---------------------------\r\n");
		pLogg->AppendString("Test OK");
		stmp.Format("RSA/DSA Key size %i bits.",nNsize);
		pLogg->AppendString(stmp);
		stmp.Format("RSA/DSA Key Computation time: %ims.\r\n",dwTotalRSAKeyGenerationTime);
		pLogg->AppendString(stmp);
		stmp.Format("Mean Signature time: %0.4fms.\r\n",dwTotalSignTime/(double)i);
		pLogg->AppendString(stmp);
		stmp.Format("Mean Verfication time: %0.4fms.\r\n",dwTotalVerifyTime/(double)i);
		pLogg->AppendString(stmp);
	}	
	// free the variables. 
	BNFree(&n);
	BNFree(&d);
	BNFree(&p);
	BNFree(&q);
	BNFree(&dQ);
	BNFree(&dP);
	BNFree(&qInv);
	BNFree(&m);
	BNFree(&S);
	BNFree(&e);
}


void MyCryptLib::DemoRSA(CHistoryEdit *pLogg, UINT nSize)
{
	if ( !pLogg ) // be safe.. 
		return; 

	// The size of prime nrs P,Q. 
	UINT nPSize=nSize/2;
	UINT nQSize=nSize - nPSize;


	pLogg->AppendString("RSA Test.. \r\n---------");



	CString stmp;
	// We need some variables. 
	BOOL bTestOK=TRUE;
	UINT i=0;
	UINT j=0;
	DWORD dwStartTime=0;
	DWORD dwEndTime=0;
	DWORD dwTotalEncryptionTime=0;
	DWORD dwTotalNormalDecryptionTime=0;
	DWORD dwTotalDecryptionTime=0;
	DWORD dwTotalRSAKeyGenerationTime=0;
	DWORD dwOverFlow=0;
	// Allocate memory 
	DWORD* n=BNAlloc(nSize);
	DWORD* d=BNAlloc(nSize);
	DWORD* p=BNAlloc(nSize);
	DWORD* q=BNAlloc(nSize);	
	DWORD* dQ=BNAlloc(nSize);
	DWORD* dP=BNAlloc(nSize);
	DWORD* qInv=BNAlloc(nSize);
	DWORD* m=BNAlloc(nSize);
	DWORD* e=BNAlloc(nSize);
	DWORD* c=BNAlloc(nSize);
	DWORD* m1=BNAlloc(nSize);
	DWORD* m2=BNAlloc(nSize);
	DWORD* h=BNAlloc(nSize);
	DWORD* hq=BNAlloc(nSize);

	// be Safe.. 
	if ( !n||!d||!p||!q||!dQ||!dP||!qInv||!m||!e||!c||!m1||!m2||!h||!hq )
	{
		BNFree(&n);
		BNFree(&d);
		BNFree(&p);
		BNFree(&q);
		BNFree(&dQ);
		BNFree(&dP);
		BNFree(&qInv);
		BNFree(&m);
		BNFree(&e);
		BNFree(&c);
		BNFree(&m1);
		BNFree(&m2);
		BNFree(&h);
		BNFree(&hq);
		return ;

	}



	// Make them all zero.. 

	BNSetZero(n,nSize);
	BNSetZero(d,nSize);
	BNSetZero(p,nSize);
	BNSetZero(q,nSize);
	BNSetZero(dP,nSize);
	BNSetZero(dQ,nSize);
	BNSetZero(qInv,nSize);
	BNSetZero(m,nSize);
	BNSetZero(e,nSize);
	BNSetZero(c,nSize);
	BNSetZero(m1,nSize);
	BNSetZero(m2,nSize);
	BNSetZero(h,nSize);
	BNSetZero(hq,nSize);

	// Compute how much time in sekonds it takes to generate the prime nrs. 
	// The Keygeneration is an socastic function with these estimated parameters. 
	double time=0.3518*exp(0.0016*nSize*8*4);


	stmp.Format("Generating a ~ %i bit RSA/DSA key. This may take approximately %0.1f seconds. \r\n",nSize*8*4,time);
	pLogg->AppendString(stmp);

	timeBeginPeriod(1);
	dwStartTime=timeGetTime();

	// Generate keys. using standard e=65537;
	BNSetEqualdw(e,65537,nSize);
	int iRet=RSAGenerateKey(n,d,p,q,dP,dQ,qInv,nSize,nPSize,nQSize,65537);

	if ( iRet<0 )
	{
		pLogg->AppendString("Failed to Generate RSA Keys..");
		BNFree(&n);
		BNFree(&d);
		BNFree(&p);
		BNFree(&q);
		BNFree(&dQ);
		BNFree(&dP);
		BNFree(&qInv);
		BNFree(&m);
		BNFree(&e);
		BNFree(&c);
		BNFree(&m1);
		BNFree(&m2);
		BNFree(&h);
		BNFree(&hq);
		return;
	}

	dwEndTime=timeGetTime();
	timeEndPeriod(1);

	pLogg->AppendString("n= "+BNToString(n,nSize,16));
	pLogg->AppendString("d= "+BNToString(d,nSize,16));
	pLogg->AppendString("p= "+BNPrint(p,nSize));
	pLogg->AppendString("q= "+BNPrint(q,nSize));
	pLogg->AppendString("dP= "+BNToString(dP,nSize,16));
	pLogg->AppendString("dQ= "+BNToString(dQ,nSize,16));
	pLogg->AppendString("QInv= "+BNToString(qInv,nSize,16));


	dwTotalRSAKeyGenerationTime=dwEndTime-dwStartTime;


	UINT nNsize=BNBitLength(n,nSize);	
	pLogg->AppendString("-------------- Encryption/Decryption test");
	for ( i=0 ; i<5 ; i++ )
	{

		stmp.Format("------ Test nr %i.\r\n",i+1);
		pLogg->AppendString(stmp);
		pLogg->AppendString("Generating an Random message m<n.");
		for (j = 0; j <nSize-2 ; j++)
			m[j] = MTRandom();	

		ASSERT(BNCompare(m,n,nSize)<0);

		pLogg->AppendString("Encrypt c = m^e mod n");
		timeBeginPeriod(1);
		dwStartTime=timeGetTime();

		//BNModExp(c, m, e, n,nSize);
		RSAEncrypt(c,m,n,e,nSize);


		dwEndTime=timeGetTime();
		dwTotalEncryptionTime+=dwEndTime-dwStartTime;

		// Check decrypt  
		pLogg->AppendString("Decrypting m1 = c^d mod n");
		timeBeginPeriod(1);
		dwStartTime=timeGetTime();
		BNModExp(m1, c, d, n,nSize);
		dwEndTime=timeGetTime();
		timeEndPeriod(1);
		if ( !BNIsEqual(m1,m,nSize) )
		{
			pLogg->AppendString("Error m1 not equal to m..");
			BNFree(&n);
			BNFree(&d);
			BNFree(&p);
			BNFree(&q);
			BNFree(&dQ);
			BNFree(&dP);
			BNFree(&qInv);
			BNFree(&m);
			BNFree(&e);
			BNFree(&c);
			BNFree(&m1);
			BNFree(&m2);
			BNFree(&h);
			BNFree(&hq);
			return;
		}else
			pLogg->AppendString("Decryption Successfull");


		dwTotalNormalDecryptionTime+=(dwEndTime-dwStartTime);
		pLogg->AppendString("Decrypting using CRT method..");
		timeBeginPeriod(1);
		dwStartTime=timeGetTime();
		BNSetZero(m1,nSize);

		RSADecryptCRT(m1,c,p,q,dP,dQ,qInv,nSize);

		// Let m_1 = c^dP mod p.
		dwOverFlow=BNModExp(m1, c, dP, p,nSize);
		// Let m_2 = c^dQ mod q.
		dwOverFlow=BNModExp(m2, c, dQ, q,nSize);

		if (BNCompare(m1, m2,nSize) < 0)
			BNAdd(m1, m1, p,nSize);

		BNSubtract(m1, m1, m2,nSize);	
		BNModMult(h, qInv, m1, p,nSize/2);
		BNMultiply(hq, h, q,nSize/2);
		BNAdd(m1, m2, hq,nSize);

		dwEndTime=timeGetTime();
		timeEndPeriod(1);

		//stmp.Format("CRT Decryption computation time: %ims.\r\n",dwEndTime-dwStartTime);
		dwTotalDecryptionTime+=dwEndTime-dwStartTime;
		//sRet+=stmp;	

		if (! BNIsEqual(m1,m,nSize) )
		{
			pLogg->AppendString("Error m1 not equal to m..");
			BNFree(&n);
			BNFree(&d);
			BNFree(&p);
			BNFree(&q);
			BNFree(&dQ);
			BNFree(&dP);
			BNFree(&qInv);
			BNFree(&m);
			BNFree(&e);
			BNFree(&c);
			BNFree(&m1);
			BNFree(&m2);
			BNFree(&h);
			BNFree(&hq);
			return;
		}else
			pLogg->AppendString("CRT Decryption Successfull.");

	}

	pLogg->AppendString("\r\n---------------------------\r\n");
	stmp.Format("RSA Key Computation time: %ims, keysize: %i \r\n",dwTotalRSAKeyGenerationTime,nNsize);
	pLogg->AppendString(stmp);
	stmp.Format("Mean Encryption computation time: %0.2fms.\r\n",dwTotalEncryptionTime/(double)i);
	pLogg->AppendString(stmp);
	stmp.Format("Mean Decryption computation time: %0.2fms.\r\n",dwTotalNormalDecryptionTime/(double)i);
	pLogg->AppendString(stmp);
	stmp.Format("Mean CTR Decryption computation time: %0.2fms.\r\n",dwTotalDecryptionTime/(double)i);
	pLogg->AppendString(stmp);

	BNFree(&n);
	BNFree(&d);
	BNFree(&p);
	BNFree(&q);
	BNFree(&dQ);
	BNFree(&dP);
	BNFree(&qInv);
	BNFree(&m);
	BNFree(&e);
	BNFree(&c);
	BNFree(&m1);
	BNFree(&m2);
	BNFree(&h);
	BNFree(&hq);	
}



void MyCryptLib::DemoSimpleTest(CHistoryEdit *pLogg)
{
	// Be Safe.
	if(!pLogg)
		return;

	const UINT nSize=32; // 256 bits operations
	pLogg->AppendString("Multiprecision number operation test..\r\n-------------------");

	CString stmp;
	// We need some variables. 
	BOOL bTestOK=TRUE;
	UINT i=0;
	DWORD dwStartTime=0;
	DWORD dwEndTime=0;

	DWORD w[nSize]; 
	DWORD u[nSize];
	DWORD v[nSize];
	DWORD q[nSize];
	DWORD r[nSize];
	DWORD p1[nSize];
	DWORD p2[nSize];
	DWORD p3[nSize];
	DWORD g[nSize];

	// Make them all zero.. 

	BNSetZero(w,nSize);
	BNSetZero(u,nSize);
	BNSetZero(v,nSize);
	BNSetZero(q,nSize);
	BNSetZero(r,nSize);
	BNSetZero(p1,nSize);
	BNSetZero(p2,nSize);
	BNSetZero(p3,nSize);
	BNSetZero(g,nSize);

	/////////////////////////////////////////////////////////////////////////////
	// Start with 1+1=2 and 0xffffffff + 0xffffffff = 00000001 fffffffe


	pLogg->AppendString("----> 1+1=2 and 0xffffffff + 0xffffffff = 00000001 fffffffe.");
	BNSetEqualdw(u, 1, nSize);	// u = 1 

	DWORD carry = BNAdd(w, u, u, nSize);	// w = u + u 
	stmp.Format("%s + %s = %s, carry %lx.\r\n",BNPrint(u,nSize),BNPrint(u,nSize),BNPrint(w,nSize),carry);
	pLogg->AppendString(stmp);
	bTestOK&=(BNComparedw(w,2,nSize)==0);


	////////////////////////////////////////////////////////////////////////////
	/// Owerflow test 

	BNSetEqualdw(u, _MAXIMUMNR_, nSize);	// u = 0xffffffff
	BNSetEqualdw(v, _MAXIMUMNR_, nSize);	// u = 0xffffffff	
	carry = BNAdd(w, u, v, nSize);	// w = u + u 
	stmp.Format("%s + %s = %s, carry %lx.\r\n",BNPrint(u,nSize),BNPrint(v,nSize),BNPrint(w,nSize),carry);
	pLogg->AppendString(stmp);

	if ( bTestOK )
	{
		pLogg->AppendString("<---- Test OK\r\n");
	}else
	{
		pLogg->AppendString("<----- Test Failed\r\n");
		return;
	}

	/////////////////////////////////////////////////////////////////////////////
	/// Now Add and subtract

	pLogg->AppendString("----> Add and subtract of two random nr, 100 times..\r\n");
	for ( i=0; i<100 && bTestOK ; i++ )
	{
		BNSetZero(u,nSize);
		BNSetZero(v,nSize);
		BNMakeRandomNr(u, nSize-1);
		BNMakeRandomNr(v, nSize-1);
		carry = BNAdd(w, u, v, nSize);
		// r = w - v 
		carry = BNSubtract(r, w, v, nSize);
		// Check r == u
		bTestOK=BNIsEqual(r, u, nSize);
		ASSERT(bTestOK);
	}

	if ( bTestOK )
	{
		pLogg->AppendString("<---- Test OK\r\n");
	}else
	{
		pLogg->AppendString("<----- Test Failed\r\n");
		return;
	}

	/////////////////////////////////////////////////////////////////////////////
	/// Multiply and divide

	pLogg->AppendString("----> Multiply and divide test of two random nr, 100 times..\r\n");
	bTestOK=TRUE;
	timeBeginPeriod(1);
	dwStartTime=timeGetTime();
	for ( i=0 ; i<100 && bTestOK ; i++ )
	{
		// Make them all zero.. 
		BNSetZero(w,nSize);
		BNSetZero(u,nSize);
		BNSetZero(v,nSize);
		BNSetZero(q,nSize);
		BNSetZero(r,nSize);
		BNSetZero(p1,nSize);
		BNSetZero(p2,nSize);
		BNSetZero(p3,nSize);
		BNSetZero(g,nSize);
		// Short multipli and divide. 

		BNSetEqualdw(u,MTRandom(),nSize/2);
		BNSetEqualdw(v,MTRandom(),nSize/2);
		BNMultiply(w, u, v, nSize / 2);
		BNDivide(q, r, w, nSize, v, nSize / 2);
		bTestOK&=BNIsEqual(q, u, nSize / 2);
		bTestOK&=BNIsZero(r, nSize / 2);
		// Make them all zero.. 
		BNSetZero(w,nSize);
		BNSetZero(u,nSize);
		BNSetZero(v,nSize);
		BNSetZero(q,nSize);
		BNSetZero(r,nSize);
		BNSetZero(p1,nSize);
		BNSetZero(p2,nSize);
		BNSetZero(p3,nSize);
		BNSetZero(g,nSize);
		BNMakeRandomNr(u, nSize/2);
		BNMakeRandomNr(v, nSize/2);
		if ( BNIsZero(v,nSize/2) ) // is we have an zero divider 
			BNSetEqualdw(v,RandBetween(1,99999),nSize/2);
		//w=u*v
		BNMultiply(w, u, v, nSize / 2);
		// q=w/v, r=w%u
		BNDivide(q, r, w, nSize, v, nSize / 2);
		// Check q == u and r == 0 
		bTestOK&=BNIsEqual(q, u, nSize/2);
		bTestOK&=BNIsZero(r, nSize / 2);
		ASSERT(bTestOK);

		// Make them all zero.. 
		BNSetZero(w,nSize);
		BNSetZero(u,nSize);
		BNSetZero(v,nSize);
		BNSetZero(q,nSize);
		BNSetZero(r,nSize);
		BNSetZero(p1,nSize);
		BNSetZero(p2,nSize);
		BNSetZero(p3,nSize);
		BNSetZero(g,nSize);
		BNMakeRandomNr(u, nSize/2);
		BNMakeRandomNr(v, nSize/2);

		if ( BNIsZero(v,nSize/2) ) // Get zeros. 
			BNSetEqualdw(v,RandBetween(1,99999),nSize/2);
		// Divide one by the other: q = u / v, r = u % v 
		BNDivide(q, r, u, nSize/2, v, nSize/2);
		// Check w = q * v + r == u 
		BNMultiply(g, q, v, nSize/2);
		BNAdd(w, g, r, nSize/2);
		bTestOK&=BNIsEqual(w, u, nSize/2);
		ASSERT(bTestOK);
	}

	dwEndTime=timeGetTime();
	timeEndPeriod(1);
	stmp.Format("Computation time: %ims.\r\n",dwEndTime-dwStartTime);
	pLogg->AppendString(stmp);

	if ( bTestOK )
	{
		pLogg->AppendString("<---- Test OK\r\n");
	}else
	{
		pLogg->AppendString("<----- Test Failed\r\n");
		return;
	}

	pLogg->AppendString("----> Mult Test: ffffffff*ffffffff=fffffffe 00000001\r\n");
	BNSetEqualdw(v,_MAXIMUMNR_,nSize/2);
	BNSetEqualdw(u,_MAXIMUMNR_,nSize/2);
	//w=u*v
	BNMultiply(w, u, v, nSize / 2);

	stmp.Format("%s * %s = %s.\r\n",BNPrint(u,nSize),BNPrint(v,nSize),BNPrint(w,nSize));
	pLogg->AppendString(stmp);


	BNMultiplydw(w, u,_MAXIMUMNR_ , nSize / 2);
	stmp.Format("(short) %s * %s = %s.\r\n",BNPrint(u,nSize),BNPrint(v,nSize),BNPrint(w,nSize));
	pLogg->AppendString(stmp);

	pLogg->AppendString("<---- OK?\r\n");

	/////////////////////////////////////////////////////////////////////////////
	///  Greatest Common Divisor test & Prime nr generator ..
	pLogg->AppendString("----> Greatest Common Divisor & Prime nr generator test..\r\n");
	bTestOK=TRUE;

	dwStartTime=timeGetTime();	
	UINT np1=BNMakePrime(p1, nSize / 2);
	UINT np2=BNMakePrime(p2, nSize / 2);
	UINT np3=BNMakePrime(p3, nSize / 2);
	dwEndTime=timeGetTime();
	stmp.Format("%ims to Generate 3 prime numbers of size %ibits\r\n",dwEndTime-dwStartTime,np1);
	pLogg->AppendString(stmp);
	// u = p1 * p2 
	BNMultiply(u, p1, p2, nSize / 2);
	// v = p1 * p3 
	BNMultiply(v, p1, p3, nSize / 2);
	// Now calculate g = gcd(u, v) 
	BNGcd(g, u, v, nSize);

	bTestOK&=BNIsEqual(g, p1, nSize);

	if ( bTestOK )
	{
		pLogg->AppendString("<---- Test OK\r\n");
	}else
	{
		pLogg->AppendString("<----- Test Failed\r\n");
		return;
	}
	/////////////////////////////////////////////////////////////////////////////
	///  Modular Inverse 	

	pLogg->AppendString("----> Modular Inverse ..\r\n");
	bTestOK=TRUE;
	// Use previous prime as modulus, v.
	BNSetEqual(v, p1, nSize);

	// Pick a small multiplier
	DWORD m = MTRandom();

	// Set u = (vm - 1) 
	BNMultiplydw(u, v, m, nSize);
	BNSubtractdw(u, u, 1, nSize);

	BNModInv(w, u, v, nSize);
	// Check that g = (w * u) mod v = 1 
	BNModMult(g, w, u, v, nSize);
	bTestOK&=(BNComparedw(g, 1, nSize) == 0);
	if ( bTestOK )
	{
		pLogg->AppendString("<---- Test OK\r\n");
	}else
	{
		pLogg->AppendString("<----- Test Failed\r\n");
		return;
	}
	///////////////////////////////////////////////////////////////////////
	/// Check that (u mod n + v mod n) mod n == (u+v) mod n

	pLogg->AppendString("----> Check that (u mod n + v mod n) mod n == (u+v) mod n \r\n");
	bTestOK=TRUE;
	// Make them all zero.. 
	BNSetZero(w,nSize);
	BNSetZero(u,nSize);
	BNSetZero(v,nSize);
	BNSetZero(q,nSize);
	BNSetZero(r,nSize);
	BNSetZero(p1,nSize);
	BNSetZero(p2,nSize);
	BNSetZero(p3,nSize);
	BNSetZero(g,nSize);
	BNMakeRandomNr(u, nSize/2);
	BNMakeRandomNr(v, nSize/2);
	BNMakeRandomNr(w, nSize/2);
	// r = u mod w 
	BNMod(r,u,nSize/2,w,nSize/2);
	// q = v mod w 
	BNMod(q,v,nSize/2,w,nSize/2);
	// g = u mod n + v mod n 
	BNAdd(g,q,r,nSize/2);
	// r = (u mod w + v mod w) mod w 
	BNMod(r,g,nSize/2,w,nSize/2);
	// q = (u+v) mod w 
	BNSetEqual(p1, u,nSize/2);
	BNAdd(p2, p1, v,nSize/2);

	BNMod(q,p2,nSize/2,w,nSize/2);

	bTestOK&=(BNIsEqual(r,q,nSize/2));
	ASSERT(bTestOK);
	if ( bTestOK )
	{
		pLogg->AppendString("<---- Test OK\r\n");
	}else
	{
		pLogg->AppendString("<----- Test Failed\r\n");
		return;
	}
	///////////////////////////////////////////////////////////////////////
	/// Set u = v = ffff...ffff  test BNFromOct(..) & BNToOct(..) 
	pLogg->AppendString("---->  u = v = ffff...ffff  test BNFromOct(..) & BNToOct(..)  \r\n");
	bTestOK=TRUE;

	// Make them all zero.. 
	BNSetZero(w,nSize);
	BNSetZero(u,nSize);
	BNSetZero(v,nSize);
	BNSetZero(q,nSize);
	BNSetZero(r,nSize);
	BNSetZero(p1,nSize);
	BNSetZero(p2,nSize);
	BNSetZero(p3,nSize);
	BNSetZero(g,nSize);

	unsigned char ff [64];
	for ( i = 0; i < sizeof(ff) ; i++ )
		ff[i] = 0xff;


	BNFromOctets(u,nSize/2,ff, sizeof(ff));
	BNFromOctets(v,nSize/2,ff, sizeof(ff));

	//w=u*v
	BNMultiply(w, u, v, nSize / 2);

	stmp.Format("%s * %s = %s.",BNPrint(u,nSize),BNPrint(v,nSize),BNPrint(w,nSize));
	pLogg->AppendString(stmp);

	// q=w/v, r=w%u
	BNDivide(q, r, w, nSize, v, nSize / 2);
	// Check q == u and r == 0 
	bTestOK&=BNIsEqual(q, u, nSize/2);
	bTestOK&=BNIsZero(r, nSize / 2);
	ASSERT(bTestOK);

	if ( bTestOK )
	{
		pLogg->AppendString("<---- Test OK\r\n");
	}else
	{
		pLogg->AppendString("<----- Test Failed\r\n");
		return;
	}

	///////////////////////////////////////////////////////////////////////
	/// Do some conversions 

	pLogg->AppendString("---->  Do some conversions..\r\n");
	bTestOK=TRUE;

	// Make them all zero.. 
	BNSetZero(w,nSize);
	BNSetZero(u,nSize);
	BNSetZero(v,nSize);
	BNSetZero(q,nSize);
	BNSetZero(r,nSize);
	BNSetZero(p1,nSize);
	BNSetZero(p2,nSize);
	BNSetZero(p3,nSize);
	BNSetZero(g,nSize);

	char sHex[]= "BEA000CDC8A927BC36D29074EDDAACCBBBDEAD99922";
	BNFromHex(u,nSize,sHex,sizeof(sHex));
	stmp.Format("FromHex: %s.",BNPrint(u,nSize));
	pLogg->AppendString(stmp);

	stmp.Format("ToHex: %s.",BNToString(u,nSize,16));
	pLogg->AppendString(stmp);


	BNSetZero(u,nSize);
	char sInt[]= "1234567890123456789012345678901234567890";
	BNFromDecimal(u,nSize,sInt,sizeof(sInt));

	stmp.Format("FromInt: %s.",BNPrint(u,nSize));
	pLogg->AppendString(stmp);
	stmp.Format("ToInt: %s.",BNToString(u,nSize,10));
	pLogg->AppendString(stmp);
	//  343466 x 122 = 41902852 
	BNFromDecimal(u,nSize,"343466",6);
	BNFromHex(w,nSize,"27F6304",7);
	BNMultiplydw(v,u,122,nSize);
	stmp.Format("343466 * 122 = %s.",BNToString(u,nSize,10));
	pLogg->AppendString(stmp);
	bTestOK&=BNIsEqual(w,v,nSize);
	ASSERT(bTestOK);
	if ( bTestOK )
	{
		pLogg->AppendString("<---- Test OK\r\n");
	}else
	{
		pLogg->AppendString("<----- Test Failed\r\n");
		return;
	}
	pLogg->AppendString("<---- Test Finished\r\n");


}
#endif

/*
* Encrypts the message m with the public key n and public exp e. 	
* 
* Assumed that c,m,n have the same size. 
*
*/
int MyCryptLib::RSAEncrypt(DWORD c[], DWORD m[], DWORD n[], UINT nSize, DWORD e)
{
	// be Safe 
	if ( !c||!m||!n||nSize<=0 )
		return 0;

	int iRet=0;

	// Create some temporary data. 
	DWORD *pE=BNAlloc(nSize);
	if ( pE==NULL )
	{
		return -1;
	}
	BNSetEqualdw(pE,e,nSize);
	iRet=RSAEncrypt(c,m,n,pE,nSize);

	if( pE )
		BNFree(&pE);
	return iRet;
}

/*
* Encrypts the message m with the public key n and public exp e. 	
* 
* Assumed that c,m,n have the same size. 
*
*/
int MyCryptLib::RSAEncrypt(DWORD c[], DWORD m[], DWORD n[], DWORD e[], UINT nSize)
{
	// be Safe 
	if ( !c || !m || !n || !e || nSize<=0 )
		return -1;
	return  BNModExp(c, m, e, n,nSize);
}

/*
* Decrypt using the CRT RSA Method. 	
*
* Chinese Remainder Theorem
*
* The  private key as a quintuple  (p, q, dP, dQ, and qInv), is used 
* for the Chinese Remainder Theorem (CRT) decryption. 
* The CRT method of decryption is four times faster overall 
* than calculating m = c^d mod n.
* p and q are prime factors of n.
* dP and dQ are known as the CRT exponents.
* qInv is the CRT coefficient. 
* 
* nSize is the size of the public key n in bits. 
* The size of the Primenumbers is ~nSize/2. 
*
* In practice, common choices for e are 3, 17 and 65537 (2^16+1). These are Fermat primes and are chosen 
* because they make the modular exponentiation operation faster. 
*  
*/
int MyCryptLib::RSADecryptCRT(DWORD m[],DWORD c[],DWORD p[], DWORD q[], DWORD dP[], DWORD dQ[], DWORD qInv[], UINT nSize)
{
	DWORD dwOverFlow=0;
	// Create some temporary data. 
	DWORD *pm2=BNAlloc(nSize);
	if ( pm2==NULL )
	{
		return -1;
	}
	DWORD *ph=BNAlloc(nSize);

	if ( ph==NULL )
	{
		BNFree(&pm2);
		return -2;
	}

	DWORD *phq=BNAlloc(nSize);

	if ( phq==NULL )
	{
		BNFree(&pm2);
		BNFree(&ph);
		return -3;
	}

	// Clear the temporary variables.
	BNSetZero(pm2,nSize);
	BNSetZero(ph,nSize);
	BNSetZero(phq,nSize);


	// Let m_1 = c^dP mod p.
	dwOverFlow+=(DWORD)BNModExp(m, c, dP, p,nSize);
	// Let m_2 = c^dQ mod q.
	dwOverFlow+=(DWORD)BNModExp(pm2, c, dQ, q,nSize);

	// if  m < pm2 the make m=m+p
	if ( BNCompare(m, pm2,nSize) < 0 )
	{
		dwOverFlow+=BNAdd(m, m, p,nSize);
	}
	dwOverFlow+=BNSubtract(m, m, pm2,nSize);	
	dwOverFlow+=BNModMult(ph, qInv, m, p,nSize/2);
	dwOverFlow+=BNMultiply(phq, ph, q,nSize/2);
	dwOverFlow+=BNAdd(m, pm2, phq,nSize);

	BNFree(&pm2);
	BNFree(&ph);
	BNFree(&phq);
	return (int)dwOverFlow;
}

/*
* 	DigitalSignSHA1rDSA(...) 
*  Computes the SHA1 hash value of pmsgbuff and sign 
*  the result using. 
*
*  Digital Signatures Using Reversible Public Key (ANSI X9.31 -1998)
*    
*  pmsgBuff  - the msg that is going to be signed. 
*  nSizeMsg  - the size of pmsgBuff
*  d		  - the private RSA key. 
*  e		  - the public key. 
*  n		  - the trusted public key. (that the client already have) 
*  S		  - the signature. 
*  nSize	  - the size of n,d. 
* 
*/

int MyCryptLib::DigitalSignSHA1rDSA(unsigned char* pmsgbuff, UINT nSizeMsg,DWORD d[],DWORD n[],DWORD S[],UINT nSize)
{
	// Create some temporary data. 
	int iRet=0;
	DWORD *pHashvalue=BNAlloc(5); // 5*4 = 20 byte for SHA1 in enough
	if ( pHashvalue==NULL )
	{
		return -2;
	}

	BNSetZero(pHashvalue,5);
	BNSetZero(S,nSize);

	// Compute the hash... 
	SHA1Hash((unsigned char*)pHashvalue,pmsgbuff,nSizeMsg);

	//  Compute hash^d mod n
	iRet=BNModExp(S,pHashvalue,d,n,nSize);	

	BNFree(&pHashvalue);
	return iRet; 
}





BOOL MyCryptLib::DigitalVerifySHA1rDSA(unsigned char* pmsgbuff, UINT nSizeMsg,DWORD n[],DWORD e,DWORD S[],UINT nSize)
{

	BOOL bRet=TRUE;
	// Create some temporary data. 
	DWORD *ptmp=BNAlloc(nSize);
	if ( ptmp==NULL )
	{
		return FALSE;
	}

	DWORD *pHashvalue=BNAlloc(5); 
	if ( pHashvalue==NULL )
	{
		BNFree(&ptmp);
		return FALSE;
	}

	DWORD *ptmp2=BNAlloc(nSize); // 5*4 = 20 byte for SHA1 in enough
	if ( ptmp2==NULL ) 
	{

		BNFree(&ptmp);
		BNFree(&pHashvalue);
		return FALSE;
	}

	BNSetZero(pHashvalue,5);
	BNSetZero(ptmp,nSize);
	BNSetEqualdw(ptmp2,e,nSize);


	// Compute the hash... 
	SHA1Hash((unsigned char*)pHashvalue,pmsgbuff,nSizeMsg);

	// y=(S)^e mod n ptmp2=e=3. 
	BNModExp(ptmp,S,ptmp2,n,nSize);	

	//FIXME: change this.. 
	bRet=BNIsEqual(ptmp,pHashvalue,5);

	BNFree(&ptmp);
	BNFree(&ptmp2);
	BNFree(&pHashvalue);
	return bRet;
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

spinoza
Program Manager
Sweden Sweden
Amin Gholiha.
Education:
- Master of Science in Information Technology.
- Degree of Master of Education.
Knowledge/interest: programming (.NET,Visual, C#/C++), neural network, mathematical modeling, signal processing, sequence analysis, pattern recognition,robot technology, system design, security and business management systems. For business proposal email Gholiha@rocketmail.com, all other emails will be ignored.
Current Work:
Project Manager
www.easysoft.nu (the best free e-signature tool)

| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.141223.1 | Last Updated 21 Jun 2006
Article Copyright 2006 by spinoza
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid