bignumber.h

RSA 高级实现

// BigNumber.h: interface for the CBigNumber class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_BIGNUMBER_H__87A218D7_579F_4D1C_92F2_9AD6B05FB1DB__INCLUDED_)
#define AFX_BIGNUMBER_H__87A218D7_579F_4D1C_92F2_9AD6B05FB1DB__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#define bnExtractBigBytes		bnExtractBigBytes_32
#define bnInsertBigBytes		bnInsertBigBytes_32
#define bnExtractLittleBytes	bnExtractLittleBytes_32
#define bnInsertLittleBytes		bnInsertLittleBytes_32
#define bnCopy					bnCopy_32
#define bnNorm					bnNorm_32
#define bnLSWord				bnLSWord_32
#define bnBits					bnBits_32
#define bnAdd					bnAdd_32
#define bnSub					bnSub_32
#define bnCmpQ					bnCmpQ_32
#define bnSetQ					bnSetQ_32
#define bnAddQ					bnAddQ_32
#define bnSubQ					bnSubQ_32
#define bnCmp					bnCmp_32
#define bnSquare				bnSquare_32
#define bnMul					bnMul_32
#define bnMulQ					bnMulQ_32
#define bnDivMod				bnDivMod_32
#define bnMod					bnMod_32
#define bnModQ					bnModQ_32
#define bnExpMod				bnExpMod_32
#define bnDoubleExpMod			bnDoubleExpMod_32
#define bnTwoExpMod				bnTwoExpMod_32
#define bnGcd					bnGcd_32
#define bnInv					bnInv_32
#define bnLShift				bnLShift_32
#define bnRShift				bnRShift_32
#define bnMakeOdd				bnMakeOdd_32

#define BITS2BYTES(b)	((b + 7) >> 3)

class CBigNumber  
{
protected:
	BOOL _ToStringXX(int nType, char* pszString, int nBufferSize) const;
	BOOL _StringXXFrom(int nType, const char* pszString);
	BOOL _GetNumber(int& n, int& nRunLen, int nType, const char* psz, int len);
public:
	void*		ptr;
	unsigned	size;
	unsigned	allocated;
	
	CBigNumber();
	virtual ~CBigNumber();

	//bytes array
	BOOL ToBytes(PBYTE pb, int nBufferSize, int* pnNeedBufferSize = NULL) const;
	BOOL BytesFrom(const PBYTE pb, int nBufferSize);
	
	//\x??  ? = 0123456789ABCDEF
	BOOL ToStringC(char* pszString, int nBufferSize) const;
	BOOL StringCFrom(const char* pszString);
	
	//??	? = 0123456789ABCDEF
	BOOL ToStringHex(char* pszString, int nBufferSize) const;
	BOOL StringHexFrom(const char* pszString);
	
	//?		? = 0123456789
	BOOL ToStringDec(char* pszString, int nBufferSize) const;
	BOOL StringDecFrom(const char* pszString);
	
	//friend helper functions
	//default, these functions are 64 bits
	friend void bnExtractBigBytes_32(CBigNumber const *bn, unsigned char *dest, unsigned lsbyte, unsigned dlen);
	friend int bnInsertBigBytes_32(CBigNumber *bn, unsigned char const *src, unsigned lsbyte, unsigned len);
	friend void bnExtractLittleBytes_32(CBigNumber const *bn, unsigned char *dest, unsigned lsbyte, unsigned dlen);
	friend int bnInsertLittleBytes_32(CBigNumber *bn, unsigned char const *src, unsigned lsbyte, unsigned len);
	friend int bnCopy_32(CBigNumber *dest, CBigNumber const *src);
	friend void bnNorm_32(CBigNumber *bn);
	friend unsigned bnLSWord_32(CBigNumber const *src);
	friend unsigned bnBits_32(CBigNumber const *src);
	friend int bnAdd_32(CBigNumber *dest, CBigNumber const *src);
	friend int bnSub_32(CBigNumber *dest, CBigNumber const *src);
	friend int bnCmpQ_32(CBigNumber const *a, unsigned b);
	friend int bnSetQ_32(CBigNumber *dest, unsigned src);
	friend int bnAddQ_32(CBigNumber *dest, unsigned src);
	friend int bnSubQ_32(CBigNumber *dest, unsigned src);
	friend int bnCmp_32(CBigNumber const *a, CBigNumber const *b);
	friend int bnSquare_32(CBigNumber *dest, CBigNumber const *src);
	friend int bnMul_32(CBigNumber *dest, CBigNumber const *a, CBigNumber const *b);
	friend int bnMulQ_32(CBigNumber *dest, CBigNumber const *a, unsigned b);
	friend int bnDivMod_32(CBigNumber *q, CBigNumber *r, CBigNumber const *n, CBigNumber const *d);
	friend int bnMod_32(CBigNumber *dest, CBigNumber const *src, CBigNumber const *d);
	friend unsigned bnModQ_32(CBigNumber const *src, unsigned d);
	friend int bnExpMod_32(CBigNumber *dest, CBigNumber const *n, CBigNumber const *exp, CBigNumber const *mod);
	friend int bnDoubleExpMod_32(CBigNumber *dest, CBigNumber const *n1, CBigNumber const *e1, CBigNumber const *n2, CBigNumber const *e2, CBigNumber const *mod);
	friend int bnTwoExpMod_32(CBigNumber *n, CBigNumber const *exp, CBigNumber const *mod);
	friend int bnGcd_32(CBigNumber *dest, CBigNumber const *a, CBigNumber const *b);
	friend int bnInv_32(CBigNumber *dest, CBigNumber const *src, CBigNumber const *mod);
	friend int bnLShift_32(CBigNumber *dest, unsigned amt);
	friend void bnRShift_32(CBigNumber *dest, unsigned amt);
	friend unsigned bnMakeOdd_32(CBigNumber *n);
	
	//this operators
	inline CBigNumber& operator=(unsigned n)			{ bnSetQ(this, n); return *this;	}
    inline CBigNumber& operator=(int i)					{ bnSetQ(this, i); return *this;	}
    inline CBigNumber& operator=(long lg)				{ bnSetQ(this, lg); return *this;	}
    inline CBigNumber& operator=(const CBigNumber& bn)	{ bnCopy(this, &bn); return *this;	}
    inline CBigNumber& operator=(CBigNumber* pbn)		{ bnCopy(this, pbn); return *this;	}
	
    inline CBigNumber& operator++()						{ bnAddQ(this, 1); return *this;	}
    inline CBigNumber& operator--()						{ bnSubQ(this, 1); return *this;	}

    inline CBigNumber& operator+=(int i)				{ bnAddQ(this, i); return *this;	}
    inline CBigNumber& operator+=(const CBigNumber& b)	{ bnAdd(this, &b); return *this;	}
	
    inline CBigNumber& operator-=(int i)				{ bnSubQ(this, i); return *this;	}
    inline CBigNumber& operator-=(const CBigNumber& b)	{ bnSub(this, &b); return *this;	}
	
    inline CBigNumber& operator*=(int i)				{ CBigNumber b; b = *this; bnMulQ(this, &b, i); return *this;}
    inline CBigNumber& operator*=(const CBigNumber& b)	{ CBigNumber br; br = *this; bnMul(this, &br, &b); return *this;}
	
    inline CBigNumber& operator/=(const CBigNumber& b)	{ CBigNumber q, r; bnDivMod(&q, &r, this, &b); *this = q; return *this;}
    inline CBigNumber& operator/=(int i)				{ CBigNumber b; b = i; *this /= b; return *this;}
	
    inline CBigNumber& operator%=(const CBigNumber& b)	{ CBigNumber q, r; bnDivMod(&q, &r, this, &b); *this = r; return *this;}
    inline CBigNumber& operator%=(int i)				{ CBigNumber b; b = i; *this %= b; return *this;}
	
    inline CBigNumber& operator<<=(int i)				{ bnLShift(this, i); return *this; }
    inline CBigNumber& operator>>=(int i)				{ bnRShift(this, i); return *this; }

	//friend operators
    friend CBigNumber operator-(const CBigNumber& bn)	
	{ CBigNumber b; b = 0; b -= bn; return b; }
	
    friend CBigNumber operator+(const CBigNumber& bn, int n)	
	{ CBigNumber b; b = bn; b += n; return b; };
    friend CBigNumber operator+(int n, const CBigNumber& bn)	
	{ CBigNumber b; b = bn; b += n; return b; };
    friend CBigNumber operator+(const CBigNumber& bn1,const CBigNumber& bn2) 
	{ CBigNumber b; b = bn1; b += bn2; return b; }
	
    friend CBigNumber operator-(const CBigNumber& bn, int n)
	{ CBigNumber b; b = bn; b -= n; return b; }
    friend CBigNumber operator-(int n,const CBigNumber& bn)
	{ CBigNumber b; b = n; b -= bn; return b; }
    friend CBigNumber operator-(const CBigNumber& bn1,const CBigNumber& bn2)
	{ CBigNumber b; b = bn1; b -= bn2; return b; }
	
    friend CBigNumber operator*(const CBigNumber& bn, int n)
	{ CBigNumber b; b = bn; b *= n; return b; }
    friend CBigNumber operator*(int n, const CBigNumber& bn)
	{ CBigNumber b; b = bn; b *= n; return b; }
    friend CBigNumber operator*(const CBigNumber& bn1, const CBigNumber& bn2)
	{ CBigNumber b; b = bn1; b *= bn2; return b; }
	
    friend CBigNumber operator/(const CBigNumber& bn, int n)
	{ CBigNumber b; b = bn; b /= n; return b; }
    friend CBigNumber operator/(const CBigNumber& bn1, const CBigNumber& bn2)
	{ CBigNumber b; b = bn1; b /= bn2; return b; }
	
	//the return value will be <= n, so bnLSWord is safe
    friend int operator%(const CBigNumber& bn, int n) 
	{ CBigNumber b; b = bn; b %= n; return bnLSWord(&b); }
    friend CBigNumber operator%(const CBigNumber& bn1, const CBigNumber& bn2)
	{ CBigNumber b; b = bn1; b %= bn2; return b; }
	
    friend CBigNumber operator<<(const CBigNumber& bn, int n)
	{ CBigNumber b; b = bn; b <<= n; return b; }
    friend CBigNumber operator>>(const CBigNumber& bn, int n)
	{ CBigNumber b; b = bn; b >>= n; return b; }
	
    friend BOOL operator<=(const CBigNumber& b1,const CBigNumber& b2)
	{ int n = bnCmp(&b1, &b2); return n <= 0; }
    friend BOOL operator>=(const CBigNumber& b1,const CBigNumber& b2)
	{ int n = bnCmp(&b1, &b2); return n >= 0; }
    friend BOOL operator==(const CBigNumber& b1,const CBigNumber& b2)
	{ int n = bnCmp(&b1, &b2); return n == 0; }
    friend BOOL operator!=(const CBigNumber& b1,const CBigNumber& b2)
	{ int n = bnCmp(&b1, &b2); return n != 0; }
    friend BOOL operator<(const CBigNumber& b1,const CBigNumber& b2)
	{ int n = bnCmp(&b1, &b2); return n < 0; }
    friend BOOL operator>(const CBigNumber& b1,const CBigNumber& b2)
	{ int n = bnCmp(&b1, &b2); return n > 0; }

    friend BOOL operator<=(const CBigNumber& b1,const int n2)
	{ int n = bnCmpQ(&b1, n2); return n <= 0; }
    friend BOOL operator>=(const CBigNumber& b1,const int n2)
	{ int n = bnCmpQ(&b1, n2); return n >= 0; }
    friend BOOL operator==(const CBigNumber& b1,const int n2)
	{ int n = bnCmpQ(&b1, n2); return n == 0; }
    friend BOOL operator!=(const CBigNumber& b1,const int n2)
	{ int n = bnCmpQ(&b1, n2); return n != 0; }
    friend BOOL operator<(const CBigNumber& b1,const int n2)
	{ int n = bnCmpQ(&b1, n2); return n < 0; }
    friend BOOL operator>(const CBigNumber& b1,const int n2)
	{ int n = bnCmpQ(&b1, n2); return n > 0; }
	
	int AsInt() { return bnLSWord(this); }
	int GetBits() { return bnBits(this); };

#if !defined(__NO_RSA_HELPER__)
	//RSA helper
	/* Generate a prime >= bn. leaving the result in bn. */
	int __cdecl bnPrimeGen(unsigned (*randnum)(unsigned),
			   int (*f)(void *arg, int c), void *arg, unsigned exponent, ...);
	/*
	 * Generate a prime of the form bn + k*step.  Step must be even and
	 * bn must be odd.
	 */
	int bnPrimeGenStrong(CBigNumber const *step, int (*f)(void *arg, int c), void *arg);
#endif /*!__NO_RSA_HELPER__*/
};

#endif // !defined(AFX_BIGNUMBER_H__87A218D7_579F_4D1C_92F2_9AD6B05FB1DB__INCLUDED_)