gbignumber.cpp

一个非常有用的开源代码

		m_pBits[n] <<= nBits;
		m_pBits[n] |= nCarry;
		nCarry = nNextCarry;
	}
}

void GBigNumber::ShiftLeftUInts(unsigned int nUInts)
{
	if(m_nUInts == 0)
		return;
	if(nUInts == 0)
		return;
	if(!(nUInts == 1 && m_pBits[m_nUInts - 1] == 0)) // optimization to make Multiply faster
		Resize((m_nUInts + nUInts) * BITS_PER_INT);
	unsigned int n = m_nUInts - 1;
	if(n >= nUInts)
	{
		while(true)
		{
			m_pBits[n] = m_pBits[n - nUInts];
			if(n - nUInts == 0)
			{
				n--;
				break;
			}
			n--;
		}
	}
	while(true)
	{
		m_pBits[n] = 0;
		if(n == 0)
			break;
		n--;
	}
	return;
}

void GBigNumber::ShiftRight(unsigned int nBits)
{
	ShiftRightBits(nBits % BITS_PER_INT);
	ShiftRightUInts(nBits / BITS_PER_INT);
}

void GBigNumber::ShiftRightBits(unsigned int nBits)
{
	if(m_nUInts == 0)
		return;
	if(nBits == 0)
		return;
	unsigned int n = m_nUInts - 1;
	unsigned int nCarry = 0;
	unsigned int nNextCarry;
	while(true)
	{
		nNextCarry = m_pBits[n] << (BITS_PER_INT - nBits);
		m_pBits[n] >>= nBits;
		m_pBits[n] |= nCarry;
		nCarry = nNextCarry;
		if(n == 0)
			break;
		n--;
	}
}

void GBigNumber::ShiftRightUInts(unsigned int nUInts)
{
	if(m_nUInts == 0)
		return;
	if(nUInts == 0)
		return;
	unsigned int n;
	for(n = 0; n + nUInts < m_nUInts; n++)
		m_pBits[n] = m_pBits[n + nUInts];
	for(;n < m_nUInts; n++)
		m_pBits[n] = 0;
}

void GBigNumber::Or(GBigNumber* pBigNumber)
{
	if(m_nUInts < pBigNumber->m_nUInts)
		Resize(pBigNumber->m_nUInts * BITS_PER_INT);
	unsigned int n;
	for(n = 0; n < m_nUInts; n++)
		m_pBits[n] |= pBigNumber->GetUInt(n);
}

void GBigNumber::And(GBigNumber* pBigNumber)
{
	unsigned int n;
	for(n = 0; n < m_nUInts; n++)
		m_pBits[n] &= pBigNumber->GetUInt(n);
}

void GBigNumber::Xor(GBigNumber* pBigNumber)
{
	if(m_nUInts < pBigNumber->m_nUInts)
		Resize(pBigNumber->m_nUInts * BITS_PER_INT);
	unsigned int n;
	for(n = 0; n < m_nUInts; n++)
		m_pBits[n] ^= pBigNumber->GetUInt(n);
}

void GBigNumber::Multiply(GBigNumber* pBigNumber, unsigned int nUInt)
{
	if(nUInt == 0)
	{
		SetToZero();
		return;
	}
	SetToZero();
	Resize((pBigNumber->m_nUInts + 1) * BITS_PER_INT);
	unsigned int n;
	for(n = 0; n < pBigNumber->m_nUInts; n++)
	{
#ifdef BYTE_ORDER_BIG_ENDIAN
		__int64 prod = (__int64)pBigNumber->m_pBits[n] * (__int64)nUInt;
		__int64 rev;
		((unsigned int*)&rev)[0] = ((unsigned int*)&prod)[1];
		((unsigned int*)&rev)[1] = ((unsigned int*)&prod)[0];
		*((__int64*)&m_pBits[n]) += rev;
#else // BYTE_ORDER_BIG_ENDIAN
		*((__int64*)&m_pBits[n]) += (__int64)pBigNumber->m_pBits[n] * (__int64)nUInt;
#endif // !BYTE_ORDER_BIG_ENDIAN
	}
}

void GBigNumber::Multiply(GBigNumber* pFirst, GBigNumber* pSecond)
{
	SetToZero();
	Resize(pFirst->GetBitCount() + pSecond->GetBitCount());
	GBigNumber tmp;
	unsigned int nUInts = pFirst->m_nUInts;
	if(pSecond->m_nUInts > nUInts)
		nUInts = pSecond->m_nUInts;
	unsigned int n;
	for(n = 0; n < nUInts; n++)
	{
		ShiftLeftUInts(1);
		tmp.Multiply(pFirst, pSecond->GetUInt(nUInts - 1 - n));
		Add(&tmp);
	}
	m_bSign = ((pFirst->m_bSign == pSecond->m_bSign) ? true : false);
}

void GBigNumber::Divide(GBigNumber* pInNominator, GBigNumber* pInDenominator, GBigNumber* pOutRemainder)
{
	SetToZero();
	Resize(pInNominator->GetBitCount());
	pOutRemainder->SetToZero();
	pOutRemainder->Resize(pInDenominator->GetBitCount());
	unsigned int nBits = pInNominator->GetBitCount();
	unsigned int n;
	for(n = 0; n < nBits; n++)
	{
		pOutRemainder->ShiftLeftBits(1);
		pOutRemainder->SetBit(0, pInNominator->GetBit(nBits - 1 - n));
		ShiftLeftBits(1);
		if(pOutRemainder->CompareTo(pInDenominator) >= 0)
		{
			SetBit(0, true);
			pOutRemainder->Subtract(pInDenominator);
		}
		else
		{
			SetBit(0, false);
		}
	}
	m_bSign = ((pInNominator->m_bSign == pInDenominator->m_bSign) ? true : false);
	pOutRemainder->m_bSign = pInNominator->m_bSign;
}

// DO NOT use for crypto
// This is NOT a cryptographic random number generator
void GBigNumber::SetRandom(unsigned int nBits)
{
	Resize(nBits);
	unsigned int nBytes = nBits / 8;
	unsigned int nExtraBits = nBits % 8;
	unsigned int n;
	for(n = 0; n < nBytes; n++)
		((unsigned char*)m_pBits)[n] = (unsigned char)rand();
	if(nExtraBits > 0)
	{
		unsigned char c = (unsigned char)rand();
		c <<= (8 - nExtraBits);
		c >>= (8 - nExtraBits);
		((unsigned char*)m_pBits)[n] = c;
	}
}

// Input:  integers a, b
// Output: [this,x,y] where "this" is the greatest common divisor of a,b and where g=xa+by (x or y can be negative)
void GBigNumber::Euclid(GBigNumber* pA1, GBigNumber* pB1, GBigNumber* pOutX/*=NULL*/, GBigNumber* pOutY/*=NULL*/)
{
	GBigNumber q;
	GBigNumber r;
	GBigNumber x;
	GBigNumber y;

	GBigNumber a;
	a.Copy(pA1);
	a.SetSign(true);

	GBigNumber b;
	b.Copy(pB1);
	b.SetSign(true);

	GBigNumber x0;
	x0.Increment();
	x0.SetSign(pA1->GetSign());
	GBigNumber x1;
	GBigNumber y0;
	GBigNumber y1;
	y1.Increment();
	y1.SetSign(pB1->GetSign());

	while(!b.IsZero())
	{
		q.Divide(&a, &b, &r);
		a.Copy(&b);
		b.Copy(&r);
		
		x.Multiply(&x1, &q);
		x.Invert();
		x.Add(&x0);
		
		x0.Copy(&x1);
		x1.Copy(&x);

		y.Multiply(&y1, &q);
		y.Invert();
		y.Add(&y0);

		y0.Copy(&y1);
		y1.Copy(&y);
	}
	Copy(&a);
	if(pOutX)
		pOutX->Copy(&x0);
	if(pOutY)
		pOutY->Copy(&y0);
}


// Input:  pProd is the product of (p - 1) * (q - 1) where p and q are prime
//         pRandomData is some random data that will be used to pick the key.
// Output: It will return a key that has no common factors with pProd.  It starts
//         with the random data you provide and increments it until it fits this
//         criteria.
void GBigNumber::SelectPublicKey(const unsigned int* pRandomData, int nRandomDataUInts, GBigNumber* pProd)
{
	// copy random data
	SetToZero();
	int n;
	for(n = nRandomDataUInts - 1; n >= 0; n--)
		SetUInt(n, pRandomData[n]);

	// increment until this number has no common factor with pProd
	GBigNumber tmp;
	while(true)
	{
		tmp.Euclid(this, pProd);
		tmp.Decrement();
		if(tmp.IsZero())
			break;
		Increment();
	}
}

// (Used by CalculatePrivateKey)
void EuclidSwap(GBigNumber* a, GBigNumber* b, GBigNumber* c)
{
	GBigNumber t1;
	t1.Copy(a);
	a->Copy(b);
	GBigNumber tmp;
	tmp.Multiply(b, c);
	b->Copy(&t1);
	b->Subtract(&tmp);
}

// Input:  pProd is the product of (p - 1) * (q - 1) where p and q are prime
//         pPublicKey is a number that has no common factors with pProd
// Output: this will become a private key to go with the public key
void GBigNumber::CalculatePrivateKey(GBigNumber* pPublicKey, GBigNumber* pProd)
{
	GBigNumber d;
	GBigNumber q;
	GBigNumber d2;
	GBigNumber u;
	GBigNumber u2;
	GBigNumber v;
	GBigNumber v2;
	GBigNumber r; // holds a remainder (unused)

	d.Copy(pPublicKey);
	d2.Copy(pProd);

	u.Increment();
	v2.Increment();

	while(true)
	{
		if(d2.IsZero())
			break;

		q.Divide(&d, &d2, &r);

		EuclidSwap(&d, &d2, &q);                
		EuclidSwap(&u, &u2, &q);                
		EuclidSwap(&v, &v2, &q);       
	}        

	if(!u.GetSign())
		u.Add(pProd);        
	Copy(&u);
}

// Input:  a, k>=0, n>=2
// Output: "this" where "this" = (a^k)%n   (^ = exponent operator, not xor operatore)
void GBigNumber::PowerMod(GBigNumber* pA, GBigNumber* pK, GBigNumber* pN)
{
	GBigNumber k;
	k.Copy(pK);
	GBigNumber c;
	c.Copy(pA);
	GBigNumber b;
	b.Increment();
	GBigNumber p;
	GBigNumber q;
	while(!k.IsZero())
	{
		if(k.GetBit(0))
		{
			k.Decrement();
			p.Multiply(&b, &c);
			q.Divide(&p, pN, &b);
		}
		p.Multiply(&c, &c);
		q.Divide(&p, pN, &c);
		k.ShiftRightBits(1);
	}
	Copy(&b);
}

// Input:  n>=3, a where 2<=a<n
// Output: "true" if this is either prime or a strong pseudoprime to base a,
//		   "false" otherwise
bool GBigNumber::MillerRabin(GBigNumber* pA)
{
	if(!GetBit(0))
		return false;
	GBigNumber g;
	g.Euclid(pA, this);
	GBigNumber one;
	one.Increment();
	if(g.CompareTo(&one) > 0)
		return false;
	GBigNumber m;
	m.Copy(this);
	m.Decrement();
	GBigNumber s;
	while(!m.GetBit(0))
	{
		m.ShiftRightBits(1);
		s.Increment();
	}
	GBigNumber b;
	b.PowerMod(pA, &m, this);
	if(b.CompareTo(&one) == 0)
		return true;
	Decrement();
	int nCmp = b.CompareTo(this);
	Increment();
	if(nCmp == 0)
		return true;
	GBigNumber i;
	GBigNumber b1;
	i.Increment();
	while(i.CompareTo(&s) < 0)
	{
		m.Multiply(&b, &b);
		g.Divide(&m, this, &b1);
		Decrement();
		nCmp = b1.CompareTo(this);
		Increment();
		if(nCmp == 0)
			return true;

		if(b1.CompareTo(&one) == 0)
			return false;
		b.Copy(&b1);
		i.Increment();
	}
	return false;
}

// Output: true = pretty darn sure (99.99%) it's prime
//		   false = definately (100%) not prime
bool GBigNumber::IsPrime()
{
	// Two is prime.  All values less than Two are not prime
	GBigNumber two;
	two.Increment();
	two.Increment();
	int nCmp = CompareTo(&two);
	if(nCmp < 1)
	{
		if(nCmp == 0)
			return true; // two is prime
		else
			return false; // values less than two are not prime
	}

	// 9 and 15 are the only 4-bit odd primes
	unsigned int nBits = GetBitCount();
	if(nBits <= 4)
	{
		unsigned int nValue = GetUInt(0);
		if((nValue & 1) == 0)
			return false;
		if(nValue == 9 || nValue == 15)
			return false;
		return true;
	}

	// Do 25 itterations of Miller-Rabin
	nBits--;
	unsigned int i;
	GBigNumber a;
	for(i = 1; i <= 25; i++)
	{
		a.SetRandom(nBits);
		if(a.CompareTo(&two) < 0)
		{
			i--;
			continue;
		}
		if(!MillerRabin(&a))
			return false;
	}
	return true;
}

void GBigNumber::SetToRand(GRand* pRand)
{
	SetToZero();
	const unsigned int* pData = (const unsigned int*)pRand->GetRand();
	int nUInts = pRand->GetRandByteCount() / sizeof(unsigned int);
	int n;
	for(n = nUInts - 1; n >= 0; n--)
		SetUInt(n, pData[n]);
}