rsa.txt

rsa加密算法的vc实现

value = x.value; 
value->share += 1; 
} 

//赋值函数 
vlong& vlong::operator =(const vlong& x) 
{ 
if ( value->share ) value->share -=1; else delete value; 
value = x.value; 
value->share += 1; 
negative = x.negative; 
return *this; 
} 

//析构函数 
vlong::~vlong() 
{ 
if ( value->share ) value->share -=1; else delete value; 
} 

//unsigned转换符，将大数转换为无符号整数 
vlong::operator unsigned () // conversion to unsigned 
{ 
return *value; 
} 

//重载+=运算符 
vlong& vlong::operator +=(const vlong& x) 
{ 
if ( negative == x.negative ) 
{ 
 docopy(); 
 value->add( *x.value ); 
} 
else if ( value->cf( *x.value ) >= 0 ) 
{ 
 docopy(); 
 value->subtract( *x.value ); 
} 
else 
{ 
 vlong tmp = *this; 
 *this = x; 
 *this += tmp; 
} 
return *this; 
} 

//重载-=运算符 
vlong& vlong::operator -=(const vlong& x) 
{ 
if ( negative != x.negative ) 
{ 
 docopy(); 
 value->add( *x.value ); 
} 
else if ( value->cf( *x.value ) >= 0 ) 
{ 
 docopy(); 
 value->subtract( *x.value ); 
} 
else 
{ 
 vlong tmp = *this; 
 *this = x; 
 *this -= tmp; 
 negative = 1 - negative; 
} 
return *this; 
} 

//重载 + 运算符，大数加法 
vlong operator +( const vlong& x, const vlong& y ) 
{ 
vlong result = x; 
result += y; 
return result; 
} 

//重载 - 运算符，大数减法 
vlong operator -( const vlong& x, const vlong& y ) 
{ 
vlong result = x; 
result -= y; 
return result; 
} 

//重载 * 运算符，大数乘法 
vlong operator *( const vlong& x, const vlong& y ) 
{ 
vlong result; 
result.value->mul( *x.value, *y.value ); 
result.negative = x.negative ^ y.negative; 
return result; 
} 

//重载 / 运算符，大数除法 
vlong operator /( const vlong& x, const vlong& y ) 
{ 
vlong result; 
vlong_value rem; 
result.value->divide( *x.value, *y.value, rem ); 
result.negative = x.negative ^ y.negative; 
return result; 
} 

//重载 % 运算符，大数求模 
vlong operator %( const vlong& x, const vlong& y ) 
{ 
vlong result; 
vlong_value divide; 
divide.divide( *x.value, *y.value, *result.value ); 
result.negative = x.negative;  
return result; 
} 

//辗转相除求最大因子 
vlong gcd( const vlong &X, const vlong &Y ) 
{ 
vlong x=X, y=Y; 
while (1) 
{ 
 if ( y == (vlong)0 ) return x; 
 x = x % y; 
 if ( x == (vlong)0 ) return y; 
 y = y % x; 
} 
} 

//密钥产生流程最后一步，Euclid 算法 
// 返回在1到m-1之间的长整数i,使i*a = 1 mod m 
// a必须为在1到m-1之间的长整数 
vlong modinv( const vlong &a, const vlong &m )  
{ 
vlong j=1,i=0,b=m,c=a,x,y; 
while ( c != (vlong)0 ) 
{ 
 x = b / c; 
 y = b - x*c; 
 b = c; 
 c = y; 
 y = j; 
 j = i - j*x; 
 i = y; 
} 
if ( i < (vlong)0 ) 
 i += m; 
return i; 
} 

/*-----------------------------------以下为vlong类实现-------------------------------*/ 


/*--------------------------以下为monty类定义与实现-------------------------------*/ 

//monty：求模与幂的相关类，主要用于分块加密与解密 
//加密： = ^e ( mod n ) 
//解密： = ^d ( mod n )      
class monty      
{ 
vlong R,R1,m,n1; 
vlong T,k;           //工作寄存器 
unsigned N;         //R的位（bit）数 
void mul( vlong &x, const vlong &y ); 
public: 
vlong exp( const vlong &x, const vlong &e ); 
monty( const vlong &M ); 
}; 

//赋M为默认除数，即加/解密式中的n 
monty::monty( const vlong &M ) 
{ 
m = M; 
N = 0;  
R = 1;  
while ( R < M )  
{  
 R += R;  
 N += 1;  
} 
R1 = modinv( R-m, m ); 
n1 = R - modinv( m, R ); 
} 

void monty::mul( vlong &x, const vlong &y ) 
{ 
// T = x*y; 
T.value->fast_mul( *x.value, *y.value, N*2 ); 

// k = ( T * n1 ) % R; 
k.value->fast_mul( *T.value, *n1.value, N ); 

// x = ( T + k*m ) / R; 
x.value->fast_mul( *k.value, *m.value, N*2 ); 
x += T; 
x.value->shr( N ); 

if (x>=m) x -= m; 
} 

//返回值= (x^e)%(this->m) 
vlong monty::exp( const vlong &x, const vlong &e ) 
{ 
vlong result = R-m; 
vlong t = ( x * R ) % m; 
unsigned bits = e.value->bits(); 
unsigned i = 0; 
while (1) 
{ 
 if ( e.value->test(i) ) 
   mul( result, t); 
 i += 1; 
 if ( i == bits ) break; 
 mul( t, t ); 
} 
return ( result * R1 ) % m; 
} 

//返回值= (x^e)%m 
vlong modexp( const vlong & x, const vlong & e, const vlong & m ) 
{ 
monty me(m); 
return me.exp( x,e ); 
}
 




RSA算法的VC实现(VC)

程序代码： (代码标记  [code]...[/code]  )

注:要用到大整数类 
//1.头文件 
/*-----------------------------------------------RSA.h--------------------------------------------------*/ 
#include "vlong.h" 

class public_key 
{ 
public: 
vlong m,e; 
vlong encrypt( const vlong& plain ); // Requires 0 <= plain < m 
}; 

class private_key : public public_key 
{ 
public: 
vlong p,q; 
vlong decrypt( const vlong& cipher ); 

void create( const char * r1, const char * r2 ); 
// r1 和 r2 为以null结尾的字符串，长度约为35个字符（以保证n约为500位模块） 
}; 

//将以0结尾的字符串转化为长整数 
static vlong from_str( const char * s ) 
{ 
vlong x = 0; 
while (*s) 
{ 
 x = x * vlong(256) + (vlong)(unsigned char)*s; 
 s += 1; 
} 
return x; 
} 

//实现部分 
/*-----------------------------------------------RSA.cpp-----------------------------------------------*/ 
#include "rsa.h" 

/*---------------------以下为prime_factory类定义与实现-------------------*/ 

//prime_factory：用于产生质数 
class prime_factory 
{ 
unsigned np; 
unsigned *pl; 
public: 
prime_factory(); 
~prime_factory(); 
vlong find_prime( vlong & start ); 
}; 

//判定是否有很大概率为质数 
static int is_probable_prime( const vlong &p ) 
{ 
//基于费马小定理：若p是任一质数, a 是任一整数, 则 a^p = 1 mod p 。换句话说,  
//如果 a 和 p 互质, 则 a^(p-1) == 1 mod p。将{2,3,5,7}值分别代入a,若上式均成立， 
//则p为质数的概率极大 
const rep = 4; 
const unsigned any[rep] = { 2,3,5,7 }; 
for ( unsigned i=0; i<rep; i+=1 ) 
 if ( modexp( any[i], p-(vlong)1, p ) != (vlong)1 ) 
   return 0; 
return 1; 
} 

//构造小质数表 
prime_factory::prime_factory() 
{ 
np = 0; 
unsigned NP = 200; 
pl = new unsigned[NP]; 

//初始化质数表 
unsigned SS = 8*NP;            //粗略估计质数表上限 
char * b = new char[SS+1]; 
for (unsigned i=0;i<=SS;i+=1)  
    b[i] = 1; 
unsigned p = 2; 
while (1) 
{ 
 // skip composites 
 while ( b[p] == 0 ) p += 1; 
 if ( p == SS ) break; 
 pl[np] = p; 
 np += 1; 
 if ( np == NP ) break; 
 // cross off multiples 
 unsigned c = p*2; 
 while ( c < SS ) 
 { 
   b[c] = 0; 
   c += p; 
 } 
 p += 1; 
} 
delete [] b; 
} 

//析构函数 
prime_factory::~prime_factory() 
{ 
delete [] pl; 
} 


//寻找第一个>=start的质数 
vlong prime_factory::find_prime( vlong & start ) 
{ 
unsigned SS = 1000;                  //1000通常已足够 
char * b = new char[SS];            //后备质数检验位，若SS[i]=0，则不需要用 
                                  //费马小定理（is_probable_prime）检验start+i,因为它 
                                  //必非质数 
unsigned tested = 0;                  //使用is_probable_prime函数检验过的后备质数次数 
while (1) 
{ 
 unsigned i; 
 for (i=0;i<SS;i+=1) 
   b[i] = 1; 
 for (i=0;i<np;i+=1) 
 { 
   unsigned p = pl[i]; 
   unsigned r = start % (vlong)p;      //取模运算较慢，此处可专门设计函数做取模计算 
   if (r)  
          r = p - r; 
   // 去除所有能被p除尽的后备质数 
   while ( r < SS ) 
   { 
   b[r] = 0; 
   r += p; 
   } 
 } 
 // 检验后备质数 
 for (i=0;i<SS;i+=1) 
 { 
   if ( b[i] ) 
   { 
   tested += 1; 
   if ( is_probable_prime(start) ) 
     return start; 
   } 
   start += 1; 
 } 
} 
delete [] b; 
} 

//由字符串r1和r2创建p、q和公钥 
void private_key::create( const char * r1, const char * r2 ) 
{ 
// 由r1和r2产生质数p、q 
{ 
 prime_factory pf; 
 p = pf.find_prime( from_str(r1) ); 
 q = pf.find_prime( from_str(r2) ); 
 if ( p > q )  
 { 
   vlong tmp = p;  
   p = q;  
   q = tmp;  
 } 
} 
// 计算公钥 
//从[0，（p-1）（q-1）-1]中随机选取加密密钥e，使得e和（p-1）（q-1）互质。此处 
//为使e较大，直接从一较大数开始选取（50001） 
{ 
 m = p*q; 
 e = 50001;                  //必须为奇数，因p-1，q-1均为偶数 
 while ( gcd(p-(vlong)1,e) != (vlong)1 || gcd(q-(vlong)1,e) != (vlong)1 )  
          e += 2; 
} 
} 

//加密明文 
vlong public_key::encrypt( const vlong& plain ) 
{ 
return modexp( plain, e, m ); 
} 

//解密秘文 
vlong private_key::decrypt( const vlong& cipher ) 
{ 
// Calculate values for performing decryption 
// These could be cached, but the calculation is quite fast 
vlong d = modinv( e, (p-(vlong)1)*(q-(vlong)1) ); 
vlong u = modinv( p, q ); 
vlong dp = d % (p-(vlong)1); 
vlong dq = d % (q-(vlong)1); 

// 应用同余定理 
vlong a = modexp( cipher % p, dp, p ); 
vlong b = modexp( cipher % q, dq, q ); 
if ( b < a ) b += q; 
return a + p * ( ((b-a)*u) % q ); 
}