mycryptlib.cpp

提供加密的c/s 聊天程序。用到对称加密算法和非对称加密算法

	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) 
*