BZOJ_5296_[Cqoi2018]破解D-H协议_BSGS

Description

Diffie-Hellman密钥交换协议是一种简单有效的密钥交换方法。它可以让通讯双方在没有事先约定密钥（密码）的情况下

通过不安全的信道（可能被窃听）建立一个安全的密钥K，用于加密之后的通讯内容。

假定通讯双方名为Alice和Bob，协议的工作过程描述如下（其中mod表示取模运算）：

1．协议规定一个固定的质数P，以及模P的一个原根g。P和g的数值都是公开的，无需保密。

2．Alice生成一个随机数a，并计算A=g^a mod P，将A通过不安全信道发送给Bob。

3．Bob生成一个随机数b，并计算B=g^b mod P，将B通过不安全信道发送给Alice。

4．Bob根据收到的A计算出K=A^b mod P，而Alice根据收到的B计算出K=B^a mod P。

5．双方得到了相同的K，即g^(a*b) mod P。K可以用于之后通讯的加密密钥。

可见，这个过程中可能被窃听的只有A、B，而a、b、K是保密的。并且根据A、B、P、g这4个数，不能轻易计算出

K，因此K可以作为一个安全的密钥。

当然安全是相对的，该协议的安全性取决于数值的大小，通常a、b、P都选取数百位以上的大整数以避免被破解。然而如

果Alice和Bob编程时偷懒，为了避免实现大数运算，选择的数值都小于2^31，那么破解他们的密钥就比较容易了。

Input

输入文件第一行包含两个空格分开的正整数g和P。

第二行为一个正整数n，表示Alice和Bob共进行了n次连接（即运行了n次协议）。

接下来n行，每行包含两个空格分开的正整数A和B，表示某次连接中，被窃听的A、B数值。

2≤A，B<P<231，2≤g<20， n<=20

Output

输出包含n行，每行1个正整数K，为每次连接你破解得到的密钥。

Sample Input

3 31
3
27 16
21 3
9 26

Sample Output

4
21
25

通过$A=g^a\;mod\;P$用$BSGS$求出$a$的值，然后求$K=B^a\;mod\;P$。

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <map>

#include <math.h>

using namespace std;

typedef long long ll;

map<ll,int>mp;

void exgcd(ll a,ll b,ll &x,ll &y,ll &p) {

	if(!b) {x=1; y=0; p=a; return ;}

	exgcd(b,a%b,y,x,p);

	y-=a/b*x;

}

ll qp(ll x,ll y,ll p) {

	ll re=1;

	while(y) {

		if(y&1ll) re=re*x%p;

		x=x*x%p;

		y>>=1ll;

	}

	return re;

}

ll BSGS(ll a,ll b,ll n) {

	if(n==1) if(!b) return a!=1;else return -1;

	if(b==1) if(a) return 0;else return -1;

	if(a%n==0) if(!b) return 1;else return -1;

	ll m=ceil(sqrt(n)),d=1,base=1;

	mp.clear();

	int i;

	for(i=0;i<m;i++) {

		if(!mp.count(base)) mp[base]=i;

		base=base*a%n;

	}

	for(i=0;i<m;i++) {

		ll x,y,s;

		exgcd(d,n,x,y,s);

		x=(x*b%n+n)%n;

		if(mp.count(x)) return i*m+mp[x];

		d=d*base%n;

	}

	return -1;

}

int main() {

	ll g,p,n,A,B,a,b;

	scanf("%lld%lld%lld",&g,&p,&n);

	while(n--) {

		scanf("%lld%lld",&A,&B);

		a=BSGS(g,A,p);

		printf("%lld\n",qp(B,a,p));

	}

}

秒客网