三教许愿池

此题涉及 DDH Assumption ：

https://en.wikipedia.org/wiki/Decisional_Diffie–Hellman_assumption

根据 wikipedia 提供的信息，可以知道

one can efficiently compute the Legendre symbol of g^{ab}, giving a successful method to distinguishg^{ab}from a random group element.

即，在题目这样的条件下，我们使用勒让德符号，有一定几率可以辨别出 g^{ab} （非随机的一个）和 g^{c} （真随机的那个）

具体实现如下(python)：

def legendre_symbol(a, p):
    ls = pow(a, (p - 1) // 2, p)
    return -1 if ls == p - 1 else ls


def distinguisher(gx,gy,g1,g2):
    x = 1 * legendre_symbol(gx, p) == -1
    y = 1 * legendre_symbol(gy, p) == -1
    a = 1 * legendre_symbol(g1, p) == -1
    # b = 1 * legendre_symbol(g2, p) == -1
    ans.append(1 if x * y == a else 0)

其中 x, y, a, b 分别代表了 g^x, g^y, g1, g2 这些指数项的指数的奇偶性。

由于可爱的 cwk 学长精心设计，使得 g1, g2 的指数奇偶性总是不同，所以我们可以完全辨别出所有的 challenge。

最后，我们得到 ans 数组，变为 hex 即可得到答案：

hex(int(''.join([str(x) for x in ans]), 2))[2:]

戎明远 17级（校内第一个做出的同学）

首次尝试

我有g 有g^x 先把x算出来不就简单了！

看了一下数据长度……放弃

二次尝试

试图用g^x和g^y的初等运算做出g^xy

发现这是g^xy不是g^(x+y)

失败

三次尝试

吸取了第一次失败的经验，失败的原因主要是要遍历p-1才能保证找到x，这太多了，而这种大数运算唯一比较快的操作是指数运算。

所以想到考虑g^xr，g^yr和g^xyr，g^xyrr。

然而这并没有什么卵用。

突然发现g是原根(代码中有说)，则令r=(p-1)/q，其中q是p-1的小因子，就可以通过观察g^xr和g^yr判断x，y模q的余数。首先q可以等于2，我们就排除了一半的数据。其次假设q可以等于3，我们又能排除三分之二的数据……等等。

py计算发现p-1在1000000以内只有一个因子:2

GG

……

n次尝试后

睡觉大过天。

起床。

n+1次尝试

先把一半数据排了再说吧。

然后……就没有然后了。

30min 实验加编完。

付佳伟 17级

这明摆着是一道数学题啊。。。还是数论。。。。。。

先看代码查查背景，$g$是$\mathbb{Z}_p^*$的原根意味着$g^1$、$g^2$、……、$g^{p-1}$是$1$、$2$、……、$p-1$的一个排列。于是当$g^x\equiv d\ \ (\mathrm{mod}\ n)$ 时，称$x$是以$g$为底，$d$的离散对数，记为$x=\mathrm{Ind}_g{d}$。再查更多的资料发现，类似于RSA的基础假设：大质数在有意义的时间内无法分解，同样的离散对数也无法求解，所以这题让我们求56个离散对数，肯定是不可能的，想想别的办法。

注意到，根据费马小定理，我们有$g^{p-1}\equiv1\ \ (\mathrm{mod}\ p)$，而$g$又是$\mathbb{Z}_p^*$的原根，这意味着$g^\frac{p-1}{2}\equiv-1\ \ (\mathrm{mod}\ p)$，所以我们可以根据$(g^x)^\frac{p-1}{2}$和$(g^y)^\frac{p-1}{2}$的结果判断$x$和$y$的奇偶性。这是个不错的猜想，我们先试试：

q = (p - 1) // 2

def parityCheck(n):
  r = pow(n, q, p)
  if r == 1:
    return 0
  if r == p - 1:
    return 1
  return -1

def distinguisher(gx,gy,g1,g2):
  px = parityCheck(gx)
  py = parityCheck(gy)
  p1 = parityCheck(g1)
  p2 = parityCheck(g2)
  print(px, py, p1, p2)
  exit(0)

最后那个exit(0)是为了让程序对第一组数据运行完之后就先退出，毕竟现在只是试试数据。

输出：

0 1 1 0

看起来g1和g2关于$\mathbb{Z}_p^$的离散对数分别是一奇一偶，后面再测试一下，发现全部56组数据的g1和g2都是这样的*(!!!)。那么直接开始计算，先改一下代码：

def distinguisher(gx,gy,g1,g2):
  px = parityCheck(gx)
  py = parityCheck(gy)
  p1 = parityCheck(g1)
  p2 = parityCheck(g2)
  ans = px * py
  if ans == p1:
    print(1, end='')
  if ans == p2:
    print(0, end='')

运行输出：

01110100111011100001111110110001001000011010101100100001

我想手动转换这么点十六进制数应该不算太难吧，起码比写个程序用的时间短。

（编者注：这孩子或许可以用来当 ALU）

74ee1fb121ab21

好了，提交flag吧

flag{74ee1fb121ab21}