P4454 [CQOI2018]破解D-H协议

    • 168通过
    • 359提交
  • 题目提供者 Xeonacid
  • 评测方式 云端评测
  • 标签 枚举,暴力 素数判断,质数,筛法 逆元 各省省选 2018 重庆
  • 难度 省选/NOI-
  • 时空限制 1000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    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^{ab}\;mod\;P$。K 可以用于之后通讯的加密密钥。

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

    当然安全是相对的,该协议的安全性取决于数值的大小,通常a、b、P 都选取数百位以上的大整数以避免被破解。然而如果Alice 和Bob 编程时偷懒,为了避免实现大数运算,选择的数值都小于$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≤1000$

    对于100%的数据,$2≤A,B<P<2^{31},2≤g<20,1≤n≤20$

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。