我又来蹭流量了（x
原文链接：https://tover.xyz/p/Cu2ve-Pairing/
下面是正文

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

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

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

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

Cu2ve

首先看题目：https://tover.xyz/p/Cu2ve-Pairing/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}，把这几个点都转到小阶子群中

  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}的素因子）

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文档的（

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()的话就会导致映射的同态性质不能被保证

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

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映射即可

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阶的子群中？

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

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

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

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

或

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

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

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.