RSA加密演算法的實作
第一步，選擇密鑰
- 選擇兩個不同的素數
p、q - 計算公開模數
r = p x q - 計算歐拉函式
φ(r) = (p-1) * (q-1) - 選擇一個與
φ(r)互質的量k，即保證gcd(φ(r), k) = 1時，選擇k， 可以令sp = k或pk = k，
因為與 φ(r) 互質的數可能不止一個，所以 k 的值是有選擇的，可以先設 k 為一個初值，并且 k < φ(r)，然后用試探法求出滿足條件 φ(r) 與 k 的最大公約數為 1 的 k，即 gcd(φ(r), k) = 1，
注意，如果選一個密鑰的值大于 φ(r) 的值，就不能正確求出另一個密鑰，
- 根據
sk * pk ≡ 1 mod φ(r)，已知 sk 或 pk，用乘逆演算法求 pk 或 sk，
第二步，加密
對明文自乘 pk 次冪或 sk 次冪，再按模 r 求余，就可得到密文，
第三步，解密
與加密程序型別，對密文自乘 pk 次冪或 sk 次冪，再按模 r 求余，就可得到明文，
關鍵代碼：求逆元
// 拓展gcd
void exgcd(ll a,ll b,ll& d,ll& x,ll& y){
if(!b) { d = a; x = 1; y = 0; }
else{ exgcd(b, a%b, d, y, x); y -= x*(a/b); }
}
// 求逆元
ll inv(ll a, ll p){
ll d,x,y;
exgcd(a,p,d,x,y);
return d == 1 ? (x+p)%p : -1;
}
關鍵代碼：平方-乘演算法
使用 RSA 演算法進行加密和解密時需要用到此演算法，也就是我們所說的快速冪，下面給出對應模板，
#include<bits/stdc++.h>
#define mst(a,b) memset(a,b,sizeof(a);
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
// ?ì?ù?Y
ll poww(ll a,ll b,ll mod){
ll ans=1,base=a;
while(b){
if(b&1)
ans = ans*base%mod;
base = base*base%mod;
b>>=1;
}
return ans;
}
int main(){
cout<<poww(34,60,51)<<endl; //34
cout<<poww(345,89,101)<<endl; //34
}
有了上述兩段關鍵代碼后，我們的整個加密演算法就簡單了，下面給出整體實作原始碼：
實作原始碼
#include<bits/stdc++.h>
#define mst(a,b) memset(a,b,sizeof(a);
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=1e3+5;
int n,m,t;
typedef long long ll;
// 拓展gcd
void exgcd(ll a,ll b,ll& d,ll& x,ll& y){
if(!b) { d = a; x = 1; y = 0; }
else{ exgcd(b, a%b, d, y, x); y -= x*(a/b); }
}
// 求逆元
ll inv(ll a, ll p){
ll d,x,y;
exgcd(a,p,d,x,y);
return d == 1 ? (x+p)%p : -1;
}
// 快速冪
ll poww(ll a,ll b,ll mod){
ll ans=1,base=a;
while(b){
if(b&1)
ans = ans*base%mod;
base = base*base%mod;
b>>=1;
}
return ans;
}
// 加密程序
ll encryption(ll pk,ll r,ll num){
return poww(num,pk,r)%r;
}
// 解密程序
ll decrypt(ll sk,ll r,ll text){
return poww(text,sk,r)%r;
}
int main(){
ll prime1,prime2,pk;
cout<<"請輸入測驗資料組數："<<endl;
cin>>t;
while(t--){
cout<<"請輸入兩個大的素數和公鑰"<<endl;
cin>>prime1>>prime2>>pk;
// 公開模數
ll r = prime1 * prime2;
// 歐拉函式
ll n = (prime1-1)*(prime2-1);
cout<<"公開模數r為："<<r<<endl;
ll sk = inv(pk,n);
cout<<"私鑰sk為："<<sk<<endl;
cout<<"請輸入要加密的數字串（輸入0結束）："<<endl;
ll num;
cin>>num;
while(num){
// 密文
int cipherText = encryption(pk,r,num);
cout<<"加密后的密文為："<<cipherText<<endl;
// 明文
int plainText = decrypt(sk,r,cipherText);
cout<<"解密后的明文為："<<plainText<<endl;
cin>>num;
}
}
return 0;
}
學如逆水行舟，不進則退
一百個Chocolate
CSDN認證博客專家
CSDN博客專家
博客之星
前端開發攻城獅
CSDN認證博客專家
CSDN博客專家
博客之星
前端開發攻城獅
學如逆水行舟，不進則退一起手摸手闖秋招~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/22983.html
標籤：其他
下一篇：單例模式執行緒是否安全?