Algorithms&Data Structures

CQOI2018破解 D-H 协议

Description

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

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

  1. 协议规定一个固定的质数P,以及模P的一个原根gPg的数值都是公开的,无需保密。
  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 PK可以用于之后通讯的加密密钥。

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

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

Input

第一行包含两个空格分开的正整数gP

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

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

Output

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

Sample Input

3 31
3
27 16
21 3
9 26

Sample Output

4
21
25

Hint

对于30\%的数据,2\le A,B,P\le 1000

对于100\%的数据,2\le A,B<P<2^{31}2\le g<201\le n\le 20

Solution

高阶同余方程求解,2^{31}范围的数据直接上BSGS,用map作的hash,设m=\sqrt P,时间复杂度O(nm+nmlogm)

BSGS学习笔记移步链接

Code

 

发表评论

邮箱地址不会被公开。 必填项已用*标注