破解 D-H 协议

756: 破解 D-H 协议

时间限制: 1 Sec 内存限制: 128 MB
提交: 78 解决: 18
[提交] [状态] [讨论版] [命题人:admin]

题目描述

Diffie-Hellman密钥交换协议是一种简单有效的密钥交换方法。它可以让通讯双方在没有事先约定密钥（密码）的情况下，通过不安全的信道（可能被窃听）建立一个安全的密钥K，用于加密之后的通讯内容。
假定通讯双方名为Alice和Bob，协议的工作过程描述如下（其中mod表示取模运算）：
协议规定一个固定的质数P，以及模P的一个原根g。P和g的数值都是公开的，无需保密。
Alice生成一个随机数a，并计算A=ga mod P，将A通过不安全信道发送给Bob。
Bob生成一个随机数b，并计算B=gb mod P，将B通过不安全信道发送给Alice。
Bob根据收到的A计算出K=Ab mod P ，而Alice根据收到的B计算出K=Ba mod P。
双方得到了相同的K，即gab mod P。K可以用于之后通讯的加密密钥。
可见，这个过程中可能被窃听的只有A,B，而a,b,K是保密的。并且根据A,B,P,g这4个数，不能轻易计算出K，因此K可以作为一个安全的密钥。
当然安全是相对的，该协议的安全性取决于数值的大小，通常a,b,P都选取数百位以上的大整数以避免被破解。然而如果Alice和Bob编程时偷懒，为了避免实现大数运算，选择的数值都小于231，那么破解他们的密钥就比较容易了。

输入

第一行包含两个空格分开的正整数g和P。
第二行为一个正整数n，表示Alice和Bob共进行了n次连接（即运行了n次协议）。
接下来n行，每行包含两个空格分开的正整数A和B，表示某次连接中，被窃听的A,B数值。

输出

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

样例输入

样例输出

提示

对于30%的数据，2≤A,B,P≤1000。
对于100%的数据，2≤A,B<P<231,2≤g<20,1≤n≤20。

来源/分类

重庆OI2018

思路：

北上广深算法，分别解出a、b，然后用快速幂！

AC代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

struct LSnode

{

    int y,p;

} w[],q[];

int tot,tlen,g;

int mod;

int pow_mod(int a,LL b)

{

    register int ret=;

    while(b)

    {

        if(b&)ret=(LL)ret*a%mod;

        a=(LL)a*a%mod;

        b>>=;

    }

    return ret;

}

bool cmp(LSnode n1,LSnode n2)

{

    if(n1.y!=n2.y) return n1.y<n2.y;

    return n1.p<n2.p;

}

int fd(int p)

{

    int l=,r=tlen;

    while(l<=r)

    {

        int mid=(l+r)/;

        if(q[mid].y<p) l=mid+;

        else if(q[mid].y>p) r=mid-;

        else return q[mid].p;

    }

    return -;

}

int BSGS(int y,int A)

{

    if(y== && A==)return ;

    register int tmp=pow_mod(y,mod-),cnt=;

    int m=ceil(sqrt(mod));

    tot=;

    w[++tot].y=A;

    w[tot].p=m+;

    for(register int i=; i<m; i++)

    {

        cnt=(LL)cnt*tmp%mod;

        LL t=(LL)cnt*A%mod;

        w[++tot].y=t;

        w[tot].p=i;

    }

    sort(w+,w++tot,cmp);

    tlen=;

    q[]=w[];

    for(int i=; i<=tot; i++)

    {

        if(w[i].y!=w[i-].y) q[++tlen]=w[i];

    }

    tmp=pow_mod(y,m),cnt=;

    for(register int i=; i<m; i++)

    {

        int pp=fd(cnt);

        if(pp!=-)

        {

            if(pp==m+) return i*m;

            return pp+i*m;

        }

        cnt=(LL)cnt*tmp%mod;

    }

    return ;

}

int main()

{

    int T;

    scanf("%d %d",&g,&mod);

    scanf("%d",&T);

    while(T--)

    {

        int u,v;

        scanf("%d %d",&u,&v);

        int sx,sy;

        sy=BSGS(g,v);

        sx=BSGS(g,u);

        printf("%d\n",pow_mod(g,(LL)sx*sy));

    }

    return ;

}

巴特西