首页 > 代码库 > 上海五校赛 密码破解

上海五校赛 密码破解

2024-10-22 03:23:39   212人阅读

密码破解

发布时间: 2017年7月9日 18:17   最后更新: 2017年7月9日 21:04   时间限制: 1000ms   内存限制: 128M

近日来勒索病毒的事件频繁发生，小Y对它的加密原理非常感兴趣，研究了一番相关知识之后，他就来给你看他的加密程序，并给你一段密文，和你炫耀说就算把程序给你看你也破解不出来。

你扫了一眼代码发现加密的公式为b=a e %m  ，其中e  是质数。

进一步分析发现m=p∗q  ，p  和q  都为质数，p!=q  ，

作为一个计算机高手，你早就对加密算法烂熟于心，一眼就看出这个程序的算法和原理，找到了破解的方法，发现小Y疏忽在与给了你一个不够大的m  。

你知道解密的公式与加密对称，为a=b d %m  。

但是你仍然无法心算解出这个d  ，因此你需要借助计算机来将密文破解。

第一行有一个整数T  表示数据组数。（T<=100  ）
接着有T 组数据，每组数据两行。
第一行有四个数e 、p 、q 和n ，其中e 、p 、q 如题所描述，n 表示需要解密的数字序列长度。
第二行是需要解密的数字序列a 1 ..a n  。
1 < p ,q ,e <= 10 8  ，p 、q 、e 为质数且p!=q 。
$0<=a_i<m$。($1<=i<=n$)< br=""> 保证解密的结果即原数列的值小于min(p,q) 并大于等于0 
1<=n<=100 
保证m 有且仅有两个不同的质因数p 和q ，并且一定存在一个题中描述的参数d 使得解密公式能够无损解密出所有0 ~min(p,q)−1 范围之间的数字。

对于每组数据输出一行，表示解密后的数字序列，数字之间以空格隔开。

复制
15 19 29 3335 440 514
65 67 77
分析：首先有个性质，(d*e)=1(mod Φm);
　　　然后就简单了，求出Φm = (p-1)*(q-1)，利用扩欧解出d，最后快速幂即可；
　　　注意坑点是乘法可能爆long long；
代码：
#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <climits>#include <cstring>#include <string>#include <set>#include <bitset>#include <map>#include <queue>#include <stack>#include <vector>#include <cassert>#include <ctime>#define rep(i,m,n) for(i=m;i<=(int)n;i++)#define mod 1000000007#define inf 0x3f3f3f3f#define vi vector<int>#define pb push_back#define mp make_pair#define fi first#define se second#define ll long long#define pi acos(-1.0)#define pii pair<int,int>#define sys system("pause")#define ls rt<<1#define rs rt<<1|1const int maxn=1e3+10;const int N=5e2+10;using namespace std;ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}ll qmul(ll p,ll q,ll mo){ll f=0;while(q){if(q&1)f=(f+p)%mo;p=(p+p)%mo;q>>=1;}return f;}ll qpow(ll p,ll q,ll mo){ll f=1;while(q){if(q&1)f=qmul(f,p,mo)%mo;p=qmul(p,p,mo)%mo;q>>=1;}return f;}int n,m,k,t;ll a[maxn],ret[maxn];ll e_gcd(ll a,ll b,ll &x,ll &y){    if(b==0)    {        x=1;        y=0;        return a;    }    ll ans=e_gcd(b,a%b,x,y);    ll temp=x;    x=y;    y=temp-a/b*y;    return ans;}ll cal(ll a,ll b,ll c){    ll x,y;    ll gcd=e_gcd(a,b,x,y);    if(c%gcd!=0) return -1;    x*=c/gcd;    b/=gcd;    if(b<0) b=-b;    ll ans=x%b;    if(ans<=0) ans+=b;    return ans;}int main(){    int i,j;    scanf("%d",&t);    while(t--)    {        int e;        ll p,q;        scanf("%d%lld%lld%d",&e,&p,&q,&n);        rep(i,1,n)scanf("%lld",&a[i]);        ll d=cal(e,(p-1)*(q-1),1);        rep(i,1,n)ret[i]=qpow(a[i],d,p*q);        rep(i,1,n)printf("%lld%c",ret[i],i==n?‘\n‘:‘ ‘);    }    return 0;}

上海五校赛 密码破解


联系
我们