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;
 }