就前不久完成的RSA加解密實現(xiàn)這一實驗來水一篇文章
算法原理：
一.米勒拉賓素性檢測算法
米勒-拉賓(MillerRabbin)素性測試算法是一個高效判斷素數(shù)的方法。
其涉及到的原理如下：
????????1、費馬小定理： 如果p為質(zhì)數(shù) ? ????????
?(在mod p 的情況下)
????????2、對于任意一個小于p的正整數(shù)x，發(fā)現(xiàn)1（模p）的非平凡平方根存在，則說明p是合數(shù)。
其中定理第二部分可以理解為：
如果p是一個素數(shù)，0 < x< p,?? 則方程?
?≡ 1(mod p) 的解為 x=1 ,x= p-1
反之 如果? x^ 2 ≡ 1(mod p)? 的解不是 x=1 ,x= p-1?? 那 p 就不是素數(shù)
?二.拓展歐幾里得算法
如果a、b是整數(shù)，那么一定存在整數(shù)x、y使得ax+by=gcd(a,b)
1、首先，對于要求最大公約數(shù)的兩個數(shù) a, b 一定存在滿足上式關(guān)系；
2、對上式往下層層遞推：
(1)…ax + by = gcd (a, b);
(2)…bx1 + a % by1 = gcd (b, a%b); (運用歐幾里算法)
(3)…gcd (a, b) = gcd(b,a%b); (歐幾里得算法)
(4)…ax + by = b x1 + a % b*y1; (在計算機里 a % b = (a - a / b * b))
(5)…ax + by = bx1 + ay1 - a / b * by1;
(6)…ax + by = ay1 + b (x1 - a / b) y1; (合并同類項)
(7)…x = y1, y = x1 - a / b * y1; (結(jié)論）
由此得出結(jié)論，每一層的 x 都等于下一層的 y，每一層的 y 都等于下一層的 x1 - a / b * y1;
三.模平方重復(fù)算法
模平方重復(fù)算法可用于快速冪的實現(xiàn)，是RSA加解密的重要組成部件。具體見下圖，大致思路為將指數(shù)轉(zhuǎn)化為2進制形式，然后循環(huán)相乘并取模。
四.RSA加解密原理
RSA算法主要包括：密鑰生成，加密過程和解密過程。
（1）加密過程。在密鑰生成過程中，首先生成兩個大的質(zhì)數(shù)（素數(shù)）p和q，令n=p*q ;m=(p-1)*(q-1),選取較小的數(shù)e,使e 和m互質(zhì)，即e和m的最大公約數(shù)為1，然后生成d，使d*e(mod m)=1,最后丟棄P,q,m,則加密密鑰為e, n,解密密鑰為d和n.
(2) 加密過程。將明文x加密成密文y的計算公式為：y=x^e (mod n)。從公式可見，加密牽涉到明文和加密密鑰。因此，密文即使被截獲，也無法被解讀。
(3) 解密過程。將密文y解密成明文x的計算公式為：x=y^d (mod n)。從公式可見，解密至牽涉到解密密鑰和密文。
- 算法設(shè)計
快速冪算法
利用模平方重復(fù)思想，快速進行冪指數(shù)運算
int pow_mod(int a,int b,int c){
??? int res=1;
??????? while(b){
??????????? ??if((b&1)==1)res=(res*a)%c;
??????????????? a=(a*a)%c;
??????????????? b>>=1;
??????? }
??????? return (res+c)%c;
}隨機大素數(shù)（p,q）生成算法
將系統(tǒng)時間作為種子，產(chǎn)生隨機數(shù)，并利用米勒拉賓算法進行檢測，生成兩個不相等的大素數(shù)。
//米勒拉賓素性檢測
bool Miller_Rabbin(int a,int n){
??? //把n-1? 轉(zhuǎn)化成 (2^r)*d
??? int s=n-1,r=0;
??? while((s&1)==0){
??????? s>>=1;r++;
??? }
???
??? //算出 2^d? 存在 k 里
??? int k=pow_mod(a,s,n);
???
??? //二次探測? 看變化過程中是不是等于1 或 n-1
??? if(k==1)return true;
??? for(int i=0;i<r;i++,k=k*k%n){
??????? if(k==n-1)return true;
??? }
??? return false;
}
//素性判定
bool isprime(int n){
??? int times=7;
??? int prime[100]={2,3,5,7,11,233,331};
??? for(int i=0;i<times;i++){
?????? ?if(n==prime[i])return true;
??????? if(Miller_Rabbin(prime[i],n)==false)return false;//未通過探測 返回假
??? }
??? return true;//所有探測結(jié)束 返回真
}
//利用米勒拉賓素性檢測產(chǎn)生隨機素數(shù)（100以內(nèi)）
int produceRandom(){
?????? time_t t;
?????? int randnum;
?????? do{
????????????? srand((unsigned)time(&t));
??????? randnum = (rand())%100;
??????? if(isprime(randnum))return randnum;
?????? }while(1);
}擴展歐幾里得求逆元
根據(jù)擴展歐幾里得算法求得e相對于F_n的逆元d
//拓展歐幾里得算法求逆元?
int exgcd(int a,int b,int &x,int &y)
{
??? int t,gcd;
??? if(b==0)
??? {
??????? x=1,y=0;
??????? return a;
??? }
??? gcd=exgcd(b,a%b,x,y);
??? t=x,x=y,y=t-a/b*y;
??? return gcd;
}- 運行結(jié)果
對“明文.txt”進行加密得到“密文.txt”
對“密文.txt”進行解密得到“解密文.txt”
由此可見，英文大小寫均可實現(xiàn)隨機密鑰的加解密
源碼如下：
#include<cstdio>
#include<fstream>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<ctime>
using namespace std;
typedef long long ll;
int p = 0;
int q = 0;
int len = 0;
//拓展歐幾里得算法求逆元
int exgcd(int a,int b,int &x,int &y)
{
int t,gcd;
if(b==0)
{
x=1,y=0;
return a;
}
gcd=exgcd(b,a%b,x,y);
t=x,x=y,y=t-a/b*y;
return gcd;
}
//快速冪（模平方重復(fù)）
int pow_mod(int a,int b,int c){
int res=1;
while(b){
if((b&1)==1)res=(res*a)%c;
a=(a*a)%c;
b>>=1;
}
return (res+c)%c;
}
//米勒拉賓素性檢測
bool Miller_Rabbin(int a,int n){
//把n-1 轉(zhuǎn)化成 (2^r)*d
int s=n-1,r=0;
while((s&1)==0){
s>>=1;r++;
}
//算出 2^d 存在 k 里
int k=pow_mod(a,s,n);
if(k==1)return true;
for(int i=0;i<r;i++,k=k*k%n){
if(k==n-1)return true;
}
return false;
}
bool isprime(int n){
int times=7;
int prime[100]={2,3,5,7,11,233,331};
for(int i=0;i<times;i++){
if(n==prime[i])return true;
if(Miller_Rabbin(prime[i],n)==false)return false;//未通過探測 返回假
}
return true;//所有探測結(jié)束 返回真
}
//利用米勒拉賓素性檢測產(chǎn)生隨機素數(shù)（100以內(nèi)）
int produceRandom(){
int randnum;
do{
randnum = (rand())%100;
if(isprime(randnum))return randnum;
}while(1);
}
int main(){
srand(time(NULL));
int i;
here:
p = produceRandom();
q = produceRandom();
while(q==p)q=produceRandom();//p和q不能相等
int n = p*q;
while(n<128)goto here; //確保n足夠大，因為char為八位即-128~127,所以n至少要大于127
int F_n = (p-1)*(q-1);
int x,y;
int e = 7;
exgcd(e,F_n,x,y);
int d = (x + F_n) % F_n;
int flag;
while(1){
char text[1000]="";
cout<<"請選擇功能：\n 1.加密文件\n 2.解密文件\n 0.退出"<<endl;
cin>>flag;
if (!flag) break;
else if ((flag != 1) && (flag != 2))
{
cout << "輸入不合法，請重新輸入！" << endl << endl;
continue;
}
switch (flag)
{
case 1:{
char ch;
cout<<"加密密鑰為:("<<e<<','<<n<<')'<<endl;
ofstream ofs;
ifstream ifs;
ofs.open("密文.txt",ios::trunc|ios::out);
ifs.open("明文.txt",ios::in);
i = 0;
while(ifs>>ch){
text[i++]=ch;
}
len = strlen(text);
int ming [strlen(text)];
for(i = 0;i<strlen(text);i++){
ming[i]=text[i];
ming[i]=pow_mod(ming[i],e,n);
ofs<<ming[i]<<' ';
}
ofs.close();
ifs.close();
break;}
case 2:{
char ch;
int c[len];
cout<<"解密密鑰為:("<<d<<','<<n<<')'<<endl;
ofstream ofs;
ifstream ifs;
ofs.open("解密文.txt",ios::trunc|ios::out);
ifs.open("密文.txt",ios::in);
for(i = 0;i<len;i++){
ifs>>c[i];
ch = pow_mod(c[i],d,n);
ofs<<ch;
}
ofs.close();
ifs.close();
break;}
}
}
return 0;
}?參考文章：
?https://blog.csdn.net/destiny1507/article/details/81750874?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165358238516781685374707%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=165358238516781685374707&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-81750874-null-null.142^v11^pc_search_result_control_group,157^v12^control&utm_term=%E6%8B%93%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95&spm=1018.2226.3001.4187https://blog.csdn.net/destiny1507/article/details/81750874?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165358238516781685374707%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=165358238516781685374707&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-81750874-null-null.142%5ev11%5epc_search_result_control_group,157%5ev12%5econtrol&utm_term=%E6%8B%93%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95&spm=1018.2226.3001.4187文章來源：http://www.zghlxwxcb.cn/news/detail-448870.html
米勒-拉賓素性檢驗(MillerRabbin)算法詳解_1900_的博客-CSDN博客_米勒拉賓素性檢驗文章來源地址http://www.zghlxwxcb.cn/news/detail-448870.html
到了這里，關(guān)于RSA加解密算法的簡單實現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
