菲洛嘉青春动能素135HA FILLMED® NCTF 135HA LED指示灯的常见故障分析 智微智能 Elkhartlake K075终端,零售产业新选择 天空蓝拓客管理系统详细介绍版 muso公链项目 天使计划 是什么?[秘] 独家揭秘最前沿的家装“黑科技”——掌赋 天博体育欧洲杯特辑,东道主法兰西的失意2016 亚马逊的送货侦察员 学习听起来像挡泥板 Google Comics Factory使ML变得容易 笑着说-男性或女性 Amazon Rekognition中更好的人脸检测 关于Spaun的真相-大脑模拟 两个聊天机器人彼此聊天-有趣又怪异 GANPaint:将AI用于艺术 WCF和WF给予社区 从耳朵到脸 所有神经网络的深层缺陷 蠕虫在尾巴上平衡杆子 Kickstarter上的OpenCV AI套件 TensorFlow-Google的开源AI和计算引擎 众包取代新闻工作者 Google的DeepMind学会玩街机游戏 哑机器人V智能机器人 .NET与.NET 5融为一体 Google的深度学习-语音识别 LInQer将.NET LINQ移植到Javascript 机器人TED演讲-新的图灵测试? GAN的发明者加入苹果 您的智能手机会监视您键入的内容 人工智能帮助改善国际象棋 Zalando Flair NLP库已更新 TensorFlow 1.5包含移动版本 AlphaGo输了一场比赛-比分3-1 虚拟机器学习峰会 Microsoft开源AI调试工具 SharePoint走向移动 F#4.0发出文化变革的信号 克里斯蒂拍卖AI艺术品 人工智能如何区分 Facebook在蒙特利尔的新AI实验室 Mozilla想要您的声音 微软使用极深的神经网络赢得ImageNet 建立AI合作伙伴关系 .NET Core 3-Microsoft几乎回到了起点 神经网络-更好的销售商? Google使用AI查找您的住所 虹膜-适用于Android的Siri证明苹果没有优势 TensorFlow 2提供更快的模型训练 深度学习研究人员将为Google工作
您的位置:首页 >数据库 >

「信息安全-密码与隐藏技术」RSA加密算法的实现(CPP 实现)

RSA加密算法的实现

第一步,选择密钥

选择两个不同的素数 p、q计算公开模数r = p x q计算欧拉函数 φ(r) = (p-1) * (q-1)选择一个与 φ(r) 互质的量 k,即保证 gcd(φ(r), k) = 1 时,选择 k 。 可以令 sp = kpk = 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 求余,就可得到明文。

关键代码:求逆元

// 拓展gcdvoid 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 0x3f3f3f3fusing 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; //34cout<<poww(345,89,101)<<endl; //34}

有了上述两段关键代码后,我们的整个加密算法就简单了,下面给出整体实现源码:

实现源码

#include<bits/stdc++.h>#define mst(a,b) memset(a,b,sizeof(a);#define INF 0x3f3f3f3fusing namespace std;const int maxn=1e3+5;int n,m,t;typedef long long ll;// 拓展gcdvoid 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;}
学如逆水行舟,不进则退
一百个ChocolateCSDN认证博客专家CSDN博客专家博客之星前端开发攻城狮学如逆水行舟,不进则退
一起手摸手闯秋招~

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。