「信息安全-密码与隐藏技术」RSA加密算法的实现（CPP 实现）
发布时间
阅读量：
阅读量
RSA加密算法的实现
第一步，选择密钥
- 选取两个互不相同的素数 p, q
- 确定公共模数为 r = p \cdot q
- 求出欧拉函数值为 \varphi(r) = (p - 1)(q - 1)
- 选取与 \varphi(r) 互质的一个整数值 k ，即满足 \gcd(\varphi(r), k) = 1 的条件。可以选择让 sp 等于 k 或者让 pk 等于 k
由于与φ(r)互质的数不止一个，则k的选择被限定于特定范围之内。首先设定k为一个初始值，并且满足k < φ(r)，随后通过试探法确定满足条件使得φ(r)和k的最大公约数为1的k值。
注意，如果选一个密钥的值大于φ(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;
// ¿ìËÙÃÝ
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;
} 学如逆水行舟，不进则退全部评论 (0)
还没有任何评论哟~