学步园

简介:
　　RSA算法是一种非对称密码算法，所谓非对称，就是指该算法需要一对密钥，使用其中一个加密，则需要用另一个才能解密。
　　RSA的算法涉及三个参数，n、e1、e2。
　　其中，n是两个大质数p、q的积，n的二进制表示时所占用的位数，就是所谓的密钥长度。
　　e1和e2是一对相关的值，e1可以任意取，但要求e1与(p-1)*(q-1)互质；再选择e2，要求(e2*e1)mod((p-1)*(q-1))=1。
　　(n,e1)为公钥对,(n,e2)是密钥对。
　　RSA加解密的算法完全相同,设A为明文，B为密文，则：A=B^e1 mod n；B=A^e2 mod n；
　　e1和e2可以互换使用，即：A=B^e2 mod n；B=A^e1 mod n; 

　　更详解的介绍请自行查阅相关资料....

算法(源码) 注:本代码只适合小数,不适合大数)

#include <stdio.h>
#include <iostream>
#include <time.h>
#include <math.h>

// PRIMENUMBER指定构造素数数组的元素个数,200以内的素数有39个
#define PRIMENUMBER 39

usingnamespace std;

bool IsPrime(long PrimeArray[], constlong&nPositiveInteger);
void MakePrimeArray(long PrimeArray[], constlong&nPrimeNumber);
long PrimeABCalc(constlong&PrimeA, constlong&PrimeB);
void GetPrimeAuto( long PrimeArray[], long&PrimeA, long&PrimeB);
void GetPrimeHand( long PrimeArray[], long&PrimeA, long&PrimeB);
long GCD(long KeyE, long fn);
long GetKeyE(long fn);
long GetKeyD(long KeyE, long fn);
long Encrypt( long KeyE, long n, long cleartext);
long Decipher( long KeyD, long n, long ciphertext);

// 主函数
long main(long argc, char* argv[])
{
long MyPrimeArray[PRIMENUMBER] = {0};
    MakePrimeArray(MyPrimeArray, PRIMENUMBER);
long PrimeA =0;
long PrimeB =0;
long n =0;
long PrimeAB =0;
long e =0;
long d =0;
long cleartext =0;
long ciphertext =0;
long nSelect =0;
    cout<<"素数产生方式(1~100):";
    cout<<"1 手动指定   "<<"2 自动随机\t";
    cout<<"选择:";
    cin>>nSelect;

if (1== nSelect)
        GetPrimeHand(MyPrimeArray, PrimeA, PrimeB);
elseif (2== nSelect)
        GetPrimeAuto(MyPrimeArray, PrimeA, PrimeB);
else
        cout<<"选择错误!"<<endl;

    cout<<"随机数 p: "<<PrimeA<<"\tq: "<<PrimeB<<endl;
    n = PrimeA * PrimeB;
    cout<<"素数的乘积n = pq: "<<n<<"\t";
    PrimeAB = PrimeABCalc(PrimeA, PrimeB);
    cout<<"值f(n) = (p-1)(q-1): "<<PrimeAB<<endl;
    e = GetKeyE(PrimeAB);
    cout<<"公钥e: "<<e<<"\t";
    d = GetKeyD(e, PrimeAB);
    cout<<"密钥d: "<<d<<endl;
    cout<<"输入一个正整数明文:";
    cin>>cleartext;
    ciphertext = Encrypt(e, n, cleartext);
    cout<<"加密后密文: "<<ciphertext<<endl;
    cleartext = Decipher(d, n, ciphertext);
    cout<<"解密后明文: "<<cleartext<<endl;
    cout<<"\n该RSA加密仅做参考,运算时可能会溢出."<<endl;
    system("Pause");
return0;
}

// 计算f(n)=(p-1)(q-1)
long PrimeABCalc(constlong&PrimeA, constlong&PrimeB)
{
return ((PrimeA -1) * (PrimeB -1));
}

// 手动输入素数
void GetPrimeHand( long PrimeArray[], long&PrimeA, long&PrimeB )
{
bool PrimeTrue =true;
// 输入第一个素数
do 
    {
if (PrimeTrue)
        {
            cout<<"请输入第一个素数:";
        } 
else
        {
            cout<<"该数不是素数,请重新输入第一个素数:";
        }
        cin>>PrimeA;
        PrimeTrue = IsPrime(PrimeArray, PrimeA);
    } while (!PrimeTrue);
    
    PrimeTrue =true;
// 输入第二个素数
do 
    {
if (PrimeTrue)
        {
            cout<<"请输入第二个素数:";
        } 
else
        {
            cout<<"该数不是素数,请重新输入第二个素数:";
        }
        cin>>PrimeB;
        PrimeTrue = IsPrime(PrimeArray, PrimeB);
    } while (!PrimeTrue);
while (PrimeA == PrimeB)
    {
do 
        {
            cout<<"请重新输入第二个素数:";
            cin>>PrimeB;
        } while (!IsPrime(PrimeArray, PrimeB));
    }
return;
}

// 自动产生1~100的随机数
void GetPrimeAuto( long PrimeArray[], long&PrimeA, long&PrimeB)
{
    srand((unsigned)time(NULL));
do 
    {
        PrimeA = rand()%100;
    } while (!IsPrime(PrimeArray, PrimeA));
    
do 
    {
        PrimeB = rand()%100;
    } while (!IsPrime(PrimeArray, PrimeB));
    
while (PrimeA == PrimeB)
    {
do 
        {
            PrimeB = rand()%200;
        } while (!IsPrime(PrimeArray, PrimeB));
    }
return;
}

// 判断是否是素数
bool IsPrime(long PrimeArray[], constlong&nPositiveInteger)
{
if(nPositiveInteger <2) 
returnfalse;
for(long i =0; PrimeArray[i]*PrimeArray[i] <= nPositiveInteger; ++i)
    {
if(nPositiveInteger%PrimeArray[i] ==0)
returnfalse;
    }
returntrue;
}

// 构造素数序列primes[]
void MakePrimeArray(long PrimeArray[], constlong&nPrimeNumber)
{
long i, cnt;
    PrimeArray[0] =2;
    PrimeArray[1] =3;
for(i =5, cnt =2; cnt < nPrimeNumber; i +=2)
    {
bool flag =true;
        flag = IsPrime(PrimeArray, i);
if(flag)
            PrimeArray[cnt++] = i;
    }
}

// 找一个与f(n)互质的数e,且1<e<f(n),此处随机产生
long GetKeyE( long fn )
{
long KeyE =0;
long SelectKeyE =0;
    
    cout<<"产生公钥e方式: "<<"1 随机   2 顺序"<<"\t";
while (1)
    {
        cout<<"选择: ";
        cin>>SelectKeyE;
if ( 1== SelectKeyE)
        {
            srand(NULL);
while(1)
            {
/*KeyE = rand()%fn;    // 如果随机可能会造成后面幂运算溢出*/
                KeyE++;
if ((KeyE>=2) && (GCD(KeyE, fn) ==1))
break;
if ( KeyE > fn)
break;
            }
break;
        }
elseif ( 2== SelectKeyE)
        {
long i =2;
while (1)
            {
if (GCD(i, fn) ==1)
                {
                    KeyE = i;
break;
                }
                i++;
            }
break;
        }
else
            cout<<"选择有误!"<<endl;
    }
return KeyE;    
}

// 求两数最大公约数,若为1则说明两数为互质数
long GCD( long KeyE, long fn )
{
long iDividend = fn;        // 被除数
long iDivisor = KeyE;    // 除数
long iResidual = iDividend%iDivisor;        //余数
// 辗转相除法
while (iResidual !=0)
    {
//将除数作为被除数
        iDividend=iDivisor;
//把余数作为除数
        iDivisor=iResidual;
//求新的余数
        iResidual=iDividend%iDivisor;
    }
return iDivisor;
}

// 计算d,使得d*e≡1 mod f(n).这个公式也可以表达为d ≡e-1 mod f(n)
long GetKeyD( long KeyE, long fn )
{
long iKeyD =0;
long Ji =0;
    srand(NULL);
do 
    {
/*iKeyD = rand();    // 如果随机可能会造成后面的幂运算溢出*/
        iKeyD++;
        Ji = iKeyD * KeyE;
    } while (!(GCD(Ji, fn) ==1&& ((Ji+fn)%fn ==1)));
return iKeyD;
}

// 加密
long Encrypt( long KeyE, long n, long cleartext )
{
long ciphertext =0;
    ciphertext = ((long)pow(cleartext, KeyE)%n);
return ciphertext;
}

// 解密
long Decipher( long KeyD, long n, long ciphertext )
{
//     long cleartext = 0;
//     cleartext = ((long)pow(ciphertext, KeyD)%n);
//     return cleartext;
// 下面是用的模幂运算的简便算法,我自己的代码会造成计算溢出.
long cleartext =1;
    KeyD = KeyD +1;
while( KeyD !=1)
    {
        cleartext = cleartext * ciphertext;
        cleartext = cleartext % n;
        KeyD--;
    }
return cleartext;
}

【参考资料 感谢作者】
RSA加密算法(转) ：http://hi.baidu.com/%CE%E2%D2%A2%C1%D6/blog/item/414229ce214a7c0693457e18.html 
RSA算法_百科：http://baike.baidu.com/view/7520.htm
论文:RSA算法的分析与实现：http://ces.ustc.edu.cn/jpg/pap/xbq/index.htm