「CQOI2018」破解D-H协议-BSGS算法

简单题意：

给定一个质数 $P$ 和其原根 $g$，给定 $X$ 求 $g^x \equiv X \pmod p$ 的非负整数解 $x$。

假定通讯双方名为 $\text{Alice}$ 和 $\text{Bob}$ ，协议的工作过程描述如下(其中 $\bmod$ 表示取模运算) :

协议规定一个固定的质数 $P$ ，以及模 $P$ 的一个原根 $g$ 。 $P$ 和 $g$ 的数值都是公开的，无需保密。
$\text{Alice}$ 生成一个随机数 $a$ ，并计算 $A=g^a \bmod P$, 将 $A$ 通过不安全信道发送给Bob。
$\text{Bob}$ 生成一个随机数 $b$ ，并计算 $B=g^b \bmod P$ ，将 $B$ 通过不安全信道发送给 $\text{Alice}$ 。
$\text{Bob}$ 根据收到的 $A$ 计算出 $K=A^b\bmod P$ ，而 Alice 根据收到的 $B$ 计算出$K=B^a\bmod P$。
双方得到了相同的 $K$ 即 $g^{ab} \bmod P$。 $K$ 可以用于之后通讯的加密密钥。

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

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

链接

Luogu P4454

题解

$\text{BSGS}$ 模版题，甚至连分类讨论都没有…

代码

 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
#include <cstdio>
#include <cmath>
#include <map>
#define ll long long
using namespace std;

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

ll pow(ll x,ll k,ll p){
  x %= p;
  ll ans = 1;
  for(ll i = k;i;i>>=1,x=x*x%p) if(i & 1) ans = ans * x % p;
  return ans;
}

ll bsgs(ll a,ll b,ll p){
  //printf("a:%lld b:%lld P:%lld\n",a,b,p);
  a %= p,b %= p;
  if(b == 1) return 0;
  ll cnt = 0,t = 1;
  for(ll g = gcd(a,p);g!=1;g = gcd(a,p)){
    if(b % g) return -1;
    a /= g,p /= g, t =  t * a/g % p;
    cnt++;
    if(t == b) return cnt; 
  }
  
  map<ll,ll> S;
  ll m = (ll)(sqrt(p)) + 1;
  ll base = b;
  for(ll i = 0;i<m;i++){
    S[base] = i;
    base = base * a % p;
  }
  ll now = t;
  base = pow(a,m,p);
  for(ll i = 1;i<=m+1;i++){
    now = now * base % p;
    if(S.count(now)){
      return i*m-S[now]+cnt;
    }
  }
  return -1;
}

ll n;
ll p,G;

ll cal(ll A,ll B){
  ll a = bsgs(G,A,p),b = bsgs(G,B,p);
  //printf("a:%lld b:%lld\n",a,b);
  return pow(G,a*b,p); 
}

void init(){
  scanf("%lld %lld",&G,&p);
}

void solve(){
  scanf("%lld",&n);
  for(int i = 1;i<=n;i++){
    ll a,b;
    scanf("%lld %lld",&a,&b);
    printf("%lld\n",cal(a,b));
  }
}

int main(){
  init();
  solve();
  return 0;
}

「CQOI2018」破解D-H协议-BSGS算法

链接

题解

代码

See Also

Comments