【實驗目的】
1) 學習RSA密碼算法的原理
2) 學習RSA密碼算法的程式設計實作
【實驗原理】
RSA公鑰加密算法是1977年由Ron Rivest、Adi Shamirh和LenAdleman在美國麻省理工學院開發的。RSA算法基于一個十分簡單的數論事實:将兩個大素數相乘十分容易,但那時想要對其乘積進行因式分解卻極其困難,是以可以将乘積公開作為加密密鑰。
算法原理
解密過程
算法參數
算法流程
(1)RSA密鑰生成部分代碼流程圖:
(2)RSA加密部分流程圖:
(3)RSA解密部分流程圖:
源代碼如下所示
大數的資料結構:
class BigNum`
{`
public:`
int length; //大數長度`
int signal; //大數符号`
unsigned long array[len1]; //大數絕對值`
BigNum(); //構造函數`
BigNum(unsigned __int64); //構造函數用于賦初始值`
BigNum::BigNum(string s); //讀入字元串`
BigNum(BigNum const& A); //複制大數,const保護了原對象的屬性`
BigNum(); //析構函數`
BigNum operator+(BigNum & A); //運算符+重載`
BigNum operator-(BigNum & A); //運算符-重載`
BigNum operator*(BigNum & A); //運算符*重載
BigNum operator/(BigNum & A); //運算符/重載
BigNum operator%(BigNum & A); //運算符%重載
BigNum operator-(void); //負号重載
int operator==(BigNum& A); //等于号重載
int operator!=(BigNum& A); //不等号重載
int Compare(BigNum const& A); //比較兩大數絕對值大小
void GeneratePrime(void); //産生素數
int Rabin_Miller(void); //拉賓米勒算法用于素數測試
void Random(int a); //随機産生一個大數
void Random(BigNum A); //随機産生一個小于A的大數
void print(void); //輸出大數
void printS(void); //輸出字元串
BigNum power_mod(BigNum& A, BigNum& B); //模幂算法計算X^A mod B
BigNum ex_euclid(BigNum a,BigNum b); //擴充歐幾裡德算法
}
RSA系統初始化部分代碼:
RSA::RSA_Generated_Parameter (){
q.GeneratePrime();
while(p==q) //判斷兩個素數不等
q.GeneratePrime();
temp=p-I;
t=q-I;
t=t*temp;
cout<<"素數p為:"<<endl; //輸出素數
p.print();
cout<<endl;
cout<<"素數q為:"<<endl;
q.print();
cout<<endl;
cout<<"公鑰n為:"<<endl;
n=p*q;
n.print();
cout<<endl;
cout<<"公鑰e為:"<<endl;
e.print();
cout<<endl;
d.ex_euclid(e,t); //計算私鑰d
cout<<"私鑰d為:"<<endl;
d.print();
cout<<endl;
}
RSA加解密部分代碼:
RSA::RSA_Decrypt_Crypt (char s)
{
a=BigNum(A);
cout<<endl;
b=a.power_mod(e,n); //産生密文b
cout<<"加密結果為:"<<endl;
b.print();
cout<<endl;
c=b.power_mod(d,n); //解密
cout<<"解密後的結果為:"<<endl<<endl;
c.printS();
}
【實驗思考】
RSA密碼算法的安全性在于什麼?
RSA算法的安全在于,e、p、N,是随機生成的。
知道e和N,想尋找p,在計算上是不可行的(基于對大質數進行因式分解過于困難)。