我又来蹭流量了（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.