RSA C++

// LargeInt.cpp // 作者 pAnic 2005年9月22日。 // CLargeInt 类的实现。 ////////////////////////////////////////////////////////////////////// #include "LargeInt.h" #include <memory.h> #include <algorithm rel='nofollow' onclick='return false;'> namespace panic { std::vector<T_DWORD> CLargeInt::_smallPrimes; void CLargeInt::InitSmallPrimes(T_DWORD count) { if( !_smallPrimes.size() ) //尚未初始化 { _smallPrimes.reserve(count); _smallPrimes.push_back(3); _smallPrimes.push_back(5); _smallPrimes.push_back(7); _smallPrimes.push_back(11); _smallPrimes.push_back(13); T_DWORD i = 0; for( i = 17; _smallPrimes.size() < count; i+= 2) { bool bePrime = true; for( T_DWORD j = 0; j < _smallPrimes.size(); j++ ) { if( ( _smallPrimes[j] * _smallPrimes[j] ) > i ) //已经不可能了。 break; if( (i % _smallPrimes[j]) == 0) //可以整除 bePrime = false; } if( bePrime ) //是素数 { _smallPrimes.push_back(i); } } } } bool CLargeInt::SmallPrimeTest(const CLargeInt& n) { if( n._data[0] == 2 && n._len == 1) return true; //2是质数。 if( n._len == 1 && n._data[0] <= _smallPrimes.back() ) //整数比表中的数据小。 { if( std::binary_search(_smallPrimes.begin(),_smallPrimes.end(),n._data[0]) ) //找到，n存在于质数表中。 { return true; //通过测试，数n是质数。 } return false; //没有通过，n是合数。 } else { CLargeInt temp; T_DWORD r; for( T_DWORD i = 0; i < _smallPrimes.size(); i++) { Div(n,_smallPrimes[i],temp,r); //依次检查是否能整除。 if( r == 0) return false; //能整除，说明 n 有小于它的质因子。n 是合数。 } return true; // n 没有表中已有的质因子，n有可能是质数。 } } bool CLargeInt::IsPrime(const CLargeInt &n) { InitSmallPrimes(); if( n._data[0]&1 ) //奇数 { if( n._len == 1 && n._data[0] <= _smallPrimes.back() ) { return SmallPrimeTest(n); //是小质数表中的一个质数。 } else { if( SmallPrimeTest(n) ) //通过小质数测试 { for( int i = 0; i < 5; i++) { CLargeInt a(_smallPrimes[ _smallPrimes.size() - i]); if( !RabinMillerTest(n,a) ) return false; } return true; //99.9%的可能是质数。 } else return false; } } return false; } void CLargeInt::CreatePrime(CLargeInt &n) { n._data[0] |= 0x01; while( !IsPrime(n) ) { Add(n,2,n); //步进2，寻找最接近的下一个质数。这个算法并不是寻找质数最好的算法，但是它可以保证寻找到相邻的质数。 } } CLargeInt::CLargeInt(T_DWORD value) : _len(1) { _data[0] = value; } CLargeInt::CLargeInt(const CLargeInt& other) { Copy(other,*this); } CLargeInt::CLargeInt(const char * str): _len(1) { _data[0] = 0; if(str && strlen(str) > 2 && ( strncmp(str,"0x",2) == 0 || strncmp(str,"0X",2) == 0 ) ) { CLargeInt temp; const char * p = str + 2; while( *p ) { char ch = *p; T_DWORD n = 0; switch(ch) { case '0':case '1':case '2': case '3':case '4':case '5':case '6':case '7':case '8':case '9': n = (ch - '0'); break; case 'A':case 'B':case 'C':case 'D':case 'E':case 'F': n = (ch - 'A' + 10); break; case 'a':case 'b':case 'c':case 'd':case 'e':case 'f': n = (ch - 'a' + 10); break; } p++; Mul(*this,16,temp); Add(temp,n,*this); } } else {//这里应该用来处理除了0x开头的16进制字符串的情况。 __asm int 3; } } CLargeInt::~CLargeInt() { } void CLargeInt::Copy(const CLargeInt& source,CLargeInt& target) { if( &source != &target ) //避免自身拷贝。 { target._len = source._len; //相信库函数能提供最高效的实现。 memcpy(target._data,source._data,source._len*4); } } bool CLargeInt::Equal(const CLargeInt& source,const CLargeInt& target) { if( source._len == target._len ) { //相信库函数能提供最高效的实现。 return !(memcmp(source._data,target._data,source._len*4)); } else return false; } bool CLargeInt::LargerEqual(const CLargeInt& source,const CLargeInt& target,T_DWORD offset ) { if( source._len > (target._len + offset) ) return true; else if( source._len < (target._len + offset) ) return false; else { int end = offset; for( int i = source._len - 1; i >= end ; i--) { T_DWORD ii = i - offset; if( source._data[i] > target._data[ii] ) return true; //大于 else if( source._data[i] < target._data[ii] ) return false; } return true; //相等。 } } void CLargeInt::Add(const CLargeInt &augend, const CLargeInt &addend, CLargeInt &sum,T_DWORD offset) { T_DWORD len,len1,len2; //len绝对不能<1，否则会出错。 T_DWORD *p1 = 0; T_DWORD *p2 = 0; T_DWORD *p3 = 0; if( augend._len >= (addend._len+offset) ) { len = augend._len - offset; len1 = addend._len; len2 = len - len1; p1 = augend._data+offset; p2 = addend._data; p3 = sum._data+offset; } else { len = addend._len; if( augend._len <= offset ) { augend._data[offset] = 0; len1 = 1; len2 = addend._len - len1; } else { len1 = augend._len - offset; len2 = addend._len - len1; } p1 = addend._data; p2 = augend._data + offset; p3 = sum._data + offset; } __asm { pushad; //载入计算地址 mov esi,p1; mov ebx,p2; mov edi,p3; mov eax,len1; sal eax,2; //计算末地址 add esi,eax; add ebx,eax; add edi,eax; mov ecx,eax; add ecx,4*7; and ecx,0xFFFFFFE0; //ecx - ecx%32,这里的ecx就变成了偏移址，同时也是累加器。 neg ecx; //取负，用作累加。 sar eax,2; //回复到原来的长度 neg eax; //取负 and eax,dword ptr 7; jz labeladd0; //如果低位是0，说明长度至少有8(因为长度为0是非法的) mov edx,dword ptr 0xC; mul edx; //eax变为相对偏移址。 lea edx,labeladd1; //载入起始地址 sub edx,dword ptr 0xC; add eax,edx; //计算出跳转地址 clc; //清除标志位。 jmp eax; //跳转 labeladdloop: popf; labeladd0: mov eax,[esi+ecx+0*4]; adc eax,[ebx+ecx+0*4]; mov [edi+ecx+0*4],eax; labeladd1: mov eax,[esi+ecx+1*4]; adc eax,[ebx+ecx+1*4]; mov [edi+ecx+1*4],eax; //labeladd2: mov eax,[esi+ecx+2*4]; adc eax,[ebx+ecx+2*4]; mov [edi+ecx+2*4],eax; //labeladd3: mov eax,[esi+ecx+3*4]; adc eax,[ebx+ecx+3*4]; mov [edi+ecx+3*4],eax; //labeladd4: mov eax,[esi+ecx+4*4]; adc eax,[ebx+ecx+4*4]; mov [edi+ecx+4*4],eax; //labeladd5: mov eax,[esi+ecx+5*4]; adc eax,[ebx+ecx+5*4]; mov [edi+ecx+5*4],eax; //labeladd6: mov eax,[esi+ecx+6*4]; adc eax,[ebx+ecx+6*4]; mov [edi+ecx+6*4],eax; //labeladd7: mov eax,[esi+ecx+7*4]; adc eax,[ebx+ecx+7*4]; mov [edi+ecx+7*4],eax; //labeladd8: pushf; add ecx,32; jnz labeladdloop; //运行到这里了，说明两数重合部分已经处理完了。开始处理两数相差的部分。 mov ecx,len2; //载入长度 xor ebx,ebx; //因为ebx指向的缓冲区废弃不用了，所以使用已经空闲的ebx寄存器。 cmp ebx,ecx; //判断ecx是否等于ebx(0) jz labelcarry; //如果相等，说明已经处理完了，跳转到处理最后一次进位的地方。 labelfix: popf; //弹出上次的标志位。 mov eax,[esi+ebx*4]; adc eax,0; mov [edi+ebx*4],eax; //如果这里没有进位，剩下的部分可以直接拷贝。拷贝的长度就是ecx-1 jnc labelcopy; pushf; //保存标志位。 inc ebx; //步进 dec ecx; jnz labelfix; //循环。 labelcarry: popf; //弹出标志位 jnc labelend; //没有进位就直接结束 //没有跳转说明有进位： mov dword ptr [edi+ebx*4],dword ptr 0x00000001; //直接置1 lea eax,len; inc [eax]; //总长度+1 inc ecx; //补一次。 labelcopy: dec ecx; sal ecx,2; cmp edi,esi; //比较源地址和目标地址，如果相同就跳过。 jz labelend; sal ebx,2; add ebx,4; add edi,ebx;