rsa加密算法

RSA 算法：
其中加密encode和解密decode中的效率可以提高的log（n）

但是这个算法只是原型，只能对数字加密，对字符串加密时要将转换成AScII码的东东进行拆分才可以。要按位加密。当q，p过大时，将有溢出。改进的可以自己写一个大
数类。但没有时间了，暂时就做成这个样子吧。

#include < iostream >

#include < string >

#include < ctime >

#include “ math.h “

using namespace std;


bool isPrime( long ); // the number is prime and return true, else return
false;

long gcd( long a, long b); // find a number which the two number a and
b divide exactly.

long publicKey( long p, long q); // using p, q to calculate the public
key e.

long privateKey( long e, long Qn); // using e ,Qn to calculate the
private key d.

long generKey( const long p, const long q, long pubKey, long
priKey); // get the public key and private key. And return n = pq.
//
char encode(char ,long n,long pubKey); // encode the Text
//
char decode(char ,long n,long priKey); // decode the Text which has been
encoded.

long encode( long , long n, long pubKey); // encode the Text

long decode( long , long n, long priKey); // decode the Text which
has been encoded.

int main()
… {


long p,q;

long pubKey ;

long priKey ;

bool pass = true ;

while (pass)
… {

cout << “ input two prime numbers! and the two numbers are bigger than two
!! “ << endl;

cin >> p >> q;

// srand(time(0));

// q = rand();

// p = rand();

if (isPrime(p) && isPrime(q))

pass = false ;
}

cout << “ p = “ << p << “ q = “ << q << endl;

long n = generKey(p,q, & pubKey, & priKey);

cout << “ n: “ << n << endl;

cout << “ input the number for encoding! “ << endl;

long num;

cin >> num;

// cout << decode(encode(txt,n,pubKey),n,priKey);

long enText = encode(num,n,pubKey);

cout << “ encode the Text: “ << enText << endl;

cout << “ decode the Text: “ << decode(enText,n,priKey) << endl;

return 0 ;
}


bool isPrime( long a)
… {

if (a > 2 )
… {

int b = 2 ,c = sqrt(a);

for (; b < c; b ++ )
… {

if (a % b == 0 )

return false ;
}

return true ;
}

return false ;
}


long gcd( long a, long b)
… {

int x = a % b;

if (x == 0 )

return b;

else

return gcd(b,x);
}


long publicKey( const long p, const long q, const long Qn)
… {


srand(time( 0 ));

long e = rand();

if (e >= Qn)

e = 3 ;

while (gcd(e,Qn) != 1 )
… {


e ++ ;

if (e >= Qn)
… {

e = 3 ;
}
}

cout << “ e: “ << e << endl;

return e;
}


long privateKey( const long e, const long Qn)
… {

srand(time( 0 ));

long d = rand();

if (d >= Qn)

d = 3 ;

while (e d % Qn != 1 || e == d)
… {

d ++ ;

if (d >= Qn)
… {

d = 3 ;
}
}

cout << “ d: “ << d << endl;

return d;
}


long generKey( const long p, const long q, long pubKey, long
priKey)
… {

long n = p q;

long Qn = (p - 1 ) (q - 1 );

• pubKey = publicKey(p,q,Qn);
  
• priKey = privateKey( pubKey,Qn);
  
  return n;
  }
  
  
  
  /**/ /
  
  
  char encode(char txt,long n,long pubKey)
  
  {
  
  int length = strlen(txt);
  
  char text = new char[length];
  
  strcpy(text,txt);
  
  for(int i = 0; i < length; i++)
  
  {
  
  
  text[i] =(int) pow(text[i],pubKey) % n;
  
  }
  
  return text;
  
  }
  
  
  char decode(char txt,long n,long priKey)
  
  {
  
  int length = strlen(txt);
  
  char text = new char[length];
  
  strcpy(text,txt);
  
  for(int i = 0; i < length; i++)
  
  {
  
  text[i] = (int)pow(text[i],priKey) % n;
  
  }
  
  return text;
  
  }
  /
  
  long encode( long num, long n, long pubKey)
  … {
  
  long tmp = 1 ;
  
  for ( int i = 0 ; i < pubKey; i ++ )
  … {
  
  tmp = num ;
  
  tmp %= n;
  }
  
  return tmp;
  }
  
  long decode( long num, long n, long priKey)
  … {
  
  long tmp = 1 ;
  
  for ( int i = 0 ; i < priKey; i ++ )
  … {
  
  tmp *= num ;
  
  tmp %= n;
  }
  
  return tmp;
  }