rsa.txt

rsa加密算法的vc实现

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

//1.大整数计算头文件 
/*------vlong.h----------*/ 

//长整数类，可随意定义其长度 
class vlong                
{ 
public: 

// 重载常用算术运算符 
friend vlong operator +( const vlong& x, const vlong& y ); 
friend vlong operator -( const vlong& x, const vlong& y ); 
friend vlong operator *( const vlong& x, const vlong& y ); 
friend vlong operator /( const vlong& x, const vlong& y ); 
friend vlong operator %( const vlong& x, const vlong& y ); 
vlong& operator +=( const vlong& x ); 
vlong& operator -=( const vlong& x ); 

// 重载常用比较运算符 
friend inline int operator !=( const vlong& x, const vlong& y ){ return x.cf( y ) != 0; } 
friend inline int operator ==( const vlong& x, const vlong& y ){ return x.cf( y ) == 0; } 
friend inline int operator >=( const vlong& x, const vlong& y ){ return x.cf( y ) >= 0; } 
friend inline int operator <=( const vlong& x, const vlong& y ){ return x.cf( y ) <= 0; } 
friend inline int operator > ( const vlong& x, const vlong& y ){ return x.cf( y ) > 0; } 
friend inline int operator < ( const vlong& x, const vlong& y ){ return x.cf( y ) < 0; } 

// 构造函数 
vlong ( unsigned x=0 ); 
vlong ( const vlong& x ); 

// 析构函数 
~vlong(); 

// 转换操作符 
operator unsigned (); 
vlong& operator =(const vlong& x); 

private: 
class vlong_value * value; 
int negative; 
int cf( const vlong x ) const; 
void docopy(); 
friend class monty; 
}; 

vlong modexp( const vlong & x, const vlong & e, const vlong & m ); // m必须为质数 
vlong gcd( const vlong &X, const vlong &Y ); // 求最大因子 
vlong modinv( const vlong &a, const vlong &m ); //Euclid算法 

//2.大整数类方法的实现 
/*----------------------vlong.cpp*---------------------------------------------------------*/ 
#include "vlong.h" 

class vlong_value; 

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

//flex_unit类：提供存储分配与索引检查的类 
class flex_unit                        
{ 
unsigned * a;                       //内存unsigned int单元数组 
unsigned z;                       //分配单元数 
public: 
unsigned n;                       //已使用的单元数(只读属性) 
flex_unit(); 
~flex_unit(); 
void clear();                         //已使用单元数n清0 
unsigned get( unsigned i ) const;         //获取第i个单元值 
void set( unsigned i, unsigned x );       //设置第i个单元值 
void reserve( unsigned x );       //扩展存储区 

//有时间要求的乘法 
void fast_mul( flex_unit &x, flex_unit &y, unsigned n ); 
}; 

//按索引获取单元值 
unsigned flex_unit::get( unsigned i ) const 
{ 
if ( i >= n ) return 0; 
return a[i]; 
} 

//清空 
void flex_unit::clear() 
{ 
 n = 0; 
} 

//构造函数 
flex_unit::flex_unit() 
{ 
z = 0; 
a = 0; 
n = 0; 
} 

//析构函数 
flex_unit::~flex_unit() 
{ 
unsigned i=z; 
while (i)  
{ 
     i-=1;  
     a[i] = 0;  
} 
delete [] a; 
} 

//改变大数尺寸 
void flex_unit::reserve( unsigned x ) 
{ 
if (x > z) 
{ 
 unsigned * na = new unsigned[x]; 
 for (unsigned i=0;i<n;i+=1) na[i] = a[i]; 
 delete [] a; 
 a = na; 
 z = x; 
} 
} 

//根据索引设置元素值 
void flex_unit::set( unsigned i, unsigned x ) 
{ 
if ( i < n ) 
{ 
 a[i] = x; 
 if (x==0)  
 while (n && a[n-1]==0)               //去除高位0 
       n-=1;            
} 
else if ( x ) 
{ 
 reserve(i+1); 
 for (unsigned j=n;j<i;j+=1) a[j] = 0; 
 a[i] = x; 
 n = i+1; 
} 
} 

#define BPU ( 8*sizeof(unsigned) )         //unsigned int类型bit数 
#define lo(x) ( (x) & ((1<<(BPU/2))-1) )     //unsigned int低半部分 
#define hi(x) ( (x) >> (BPU/2) )               //unsigned int高半部分 
#define lh(x) ( (x) << (BPU/2) )           //使低半部分左移至高半部分 

//快速乘法 
void flex_unit::fast_mul( flex_unit &x, flex_unit &y, unsigned keep ) 
{ 
// *this = (x*y) % (2**keep) 
unsigned i,limit = (keep+BPU-1)/BPU;     //运算结果单元数 
reserve(limit);  
for (i=0; i<limit; i+=1)  
 a[i] = 0; 
unsigned min = x.n;  
if (min>limit)  
 min = limit; 
for (i=0; i<min; i+=1) 
{ 
 unsigned m = x.a[i]; 
 unsigned c = 0;  
 unsigned min = i+y.n;  
 if (min>limit) min = limit; 
 for ( unsigned j=i; j<min; j+=1 ) 
 { 
   //此处代码为运算关键，可使用机器或汇编代码以加快速度 
   // c:a[j] = a[j] + c + m*y.a[j-i]; 
   unsigned w, v = a[j], p = y.a[j-i]; 
   v += c; c = ( v < c ); 
   w = lo(p)*lo(m); v += w; c += ( v < w ); 
   w = lo(p)*hi(m); c += hi(w); w = lh(w); v += w; c += ( v < w ); 
   w = hi(p)*lo(m); c += hi(w); w = lh(w); v += w; c += ( v < w ); 
   c += hi(p) * hi(m); 
   a[j] = v; 
 } 
 while ( c && j<limit ) 
 { 
   a[j] += c; 
   c = a[j] < c; 
   j += 1; 
 } 
} 

//去除不必要的bit 
keep %= BPU;  
if (keep) 
 a[limit-1] &= (1<<keep)-1; 

 //计算使用单元数 
while (limit && a[limit-1]==0)  
 limit-=1; 
n = limit; 
}; 

/*---------------------------------以上为flex_unit类定义与实现----------------------------*/ 


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

class vlong_value : public flex_unit     //继承自flex_unit，负责vlong类内存管理 
{ 
public: 
unsigned share;                    
int is_zero() const; 
int test( unsigned i ) const; 
unsigned bits() const; 
int cf( vlong_value& x ) const; 
void shl(); 
void shr(); 
void shr( unsigned n ); 
void add( vlong_value& x ); 
void subtract( vlong_value& x ); 
void init( unsigned x ); 
void copy( vlong_value& x ); 
operator unsigned();               //转换至unsigned int类型，不安全 
vlong_value(); 
void mul( vlong_value& x, vlong_value& y ); 
void divide( vlong_value& x, vlong_value& y, vlong_value& rem ); 
}; 


// 将大数转换为无符号整数 
vlong_value::operator unsigned() 
{ 
return get(0); 
} 

// 测试大数是否为0 
int vlong_value::is_zero() const 
{ 
return n==0; 
} 

//测试第i位（bit）值是否为0 
int vlong_value::test( unsigned i ) const 
{  
 return ( get(i/BPU) & (1<<(i%BPU)) ) != 0;  
} 

//获取大数位（bit）数 
unsigned vlong_value::bits() const 
{ 
unsigned x = n*BPU; 
while (x && test(x-1)==0) x -= 1; 
return x; 
} 

//比较两个大数值大小 
int vlong_value::cf( vlong_value& x ) const 
{ 
if ( n > x.n ) return +1; 
if ( n < x.n ) return -1; 
unsigned i = n; 
while (i) 
{ 
 i -= 1; 
 if ( get(i) > x.get(i) ) return +1; 
 if ( get(i) < x.get(i) ) return -1; 
} 
return 0; 
} 

//按位左移 
void vlong_value::shl() 
{ 
unsigned carry = 0; 
unsigned N = n; 
for (unsigned i=0;i<=N;i+=1) 
{ 
 unsigned u = get(i); 
 set(i,(u<<1)+carry); 
 carry = u>>(BPU-1); 
} 
} 

//按位右移 
void vlong_value::shr() 
{ 
unsigned carry = 0; 
unsigned i=n; 
while (i) 
{ 
 i -= 1; 
 unsigned u = get(i); 
 set(i,(u>>1)+carry); 
 carry = u<<(BPU-1); 
} 
} 

//左移x位 
void vlong_value::shr( unsigned x ) 
{ 
unsigned delta = x/BPU;  
x %= BPU; 
for (unsigned i=0;i<n;i+=1) 
{ 
 unsigned u = get(i+delta); 
 if (x) 
 { 
   u >>= x; 
   u += get(i+delta+1) << (BPU-x); 
 } 
 set(i,u); 
} 
} 

//大数加法 
void vlong_value::add( vlong_value & x ) 
{ 
unsigned carry = 0; 
unsigned max = n; if (max<x.n) max = x.n; 
reserve(max); 
for (unsigned i=0;i<max+1;i+=1) 
{ 
 unsigned u = get(i); 
 u = u + carry; carry = ( u < carry ); 
 unsigned ux = x.get(i); 
 u = u + ux; carry += ( u < ux ); 
 set(i,u); 
} 
} 

//大数减法 
void vlong_value::subtract( vlong_value & x ) 
{ 
unsigned carry = 0; 
unsigned N = n; 
for (unsigned i=0;i<N;i+=1) 
{ 
 unsigned ux = x.get(i); 
 ux += carry; 
 if ( ux >= carry ) 
 { 
   unsigned u = get(i); 
   unsigned nu = u - ux; 
   carry = nu > u; 
   set(i,nu); 
 } 
} 
} 

//使用无符号整数x初始化大数 
void vlong_value::init( unsigned x ) 
{ 
clear(); 
set(0,x); 
} 

//将参数x（大数类型）值赋给本实例 
void vlong_value::copy( vlong_value& x ) 
{ 
clear(); 
unsigned i=x.n; 
while (i) { i -= 1; set( i, x.get(i) ); } 
} 
    
vlong_value::vlong_value() 
{ 
share = 0; 
} 

//大数乘法 
void vlong_value::mul( vlong_value& x, vlong_value& y ) 
{ 
fast_mul( x, y, x.bits()+y.bits() ); 
} 

//大数除法 
void vlong_value::divide( vlong_value& x, vlong_value& y, vlong_value& rem ) 
{ 
init(0); 
rem.copy(x); 
vlong_value m,s; 
m.copy(y); 
s.init(1); 
while ( rem.cf(m) > 0 ) 
{ 
 m.shl(); 
 s.shl(); 
} 
while ( rem.cf(y) >= 0 ) 
{ 
 while ( rem.cf(m) < 0 ) 
 { 
   m.shr(); 
   s.shr(); 
 } 
 rem.subtract( m ); 
 add( s ); 
} 
} 

/*---------------------以上为vlong_value类定义与实现---------------------------*/ 


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

void vlong::docopy() 
{ 
if ( value->share ) 
{ 
 value->share -= 1; 
 vlong_value * nv = new vlong_value; 
 nv->copy(*value); 
 value = nv; 
} 
} 

//大数比较 
int vlong::cf( const vlong x ) const 
{ 
int neg = negative && !value->is_zero(); 
if ( neg == (x.negative && !x.value->is_zero()) ) 
 return value->cf( *x.value ); 
else if ( neg ) return -1; 
else return +1; 
} 

//构造函数 
vlong::vlong (unsigned x) 
{ 
value = new vlong_value; 
negative = 0; 
value->init(x); 
} 

//复制构造函数 
vlong::vlong ( const vlong& x )  
{ 
negative = x.negative;