superint.cpp

rsa加密过程中需要大数的幂运算后求模

// Superint.cpp: implementation of the CSuperint class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "SoftProtect.h"
#include "Superint.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
#define	BUFFER_STEP 16
#define BUFFER_BITS	4
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CSuperint::CSuperint(DWORD dwInit)
{
	m_pdwBuffer = new DWORD[BUFFER_STEP];
	memset(m_pdwBuffer,0,sizeof(DWORD)*BUFFER_STEP);
	m_BufferSize = BUFFER_STEP;
	m_BufferUsed = 1;
	m_pdwBuffer[0] = dwInit;
}

CSuperint::CSuperint(const CSuperint &siSource)
{
	m_BufferSize = siSource.m_BufferSize;
	m_BufferUsed = siSource.m_BufferUsed;
	m_pdwBuffer = new DWORD[m_BufferSize];
	memcpy(m_pdwBuffer,siSource.m_pdwBuffer,sizeof(DWORD)*m_BufferSize);
}

CSuperint::~CSuperint()
{
	delete []m_pdwBuffer;
}

void CSuperint::Expand(int iNewBufferSize)
{
	if(iNewBufferSize == 0)
		iNewBufferSize = m_BufferSize+BUFFER_STEP;	
	else
	{
		if(iNewBufferSize <= m_BufferSize)
			return;
	}

	iNewBufferSize += BUFFER_STEP-1;
	iNewBufferSize >>= 4;
	iNewBufferSize <<= 4;

	DWORD *pdwNewBuffer = new DWORD[iNewBufferSize];
	memset(pdwNewBuffer, 0, sizeof(DWORD)*iNewBufferSize);
	memcpy(pdwNewBuffer, m_pdwBuffer, sizeof(DWORD)*m_BufferSize);

	delete []m_pdwBuffer;
	m_pdwBuffer = pdwNewBuffer;
	m_BufferSize = iNewBufferSize;
}

BOOL CSuperint::IsBitOn(int iBitIndex)const 
{
	if(iBitIndex >= m_BufferUsed<<5)
		return FALSE;
	if(m_pdwBuffer[iBitIndex>>5]&(1<<(iBitIndex&0x1f)))
		return TRUE;
	else
		return FALSE;
}

void CSuperint::AddUnit(int iUnitIndex, DWORD dwAdding)
{
	if(dwAdding == 0)
		return;

	if(m_BufferSize <= iUnitIndex)
		Expand(iUnitIndex+1);//需要扩张容量

	if(m_BufferUsed < iUnitIndex+1)
		m_BufferUsed = iUnitIndex+1;

	m_pdwBuffer[iUnitIndex] += dwAdding;
	if(m_pdwBuffer[iUnitIndex] < dwAdding)
		AddUnit(iUnitIndex+1,1);//产生进位双字
}

CSuperint CSuperint::operator +(const CSuperint &siAdding) const
{
	CSuperint	siAdd1(*this);
	CSuperint	siAdd2(siAdding);

	if(siAdd1.m_BufferUsed < siAdd1.m_BufferUsed )
	{
		for(int i=0; i<siAdd1.m_BufferUsed; i++)
			siAdd2.AddUnit(i,siAdd1.m_pdwBuffer[i]);
		return siAdd2;
	}
	else
	{
		for(int i=0; i<siAdd2.m_BufferUsed; i++)
			siAdd1.AddUnit(i,siAdd2.m_pdwBuffer[i]);
		return siAdd1;
	}
}

void CSuperint::SubUnit(int iUnitIndex, DWORD dwSubbing)
{
	if(m_pdwBuffer[iUnitIndex] >= dwSubbing)
		m_pdwBuffer[iUnitIndex] -= dwSubbing;
	else
	{
		m_pdwBuffer[iUnitIndex] += 0xffffffff - dwSubbing;
		m_pdwBuffer[iUnitIndex] += 1;
		SubUnit(iUnitIndex+1,1);//高双字减1
	}
}

CSuperint CSuperint::operator -(const CSuperint &siSubbing) const
{
	CSuperint siSubbed(*this);
	if(siSubbed >= siSubbing)
	{
		for(int i=0; i<siSubbing.m_BufferUsed; i++)
			siSubbed.SubUnit(i, siSubbing.m_pdwBuffer[i]);
	}
	else
	{//被减数小于减数,则被减数归0
		memset(siSubbed.m_pdwBuffer, 0, siSubbed.m_BufferSize*sizeof(DWORD));
		siSubbed.m_BufferUsed = 1;
	}
	int iBitCount = siSubbed.GetUsedBits();
	siSubbed.m_BufferUsed = (iBitCount+31)>>5;
	if(siSubbed.m_BufferUsed == 0)
		siSubbed.m_BufferUsed = 1;
	return siSubbed;
}

BOOL CSuperint::operator >=(const CSuperint &siRight) const
{
	if(m_BufferUsed != siRight.m_BufferUsed)
		return (m_BufferUsed > siRight.m_BufferUsed);
	else
	{
		for(int i=m_BufferUsed-1; i>=0; i--)
		{
			if(m_pdwBuffer[i] == siRight.m_pdwBuffer[i])
				continue;
			return (m_pdwBuffer[i] > siRight.m_pdwBuffer[i]);
		}		
	}

	return TRUE;
}

void CSuperint::MulUnit(int iUnitIndex, DWORD dwMultting)
{
	CSuperint siTotal;
	for(int i=0; i<m_BufferUsed; i++)
	{
		DWORD dwMulLeft = m_pdwBuffer[i];

		DWORD dwLoLo = (dwMulLeft&0xffff)*(dwMultting&0xffff);
		DWORD dwHiHi = (dwMulLeft>>16)*(dwMultting>>16);
		DWORD dwHiLo = (dwMulLeft&0xffff)*(dwMultting>>16);
		DWORD dwLoHi = (dwMulLeft>>16)*(dwMultting&0xffff);
		siTotal.AddUnit(iUnitIndex+i,	dwLoLo);
		siTotal.AddUnit(iUnitIndex+i,	dwHiLo<<16);
		siTotal.AddUnit(iUnitIndex+i,	dwLoHi<<16);
		siTotal.AddUnit(iUnitIndex+i+1,	dwHiHi);
		siTotal.AddUnit(iUnitIndex+i+1,	dwHiLo>>16);
		siTotal.AddUnit(iUnitIndex+i+1,	dwLoHi>>16);
	}
	*this = siTotal;
}

void CSuperint::operator =(const CSuperint &siSource)
{
	if(siSource.m_BufferSize != m_BufferSize)
	{
		delete []m_pdwBuffer;
		m_BufferSize = siSource.m_BufferSize;
		m_pdwBuffer = new DWORD[m_BufferSize];
	}

	m_BufferUsed = siSource.m_BufferUsed;
	memcpy(m_pdwBuffer, siSource.m_pdwBuffer, sizeof(DWORD)*siSource.m_BufferSize);
}

CSuperint CSuperint::operator *(const CSuperint &siMultting) const
{
	CSuperint siTotal;

	for(int i=0; i<m_BufferUsed; i++)
	{
		CSuperint	temp(siMultting);
		temp.MulUnit(i,m_pdwBuffer[i]);//从右向左处理
		siTotal = siTotal +temp;
	}

	return siTotal;
}

CSuperint CSuperint::operator %(const CSuperint &siRight) const
{
	CSuperint siLeft(*this);
	int iRightSubLeftTimes = 0;
	int iRightBitCount = siRight.GetUsedBits();
	while(siLeft >= siRight)
	{
		int iLeftBitCount = siLeft.GetUsedBits();
		int iMoveBitCount = iLeftBitCount - iRightBitCount;
		CSuperint siSubbing(siRight);
		siSubbing.MulUnit(iMoveBitCount>>5,1<<(iMoveBitCount&31));
		if(siLeft >= siSubbing)
			siLeft = siLeft - siSubbing; 
		else
		{
			siLeft = siSubbing - siLeft;
			iRightSubLeftTimes++;
		}	
	}
	if(iRightSubLeftTimes&1)
		siLeft = siRight - siLeft ;
	return siLeft;
}

int CSuperint::GetUsedBits()const
{
	int iUsedBits = m_BufferUsed<<5;
	for(int i=0; i<m_BufferUsed<<5; i++)
	{
		int iMask = 1<<(31-(i&31));
		if(m_pdwBuffer[m_BufferUsed-1-(i>>5)]&iMask )
			break;
		iUsedBits--;
	}
	return iUsedBits;
}

CSuperint::CSuperint(const TCHAR *pInit)
{
	const int iBufferLength = _tcslen(pInit); 
	TCHAR tsValue[9];
	memset(tsValue,0,sizeof(tsValue));
	m_BufferUsed = (iBufferLength+7)>>3;
	m_BufferSize = (m_BufferUsed+BUFFER_STEP-1)>>BUFFER_BITS<<BUFFER_BITS;
	m_pdwBuffer = new DWORD[m_BufferSize];

	//头残余,即不能被8整除的部分在最高双字
	int iHeadStub = iBufferLength&7;
	memcpy(tsValue, pInit, sizeof(TCHAR)*iHeadStub);
	_stscanf(tsValue,_T("%x"),m_pdwBuffer+m_BufferUsed-1);

	//整dword值
	int iLoop = iBufferLength>>3;
	for(int i=0; i<iLoop; i++)
	{
		memcpy(tsValue,pInit+iBufferLength-(i+1)*8,sizeof(TCHAR)*8);
		_stscanf(tsValue,_T("%x"),m_pdwBuffer+i);
	}
}

int CSuperint::GetHex(TCHAR *pBuffer, int iBufferSize)
{
	int iBufferNumber = 0;
	if(m_BufferUsed > 0)
	{
		//头残余
		TCHAR tsHeadStub[9];
		memset(pBuffer,0,iBufferSize*sizeof(TCHAR));
		iBufferNumber = _stprintf(tsHeadStub,_T("%X"),m_pdwBuffer[m_BufferUsed-1]);
		if(iBufferNumber >= iBufferSize)
			return 0;
		
		//整dword值
		int iLoop = m_BufferUsed - 1;
		if(iBufferNumber+iLoop*8 >= iBufferSize)
			return 0;
		else
			_tcscpy(pBuffer,tsHeadStub);
		
		int iStart =  m_BufferSize+1-m_BufferUsed;
		for(int i=0; i<iLoop; i++)
		{
			_stprintf(pBuffer+iBufferNumber,_T("%08X"),m_pdwBuffer[m_BufferUsed-2-i]);
			iBufferNumber += 8;
		}
	}
	pBuffer[iBufferNumber] = _T('\0');
	return iBufferNumber;
}