学步园

题目链接：RUAL  1141. RSA Attack

知道RSA,这个题目就算水题了

RSA加密过程很简单：

  1. 选取很大的数p,q，令 n = p*q

  2. 取一个数e，满足gcd(e,(p-1)*(q-1)) = 1 && e < (p-1)*(q-1)

  3. 求出一个数d，d*e = 1 mod ( (p-1)*(q-1))

n d两个数构成公钥，可以告诉别人；
n e两个数构成私钥，e自己保留，不让任何人知道。

具体怎么加密看这里

由于这里p，q 都很小，所以可以很容易的破解RSA

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn=32010;
int prime[maxn],num;
bool isprime[maxn];

void init()
{
    for(int i=2;i<maxn;i++)
      if(!isprime[i])
      {
          prime[num++]=i;
          for(int j=2*i;j<maxn;j+=i)
            isprime[j]=1;
      }
}
int ex_gcd(int &x,int &y,int a,int b)
{
    if(b==0){
        x=1;y=0;
        return a;
    }
    int d=ex_gcd(x,y,b,a%b);
    int t=x;
    x=y,y=t-a/b*y;
    return d;
}
long long quick_mod(int c,int x,int mod)
{
    long long ret=1;
    for(long long b=c;x;x>>=1,b=b*b%mod)
       if(x&1) ret=ret*b%mod;
    return ret;
}
int main()
{
    init();
    int e,n,c,T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&e,&n,&c);
        int i;
        for(i=0;i<num;i++)
          if(n%prime[i]==0&&!isprime[n/prime[i]]) break;
        int p=prime[i],q=n/prime[i],x,y;
        int mod=(p-1)*(q-1);
        ex_gcd(x,y,e,mod);
        x=(x%mod+mod)%mod;
        printf("%lld\n",quick_mod(c,x,n));
    }
    return 0;
}