【RSA解密】蓝桥杯第十届省赛A组扩展欧几里得算法

Cyril-KI

发布于 2022-09-16 17:19:26

6170

点击蓝字关注我

思路分析：n,d已知的，我们第一步要生成两个质数p，q，这两个质数满足n=pq，且d与(p-1)(q-1)互质，那么我们先找到这两个质数：

for(long long i=1000; ;i++) {
    if(n % i == 0 && prime(i) && prime(n/i) && gcd(d, (i - 1) * (n / i - 1))==1) {
      p = i;
      q = n / i;
      break;
    }
 }

解出来：p=891234941,q=1123984201;

接下来de模上(p-1)(q-1)等于1，那我们再去寻找e：

这里我们引入逆元的概念：我们通常说 A 是 B 模 C 的逆元，实际上是指 A * B = 1 mod C，也就是说 A 与 B 的乘积模 C 的余数为 1。那么这里d就相当于是e模(p-1)*(q-1)的逆元，求解逆元需要用到扩展欧几里算法（exgcd），exgcd的应用场景为：求解ax+by=gcd(a,b)的整数解！！

扩展欧几里得算法的代码如下：

int gcd_Ex(int a,int b,int &x,int &y) {   //ax+by=gcd(a,b)的整数解 
  if(b==0) {
    x=1;
    y=0;
    return a;
  }
  int x1,y1;
  int gcd=gcd_Ex(b,a%b,x1,y1);  //bx+(a%b)y=gcd(a,b)有整数解x1,y1; 
  x=y1;y=x1-a/b*y1;
  return gcd;
}

exgcd的核心思想是：

1.设bx+(a%b)y=gcd(a,b)有整数解x1,y1；

2.x=y1;y=x1-[a/b] * y1

求解逆元代码如下：

ll mod_reverse(ll a,ll b) {   //求解ax%b==1 
  ll d,x,y;
  d=gcd_Ex(a,b,x,y);   //ax+by=gcd(a,b)有整数解x,y
  if(d==1) {
    return (x%b+b)%b;
  }else {    //无解 
    return -1;
  }
}

解出：e=823816095946741158;

于是：

n=1001733993063167141,d=212353;
p=891234941,q=1123984201;
e=823816095946741158;
C=20190324

而：，现在我们要求解X，根据题意我们只需要求解：即可，快速幂求模代码如下：

ll pow_mod(ll a,ll b,ll mod) {   //快速求解a^b%mod
  ll res=1,base=a%mod;
  while(b) {
    if(b&1) {
      res=fast_mul(res,base,mod);
    }
    base=fast_mul(base,base,mod);
    b >>= 1;
  }
  return res;
}

因此最终我们只需要调用：

pow_mod(C,e,n)

很悲催的是。。。。程序好像一直在运行。。。然后通过调试发现是最后一步快速幂求模很慢，而pow_mod中主要的运算集中在快速乘求模，于是可以再优化一下：

ll fast_mul(ll a, ll b, ll mod){  //快速求解a*b%mod 
  ll ans = 0;
  while(b) {
    if(b&1) {
      ans = (ans + a) % mod;
    }
    a=(a+a) % mod;
    b >>= 1;
  }
  return ans;
}

完整代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll p,q,e,ans;
ll n=1001733993063167141,d=212353;
ll C=20190324;

bool prime(ll x) {
  for(ll i=2;i<=sqrt(x);i++) {
    if(x%i==0) {
      return false;
    }
  }
  return true;
}

ll gcd(ll a,ll b) {
  return b?gcd(b,a%b):a;
}

ll gcd_Ex(ll a,ll b,ll &x,ll &y) {   //ax+by=c的整数解 
  if(b==0) {
    x=1;
    y=0;
    return a;
  }
  ll x1,y1;
  ll gcd=gcd_Ex(b,a%b,x1,y1);  //bx+(a%b)y=gcd(a,b)有整数解x1,y1; 
  x=y1;y=x1-a/b*y1;
  return gcd;
}

ll mod_reverse(ll a,ll b) {   //求解ax%b==1 
  ll d,x,y;
  d=gcd_Ex(a,b,x,y);   //ax+by=gcd(a,b)有整数解x,y
  if(d==1) {
    return (x%b+b)%b;
  }else {             //无解 
    return -1;
  }
}

ll fast_mul(ll a, ll b, ll mod){  //快速求解a*b%mod 
  ll ans = 0;
  while(b) {
    if(b&1) {
      ans = (ans + a) % mod;
    }
    a=(a<<=1) % mod;
    b >>= 1;
  }
  return ans;
}

ll pow_mod(ll a,ll b,ll mod) {   //快速求解a^b%mod
  ll res=1,base=a%mod;
  while(b) {
    if(b&1) {
      res=fast_mul(res,base,mod);
    }
    base=fast_mul(base,base,mod);
    b >>= 1;
  }
  return res;
}

int main() {
  //求解p,q 
  /*for(ll i=1000;;i++) {
    if(n%i==0&&prime(i)&&prime(n/i)&&gcd(d,(i-1)*(n/i-1))==1) {
      p=i;
      q=n/i;
      break;
    }
  }*/
  p=891234941,q=1123984201;
  ll t=(p-1)*(q-1);
    e=mod_reverse(d,t);
  ll x=pow_mod(C,e,n);
  cout<<x;
  return 0;
}

ans：579706994112328949

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-11-27，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自 KI的算法杂记微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度