BZOJ5296 CQOI2018Day1T1 破解D-H协议

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

看到的时候蒙圈了。。打了一个三十分暴力。。然后GG了

后来大佬们讲了BSGS，发现这是个模板题

BSGS可以快速求解Ax=B(mod C)(C为质数)" role="presentation">Ax=B(mod C)(C为质数)Ax=B(mod C)(C为质数)这样的同余方程

把系数x换成am+b的形式，然后可以通过

* 预处理1到根号次数的哈希值

* 查表

算出答案

#include<bits/stdc++.h>

using namespace std;

#define N 10000010

#define LL long long

#define mp make_pair

const LL up=50000;

const LL Base=10000007;

LL g,p,n,A,B;

vector<pair<LL,LL> >hash[N];

LL fast_pow(LL a,LL b){

    int ans=1;

    while(b){

        if(b&1)ans=(ans*a)%p;

        b>>=1;

        a=(a*a)%p;

    }

    return ans;

}

void Hash(){

    LL h=fast_pow(g,up),pic=h;

    for(LL i=1;(i-1)*up<=INT_MAX;i++,h=(h*pic)%p)

        hash[h%Base].push_back(mp(i,h));

}

LL solve(LL x){

    LL h=g;

    for(int i=1;i<=up;i++,h=(h*g)%p){

        LL tmp=(h*x)%p;

        for(int j=0;j<hash[tmp%Base].size();j++){

            LL cas=hash[tmp%Base][j].second;

            if(cas==tmp){

                cas=hash[tmp%Base][j].first;

                return cas*up-i;

            }

        }

    }

}

int main(){

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

    Hash();

    for(int i=1;i<=n;i++){

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

        printf("%lld\n",fast_pow(B,solve(A)));

    }

    return 0;

}

巴特西

BZOJ5296 CQOI2018 破解D-H协议【BSGS】

BZOJ5296 CQOI2018Day1T1 破解D-H协议

Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章

巴特西

BZOJ5296 CQOI2018 破解D-H协议 【BSGS】

BZOJ5296 CQOI2018Day1T1 破解D-H协议

Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章

BZOJ5296 CQOI2018 破解D-H协议【BSGS】