洛谷P4454 破解D-H协议

传送门

题目背景

Diffie-Hellman密钥交换协议是一种简单有效的密钥交换方法。它可以让通讯双方在没有事先约定密钥(密码) 的情况下，通过不安全的信道(可能被窃听) 建立一个安全的密钥K,用于加密之后的通讯内容。

题目描述

假定通讯双方名为Alice和Bob,协议的工作过程描述如下(其中 mod 表示取模运算) :

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

Alice 生成一个随机数a,并计算A=g^a;mod;PA=g
a
modP, 将A 通过不安全信道发送给Bob。

Bob 生成一个随机数b,并计算B=g^b;mod;PB=g
b
modP,将B 通过不安全信道发送给Alice。

Bob 根据收到的A 计算出K=A^b;mod;PK=A
b
modP,而Alice 根据收到的B 计算出K=B^a;mod;PK=B
a
modP。

双方得到了相同的K,即g^{ab};mod;Pg
ab
modP。K 可以用于之后通讯的加密密钥。

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

当然安全是相对的，该协议的安全性取决于数值的大小，通常a、b、P 都选取数百位以上的大整数以避免被破解。然而如果Alice 和Bob 编程时偷懒，为了避免实现大数运算,选择的数值都小于2^{31}2
31
,那么破解他们的密钥就比较容易了。

输入格式

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

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

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

输出格式

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

输入输出样例

输入 #1复制
3 31
3
27 16
21 3
9 26
输出 #1复制
4
21
25

说明/提示

对于30%的数据，2≤A,B,P≤10002≤A,B,P≤1000

对于100%的数据，2≤A,B 31
,2≤g<20,1≤n≤20

上代码：

#include 
#include 
#include 
#include 
#include 
#define int long long
using namespace std;
int A,B,p,g,n,a,b,K;
map <int,int> f;
int gcd(int a,int b)     //最大公约数
{
	if (!b)return a;
	return gcd(b,a%b);
}
int mypow(int a,int x,int p)   //快速幂
{
	int s=1;
	while (x)
	{
		if (x&1)s=s*a%p;
		a=a*a%p;
		x>>=1;
	}
	return s;
}
int exgcd(int a,int b,int &x,int &y)  //扩欧求逆元
{
	if (!b)x=1,y=0;
	else
	{
		exgcd(b,a%b,x,y);
		int t=x;
		x=y;
		y=t-a/b*y;
	}
}
int inv(int a,int b)   //逆元
{
	int x,y;
	exgcd(a,b,x,y);
	return (x%b+b)%b;
}
int bsgs(int a,int b,int p)
{
	f.clear();
	int m=ceil(sqrt(p));
	for (int i=1;i<=m;i++)
	{
		b=b*a%p;
		f[b]=i;
	}
	b=1;
	int tmp=mypow(a,m,p);
	for (int i=1;i<=m;i++)
	{
		b=b*tmp%p;
		if (f[b])return (i*m-f[b]+p)%p;
	}
}
int exbsgs(int a,int b,int p)
{
	if (b==1||p==1)return 0;
	int g=gcd(a,p),k=0,na=1;
	while (g!=1)
	{
		k++;b/=g;p/=g;na=na*(a/g)%p;
		if (na==b)return k;
		g=gcd(a,p);
	}
	return bsgs(a,b*inv(na,p)%p,p)+k;
}
signed main()
{
	cin>>g>>p>>n;
	g%=p;
	for (int i=1;i<=n;i++)
	{
		cin>>A>>B;
		A%=p;
		B%=p;
		b=exbsgs(g,B,p);
		a=mypow(A,b,p);
		cout<<a<<endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86