和S1uM4i打了今年的XCTF Final，首先恭喜S1uM4i获得了季军，师傅们太强了，被狠狠地带飞了

我做了其中的Cu2ve，理论上这题需要用Pairing的方法去解，但这题有一种非预期的解法，所以比赛的时候就偷鸡了

赛后复现了一下预期的解法，学到了挺多的东西，于是在这里记录一下

以下内容在S1uM4i的WP中有简版，虽然WP好像没发。。。发了再补链接

Cu2ve·

首先看题目：Cu2ve.zip

题目分为两部分，在task.sage中需要解决一个椭圆曲线上的DDH问题，然后获得utils.py中prp的每次的next输出，根据这些输出解出初始的state，最后使用state获得密钥，做一次OTP的解密得flag

prp与解密·

prp的部分会相对简单一点，所以先看prp的部分，其中的next函数其实就是输出state表中的每一位状态

每当state表中的每位（一共100位）状态都输出过后，就使用twsit_state表对state表进行置换，即题目的twist函数的操作

由于twsit_state表是已知的，所以可以根据twsit_state表写一种twist的逆操作，比如下面的unTwisit（当然这样的写法好像有点粗暴，应该有更好看的写法）

tmp = list(range(100))
uts = [0 for _ in range(100)]
for i in range(100):
    uts[twsit_state[i]] = tmp[i]

def unTwisit(s):
    return [s[uts[i]] for i in range(100)]

而加密所用的key做一次twist后（注意__init__中有一次twist）就是前100位state，那么其实如果知道前100位state的话，也就可以知道key，就可以对密文解密得到flag

但事情肯定没有这么简单的，因为看task.sage的话发现给了615位的state，这些state大概可以分为6（或7）组，其中

$S_{i+1} = twist(S_i)$

我们需要的是 $S_0$ ，所以如果知道后面的 $S_i$ 的话，也可以通过求 $S_0 = unTwist^i(S_i)$ 得到 $S_0$ ，或者 $S_0$ 的某些比特，这个后面用到的时候再细说

Pohlig-Hellman与非预期解法·

那么现在题目的难点就是如何通过task.sage的输出得到那615位的state

审题可以发现task.sage里其实是个ECC的DDH（Decisional Diffie–Hellman）问题，即给定随机的 $x$ 和 $y$ ，给点 $P$ 、 $xP$ 、 $yP$ 和 $zP$ ，判断究竟 $z = xy$ 还是 $z$ 也是随机选取的数

在题目中，如果 $z = xy$ ，则当前的state为1，否则为0

首先一个事实是，如果能够解决DLP问题，那么DDH问题是简单的，因为DLP问题可以解出 $x$ 、 $y$ 和 $z$ ，那么通过对比 $z$ 是否等于 $xy$ 就好了

另一个事实是ECC的DLP问题也是难解的，但对题目的群阶n分解后发现它有个小因子500（注：无论用factorDB还是yafu都可以找到这个小因子），所以这条曲线上就会存在一个阶为500或者500的因子的小阶子群

熟悉Pohlig-Hellman算法的都会知道，在小阶子群上的DLP问题是容易的，因为直接枚举子群上所有的点就好了，那么题目的问题就可以转化为：先在小阶子群中解DLP问题，然后在 $\mathbb{Z}_{n'}$ 中对比是否 $z=xy$ 来解决 $\mathbb{Z}_{n'}$ 中的DDH问题（其中 $n'$ 为500的因子），那么这个 $\mathbb{Z}_{n'}$ 中DDH的解就大概率是原DDH问题的解

理论如此，然后就开干，第一步是先对点 $P$ 、 $xP$ 、 $yP$ 和 $zP$ 都乘上 $\frac{n}{500}$ ，把这几个点都转到小阶子群中

1
2
3

s = n // ns[0]
P, xP, yP, zP = [E1(_) for _ in output[i][:4]]
sp, sxp, syp, szp = [s * _ for _ in (P, xP, yP, zP)]

第二步就是枚举 $\mathbb{Z}_{500}$ ，解子群的DLP

for j in range(ns[0]):  # ns[0] == 500
  if j * sp == sxp:
    x += [j]
  if j * sp == syp:
    y += [j]
  if j * sp == szp:
    z += [j]

在这一步中，可能会出现DLP有多解的情况，其实这是正常的情况，因为这四个点乘上 $\frac{n}{500}$ 后的阶可能并不是500，假设点的阶是100的话，那么 $x$ 、 $x+100$ 、 $x+200$ 、 $x+300$ 和 $x+400$ 都是 $xP$ 的解

于是，为了解决多解的问题，一种方法是先找到这几个点的准确阶 $n'$ ，然后再在 $\mathbb{Z}_{n'}$ 中去解

我用的另一种方法是，把 $\mathbb{Z}_{500}$ 中得到的所有解的z和xy分别存在两个集合中，然后对比两个集合的交集是否为空，如果为空则说明z大概率是随机选择的

具体的参考代码如下：

#!/usr/bin/env sage
p = 176857581480948244867604802349863732783663856225560523858099969581030268141874483416875345636657439749959951621
n = 176857581480948244867604802349863732783663856225560523834310386551077128936406127697123918346523659026470270500
A = 1

m = 100
F1 = GF(p)
F2.<u> = GF(p^2)
E1 = EllipticCurve(F1,[A,0]) 

'''
for k in range(100):
  print(gcd(n, p^k-1))
'''
ns = [500, 158465746173819028262477785344468517, 2232123796482243553563388394642252242447624758532104909445052499370196473]

with open('./output.txt', 'r') as f:
  data = f.read().split('\n')
exec(data[0])
exec('output = %s' % data[1])

st = []
for i in range(len(output)):
  s = n // ns[0]
  P, xP, yP, zP = [E1(_) for _ in output[i][:4]]
  sp, sxp, syp, szp = [s * _ for _ in (P, xP, yP, zP)]
  x = []
  y = []
  z = []
  for j in range(ns[0]):
    if j * sp == sxp:
      x += [j]
    if j * sp == syp:
      y += [j]
    if j * sp == szp:
      z += [j]

  xy = []
  for xi in x:
    for yi in y:
      xy += [Integer(xi * yi % ns[0])]
  xy = list(set(xy))
  s = 1 - Integer(set(xy) & set(z) == set())
  print(s)
  st += [s]
print(st)


'''
[0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0]
'''

如果把以上输出的前100比特拿去解密的话，会发现解出来的是乱码，原因是在以上操作中会出现因群阶太小导致的误差

举个栗子，假设 $\frac{n}{500} P$ 的阶为1，即 $\frac{n}{500} P = 1$ ，那么自然地会有 $\frac{n}{500} xP = 1$ 、 $\frac{n}{500} yP = 1$ 和 $\frac{n}{500} zP = 1$ ，在这种情况下DDH的结果永远是 $z = xy$ ，就造成误差

所以最后还需要对这样的结果进行除杂，除杂的方式是利用前面提到的 $S_0 = unTwist^i(S_i)$ ，即把冗余几组的state先unTwist到 $S_0$ ，然后对比所得到的 $S_0$ 是否相同

注意上面说的误差只会把0误判为1，所以如果在 $S_0$ 某个位置中出现分歧的话，只需要把这个位置置为0即可

参考的除杂与解密代码：

from hashlib import shake_128

c = 'dbc2eddcafdbd5d2dbc1b92cb32b4d6a604950c127a9d77007ee81bf'
c = bytes.fromhex(c)
st = [0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0]

twsit_state = [ 76, 5, 29, 61, 62, 54, 66, 69, 81, 48,
                20, 64, 14, 77, 50, 79, 71, 40, 93, 58,
                59, 19, 31, 63,  2, 96, 35, 18, 85, 56,
                21, 33,  7, 99, 17, 38, 97, 89, 74, 32,
                27, 42,  3, 82, 91, 41, 86,  9, 13, 30,
                11, 87,  1, 88, 26, 67, 25, 75, 94, 45,
                68, 39, 55, 16, 28, 57, 49, 37, 52, 22,
                70, 36,  0,  8, 65, 72, 43, 12, 23, 53,
                51, 60,  4, 46, 83, 90, 84, 92, 24, 15,
                80, 98, 34, 78, 95, 44, 73, 10,  6, 47]
tmp = list(range(100))
uts = [0 for _ in range(100)]
for i in range(100):
    uts[twsit_state[i]] = tmp[i]
st = [st[100*i: 100*(i+1)] for i in range(7)]

def twist(s):
    return [s[twsit_state[i]] for i in range(100)]

def unTwisit(s):
    return [s[uts[i]] for i in range(100)]

#print(twist(unTwisit(st[1])) == st[1])
for i in range(len(st)-1):
    for _ in range(i):
        st[i] = unTwisit(st[i])
    #print(st[i])

s0 = st[0]
for i in range(1, len(st)-1):
    for j in range(100):
        if st[i][j] == 0:
            if s0[j] != 0:
                print(j)
                s0[j] = 0
print(s0)

def encrypt(msg, key):
    y = shake_128("".join(map(str, key)).encode()).digest(len(msg))
    return bytes([msg[i] ^ y[i] for i in range(len(msg))])

flag = encrypt(c, unTwisit(s0))
print(flag)

# b'flag{u_kn0w_curv3.h@v3_fun!}'

Pairing与预期解·

上面的解法肯定是一种非预期的解法，因为题目中还给了点 $Q$ 和 $yQ$ ，而上面的解法根本就没用到这两个点

预期的解法会比非预期的复杂很多，其中用到一种Pairing的方法

Bilinear Pairing·

双线性配对（Bilinear Pairing），一般简称为Pairing，所谓双线性就是它是一种二到一的映射，可以把两个群元映射到一个群中

令 $e$ 是一种Pairing的话，它会满足

$e(P_1 + P_2, Q) = e(P_1, Q) e(P_2, Q) \\ e(P, Q_1 + Q_2) = e(P, Q_1) e(P, Q_2)$

把这个性质扩展一下的话，可以得到

$e(P, xP) = e(P, \sum_{i=1}^x P) = \prod_{i=1}^x e(P, P) = e(P, P)^x$

那么在题目中，我们就可以通过计算

$e(P, zP) = e(P, P)^z \\ e(xP, yP) = e(P, P)^{xy}$

然后对比 $e(P, zP)$ 和 $e(xP, yP)$ 来解DDH问题

但这种解法也没用到 $Q$ 和 $yQ$ 这两个点，所以实际测试中也并没搞出来

另一种更好的方法是，计算

$e(zP, Q) = e(P, Q)^z \\ e(xP, yQ) = e(P, Q)^{xy}$

然后对比 $e(zP, Q)$ 和 $e(xP, yQ)$

Tate Pairing·

Tate Pairing是一种经典的Pairing，先看定义

在题目中其实有很明显的提示说明要使用Tate Pairing

首先从定义中看，如果要使用Tate Pairing，则需要一个因子 $r$ 和一个嵌入度 $k$ ，其中因子 $r$ 是曲线阶（或者说Cardinality，题目中的n）的大于 $\sqrt{p}$ 的素因子，而且 $r$ 同时也是 $p^k-1$ 的因子，其中 $k$ 是满足该性质的最小 $k$

然后由于Tate Pairing映射后的结果落在域 $\mathbb{F}_{p^k}$ 中，所以这个 $k$ 肯定不能太大，不然域 $\mathbb{F}_{p^k}$ 中的运算需要很大的开销

所以一种找到 $k$ 和 $r$ 的方法是，遍历小的 $k$ ，然后找 $\#E_1(\mathbb{F}_p)$ 和 $p^k-1$ 的公因子，如果遍历到某个 $k$ 时出现大的公因子，即说明这个 $k$ 就是满足要求的 $k$ ，而这个公因子中就包含满足要求的 $r$

for i in range(1, 100):
    g = gcd(n, p^i-1)
    if g > sqrt(p):
        print(i, g)
'''
8 44642475929644871071267767892845044848952495170642098188901049987403929460
16 44642475929644871071267767892845044848952495170642098188901049987403929460
... ...
'''

对应题目中的数据，得到 $k = 8$ 时有大的公因子，顺势分解群阶 $n$ 得到（注意 $r$ 是 $n$ 中大于 $\sqrt{p}$ 的素因子）

1
2
3

ns = [500, 158465746173819028262477785344468517, 2232123796482243553563388394642252242447624758532104909445052499370196473]
assert product(ns) == n
r = ns[-1]

到这里已经基本可以确定题目的曲线满足Tate Pairing的要求，如果曲线是随机生成的话其实只有极小的概率会满足这样的要求，所以可以确定这个曲线一定是出题人故意选择的，见下面引文

虽然已经确定了要用Tate Pairing，但如果用对比 $e(P, zP)$ 和 $e(xP, yP)$ 的方法求解的话，会发现结果都是1，就无法求解

而如果用对比 $e(zP, Q)$ 和 $e(xP, yQ)$ 的方法求解的话，也会有问题，因为 $P$ 和 $Q$ 分别是 $E_1$ 和 $E_2$ 这两条不同曲线上的点，而看回Tate Pairing的定义，则需要 $P$ 和 $Q$ 是同一条曲线上的点

Twist与映射·

为了可以用 $P$ 和 $Q$ 做Pairing，一种方法是可以构造一种同态映射，把点 $Q$ 映射到曲线 $E_1$ 上，或者把点 $P$ 映射到曲线 $E_2$ 上

在寻找曲线 $E_1$ 和曲线 $E_2$ 的关系的时候，我发现曲线 $E_2(\mathbb{F}_{p^2})$ 其实是曲线 $E_1(\mathbb{F}_{p^k})$ 的Twist

如果把

$E_1(\mathbb{F}_{p^k}): y^2 = x^3 + x \\ E_2(\mathbb{F}_{p^2}): y^2 = x^3 + ax$

代入上面的公式中，就可以得到以下的同态映射，注意：图中 $E$ 是 $y^2=x^3+ax$ ，而题目中的 $E_1$ 是 $y^2=x^3+x$ ，需要进行转换，且代入题目中是 $k=8$ 、 $d=4$

$\begin{aligned} \psi: E_2(\mathbb{F}_{p^{k/d}}) &\to E_1(\mathbb{F}_{p^k}) \\ (x, y) &\to (a^{-1/2} x, a^{-3/4} y) \end{aligned}$

可以大概验证一下，首先 $(x, y)$ 满足 $y^2 = x^3 + ax$ ，于是等式两边乘上一个 $a^{-3/2}$ 有

$a^{-3/2} y^2 = a^{-3/2} x^3 + a^{-3/2} a x$

稍微整理一下得到

$(a^{-3/4} y)^2 = (a^{-1/2} x)^3 + (a^{-1/2} x) \\$

令 $(x', y') = (a^{-1/2} x, a^{-3/4} y)$ 就是

$y'^2 = x'^3 + x'$

满足曲线 $E_1$

除此之外，映射 $\psi$ 还需要满足同态性，即

$\psi(x P) = x \cdot \psi(P)$

这个我还是用代码验证…

p = 176857581480948244867604802349863732783663856225560523858099969581030268141874483416875345636657439749959951621
n = 176857581480948244867604802349863732783663856225560523834310386551077128936406127697123918346523659026470270500
A = 1

F1 = GF(p)
F2.<u> = GF(p^2)
E1 = EllipticCurve(F1,[A,0]) 

ns = [500, 158465746173819028262477785344468517, 2232123796482243553563388394642252242447624758532104909445052499370196473]
r = ns[-1]
k = 8

Fk.<v> = GF(p^k)
Ek1 = EllipticCurve(Fk,[A,0]) 
phiF_2_k = Hom(F2, Fk)(F2.gen().minpoly().roots(Fk)[0][0])

def sqrt4(a):
  a = sorted(a.sqrt(all=True))[0]
  return sorted(a.sqrt(all=True))[0]

def phiE_2_k1(Q, a):
  try:
    a4 = sqrt4(1/phiF_2_k(a))
  except:
    return None

  x, y = [phiF_2_k(_) for _ in Q.xy()] 
  return Ek1([a4^2*x, a4^3*y])

for i in range(10):
  a = F2.random_element()
  E2 = EllipticCurve(F2, [a, 0]) 
  Q = E2.random_point()

  assert 1997 * phiE_2_k1(Q, a) == phiE_2_k1(1997*Q, a)
  print('Pass: %d' % i)

注意这里 $\psi$ 映射的结果是落在 $\mathbb{F}_{p^k}$ 上，所以这里的 $a^{-1/2}$ 与 $a^{-3/4}$ 都应该是 $\mathbb{F}_{p^k}$ 上的运算，而 $a$ 本来是 $\mathbb{F}_{p^{k/d}}$ 上的元素，所以需要先把 $a$ 映射到 $\mathbb{F}_{p^k}$ 上

注意这里并不能直接强行把 $a$ 转到 $\mathbb{F}_{p^k}$ 上，因为 $\mathbb{F}_{p^{k/d}}$ 和 $\mathbb{F}_{p^k}$ 模的不可约多项式并不一样，我从春乎上直接抄了个映射的构造代码，反正 @春哥也是直接抄SageMath文档的（

1	phiF_2_k = Hom(F2, Fk)(F2.gen().minpoly().roots(Fk)[0][0])

另外还有一个很坑的地方是，本来 $1/a$ 开四次方只需要(1/a).sqrt().sqrt()就好了，但是正常来说这里的开平方应该有两个解，而SageMath的sqrt()函数居然随机地返回这两个解中的一个，于是如果写(1/a).sqrt().sqrt()的话就会导致映射的同态性质不能被保证

所以我的一个修正方法是，使用排序强制开方返回最小的解

1
2
3

def sqrt4(a):
  a = sorted(a.sqrt(all=True))[0]
  return sorted(a.sqrt(all=True))[0]

调库与相同群阶·

赛后 @沛公问 @dbt 拿了份WP，我去偷瞄了一眼，发现其实这个映射还可以直接用SageMath内置的isomorphism_to函数构造，所以代码也可以写成：

Fk.<v> = GF(p^k)
Ek1 = EllipticCurve(Fk,[A,0]) 
phiF_2_k = Hom(F2, Fk)(F2.gen().minpoly().roots(Fk)[0][0])

def phiE_2_k2(Q, Ek2):
  x, y = [phiF_2_k(_) for _ in Q.xy()] 
  return Ek2([x, y])

def phiE_2_k1(Q, a):
  Ek2 = EllipticCurve(Fk, [phiF_2_k(a),0])
  phiE_k2_k1 = Ek2.isomorphism_to(Ek1)
  return phiE_k2_k1(phiE_2_k2(Q, Ek2))

for i in range(10):
  a = F2.random_element()
  E2 = EllipticCurve(F2, [a, 0]) 
  Q = E2.random_point()

  assert 1997 * phiE_2_k1(Q, a) == phiE_2_k1(1997*Q, a)
  print('Pass: %d' % i)

注意，isomorphism_to函数需要映射的原像和像的阶相同，显然 $E_2(\mathbb{F}_{p^2})$ 和 $E_1(\mathbb{F}_{p^k})$ 的群阶不相同，所以不能直接把 $E_2(\mathbb{F}_{p^2})$ 映射到 $E_1(\mathbb{F}_{p^k})$ 中，而需要先把 $E_2(\mathbb{F}_{p^2})$ 映射到 $E_2(\mathbb{F}_{p^k})$ 中，再用isomorphism_to函数把 $E_2(\mathbb{F}_{p^k})$ 映射到 $E_1(\mathbb{F}_{p^k})$

$E_2(\mathbb{F}_{p^2}) \to E_2(\mathbb{F}_{p^k})$ 的方法也不难，直接借助phiF_2_k映射即可

1
2
3

def phiE_2_k2(Q, Ek2):
  x, y = [phiF_2_k(_) for _ in Q.xy()] 
  return Ek2([x, y])

到这里好像一切都理所当然，但有个问题是，为什么 $E_1(\mathbb{F}_{p^k})$ 与 $E_2(\mathbb{F}_{p^k})$ 的群阶相同？

PS：下面是理论部分，可跳过：）

首先肯定和Twist有关，翻了一下曲线和其Twist的阶的关系，发现有

代入d = 4的情况，代码验证一下，注意：

上图是 $q = p^{k/d}$ ，对应到题目中就是 $q = p^2$
只有 $X^4 - 1/a \in \mathbb{F}_{q}$ 不可约的情况才是Twist（图中的 $v$ 是题目中的 $1/a$ ）
$f^2$ 的两个根分别是 $f$ 和 $-f$

p = 176857581480948244867604802349863732783663856225560523858099969581030268141874483416875345636657439749959951621
n = 176857581480948244867604802349863732783663856225560523834310386551077128936406127697123918346523659026470270500
A = 1

q = p^2
F1 = GF(p)
F2.<u> = GF(p^2)
PR2 = PolynomialRing(F2, 'x')
x2 = PR2.gen()

E1 = EllipticCurve(F2, [A, 0]) 
n1 = E1.order()
t = q + 1 - n1

while True:
  a = F2.random_element()
  if not PR2(x2^4-1/a).is_irreducible():
    continue
  break
E2 = EllipticCurve(F2, [a, 0]) 
n2 = E2.order()
f = q + 1 - n2

print(t^2 + f^2 == 4 * q)

但这两个阶明显不等，所以看一下 $\mathbb{F}_{p^k}$ （也即 $\mathbb{F}_{q^d}$ ）的情况

代入求根公式的话，即在 $E_1(\mathbb{F}_{p^k})$ 中，有

$\alpha^k + \beta^k = (\frac{t + \sqrt{t^2 - 4p}}{2})^k + (\frac{t - \sqrt{t^2 - 4p}}{2})^k$

根据 $t$ 和 $f$ 的关系，有

$t^2 + f^2 = 4 p$

即

$\sqrt{t^2 - 4p} = \sqrt{-f^2} = (-1)^{1/2} f$

代回，即

$\begin{aligned} \alpha^k + \beta^k &= (\frac{t + (-1)^{1/2} f}{2})^k + (\frac{t - (-1)^{1/2} f}{2})^k \\ &= \frac{(t + (-1)^{1/2} f)^k + (t - (-1)^{1/2} f)^k}{2^k} \end{aligned}$

二项式定理展开一下，可得

$\begin{aligned} &(t + (-1)^{1/2} f)^k + (t - (-1)^{1/2} f)^k \\ =& \sum_{i=0}^{k} C_k^i \cdot t^{k-i} \cdot ((-1)^{1/2} f)^i + \sum_{i=0}^{k} C_k^i \cdot t^{k-i} \cdot (-(-1)^{1/2} f)^i \\ =& \sum_{i=0}^{k} C_k^i \cdot t^{k-i} \cdot [((-1)^{1/2} f)^i + (-(-1)^{1/2} f)^i] \\ =& \sum_{i=0}^{k} C_k^i \cdot t^{k-i} \cdot f^i \cdot (-1)^{i/2} \cdot [(1)^i + (-1)^i] \\ =& \sum_{i=0}^{k} (-1)^{i/2} \cdot C_k^i \cdot t^{k-i} \cdot f^i \cdot [1 + (-1)^i] \\ \end{aligned}$

到这里可以分奇偶两种情况

$\begin{cases} 1 + (-1)^i = 0 \ ,\ i \text{ is odd} \\ 1 + (-1)^i = 2 \ ,\ i \text{ is even} \end{cases}$

于是去掉奇数的情况就是

$\begin{aligned} &\sum_{i=0}^{k} (-1)^{i/2} \cdot C_k^i \cdot t^{k-i} \cdot f^i \cdot [1 + (-1)^i] \\ =& 2 \sum_{i=0}^{\lfloor k/2 \rfloor} (-1)^{i} \cdot C_k^{2i} \cdot t^{k-2i} \cdot f^{2i} \\ =& 2 t^k \sum_{i=0}^{\lfloor k/2 \rfloor} (-1)^{i} \cdot C_k^{2i} \cdot (f^2/t^2)^i \\ \end{aligned}$

怼个代码验证一下

def getOrder(t, p, k=1):
  f2 = 4*p - t^2
  ab =  2 * t^k * sum([
            (-1)^(i) * binomial(k, 2*i) * (f2/t^2)^i
          for i in range(k//2+1)])
  return p^k + 1 - Integer(ab/(2^k))

for d in range(1, 10):
  k = 2 * d
  Fk.<v> = GF(p^k)
  phiF_2_k = Hom(F2, Fk)(F2.gen().minpoly().roots(Fk)[0][0])

  E1 = EllipticCurve(Fk, [A, 0]) 
  n1 = E1.order()
  E2 = EllipticCurve(Fk, [phiF_2_k(a), 0]) 
  n2 = E2.order()

  assert n1 == getOrder(t, q, d)
  assert n2 == getOrder(f, q, d)

print('Passed!')

再来看 $E_2(\mathbb{F}_{p^k})$ ，因为是Twist，所以有

$\#E_2(\mathbb{F}_{p}) = p + 1 - (\pm f)$

结合

$t^2 + f^2 = 4 p$

也就是上面推出来的结果中，把 $t$ 换成 $(\pm f)$ ，把 $f^2$ 换成 $t^2$ 就好了，即

$\alpha^k + \beta^k = 2 (\pm f)^k \sum_{i=0}^{\lfloor k/2 \rfloor} (-1)^{i} \cdot C_k^{2i} \cdot (t^2/f^2)^i$

回到题目中，由于 $a \in \mathbb{F}_{q} = \mathbb{F}_{p^2}$ ，所以应该把上式的 $p$ 换成 $q = p^2$ ，且 $k$ 换成 $d = k/2$

把这些替换完成后，即要证明的是（由于式子已经和 $p$ 无关，所以换 $k$ 就好了）

$2 t^d \sum_{i=0}^{\lfloor d/2 \rfloor} (-1)^{i} \cdot C_d^{2i} \cdot (f^2/t^2)^i = 2 (\pm f)^d \sum_{i=0}^{\lfloor d/2 \rfloor} (-1)^{i} \cdot C_d^{2i} \cdot (t^2/f^2)^i$

消去 $2$ 后，等号左右相减得

$\begin{aligned} &t^d \sum_{i=0}^{\lfloor d/2 \rfloor} (-1)^{i} \cdot C_d^{2i} \cdot (f^2/t^2)^i - (\pm f)^d \sum_{i=0}^{\lfloor d/2 \rfloor} (-1)^{i} \cdot C_d^{2i} \cdot (t^2/f^2)^i \\ =& \sum_{i=0}^{\lfloor d/2 \rfloor} (-1)^{i} \cdot C_d^{2i} \cdot [t^d (f^2/t^2)^i - (\pm f)^d (t^2/f^2)^i] \\ =& \sum_{i=0}^{\lfloor d/2 \rfloor} (-1)^{i} \cdot C_d^{2i} \cdot (t^{d-2i} f^{2i} - t^{2i} (\pm f)^{d-2i}) \end{aligned}$

如果 $d$ 是奇数的话，这个式子没什么特别的，也很难证是否相等

但如果 $d$ 是偶数的话就有点意思了，因为这个时候根据组合的性质会有

$C_{d}^{2i} = C_{d}^{d-2i} \\$

而且在 $2i = d/2$ 时（假设有这一项，因为需要 $d$ 能够整除 $4$ ）

$t^{d-2i} f^{2i} - t^{2i} (\pm f)^{d-2i} = t^{d/2} f^{d/2} - t^{d/2} f^{d/2} = 0$

于是处于中间的 $C_{d}^{d/2}$ 的项可以被消去

综合可得，如果 $d$ 是偶数的话，式子可以继续化简为

$\begin{aligned} & \sum_{i=0}^{\lfloor d/2 \rfloor} (-1)^{i} \cdot C_d^{2i} \cdot (t^{d-2i} f^{2i} - t^{2i} (\pm f)^{d-2i}) \\ =& \sum_{i=0}^{\lfloor d/4 \rfloor} (-1)^{i} \cdot C_d^{2i} \cdot (t^{d-2i} f^{2i} - t^{2i} f^{d-2i}) \\ &+ \sum_{i=0}^{\lfloor d/4 \rfloor} (-1)^{d/2-i} \cdot C_d^{d-2i} \cdot (t^{2i} f^{d-2i} - t^{d-2i} f^{2i}) \end{aligned}$

到这里可以发现有个两两抵消的关系

$(t^{d-2i} f^{2i} - t^{2i} f^{d-2i}) + (t^{2i} f^{d-2i} - t^{d-2i} f^{2i}) = 0$

所以如果 $(-1)^{i}$ 和 $(-1)^{d/2-i}$ 相等的话，利用这个抵消关系即可得到结果为 $0$

而要这两个东西相等，即要 $i$ 与 $d/2 - i$ 的奇偶性相同，也即

$i \equiv d/2 - i \pmod 2$

进而推出

$d/2 \equiv 2i \equiv 0 \pmod 2$

也即 $d/2$ 要是个偶数才满足情况，或者说 $d$ 要能被 $4$ 整除，即

$d \equiv 0 \pmod 4$

所以综合上面的结果可得，如果 $d \equiv 0 \pmod 4$ 的话，有

$\begin{aligned} &(\alpha_1^d + \beta_1^d) - (\alpha_2^d + \beta_2^d) \\ =& \sum_{i=0}^{\lfloor d/4 \rfloor} (-1)^{i} \cdot C_d^{2i} \cdot [(t^{d-2i} f^{2i} - t^{2i} f^{d-2i}) + (t^{2i} f^{d-2i} - t^{d-2i} f^{2i})] \\ =& \sum_{i=0}^{\lfloor d/4 \rfloor} (-1)^{i} \cdot C_d^{2i} \cdot (t^{d-2i} f^{2i} - t^{d-2i} f^{2i} + t^{2i} f^{d-2i} - t^{2i} f^{d-2i}) \\ =& \sum_{i=0}^{\lfloor d/4 \rfloor} (-1)^{i} \cdot C_d^{2i} \cdot 0 \\ =& 0 \end{aligned}$

回到题目中可以发现，题目中恰好就是 $d = 4$ 的情况，所以有

$\alpha_1^d + \beta_1^d = \alpha_2^d + \beta_2^d$

而

$\#E_1(\mathbb{F}_{p^k}) = q^d + 1 - (\alpha_1^d + \beta_1^d) \\ \#E_2(\mathbb{F}_{p^k}) = q^d + 1 - (\alpha_2^d + \beta_2^d)$

所以可得 $E_1(\mathbb{F}_{p^k})$ 和 $E_2(\mathbb{F}_{p^k})$ 的阶相等

最终EXP1·

现在映射已经构造完成了，所以题目中最难的一步已经解决了

剩下的思路是，

利用同态映射把点 $Q$ 和 $yQ$ 都映射到 $E_1(\mathbb{F}_{p^k})$ 上
把点 $xP$ 和 $zP$ 都映射到 $E_1(\mathbb{F}_{p^k})$ 上，这一步是简单的，直接映射就好了
计算Tate Pairing $e(zP, Q)$ 和 $e(xP, yQ)$ ，并对比是否相同，如果相同的话则这个state记为1，否则记为0
对615组数据做以上操作

参考代码（PS：测试了一下，如果在Sage10以上版本运行的话会快很多）

#!/uer/bin/env sage
p = 176857581480948244867604802349863732783663856225560523858099969581030268141874483416875345636657439749959951621
n = 176857581480948244867604802349863732783663856225560523834310386551077128936406127697123918346523659026470270500
A = 1

m = 100
F1 = GF(p)
E1 = EllipticCurve(F1,[A,0]) 
F2.<u> = GF(p^2)
PR2 = PolynomialRing(F2, 'x')
x2 = PR2.gen()

'''
for k in range(100):
  print(gcd(n, p^k-1))
'''
ns = [500, 158465746173819028262477785344468517, 2232123796482243553563388394642252242447624758532104909445052499370196473]
r = ns[-1]
ndr = n // r

for k in range(1, 100):
  if (p^k-1) % r == 0:
    break
print('r = %d' % r)
print('k = %d' % k)

with open('./output.txt', 'r') as f:
  data = f.read().split('\n')
exec(data[0])
exec('output = %s' % data[1])

Fk.<v> = GF(p^k)
Ek1 = EllipticCurve(Fk,[A,0]) 
phiF_2_k = Hom(F2, Fk)(F2.gen().minpoly().roots(Fk)[0][0])

def phiE_2_k2(Q, Ek2):
  x, y = [phiF_2_k(_) for _ in Q.xy()] 
  return Ek2([x, y])

def sqrt4(a):
  a = sorted(a.sqrt(all=True))[0]
  return sorted(a.sqrt(all=True))[0]

def phiE_k2_k1(Q, a):
  try:
    a4 = sqrt4(1/phiF_2_k(a))
  except:
    return None

  x, y = Q.xy()
  return Ek1([a4^2*x, a4^3*y])


st = []
for i in range(len(output)):
  x, y = output[i][4]
  a = (y^2 - x^3) * x^(-1)

  E2 = EllipticCurve(F2, [a, 0])
  Ek2 = EllipticCurve(Fk, [phiF_2_k(a),0])
  Q, yQ = [E2(_) for _ in output[i][4:]]
  P, xP, yP, zP = [E1(_) for _ in output[i][:4]]

  Q, yQ = [phiE_2_k2(_, Ek2) for _ in (Q, yQ)]
  Q, yQ = [phiE_k2_k1(_, a) for _ in (Q, yQ)]
  P, xP, yP, zP = [Ek1(_) for _ in (P, xP, yP, zP)]
  P, xP, yP, zP = [ndr * _ for _ in (P, xP, yP, zP)]

  ez = zP.tate_pairing(Q, r, k)
  exy = xP.tate_pairing(yQ, r, k)
  if ez == 1 and exy == 1:
    st += [None]
  elif ez == exy:
    st += [1]
  else:
    st += [0]

  # Twist and Tate
  checker = PR2(x2^4-1/a).is_irreducible() and E2.order() % r == 0
  print('%d\t%s\t%s' % (i, st[-1], checker))

print(st)
  

'''
Sage10 -> faster
[None, None, None, None, None, None, None, 1, 1, 0, None, None, 1, None, None, None, None, None, None, None, 0, 0, 1, None, 1, None, 0, 0, 1, 1, None, None, None, 1, None, 0, None, None, 1, None, 0, None, 1, None, None, None, None, None, None, 0, None, None, None, None, None, 1, None, 1, None, None, None, None, None, None, None, None, None, None, 0, 0, None, None, None, None, None, 0, 0, 1, None, None, None, None, None, None, None, None, None, None, None, None, None, 0, 1, None, None, None, None, None, None, None, None, None, None, None, None, None, 0, 0, None, 1, None, 0, None, None, None, 0, None, None, None, None, 1, None, None, None, None, None, None, None, None, None, None, 1, 1, None, 0, None, None, 1, 0, None, None, 1, None, None, None, 0, 0, 0, 0, 0, None, None, 1, 0, None, 1, 1, None, 1, None, None, None, None, None, 1, 1, None, 0, None, 1, None, None, None, 1, None, 0, None, None, None, None, None, None, None, None, 0, 0, None, None, None, 1, 1, 0, None, None, None, 1, None, None, None, None, 1, None, None, None, None, None, None, None, None, 0, 1, None, None, None, 1, None, None, 0, 0, None, None, 1, 1, None, 1, None, 1, None, None, None, None, None, None, 1, None, None, 0, None, None, None, None, None, None, None, None, None, None, None, 1, None, None, None, None, None, None, None, None, None, 0, 0, None, None, 1, None, None, None, 0, 1, None, None, None, None, None, None, 1, 0, None, None, 0, None, 1, None, 0, None, None, None, None, None, 1, None, None, None, None, None, None, None, None, None, None, 0, None, None, 1, None, None, None, None, None, None, 1, None, None, None, None, None, 0, None, 0, 1, None, 0, None, 1, None, None, 1, 0, None, None, None, None, None, None, None, None, None, 0, None, None, None, 0, None, None, None, None, None, None, None, None, None, None, None, None, None, 1, None, None, 0, None, None, None, None, None, 0, None, None, None, None, None, 1, 0, None, None, None, None, None, 1, None, None, None, 1, None, None, None, None, 1, None, 0, None, 1, 1, 0, None, None, None, 0, None, None, None, None, None, 0, None, None, None, None, None, None, None, None, 0, None, None, None, 1, None, None, 0, None, None, None, None, None, 0, None, None, None, None, 1, None, 1, None, None, 1, None, None, 1, None, None, None, 0, 0, 1, None, None, 1, None, None, 1, 1, 0, None, None, None, None, None, None, 0, None, None, None, 0, None, None, None, None, None, None, 0, None, None, None, 1, None, None, None, None, None, None, None, None, 1, None, None, None, None, 0, None, 0, None, 1, 0, None, None, None, 1, None, 1, None, None, None, 1, None, 0, None, None, None, None, None, None, 1, None, None, 1, None, None, 0, None, None, None, None, 1, 0, None, None, None, None, 0, None, None, None, None, 1, None, 0, 0, None, None, None, None, None, 1, None, None, None, None, 0, 1, 1, None, None, None, 0, None, None, 0, None, None, 0, None, None, None, None, None, None, 0, 1, 1, None, None, None, None, None, None, None, None, None, None, None, 1, None, None, None, None, None, None, None, None, None, None, None, 0, None, None, None, None, 0, None, 0, 1, 1, None, None, None, None, None, 1, 1, None, None, None, None, None, 0, None]
'''

运行完后发现有很多的state都无法做non-trivial 的Tate Pairing，但没关系，把能做的state拿去做unTwist，发现前100个state中只有16个比特是未知的，所以爆破未知比特即可

参考代码2：

from hashlib import shake_128

c = 'dbc2eddcafdbd5d2dbc1b92cb32b4d6a604950c127a9d77007ee81bf'
c = bytes.fromhex(c)
st = [None, None, None, None, None, None, None, 1, 1, 0, None, None, 1, None, None, None, None, None, None, None, 0, 0, 1, None, 1, None, 0, 0, 1, 1, None, None, None, 1, None, 0, None, None, 1, None, 0, None, 1, None, None, None, None, None, None, 0, None, None, None, None, None, 1, None, 1, None, None, None, None, None, None, None, None, None, None, 0, 0, None, None, None, None, None, 0, 0, 1, None, None, None, None, None, None, None, None, None, None, None, None, None, 0, 1, None, None, None, None, None, None, None, None, None, None, None, None, None, 0, 0, None, 1, None, 0, None, None, None, 0, None, None, None, None, 1, None, None, None, None, None, None, None, None, None, None, 1, 1, None, 0, None, None, 1, 0, None, None, 1, None, None, None, 0, 0, 0, 0, 0, None, None, 1, 0, None, 1, 1, None, 1, None, None, None, None, None, 1, 1, None, 0, None, 1, None, None, None, 1, None, 0, None, None, None, None, None, None, None, None, 0, 0, None, None, None, 1, 1, 0, None, None, None, 1, None, None, None, None, 1, None, None, None, None, None, None, None, None, 0, 1, None, None, None, 1, None, None, 0, 0, None, None, 1, 1, None, 1, None, 1, None, None, None, None, None, None, 1, None, None, 0, None, None, None, None, None, None, None, None, None, None, None, 1, None, None, None, None, None, None, None, None, None, 0, 0, None, None, 1, None, None, None, 0, 1, None, None, None, None, None, None, 1, 0, None, None, 0, None, 1, None, 0, None, None, None, None, None, 1, None, None, None, None, None, None, None, None, None, None, 0, None, None, 1, None, None, None, None, None, None, 1, None, None, None, None, None, 0, None, 0, 1, None, 0, None, 1, None, None, 1, 0, None, None, None, None, None, None, None, None, None, 0, None, None, None, 0, None, None, None, None, None, None, None, None, None, None, None, None, None, 1, None, None, 0, None, None, None, None, None, 0, None, None, None, None, None, 1, 0, None, None, None, None, None, 1, None, None, None, 1, None, None, None, None, 1, None, 0, None, 1, 1, 0, None, None, None, 0, None, None, None, None, None, 0, None, None, None, None, None, None, None, None, 0, None, None, None, 1, None, None, 0, None, None, None, None, None, 0, None, None, None, None, 1, None, 1, None, None, 1, None, None, 1, None, None, None, 0, 0, 1, None, None, 1, None, None, 1, 1, 0, None, None, None, None, None, None, 0, None, None, None, 0, None, None, None, None, None, None, 0, None, None, None, 1, None, None, None, None, None, None, None, None, 1, None, None, None, None, 0, None, 0, None, 1, 0, None, None, None, 1, None, 1, None, None, None, 1, None, 0, None, None, None, None, None, None, 1, None, None, 1, None, None, 0, None, None, None, None, 1, 0, None, None, None, None, 0, None, None, None, None, 1, None, 0, 0, None, None, None, None, None, 1, None, None, None, None, 0, 1, 1, None, None, None, 0, None, None, 0, None, None, 0, None, None, None, None, None, None, 0, 1, 1, None, None, None, None, None, None, None, None, None, None, None, 1, None, None, None, None, None, None, None, None, None, None, None, 0, None, None, None, None, 0, None, 0, 1, 1, None, None, None, None, None, 1, 1, None, None, None, None, None, 0, None]

twsit_state = [ 76, 5, 29, 61, 62, 54, 66, 69, 81, 48,
                20, 64, 14, 77, 50, 79, 71, 40, 93, 58,
                59, 19, 31, 63,  2, 96, 35, 18, 85, 56,
                21, 33,  7, 99, 17, 38, 97, 89, 74, 32,
                27, 42,  3, 82, 91, 41, 86,  9, 13, 30,
                11, 87,  1, 88, 26, 67, 25, 75, 94, 45,
                68, 39, 55, 16, 28, 57, 49, 37, 52, 22,
                70, 36,  0,  8, 65, 72, 43, 12, 23, 53,
                51, 60,  4, 46, 83, 90, 84, 92, 24, 15,
                80, 98, 34, 78, 95, 44, 73, 10,  6, 47]
tmp = list(range(100))
uts = [0 for _ in range(100)]
for i in range(100):
    uts[twsit_state[i]] = tmp[i]
st = [st[100*i: 100*(i+1)] for i in range(7)]

def twist(s):
    return [s[twsit_state[i]] for i in range(100)]

def unTwisit(s):
    return [s[uts[i]] for i in range(100)]

#print(twist(unTwisit(st[1])) == st[1])
st[-1] += [None] * (100 - len(st[-1]))
for i in range(len(st)):
    for _ in range(i):
        st[i] = unTwisit(st[i])
    #print(st[i])

st2 = []
for i in range(100):
    st2 += [set([st[_][i] for _ in range(7)])]
    try:
        st2[-1].remove(None)
        st2[-1] = sorted(list(st2[-1]))
    except:
        pass
print(st2)
s0 = [6 if _==[] else _[0] for _ in st2]
s0 = unTwisit(s0)
print(s0)

key = ''.join(map(str, s0))
n = key.count('6')
key = key.replace('6', '%d')
print(key)
print(n)

import itertools
from tqdm import tqdm

for xxx in tqdm(itertools.product((0, 1), repeat=n), total=2^n):
    k = key % xxx
    y = shake_128(k.encode()).digest(len(c))
    flag = bytes([c[i] ^ y[i] for i in range(len(c))])
    if b'flag' in flag:
        print(k)
        print(flag)

'''
0111110111111111010000000000010101100101010001010011000011101111101101000011000101100111100110111001
b'flag{u_kn0w_curv3.h@v3_fun!}'
'''

最终EXP2·

上面也说了，映射也可以调isomorphism_to实现，所以给出另一个版本的参考代码：

#!/uer/bin/env sage
p = 176857581480948244867604802349863732783663856225560523858099969581030268141874483416875345636657439749959951621
n = 176857581480948244867604802349863732783663856225560523834310386551077128936406127697123918346523659026470270500
A = 1

m = 100
F1 = GF(p)
E1 = EllipticCurve(F1,[A,0]) 
F2.<u> = GF(p^2)
PR2 = PolynomialRing(F2, 'x')
x2 = PR2.gen()
'''
for k in range(100):
  print(gcd(n, p^k-1))
'''
ns = [500, 158465746173819028262477785344468517, 2232123796482243553563388394642252242447624758532104909445052499370196473]
r = ns[-1]
ndr = n // r

for k in range(1, 100):
  if (p^k-1) % r == 0:
    break
print('r = %d' % r)
print('k = %d' % k)

with open('./output.txt', 'r') as f:
  data = f.read().split('\n')
exec(data[0])
exec('output = %s' % data[1])

Fk.<v> = GF(p^k)
Ek1 = EllipticCurve(Fk,[A,0]) 
phiF_2_k = Hom(F2, Fk)(F2.gen().minpoly().roots(Fk)[0][0])

def phiE_2_k2(Q, Ek2):
  x, y = [phiF_2_k(_) for _ in Q.xy()] 
  return Ek2([x, y])

st = []
for i in range(len(output)):
  x, y = output[i][4]
  a = (y^2 - x^3) * x^(-1)

  E2 = EllipticCurve(F2, [a, 0])
  Q, yQ = [E2(_) for _ in output[i][4:]]
  P, xP, yP, zP = [E1(_) for _ in output[i][:4]]

  Ek2 = EllipticCurve(Fk, [phiF_2_k(a),0])
  phiE_k2_k1 = Ek2.isomorphism_to(Ek1)

  Q, yQ = [phiE_2_k2(_, Ek2) for _ in (Q, yQ)]
  Q, yQ = [phiE_k2_k1(_) for _ in (Q, yQ)]
  P, xP, yP, zP = [Ek1(_) for _ in (P, xP, yP, zP)]
  P, xP, yP, zP = [ndr * _ for _ in (P, xP, yP, zP)]

  ez = zP.tate_pairing(Q, r, k)
  exy = xP.tate_pairing(yQ, r, k)
  if ez == 1 and exy == 1:
    st += [None]
  elif ez == exy:
    st += [1]
  else:
    st += [0]

  # Twist and Tate
  checker = PR2(x2^4-1/a).is_irreducible() and E2.order() % r == 0
  print('%d\t%s\t%s' % (i, st[-1], checker))

print(st)
  

'''
Sage10 -> faster
[None, None, None, None, None, None, None, 1, 1, 0, None, None, 1, None, None, None, None, None, None, None, 0, 0, 1, None, 1, None, 0, 0, 1, 1, None, None, None, 1, None, 0, None, None, 1, None, 0, None, 1, None, None, None, None, None, None, 0, None, None, None, None, None, 1, None, 1, None, None, None, None, None, None, None, None, None, None, 0, 0, None, None, None, None, None, 0, 0, 1, None, None, None, None, None, None, None, None, None, None, None, None, None, 0, 1, None, None, None, None, None, None, None, None, None, None, None, None, None, 0, 0, None, 1, None, 0, None, None, None, 0, None, None, None, None, 1, None, None, None, None, None, None, None, None, None, None, 1, 1, None, 0, None, None, 1, 0, None, None, 1, None, None, None, 0, 0, 0, 0, 0, None, None, 1, 0, None, 1, 1, None, 1, None, None, None, None, None, 1, 1, None, 0, None, 1, None, None, None, 1, None, 0, None, None, None, None, None, None, None, None, 0, 0, None, None, None, 1, 1, 0, None, None, None, 1, None, None, None, None, 1, None, None, None, None, None, None, None, None, 0, 1, None, None, None, 1, None, None, 0, 0, None, None, 1, 1, None, 1, None, 1, None, None, None, None, None, None, 1, None, None, 0, None, None, None, None, None, None, None, None, None, None, None, 1, None, None, None, None, None, None, None, None, None, 0, 0, None, None, 1, None, None, None, 0, 1, None, None, None, None, None, None, 1, 0, None, None, 0, None, 1, None, 0, None, None, None, None, None, 1, None, None, None, None, None, None, None, None, None, None, 0, None, None, 1, None, None, None, None, None, None, 1, None, None, None, None, None, 0, None, 0, 1, None, 0, None, 1, None, None, 1, 0, None, None, None, None, None, None, None, None, None, 0, None, None, None, 0, None, None, None, None, None, None, None, None, None, None, None, None, None, 1, None, None, 0, None, None, None, None, None, 0, None, None, None, None, None, 1, 0, None, None, None, None, None, 1, None, None, None, 1, None, None, None, None, 1, None, 0, None, 1, 1, 0, None, None, None, 0, None, None, None, None, None, 0, None, None, None, None, None, None, None, None, 0, None, None, None, 1, None, None, 0, None, None, None, None, None, 0, None, None, None, None, 1, None, 1, None, None, 1, None, None, 1, None, None, None, 0, 0, 1, None, None, 1, None, None, 1, 1, 0, None, None, None, None, None, None, 0, None, None, None, 0, None, None, None, None, None, None, 0, None, None, None, 1, None, None, None, None, None, None, None, None, 1, None, None, None, None, 0, None, 0, None, 1, 0, None, None, None, 1, None, 1, None, None, None, 1, None, 0, None, None, None, None, None, None, 1, None, None, 1, None, None, 0, None, None, None, None, 1, 0, None, None, None, None, 0, None, None, None, None, 1, None, 0, 0, None, None, None, None, None, 1, None, None, None, None, 0, 1, 1, None, None, None, 0, None, None, 0, None, None, 0, None, None, None, None, None, None, 0, 1, 1, None, None, None, None, None, None, None, None, None, None, None, 1, None, None, None, None, None, None, None, None, None, None, None, 0, None, None, None, None, 0, None, 0, 1, 1, None, None, None, None, None, 1, 1, None, None, None, None, None, 0, None]
'''

另外，关于为什么会出现不能做Tate Pairing的原因，也稍微研究了一下

首先一个是，如果要能做同态映射的话，就需要 $E_2$ 是 $E_1$ 的Twist，上面的引文中其实有说到，就需要 $X^4 - v \in \mathbb{F}_{p^{k/4}}$ 不可约，对应到题目中即 $X^4 - 1/a \in \mathbb{F}_{p^{2}}$ 不可约

这个其实可以跟二次剩余类比，差不多就是 $1/a$ 是非二次剩余，而且扩域开方后依然是非二次剩余，于是如果要把 $1/a$ 开四次方的话，就要把域扩到 $\mathbb{F}_{p^{8}}$ 上

个人感觉这样做是为了让点 $Q$ 映射后与点 $P$ 无关，有点像Distortion Maps的感觉

然后另一个原因是需要 $r\ |\ \#E_2(\mathbb{F}_{p^2})$ ，盲猜这个点 $Q$ 的选取有关，可能需要能够把 $Q$ 弄到 $r$ 阶的子群中？

关于这两点，可以结合代码中的

1	checker = PR2(x2^4-1/a).is_irreducible() and E2.order() % r == 0

反正我自己测试是要符合这两点的才有解

外传与Distortion Maps·

在查资料的时候，我还发现了另一种偷鸡方法

大概意思是，如果 $e(P, P) = 1$ ，可以搞一个Distortion Maps $\phi$ ，把 $P$ 映射到 $\phi(P)$ ，然后 $P$ 和 $\phi(P)$ 就不再相关，于是就有 $e(P, P) \ne 1$

继续搜索下去，发现针对曲线 $y^2 = x^3 + x$ ，有这样的一种Distortion Maps

不过这样的映射需要 $p \equiv 3 \pmod 4$ ，因为它需要在 $\mathbb{F}_p$ 中的 $(-1)$ 为非二次剩余

这样把 $(-1)$ 开方后， $\alpha$ 就会扩域到 $\mathbb{F}_{p^2}$ 中，而这样也会把 $\phi(P)$ 中的 $y$ 坐标扩到 $\mathbb{F}_{p^2}$ ，最终就可以使得 $P$ 与 $\phi(P)$ 不相关

不过我也不知道这样说对不对，可以参考一下这个Map的另一个引文

附一下测试代码：

p = 177777779
assert p % 4 == 3

F1 = GF(p)
F2.<u> = GF(p^2)
E1 = EllipticCurve(F1, [1, 0])
E2 = EllipticCurve(F2, [1, 0])
phiF_1_2 = Hom(F1, F2)(F1.gen().minpoly().roots(F2)[0][0])

def phiE_1_2(P):
  x, y = [phiF_1_2(_) for _ in P.xy()] 
  return E2([x, y])


P = E1.random_point()
print(P.weil_pairing(P, P.order()))

def phi1(P):
  x, y = P.xy() 
  try:
    alpha = sorted(F2(-1).sqrt(all=True))[0]
  except:
    return None
  
  return E2([-x, alpha * y])

def e(P, Q):
  return phiE_1_2(P).weil_pairing(phi1(Q), P.order())

print(e(P, 1997*P))
print(e(P, P)^1997)

不过因为题目中的 $p$ 是 $p \equiv 1 \pmod 4$ ，所以就偷鸡失败了

挖坑与Miller算法·

最后，我还是搞不懂具体在什么情况下Pairing的结果才会是 $1$ ，所以就挖个坑了

参考这里的话，好像只需要研究Tate Pairing就好了，因为如果Tate为 $1$ 的话那么Weil和Ate好像都是1

然后从数据上看的话，如果

1	xP._miller_(yP, r)^(p-1) == 1

或

1	P._miller_(Q, r)^(p^2-1) == 1

的话，Pairing的结果就是 $1$ ，因为Tate Pairing的结果是

1	P._miller_(Q, r)^((p^k-1) / r)

而p - 1和p^2 - 1都是p^k - 1的因子

不过至于为什么这两种情况会出现，我就不知道了

估计得什么时候有空深入一下Rational Function和Miller’s Algorithm才能知道了

总结·

哎，dbt！

参考文献·

Silverman J H, Pipher J, Hoffstein J. An introduction to mathematical cryptography[M]. Springer New York, 2014.
Guide to pairing-based cryptography[M]. CRC Press, 2017.
Miret J M, Sadornil D, Tena J. Elliptic curves with j= 0, 1728 and low embedding degree[J]. International Journal of Computer Mathematics, 2016, 93(12): 2042-2053.