huge.cpp

详细的AESRSASHA1实现原理

// Huge.cpp: implementation of the CHuge class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Huge.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
CHuge::CHuge ( )
{
    m_iSize = MAX_HUGE_SIZE;
    Zero();
}

CHuge::~CHuge ( )
{
    
}

void CHuge::Zero ( )
{
    for ( int i = 0; i < m_iSize; i++ ) m_pValue[i] = 0;
    
    m_bSign  = 0;
    m_iSize  = 1;
}

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
bool CHuge::CreateFromBytes ( BYTE pBytes[], int size )
{
    int  i, t;
    
    Zero( );
    t = size >> ELEM_BYTE_SIZE_LOG2;
    if ( size & ELEM_BYTE_SIZE_MASK ) t++;
    
    if ( t > MAX_HUGE_SIZE ) return false;
    if ( t == 0 ) return true;
    
    m_iSize = t;
    for ( i = 0; i < size; i++ )
    {
        int t0 = i >> ELEM_BYTE_SIZE_LOG2;
        int t1 = i &  ELEM_BYTE_SIZE_MASK;
        int t2 = t1 << 3;
        BYTE t3 = pBytes[i];
        m_pValue[t0] |= t3 << t2;
    }
    
    Tidy( );
    
    return true;
}

bool CHuge::TransToBytes ( BYTE pBytes[], int size )
{
    unsigned len, i, t0, t1, t2;
    
    if ( *this == 0 ) return true;
    
    len = (m_iSize-1) << ELEM_BYTE_SIZE_LOG2;
    for ( t0 = m_pValue[m_iSize-1]; t0; t0>>=8, len++ );
    if ( len > size ) return false;
    
    for ( i = 0; i < len; i++ )
    {
        t0 = i >> ELEM_BYTE_SIZE_LOG2;
        t1 = i & ELEM_BYTE_SIZE_MASK;
        t2 = (3-t1) << 3;

        pBytes[i] = (m_pValue[t0]<<t2) >> 24;
    }
    
    for ( i = len; i < size; i++ ) pBytes[i] = 0;
    
    return true;
}

//////////////////////////////////////////////////////////////////////
// Print
//////////////////////////////////////////////////////////////////////
void CHuge::Tidy ( )
{
    while ( (m_iSize > 0) && (m_pValue[m_iSize-1] == 0) ) --m_iSize;
    
    if ( m_iSize == 0 ) m_iSize = 1;
}

//////////////////////////////////////////////////////////////////////
// Get / Set
//////////////////////////////////////////////////////////////////////
bool CHuge::IsMinus ( )
{
    return m_bSign;
}

unsigned CHuge::GetBitLength ( )
{
    unsigned zeros = 0, t = 1<<ELEM_BIT_SIZE_MASK;
    
    while ( t && (m_pValue[m_iSize-1] & t) == 0 )
    {
        ++zeros;
        t >>= 1;
    }
    
    return (m_iSize<<ELEM_BIT_SIZE_LOG2)-zeros;
}

void CHuge::SetBit ( unsigned pos, bool flag )
{
    if ( flag )
        m_pValue[pos>>ELEM_BIT_SIZE_LOG2] |= ( 1 << (pos&ELEM_BIT_SIZE_MASK) );
    else
        m_pValue[pos>>ELEM_BIT_SIZE_LOG2] &= ~( 1 << (pos&ELEM_BIT_SIZE_MASK) );
}

bool CHuge::GetBit ( unsigned pos )
{
    if ( m_pValue[pos>>ELEM_BIT_SIZE_LOG2] & ( 1 << (pos&ELEM_BIT_SIZE_MASK) ) )
        return true;
    
    return false;
}

unsigned CHuge::CountLastZeros ( )
{
    int i, cnt, t;
    if( *this == 0 )  return 1;
    
    for ( i = 0; (i < m_iSize) && (m_pValue[i] == 0); i++ );
    cnt = i*ELEM_BIT_SIZE;
    
    t = m_pValue[i];
    while( (t&1) == 0 )
    {
        ++cnt;
        t >>= 1;
    }
    
    return cnt;
}

//////////////////////////////////////////////////////////////////////
// evaluate 
//////////////////////////////////////////////////////////////////////
void CHuge::operator = ( const int n )
{
    Zero();
    
    if( n>=0 )
    {
        m_pValue[0] = n;
    }
    else
    {
        m_pValue[0] = -n;
        m_bSign = 1;
    }
}

void CHuge::operator = ( const CHuge n )
{
    Zero();
    m_iSize = n.m_iSize;
    m_bSign = n.m_bSign;
    
    for ( int i = 0; i < m_iSize; i++ )
        m_pValue[i] = n.m_pValue[i];
}

//////////////////////////////////////////////////////////////////////
// Subscript
//////////////////////////////////////////////////////////////////////
unsigned& CHuge::operator [] ( const int index )
{
    return m_pValue[index];
}

unsigned CHuge::operator [] ( const int index )const
{
    return m_pValue[index];
}

//////////////////////////////////////////////////////////////////////
// Compare
//////////////////////////////////////////////////////////////////////
bool operator <	( CHuge& a, CHuge& b )
{
    return (Compare( a, b ) == -1);
}

bool operator >= ( CHuge& a, CHuge& b )
{ 
    return !(Compare( a, b ) == -1);
}

bool operator >	( CHuge& a, CHuge& b )
{  
    return (Compare( a, b ) == 1);
}

bool operator <= ( CHuge& a, CHuge& b )
{ 
    return !(Compare( a, b ) == 1);
}

bool operator == ( CHuge& a, CHuge& b )
{
    return (Compare( a, b ) == 0);
}

bool operator != ( CHuge& a, CHuge& b )
{
    return !(Compare( a, b ) == 0);
}

bool operator == ( CHuge& a, int n )
{
    if ( a.m_iSize != 1 )   return false;
    
    bool sign = 0;
    if ( n < 0 )
    {
        sign = 1; 
        n   = -n;
    }
    if ( sign != a.m_bSign )    return false;
    if ( a.m_pValue[0] != n )   return false;
    
    return true;
}

bool operator != ( CHuge& a, int n )
{
    if ( a.m_iSize != 1 )   return true;
    
    bool sign = 0;
    if ( n < 0 )
    {
        sign = 1; 
        n   = -n;
    }
    if ( sign != a.m_bSign )    return false;
    if ( a.m_pValue[0] == n )   return false;
    
    return true;
}

//////////////////////////////////////////////////////////////////////
// Algorithm
//////////////////////////////////////////////////////////////////////
CHuge operator << ( CHuge& n, unsigned shift )
{
    CHuge	    res;
    unsigned    t, lsh, rsh, left, right;
    int         i;
    
    t	= shift >> ELEM_BIT_SIZE_LOG2;
    lsh	= shift &  ELEM_BIT_SIZE_MASK;
    rsh = ELEM_BIT_SIZE - lsh;
    
    res.m_iSize = n.m_iSize+t;
    if ( res.m_iSize > MAX_HUGE_SIZE ) { res = 0; return res; } 
    
    if ( lsh == 0 )
    {
        for ( i = t; i < res.m_iSize; i++ )
            res[i]  = n[i-t];
    }
    else
    {
        right = 0;
        for ( i = t; i < res.m_iSize; i++ )
        {
            left	= n[i-t] << lsh;
            res[i]  = left | right;
            right	= n[i-t] >> rsh;
        }
        if ( right )
        {
            res[res.m_iSize]	= right;
            ++res.m_iSize;
        }
    }
    
    return res;
}

CHuge operator >> ( CHuge& n, unsigned shift )
{
    CHuge	    res;
    unsigned    t, lsh, rsh, left, right, mask;
    int         i;
    
    t	= shift >> ELEM_BIT_SIZE_LOG2;
    rsh	= shift &  ELEM_BIT_SIZE_MASK;
    lsh = ELEM_BIT_SIZE - rsh;
    
    res.m_iSize = n.m_iSize-t;
    
    if ( rsh == 0 )
    {
        for ( i = res.m_iSize-1; i >= 0; i-- )
            res[i]  = n[i+t];
    }
    else
    {
        left = 0;
        mask = (1<<rsh)-1;
        for ( i = res.m_iSize-1; i >= 0; i-- )
        {
            right   = n[i+t] >> rsh;
            res[i]  = left | right;
            left    = (n[i+t] & mask) << lsh;
        }
        
        res.Tidy( );
    }
    
    return res;
}

CHuge operator - ( CHuge& n )
{
    CHuge res;
    
    res = n;
    res.m_bSign = !n.m_bSign;
    
    return res;
}

CHuge operator + ( CHuge& a, CHuge& b )
{
    CHuge	res;
    
    if ( a.m_bSign == b.m_bSign )
    {
        res = AbsAdd( a, b );
        res.m_bSign = a.m_bSign;
    }
    else
    {
        int abscmp = AbsCompare( a, b );
        
        if ( abscmp == 1 )
        {
            res = AbsSub( a, b );
            res.m_bSign = a.m_bSign;
        }
        else if ( abscmp == -1 )
        {
            res = AbsSub( b, a );
            res.m_bSign = b.m_bSign;
        }
        else
        {
            res = 0;
        }
    }
    
    return res;
}

CHuge operator - ( CHuge& a, CHuge& b )
{
    return a+(-b);
}

CHuge operator * ( CHuge& a, CHuge& b )
{
    CHuge	            res;
    unsigned __int64    t;
    int		            i, j, pos;
    
    if ( a.m_iSize+b.m_iSize-1 > MAX_HUGE_SIZE ) return res;
    if ( (a == 0) || (b == 0) ) return res;
    
    for ( i = 0; i < a.m_iSize; i++ )
    {
        for ( j = 0; j < b.m_iSize; j++ )
        {
            t = (unsigned __int64)a[i]*(unsigned __int64)b[j];
            pos = i+j;
            
            do
            {
                t += res[pos];
                res[pos] = (unsigned)t;
                t >>= ELEM_BIT_SIZE;
                pos++;
            }
            while ( t );
        }
    }
    
    if ( res[pos] )
        res.m_iSize = pos+1;
    else
        res.m_iSize = pos;
    
    if ( a.m_bSign == b.m_bSign )
        res.m_bSign = 0;
    else
        res.m_bSign = 1;
    
    res.Tidy( );
    
    return res;  
}

CHuge operator / ( CHuge& a, CHuge& b )
{
    ASSERT( b != 0 );
    CHuge res, rem;
    
    Divide( a, b, res, rem );
    
    return res;
}

CHuge operator % ( CHuge& a, CHuge& b )
{
    CHuge res, rem;
    
    Divide( a, b, res, rem );
    
    return rem;
}


CHuge operator - ( CHuge& a, int n )
{
    CHuge res;
    
    res = n;
    res = a - res;
    
    return res;
}

//////////////////////////////////////////////////////////////////////
// Assistant
//////////////////////////////////////////////////////////////////////
int	AbsCompare ( CHuge& a, CHuge& b )
{
    if ( a.m_iSize > b.m_iSize )
        return 1;
    if ( a.m_iSize < b.m_iSize )
        return -1;
    
    int i = a.m_iSize-1;
    while ( (i >= 0) && (a[i] == b[i]) ) i--;
    
    if ( i<0 ) return 0;  
    if ( a[i] > b[i] ) return 1;
    
    return -1;
}

int Compare ( CHuge& a, CHuge& b )
{
    if ( a.m_bSign != b.m_bSign )
    {
        if ( a.m_bSign == 0 )
            return 1;
        else
            return -1;
    }
    else
    {
        int abscmp = AbsCompare( a, b );
        
        if ( abscmp>0 )
        {
            if ( a.m_bSign == 0 )
                return 1;
            else
                return -1;
        }
        else if ( abscmp < 0 )
        {
            if ( a.m_bSign == 1 )
                return 1;
            else
                return -1;
        }
        else
        {
            return 0;
        }
    }
}

CHuge AbsAdd ( CHuge& a, CHuge& b)
{
    CHuge res;
    
    res.m_iSize = (a.m_iSize > b.m_iSize) ? a.m_iSize:b.m_iSize;
    
    bool carry  = 0;
    for ( int i = 0; i < res.m_iSize; i++ )
    {
        res[i]  = a[i] + b[i] + carry;
        carry   = (res[i] < a[i]);
    }
    
    if ( carry )
    {
        res[res.m_iSize] = 1;
        res.m_iSize ++;
    }
    
    return res;
}

CHuge AbsSub ( CHuge& a, CHuge& b)
{
    CHuge res;
    
    res.m_iSize  = a.m_iSize;
    
    bool loan = 0;
    for ( int i = 0; i < res.m_iSize; i++ )
    {
        if ( a[i] > b[i] )
        {
            res[i] = a[i] - b[i] - loan;
            loan   = 0;
        }
        else if ( a[i] < b[i] )
        {
            res[i] = ELEM_MAX_VALUE - b[i] + a[i] - loan + 1;
            loan = 1;
        }
        else
        {
            if ( loan == 0 )
                res[i] = 0;
            else
                res[i] = ELEM_MAX_VALUE;
        }
    }
    
    res.Tidy();
    
    return res;
}

void Divide ( CHuge& a, CHuge& b, CHuge& res, CHuge& rem )
{
    CHuge   tb, t;
    int     pos, shift;
    
    if ( a.m_bSign == 1 ) rem = -a;  else rem = a;
    if ( b.m_bSign == 1 ) tb = -b;   else tb = b;
    
    if ( rem < tb )
    {
        res = 0;
        rem = a;
        return;
    }
    
    pos = rem.GetBitLength( ) - tb.GetBitLength( );
    t   = tb << pos;
    res.m_iSize  = (pos >> ELEM_BIT_SIZE_LOG2) + 1;
    
    while ( (pos >= 0) && (rem >= tb) )
    {
        if( rem >= t )
        {
            res.SetBit( pos );
            rem = rem - t;
            rem.Tidy();
        }
        shift = t.GetBitLength( ) - rem.GetBitLength( );
        if ( shift==0 ) shift = 1;
        t     = t >> shift;
        pos  -= shift;
    }
    
    if ( a.m_bSign == b.m_bSign )
        res.m_bSign = 0;
    else
        res.m_bSign = 1;
    
    rem.m_bSign = a.m_bSign;
    
    res.Tidy( );
}

//////////////////////////////////////////////////////////////////////
// Create Random Prime
//////////////////////////////////////////////////////////////////////
bool CreateRandomHuge ( CHuge& n, const unsigned bits )
{
    n.Zero( );
    
    if ( bits == 0 ) return true;
    if ( bits > (MAX_HUGE_SIZE << ELEM_BIT_SIZE_LOG2) ) return false;
    
    n.m_iSize  = bits >> ELEM_BIT_SIZE_LOG2;
    if ( bits &  ELEM_BIT_SIZE_MASK ) n.m_iSize++;
    
    for ( int i = n.m_iSize-1; i >= 0; i-- )
        n[i] = (rand()<<16) | (rand());
    
    int t = bits &  ELEM_BIT_SIZE_MASK;
    if ( t ) n[n.m_iSize-1] &= ( (1<<t)-1 );
    n[n.m_iSize-1] |= ( 1<<(t-1) );
    
    return true;
}

bool CreateRandomHugePrime ( CHuge& n, const unsigned bits )
{
    int len = bits >> ELEM_BIT_SIZE_LOG2;
    if ( bits&ELEM_BIT_SIZE_MASK ) len++;
    if ( len >= (MAX_HUGE_SIZE>>1) ) return false;

    do 
    {
        CreateRandomHuge( n, bits );
        n[0] |= 1;
    }
    while( !IsPrime( n ) );
    
    return true;
}

bool IsPrime ( CHuge& n )
{
    CHuge	    t;
    unsigned    i, shift;
    
    t = n - 1;
    shift = t.CountLastZeros( );
    t = t >> shift;
    
    for ( i = 0; i < MB_TEST_TIMES; i++ )
        if ( !Miller_Rabin( n, t, shift ) ) return false;
        
    return true;
}

bool Miller_Rabin( CHuge& n, CHuge& t, const unsigned pos )
{
    int		i;
    CHuge	a, q;
    
    q = n - 1;
    do
    {
        CreateRandomHuge( a, 2 + rand() % (n.m_iSize<<3) );
    }
    while ( (a >= n) || (a == 0) || (a == 1) );
    
    a = PowerMod( a, t, n );
    if ( a == 1 )   return true;
    
    for ( i=0; i<pos; i++ )
    {
        if ( a == q ) return true;
        a = (a*a) % n;
    }
    
    return false;
}

CHuge PowerMod( CHuge& base, CHuge& exp, CHuge& div )
{
    CHuge   rem, t0, t1;
    
    rem = 1;
    t0  = exp;
    t1	= base % div;
    
    while( t0 != 0 )
    {
        if( t0[0] & 1 )
            rem = (rem * t1) % div; // should promise the max_len is large enough, so that
                                    // make sure there is enough memory to store the product
        t1 = (t1 * t1) % div;
        t0 = t0 >> 1;
    }
    
    return rem;
}