#include?
#include?
#include?
#define?RANDOM?1
#define?UNIT?1
/*?RANDOM?and?UNIT?are?used?for?creating?random?big?integer?*/
using?namespace?std;
typedef?__int64?SuperInt;

SuperInt?random（void）;
SuperInt?quickPowMod（SuperInt?aSuperInt?bSuperInt?r）;
bool?Miller_Rabbin（SuperInt?n）;
bool?testPrime（SuperInt?n）;
SuperInt?MultiplicativeInverse（SuperInt?aSuperInt?b）;????/*?it?is?just?to?calculate?b^（-1）mod?a?*/

int?main（）
{
????ofstream?fout（“key.txt“）;
????BEGIN:SuperInt?pqnabPhi_n;
????srand（time（NULL））;
????while（1）
????{
????????p=random（）;
????????q=random（）;
????????if（testPrime（p）&&testPrime（q））
????????????break;
????}
????n=p*q;
????Phi_n=（p-1）*（q-1）;
????while（1）
????{
????????b=random（）;
????????if（b>1&&b????????{
????????????a=MultiplicativeInverse（Phi_nb）;
????????????if（a>0）?break;
????????}
????}
????if（（a*b）%Phi_n!=1）?
????????goto?BEGIN;????/*?the?A?must?be?the?right?result?of?b^（-1）mod?Phi（n）?*/
????cout<<“public?key?is?（“<????cout<<“private?key?is?（“<????fout<<“public?key?is?（“<????fout<<“private?key?is?（“<????system（“pause“）;
????return?0;
}

SuperInt?random（void）
{
????int?ij;
????SuperInt?result=0;
????for（i=0;i????{
????????SuperInt?temp=1;
????????for（j=0;j????????????temp=temp*UNIT;
????????result+=rand（）*temp;
????}
????return?result;
}

SuperInt?quickPowMod（SuperInt?aSuperInt?bSuperInt?r）
{
????SuperInt?ans=1buff=a;
????while（b）
????{
????????if（b&1）
????????????ans=（ans*buff）%r;
????????buff=（buff*buff）%r;
????????b>>=1;
????}
????return?ans;
}

bool?Miller_Rabbin（SuperInt?n）
{
????SuperInt?r=0s=n-1j;
????SuperInt?a=rand（）;
????if（n%a==0）
????????return?false;
????while（!（s&1））
????{
????????s>>=1;
????????r++;
????}
????SuperInt?k=quickPowMod（asn）;
????if（k==1）
????????return?true;
????for（j=0;j????????if（k==n-1）
????????????return?true;
????return?false;
}

bool?testPrime（SuperInt?n）
{
????for（int?i=0;i<10;i++）
????{
????????if（Miller_Rabbin（n）==0）
????????????return?false;
????}
????return?true;
}

SuperInt?MultiplicativeInverse（SuperInt?aSuperInt?b）
{
????SuperInt?tempA=atempB=btempT=0t=1;
????SuperInt?q=tempA/tempB;
????SuperInt?r=tempA-q*tempB;
????while（r>0）
????{
????????SuperInt?temp=（tempT-q*t）%a;
????????tempT=t;
????????t=temp;
????????tempA=tempB;
????????tempB=r;
????????q=tempA/tempB;
????????r=tempA-q*tempB;
????}
????if（tempB!=1）?return?0;
????else?????????return?t;
}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2013-06-27?23:26??RSA算法\
?????文件??????????68??2013-06-14?14:32??RSA算法\key.txt
?????文件????????2672??2013-06-14?14:31??RSA算法\RSA密鑰生成系統.cpp
?????文件??????479782??2013-06-14?14:32??RSA算法\RSA密鑰生成系統.exe
?????文件????????2146??2013-06-14?16:02??RSA算法\RSA算法.cpp
?????文件??????477593??2013-06-14?16:02??RSA算法\RSA算法.exe
?????文件???????58880??2013-06-27?23:26??密碼學作業.doc