RSA.rar_RSA算法_rsa_密码学RSA

// BigNum.cpp: implementation of the CBigNum class. // ////////////////////////////////////////////////////////////////////// #include <string.h> #include <stdio.h> #include <time.h> #include "bignum.h" const char CBigNum::szBase64[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"; ////////////////////////////////////////////////////////////////////// // Construction/Destruction ////////////////////////////////////////////////////////////////////// CBigNum::CBigNum() : m_arVal(0), m_nSize(0) { } CBigNum::CBigNum(unsigned int nValue) : m_arVal(0), m_nSize(0) { if (m_arVal != NULL) delete[] m_arVal; m_nSize=2; m_arVal = new unsigned int[m_nSize]; m_arVal[0] = nValue & 0xFFFF; m_arVal[1] = nValue >> 16; } CBigNum::~CBigNum() { if (m_arVal != NULL) { delete[] m_arVal; m_arVal = NULL; m_nSize = 0; } } CBigNum::CBigNum(const char *szSourceVal) : m_arVal(0), m_nSize(0) { *this=szSourceVal; } CBigNum & CBigNum::operator=(const char *szSourceVal) { unsigned int nLen = strlen(szSourceVal); unsigned int nIdx; const char *pChar; CBigNum Pow10; operator=(0U); if (m_arVal != NULL) { Pow10 = 1; for (pChar = szSourceVal + nLen - 1, nIdx=0; pChar >= szSourceVal; pChar--, nIdx++) { operator+=(Pow10 * (unsigned int)(*pChar - '0')); Pow10*=10; } } return *this; } CBigNum &CBigNum::operator+=(const CBigNum &rhs) { unsigned int nIdx; if (rhs.m_nSize > m_nSize) Resize(rhs.m_nSize); for (nIdx = 0; nIdx < rhs.m_nSize; nIdx++) { m_arVal[nIdx] += rhs.m_arVal[nIdx]; } HandleCarry(); return *this; } CBigNum &CBigNum::operator=(unsigned int intVal) { unsigned int nIdx; for (nIdx = 0; nIdx < m_nSize; nIdx++) { m_arVal[nIdx] = 0; } if (m_nSize <= 0) Resize(1); m_arVal[0] = intVal; HandleCarry(); return *this; } void CBigNum::HandleCarry() { unsigned int nIdx; for (nIdx=0; nIdx < m_nSize; nIdx++) { if ((m_arVal[nIdx] & 0xFFFF0000) != 0) { if (nIdx >= m_nSize - 1) { Resize(nIdx + 2); } m_arVal[nIdx+1] += (m_arVal[nIdx] >> 16); m_arVal[nIdx] &= 0xFFFF; } } } void CBigNum::Resize(unsigned int nNewSize) { unsigned int *pNewVal; unsigned int nIdx; if (nNewSize > 0) pNewVal = new unsigned int[nNewSize]; else pNewVal = NULL; if (nNewSize < m_nSize) m_nSize = nNewSize; for (nIdx=0; nIdx < m_nSize; nIdx++) { pNewVal[nIdx] = m_arVal[nIdx]; } for (;nIdx<nNewSize; nIdx++) { pNewVal[nIdx] = 0; } if (m_arVal) delete[] m_arVal; m_arVal = pNewVal; m_nSize = nNewSize; } CBigNum &CBigNum::operator>>=(unsigned int rhs) { unsigned int nIdx; if (m_nSize) { while(rhs>=16) { for (nIdx=0; nIdx < m_nSize-1; nIdx++) { m_arVal[nIdx] = m_arVal[nIdx+1]; } rhs-=16; m_arVal[nIdx] = 0; } } for (nIdx=0; nIdx < m_nSize-1; nIdx++) { m_arVal[nIdx] = (m_arVal[nIdx] >> rhs) | ((m_arVal[nIdx+1] << (16 - rhs)) & 0xFFFF); } if (nIdx < m_nSize) m_arVal[nIdx] >>= rhs; return *this; } CBigNum &CBigNum::operator<<=(unsigned int rhs) { unsigned int nIdx; if (m_nSize) { while(rhs>=16) { if (m_arVal[m_nSize-1]) Resize(m_nSize+1); for (nIdx = m_nSize-1; nIdx > 0; nIdx--) { m_arVal[nIdx] = m_arVal[nIdx-1]; } rhs -=16; m_arVal[0] = 0; } if ((m_arVal[m_nSize - 1] << rhs) & 0xFFFF0000) Resize(m_nSize + 1); } if (m_nSize) { for (nIdx = m_nSize-1; nIdx > 0; nIdx--) { m_arVal[nIdx] = (m_arVal[nIdx] << rhs) | (m_arVal[nIdx-1] >> (16-rhs)); m_arVal[nIdx] &= 0xFFFF; } m_arVal[0] <<= rhs; m_arVal[0] &= 0xFFFF; } return *this; } CBigNum CBigNum::operator<<(unsigned int rhs) const { CBigNum result(*this); result <<= rhs; return result; } CBigNum CBigNum::operator>>(unsigned int rhs) const { CBigNum result(*this); result >>= rhs; return result; } CBigNum::operator bool(void) const { unsigned int nIdx; for (nIdx=0; nIdx < m_nSize; nIdx++) if (m_arVal[nIdx]) return true; return false; } CBigNum & CBigNum::operator&=(CBigNum rhs) { unsigned int nIdx; unsigned int nMin; if (rhs.m_nSize < m_nSize) nMin = rhs.m_nSize; for (nIdx=0; nIdx < nMin; nIdx++) m_arVal[nIdx] &= rhs.m_arVal[nIdx]; for (;nIdx < m_nSize; nIdx++) m_arVal[nIdx] = 0; return *this; } unsigned int CBigNum::operator&(unsigned int rhs) { if (m_nSize) return m_arVal[0] & rhs; else return 0; } CBigNum &CBigNum::operator=(CBigNum rhs) { if (rhs.m_arVal != m_arVal) { delete m_arVal; m_arVal = NULL; m_nSize=0; unsigned int nIdx; Resize(rhs.m_nSize); for (nIdx = 0; nIdx < m_nSize; nIdx++) m_arVal[nIdx] = rhs.m_arVal[nIdx]; } return *this; } CBigNum CBigNum::Pow(unsigned int rhs) const { CBigNum Result(1); CBigNum CurrentVal = *this; while (rhs) { if (rhs & 1U) Result *=(CurrentVal); rhs >>= 1; CurrentVal *= CurrentVal; } return Result; } CBigNum CBigNum::PowMod(CBigNum rhs, const CBigNum &mod, const clock_t ctShowSteps) const { CBigNum Result(1); CBigNum CurrentVal = *this; int nSteps = rhs.log2(); clock_t ctStart, ctCurrent; ctStart = ctCurrent = clock(); while (rhs > 0U) { if (rhs.m_arVal[0] & 1U) { Result = (Result * CurrentVal) % mod; Result.Reduce(); } rhs>>=1U; CurrentVal = (CurrentVal * CurrentVal) % mod; CurrentVal.Reduce(); nSteps--; if (ctShowSteps) { if (clock() > ctCurrent + ctShowSteps) { ctCurrent = clock(); } } } return Result; } bool CBigNum::operator==(unsigned int rhs) const { if (m_nSize>=2) return ((m_arVal[0] == (rhs & 0xFFFF)) && ((m_arVal[1]<<16) == (rhs & 0xFFFF0000))); else if (m_nSize==1) return (m_arVal[0] == rhs); else return (rhs == 0); } bool CBigNum::operator!=(unsigned int rhs) const { return !(operator==(rhs)); } CBigNum CBigNum::operator *(const CBigNum &rhs) const { CBigNum Result=0U; unsigned int i, j; if (Result.m_nSize != rhs.m_nSize + m_nSize) Result.Resize(rhs.m_nSize + m_nSize); for (i=0; i < m_nSize; i++) { for (j=0; j<rhs.m_nSize; j++) Result.m_arVal[i+j] += m_arVal[i] * rhs.m_arVal[j]; Result.HandleCarry(); } return Result; } CBigNum &CBigNum::operator *=(const CBigNum &rhs) { return *this = *this * rhs; } CBigNum CBigNum::operator *(unsigned int rhs) const { unsigned int nIdx; CBigNum result(*this); if (result.m_nSize==0) { return result; } for (nIdx = 0; nIdx < result.m_nSize; nIdx++) { result.m_arVal[nIdx] *= rhs; } result.HandleCarry(); return result; } CBigNum::CBigNum(const CBigNum &copy) : m_nSize(0), m_arVal(0) { unsigned int nIdx; Resize(copy.m_nSize); for (nIdx = 0; nIdx < m_nSize; nIdx++) m_arVal[nIdx] = copy.m_arVal[nIdx]; } CBigNum &CBigNum::operator*=(unsigned int rhs) { unsigned int nIdx; if (m_nSize <= 0) { operator=(0U); } else { for (nIdx = 0; nIdx < m_nSize; nIdx++) { m_arVal[nIdx] *= rhs; } HandleCarry(); } return *this; } CBigNumString::CBigNumString() : m_szBuffer(NULL), m_nSize(0) { } CBigNumString::~CBigNumString() { if (m_szBuffer) { delete[] m_szBuffer; m_szBuffer = NULL; m_nSize = 0; } } void CBigNumString::Realloc(unsigned int nByteCount) { if (m_szBuffer) { delete[] m_szBuffer; m_szB