躲猫猫 | 糖醋小鸡块的blog

作为 @yolbby 师傅的忠实读者，上学期偶然发现他给他们学校CBCTF的招新赛出了一套躲猫猫题目，所以当然不能错过。

这一系列题目一共分为四个小题，每个题又分为三个小问题，每个小问题也很整齐，都是对flag逐bit的某种decision。难度总体来说是递增的，涉及的东西很广，在研究这几个题目的过程中接触到了相当多新奇有趣的东西，也收获了不少。有些题目上学期就开始研究了，现在再看可能会有一些新的思路，我会一并写上来记录这个过程。

每个题目的输出文件都较长所以不放在这里，完整的题目附件可以在这里找到：

2023-CBCTF/Crypto at main · 0RAYS/2023-CBCTF (github.com)

躲猫猫1

题目描述：

跨年夜当然少不了团建活动！

冬天雪花飘飘正适合玩躲猫猫，为配合赛博主题，0RAYS的每个队员身上都带着一小段flag，拼起来就可以兑换过年大礼包！你毛遂自荐作为抓捕者，于是队员们悄眯眯地藏起来了。

夜晚静悄悄的，你数完数踏出起点，影影绰绰看到几个人影……

题目：

import random
from Crypto.Util.number import *
from secret import flag

humble_part, Ech0_part, Z3r0_part = flag[:len(flag)//3],flag[len(flag)//3:2*len(flag)//3],flag[2*len(flag)//3:]

#学活广场 humb1e似乎在旗杆背后探头探脑
secret = bin(bytes_to_long(humble_part))[2:]
R.<humb1e> = PolynomialRing(GF(getPrime(50)))
R = R.quo(humb1e^30+random.randint(1,2^49)*humb1e+1)
look_for_humb1e = [R(humb1e ^ (1500*random.choice([ord('h'),ord('u'),ord('m'),ord('b'),ord('1'),ord('e')]))) if i == '1' else R.random_element() for i in secret]

#都放假了四教还亮着灯？抓到Ech0在躲猫猫的时候偷学密码！
secret = bin(bytes_to_long(Ech0_part))[2:]
look_for_Ech0 = [prod([j[0]^(j[1]-1)*(j[0]-1) for j in factor(random.getrandbits(100))]) if i == '1' else getPrime(100)-1 for i in secret]

#雪下得好大，花圃周围的亮白色身影是Z3r0吗
secret = bin(bytes_to_long(Z3r0_part))[2:]
p = getPrime(512)
look_for_Z3r0 = [pow(31137,65537,p*getPrime(512)) if i == '1' else pow(31137,65537,getPrime(512)*getPrime(512)) for i in secret]

print(look_for_humb1e)
print(look_for_Ech0)
print(look_for_Z3r0)

1.1

题目：

#学活广场 humb1e似乎在旗杆背后探头探脑
secret = bin(bytes_to_long(humble_part))[2:]
R.<humb1e> = PolynomialRing(GF(getPrime(50)))
R = R.quo(humb1e^30+random.randint(1,2^49)*humb1e+1)
look_for_humb1e = [R(humb1e ^ (1500*random.choice([ord('h'),ord('u'),ord('m'),ord('b'),ord('1'),ord('e')]))) if i == '1' else R.random_element() for i in secret]

对于这个小问，先定义了一个商环R，在这个商环下要做的decision是：

1 : $R(x^{1500\alpha})$

0 : $R(f(x))$

其中，$\alpha$是”humb1e”其中一个字符的ascii码，而f(x)则是R里完全随机的多项式。可以看出flag当前bit为0是，其实是在六个多项式里随机选择，所以大概率会重复出现；而1则很难重复出现，因此可以作出判断。

exp：

from Crypto.Util.number import *

#part1
flag = ""
R.<humb1ebar> = PolynomialRing(ZZ)
with open(r"/home/tiffany/Desktop/ctf/duomaomao/duomaomao1/here humb1e is.txt","r") as f:
    c = eval(f.read())
for i in range(len(c)):
    if(c.count(c[i]) != 1):
        flag += "1"
    else:
        flag += "0"
print(long_to_bytes(int(flag,2)))

#CBCTF{H4ppy_N3wyear

1.2

题目：

1
2
3

#都放假了四教还亮着灯？抓到Ech0在躲猫猫的时候偷学密码！
secret = bin(bytes_to_long(Ech0_part))[2:]
look_for_Ech0 = [prod([j[0]^(j[1]-1)*(j[0]-1) for j in factor(random.getrandbits(100))]) if i == '1' else getPrime(100)-1 for i in secret]

这一小问其实是在计算一个随机数字的欧拉函数，这个随机数字为：

1 : 完全随机的数字

0 : 100bit的素数

所以对于得到的结果，加一之后判断是不是100bit的素数就可以了。但有一点需要注意，即使flag当前bit是1也有可能随机到素数，但是概率并不大，并且由于flag有意义所以即使出现一点点误差也很容易修正。

exp：

from Crypto.Util.number import *

#part2
flag = ""
with open(r"/home/tiffany/Desktop/ctf/duomaomao/duomaomao1/here Ech0 is.txt","r") as f:
    c = eval(f.read())
for i in range(len(c)):
    p = c[i] + 1
    if(isPrime(p) and p.bit_length() == 100):
        flag += "0"
    else:
        flag += "1"
print(long_to_bytes(int(flag,2)))

#!Hope_y0u_can_h4ve_

1.3

题目：

#雪下得好大，花圃周围的亮白色身影是Z3r0吗
secret = bin(bytes_to_long(Z3r0_part))[2:]
p = getPrime(512)
look_for_Z3r0 = [pow(31137,65537,p*getPrime(512)) if i == '1' else pow(31137,65537,getPrime(512)*getPrime(512)) for i in secret]

这一小问是：

1 : $c_i = 31137^{65537} \quad(mod\;pa_i)$

0 : $c_i = 31137^{65537} \quad(mod\;b_ic_i)$

其中模数只有p是固定的，ai、bi、ci每次都会重新随机。

可以看出，对于三个为1的比特，密文在模p下是相同的。所以不妨假设我们现在有三个均为1的比特对应的密文，他们两两做差得到的值都会是p的倍数，所以gcd得到的值也至少应该是p。

所以就给出了一个实施的办法，假设我们拥有两个bit为1的位置(可以先随机选择，用结果来验证是否选择正确；也可以利用flag最后一个字符是}这一事实)，然后对剩余的每一bit，将其密文与这两bit的密文作差求gcd，如果得到的结果比较大则说明该bit为1，否则为0。

exp：

from Crypto.Util.number import *

#part3
flag = ""
with open(r"/home/tiffany/Desktop/ctf/duomaomao/duomaomao1/here Z3r0 is.txt","r") as f:
    c = eval(f.read())

temp1 = c[-1]
temp2 = c[-3]

for i in range(len(c)):
    if(GCD(c[i] - temp1 , c[i] - temp2) > 2^511):
        flag += "1"
    else:
        flag += "0"
print(long_to_bytes(int(flag,2)))

#fun_1n_CBCTF_Juni0r}

躲猫猫2

题目描述：

1
2
3

Humb1e，Ech0，Z3r0藏得都太草率了，显然没有把游戏放在心上。你语重心长地批评了他们一顿，踏上寻找其他人的旅途。

这下游戏就没有那么简单了。已经拿到一个新年大礼包的你能否再次创造奇迹呢？

题目：

import random
from Crypto.Util.number import *
from Crypto.Cipher import AES
import os
from secret import flag

gtg_part, beeee_part, Seg_Tree_part = flag[:len(flag)//3],flag[len(flag)//3:2*len(flag)//3],flag[2*len(flag)//3:]


#你惊异地发现，树丛里黑糊糊的枝叶居然有点神似gtg的辫子
secret = bin(bytes_to_long(gtg_part))[2:]

def matrix_crt(mp,mq,p,q):
    m = matrix(Zmod(p*q),[[crt([int(mp[i,j]),int(mq[i,j])],[p,q]) for i in range(2)] for j in range(2)])
    return m

p = getPrime(20)
a,b = MatrixGroup(matrix(GF(149),[[41,21],[82,81]])),MatrixGroup(matrix(GF(163),[[41,21],[82,81]]))
ma,mb = a.gens()[0],b.gens()[0]

look_for_gtg = [list(matrix_crt(matrix(ZZ,ma^random.randint(1,p)),matrix(ZZ,mb^random.randint(1,p)),149,163)) if i == '1' else list(matrix(Zmod(149*163),[[random.randint(1,149*163)for _ in range(2)] for __ in range(2)])) for i in secret]


#前两天刚考完研，图书馆难得清静，你在9楼搜寻，只见角落闪烁着微光。好像是beeee！
secret = bin(bytes_to_long(beeee_part))[2:]
m,p = getPrime(1023),getPrime(1024)

def ppallier(m,p):
    c = pow(p+1,getPrime(40)*m,p^2)*pow(random.randint(1,p^2-1),p,p^2)%p^2
    return c

look_for_beeee = [pow(ppallier(m,p),p-1,p^2) if i == '1' else random.randint(1,p^2-1) for i in secret]


#看上去有人卡视野藏在协会天台上。你走了过去，Seg_Tree正在假装自己是一颗树。
secret = bin(bytes_to_long(Seg_Tree_part))[2:]
look_for_Seg_Tree = [AES.new(key = os.urandom(16),mode = AES.MODE_CFB,iv = os.urandom(16)).decrypt((os.urandom(16)*3)[:33]) if i == '1' else AES.new(key = os.urandom(16),mode = AES.MODE_CFB,iv = os.urandom(16)).encrypt((os.urandom(16)*3)[:33]) for i in secret]


print(look_for_gtg)
print(look_for_beeee)
print(look_for_Seg_Tree)

2.1

题目：

#你惊异地发现，树丛里黑糊糊的枝叶居然有点神似gtg的辫子
secret = bin(bytes_to_long(gtg_part))[2:]

def matrix_crt(mp,mq,p,q):
    m = matrix(Zmod(p*q),[[crt([int(mp[i,j]),int(mq[i,j])],[p,q]) for i in range(2)] for j in range(2)])
    return m

p = getPrime(20)
a,b = MatrixGroup(matrix(GF(149),[[41,21],[82,81]])),MatrixGroup(matrix(GF(163),[[41,21],[82,81]]))
ma,mb = a.gens()[0],b.gens()[0]

look_for_gtg = [list(matrix_crt(matrix(ZZ,ma^random.randint(1,p)),matrix(ZZ,mb^random.randint(1,p)),149,163)) if i == '1' else list(matrix(Zmod(149*163),[[random.randint(1,149*163)for _ in range(2)] for __ in range(2)])) for i in secret]

这一小问基于一般线性群，先由两个特定矩阵ma、mb作为生成元，各自生成一个循环群，然后对于flag的每一bit，decision是如下形式：

1 : $crt(ma^{r_i} \;,\; mb^{s_i})$

0 : Zmod(149*163)下的完全随机矩阵

其中crt就是把矩阵的每个位置的元素对应crt起来，得到的新矩阵。

思路1

这里先说我之前的做法，由于躲猫猫1、2、3我都是上学期完成的，而当时对群的概念比较模糊，所以思路有点稚嫩。具体来说，既然矩阵成群，那么一定有群阶，直接计算a、b的order发现分别为：

1 2	print(a.order()) print(b.order())

1
2

148
4428

可以看到数字都不是很大，而由于ma、mb是两个群的生成元，所以其实crt起来的所有可能矩阵应该只有148x4428那么多个，而在Zmod(149x163)下的2x2矩阵则应该有$(149\cdot 163)^4$种，随机取到前面那些矩阵的概率相当小。所以可以直接通过判断矩阵是否在所有可能矩阵中，来判断当前bit是否为1。

然而这样做要提前将所有可能矩阵都算出来存在一个列表中，略显麻烦。

思路2

如果把两个群看作是子群，那么crt可以看作是两个群的组合，那么得到的新的群阶应该是两个群阶的最小公倍数，记作ord。所以一个简单的做法是，直接看当前矩阵的ord次方是否为单位阵，就可以判断当前bit是否为1了。

exp：

from Crypto.Util.number import *

#part1
flag = ""
with open(r"/home/tiffany/Desktop/ctf/duomaomao/duomaomao2/here gtg is.txt","r") as f:
    c = eval(f.read())

ord = LCM(148,4428)
E = Matrix(Zmod(149*163),[[1,0],[0,1]])
for i in range(len(c)):
    if(Matrix(Zmod(149*163),c[i]) ^ ord == E):
        flag += "1"
    else:
        flag += "0"
print(long_to_bytes(int(flag,2)))

#CBCTF{W1sh_Y0ur_N3xt_Y3

2.2

题目：

#前两天刚考完研，图书馆难得清静，你在9楼搜寻，只见角落闪烁着微光。好像是beeee！
secret = bin(bytes_to_long(beeee_part))[2:]
m,p = getPrime(1023),getPrime(1024)

def ppallier(m,p):
    c = pow(p+1,getPrime(40)*m,p^2)*pow(random.randint(1,p^2-1),p,p^2)%p^2
    return c

look_for_beeee = [pow(ppallier(m,p),p-1,p^2) if i == '1' else random.randint(1,p^2-1) for i in secret]

这一小问基于pallier，具体来说是：

1 : $c_i = ((p+1)^{a_im}b_i^p)^{p-1} \quad(mod\;p^2)$

0 : $c_i$ 为p^2内的随机数

可以注意到，由于$\phi(p^2) = p(p-1)$，所以其实bi是可以消掉的，也就得到：

$c_i = (p+1)^{a_im(p-1)} \quad(mod\;p^2)$

二项式展开可以看到：

$c_i = 1 + pa_im(p-1) \quad(mod\;p^2)$

所以其实也就是：

$c_i = 1 - pa_im \quad(mod\;p^2)$

所以在模p下所有密文都等于1，因此可以类似1.3的做法去作差求gcd得到结果。

exp：

from Crypto.Util.number import *

#part2
flag = ""
with open(r"/home/tiffany/Desktop/ctf/duomaomao/duomaomao2/here beeee is.txt","r") as f:
    c = eval(f.read())

temp1 = c[1]
temp2 = c[6]
for i in range(len(c)):
    if(GCD(c[i]-temp1 , c[i]-temp2) > 2^1023):
        flag += "1"
    else:
        flag += "0"

print(long_to_bytes(int(flag,2)))

#ar_fulf111ed_w1th_h4pp1

2.3

题目：

1
2
3

#看上去有人卡视野藏在协会天台上。你走了过去，Seg_Tree正在假装自己是一颗树。
secret = bin(bytes_to_long(Seg_Tree_part))[2:]
look_for_Seg_Tree = [AES.new(key = os.urandom(16),mode = AES.MODE_CFB,iv = os.urandom(16)).decrypt((os.urandom(16)*3)[:33]) if i == '1' else AES.new(key = os.urandom(16),mode = AES.MODE_CFB,iv = os.urandom(16)).encrypt((os.urandom(16)*3)[:33]) for i in secret]

这一小问基于AES的CFB模式，其中，key、iv均为随机的十六字节，处理的信息都是随机16字节重复三次，区别在于：

1 : 给出CFB模式解密的前33个字节

0 : 给出CFB模式加密的前33个字节

注意到33个字节恰好是两个分组多一个字节。先简单回忆一下CFB模式加解密的流程：

可以看出，对于解密来说，最后两个分组得到的明文应该是完全相同的，而对于加密则可以看作纯随机，只有1/256的概率误判，所以可以做出decision。

exp：

from Crypto.Util.number import *

#part3
flag = ""
with open(r"/home/tiffany/Desktop/ctf/duomaomao/duomaomao2/here Seg_Tree is.txt","r") as f:
    c = eval(f.read())

for i in range(len(c)):
    if(c[i][-1] == c[i][-17]):
        flag += "1"
    else:
        flag += "0"

print(long_to_bytes(int(flag,2)))

#ness_4nd_s4t1sfic4t10n!}

躲猫猫3

题目描述：

你花了点力气找到了gtg，beeee和Seg_Tree。手握两份新年礼包的你显然已经是整个协会中最富有的哥们儿，你一边畅想着未来的幸福生活和完美外设一边哼哧瘪肚在冬日里前行。

剩下的人都是难找的茬子啊……

不过你坚信这一切难不倒你。

题目：

import random
from Crypto.Util.number import *
from Crypto.Cipher import AES
import os
from secret import flag

Art0ne_part, 奶茶_part, _1manity_part = flag[:len(flag)//3],flag[len(flag)//3:2*len(flag)//3],flag[2*len(flag)//3:]

#Art0ne偷溜进体育馆，在走廊的一个拐角随时准备逃跑。你抓住他时自己已经要累得不行了。
secret = bin(bytes_to_long(Art0ne_part))[2:]

from secret import p,q
n = 7589728368000360290382663172234488251897043335410016881502715294598442607646158403453736522549655542481555536223060519309001243744487805230719883633463721
assert n == p * q and isPrime(p) and isPrime(q) and len(bin(p)) == 258 and len(bin(q)) == 258

R.<x> = PolynomialRing(Zmod(n))

def roll(mode,i):
    if mode == 0:
        return random.randint(1,p*q-1)
    else:
        x,y = random.randint(1,2^80),random.randint(1,2^256)*p
        return R(x+x*y^2+y*x^3)
    
look_for_Art0ne = [roll(1,i) if secret[i] == '1' else roll(0,i) for i in range(len(secret))]


#你找遍了学校，最后在弗雷德二店的古茗二楼意外找到了奶茶并宣判他犯规
secret = bytes_to_long(奶茶_part)

def shuffle(ll,lr):
    a = ['0']*len(奶茶_part)*ll+['1']*len(奶茶_part)*lr
    random.shuffle(a)
    return a

look_for_奶茶 = [int(''.join(shuffle(5,3)),2)^^secret if i == '1' else int(''.join(shuffle(3,5)),2)^^secret for i in bin(secret)[2:].rjust(8*len(奶茶_part),'0')]

#1manity藏在师生驿站，跨年夜店里没有值班，乌漆嘛黑的还带个笨蛋智能门锁，要不是你渴了进去买杯饮料还真的找不到他
secret = bin(bytes_to_long(_1manity_part))[2:]

p = 13692367685268431611
x = [matrix(GF(p),4,4,[random.randint(1,p-1) for i in range(16)]) for i in range(7)]

look_for_1manity = [list(sum(random.randint(1,p-1)*j for j in x)) if i == '1' else list(matrix(GF(p),4,4,[random.randint(1,p-1) for i in range(16)])) for i in secret]


print(look_for_Art0ne)
print(look_for_奶茶)
print(look_for_1manity)

3.1

题目：

#Art0ne偷溜进体育馆，在走廊的一个拐角随时准备逃跑。你抓住他时自己已经要累得不行了。
secret = bin(bytes_to_long(Art0ne_part))[2:]

from secret import p,q
n = 7589728368000360290382663172234488251897043335410016881502715294598442607646158403453736522549655542481555536223060519309001243744487805230719883633463721
assert n == p * q and isPrime(p) and isPrime(q) and len(bin(p)) == 258 and len(bin(q)) == 258

R.<x> = PolynomialRing(Zmod(n))

def roll(mode,i):
    if mode == 0:
        return random.randint(1,p*q-1)
    else:
        x,y = random.randint(1,2^80),random.randint(1,2^256)*p
        return R(x+x*y^2+y*x^3)
    
look_for_Art0ne = [roll(1,i) if secret[i] == '1' else roll(0,i) for i in range(len(secret))]

这个小问的decision是：

1 : $x_i + x_i(a_ip)^2 + a_ipx_i^3 \quad(mod\;n)$

0 : 模n下的随机数

可以看出在模p下，对于1的方程会有一个80bit的小根，所以copper会有解，而0则没有。

exp：

from Crypto.Util.number import *

n = 7589728368000360290382663172234488251897043335410016881502715294598442607646158403453736522549655542481555536223060519309001243744487805230719883633463721

#part1
flag = ""
with open(r"/home/tiffany/Desktop/ctf/duomaomao/duomaomao3/here Art0ne is.txt","r") as f:
    c = eval(f.read())

PR.<x> = PolynomialRing(Zmod(n))
for i in range(len(c)):
    f = x - c[i]
    res = f.small_roots(X=2^80,beta=0.49)
    if(res != []):
        flag += "1"
    else:
        flag += "0"

print(long_to_bytes(int(flag,2)))

#CBCTF{4nd_we_W1sh_y0u_Br1mm3

3.2

题目：

#你找遍了学校，最后在弗雷德二店的古茗二楼意外找到了奶茶并宣判他犯规
secret = bytes_to_long(奶茶_part)

def shuffle(ll,lr):
    a = ['0']*len(奶茶_part)*ll+['1']*len(奶茶_part)*lr
    random.shuffle(a)
    return a

look_for_奶茶 = [int(''.join(shuffle(5,3)),2)^^secret if i == '1' else int(''.join(shuffle(3,5)),2)^^secret for i in bin(secret)[2:].rjust(8*len(奶茶_part),'0')]

这个小问比较特别，除了decision之外，flag其实也藏在了每一个密文中，具体来说是：

1 : $c_i = secret \oplus a_i$，其中ai的0、1比例为5：3

2 : $c_i = secret \oplus b_i$，其中bi的0、1比例为3：5

首先想到的肯定是消去secret的影响，也就是flag两个bit的密文之间异或，那么可能会出现如下几种情况：

1的密文异或1的密文
0的密文异或0的密文
1的密文异或0的密文

由密文列表的长度可以推出secret为长232的比特串，那么对上面三种不同情况，可以简单算一算0、1数量期望的差别。

1的密文异或1的密文：此时这个量等于ai异或aj，异或后得到的比特串中，1的期望数量应该如下计算：

$232 \cdot (2 \cdot \frac{3}{8} \cdot \frac{5}{8}) = 108.75$

0的密文异或0的密文：此时这个量等于bi异或bj，异或后得到的比特串中，1的期望数量应该如下计算(和上面其实是一样的)：

$232 \cdot (2 \cdot \frac{3}{8} \cdot \frac{5}{8}) = 108.75$

1的密文异或0的密文：此时这个量等于ai异或bj，异或后得到的比特串中，1的期望数量应该如下计算：

$232 \cdot ((\frac{5}{8})^2 + (\frac{3}{8})^2) = 123.25$

所以如果选定了1个为0的bit，那么可以通过该bit的密文与当前bit的密文异或后1的数量来做一个粗略的decision。然后就会发现，由于每次异或的密文依然只有232bit，样本数量并不够，这个理论期望的差别并不能很好的做出准确的decision，误差很大。

然而，由于我们已知的为0的bit远远不止一个(因为所有字符都是可见字符所以MSB肯定都是0)，因此可以把多个统计结果求和取平均值，从而减小误差。这样做之后就基本上能得到一个可读的flag了，但是可以看出还是存在一些小误判：

1	d_ov3r_with_uisd0m_&_g3t_int

然而这个误判的处理方式就很多，首先在比赛期间可以多提交几次试试；再来就是，中间有一些字符肯定是不会错的，所以可以把这些已经判断正确的bit也加入到统计列表中去进一步减少误差。

exp：

from Crypto.Util.number import *

#part2
flag = ""
with open(r"/home/tiffany/Desktop/ctf/duomaomao/duomaomao3/here 奶茶 is.txt","r") as f:
    c = eval(f.read())

zero_bits = [c[8*i] for i in range(len(c)//8)]

for i in range(1,len(c)):
    count1 = 0
    res = 0
    for j in range(len(zero_bits)):
        res += bin(zero_bits[j] ^^ c[i])[2:].count("1")
    res /= (len(zero_bits))
    if(res > 116):
        flag += "1"
    else:
        flag += "0"

print(long_to_bytes(int(flag,2)))

#d_ov3r_with_wisd0m_&_g3t_int

3.3

题目：

#1manity藏在师生驿站，跨年夜店里没有值班，乌漆嘛黑的还带个笨蛋智能门锁，要不是你渴了进去买杯饮料还真的找不到他
secret = bin(bytes_to_long(_1manity_part))[2:]

p = 13692367685268431611
x = [matrix(GF(p),4,4,[random.randint(1,p-1) for i in range(16)]) for i in range(7)]

look_for_1manity = [list(sum(random.randint(1,p-1)*j for j in x)) if i == '1' else list(matrix(GF(p),4,4,[random.randint(1,p-1) for i in range(16)])) for i in secret]

这个小问先生成了一个由7个4x4矩阵组成的列表X，要做的decision是：

1 : $c_i = \sum_{j=1}^{7}a_jX_j$，其中aj是随机数

2 : ci为随机4x4矩阵

可以看出，4x4矩阵在这里其实完全可以看作是一个1x16的向量，而在当前bit为1时，得到的向量其实是这7个1x16的向量的线性组合。

把这七个向量看作一组基，这其实说明一个问题，如果我们选择8个为1的比特，由于基是相同的7个向量，所以他们拼起来形成的8x16的矩阵秩为7，反之秩大概率为8。

所以第一步要先找到七个为1的bit，由于这是本题目的最后一问，所以结尾的}就提供了六个，加上第一个bit正好就有7bit。利用这7个bit与剩余bit逐个判断组成矩阵秩是否为7，就可以判断对应bit是1还是0。

exp：

from Crypto.Util.number import *

#part3
flag = ""
with open(r"/home/tiffany/Desktop/ctf/duomaomao/duomaomao3/here 1manity is.txt","r") as f:
    c = eval(f.read())

p = 13692367685268431611
vecs = []
for i in range(len(c)):
    temp_vec = []
    for j in range(4):
        for k in range(4):
            temp_vec.append(c[i][j][k])
    vecs.append(vector(GF(p),temp_vec))

one_bits = [vecs[0],vecs[-1],vecs[-3],vecs[-4],vecs[-5],vecs[-6],vecs[-7]]
M = Matrix(GF(p),one_bits)

flag = ""
for i in range(len(c)):
    T = M.stack(vecs[i])
    if(T.rank() == 7):
        flag += "1"
    else:
        flag += "0"

print(long_to_bytes(int(flag,2)))

#3rest3d_in_fi3ld_you_w0rk_0n}

这一问有个小插曲，其实原本的题目中是：
1
look_for_1manity = [list(sum(random.randint(1,65537)*j for j in x)) if i == '1' else list(matrix(GF(p),4,4,[random.randint(1,p-1) for i in range(16)])) for i in secret]
也就是取1时，数字限制在了65537内。这个无心之失导致了一个用正交格的非预期解(我告诉yolbby时才知道他已经发现了)，有兴趣的师傅可以自己尝试一下。

当然，非预期的思路其实现在看来其实远不如预期简单巧妙

躲猫猫4

题目描述：

说来奇怪，在1manity，Art0ne和奶茶之后，你找遍了一整个学校都没能找到剩下的人，只能启动planB，使用你长期修炼凝结而成的密码解析技巧去把他们的参数调出来一一分析。

你以为你稳操胜券，但定睛一看，JBNRZ居然开了外挂卡在墙的里面！

他也把misc技巧带出了虚拟世界！

这个发现震惊了你的世界观，随着你打开每个人的视角偷看他们的位置，你的下巴不知不觉掉到了地上。

题目：

import random
from Crypto.Util.number import *
from Crypto.Cipher import AES
import os
from secret import flag

JBNRZ_part, pankas_part, v0id_part = flag[:len(flag)//3],flag[len(flag)//3:2*len(flag)//3],flag[2*len(flag)//3:]

#JBNRZ开了修改器把自己卡在七教二楼阳台的墙壁中间。你就算知道他在哪，也没法摸到他。
secret = bin(bytes_to_long(JBNRZ_part))[2:]

q = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
r = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001
k = GF(r)(q).multiplicative_order()
F = GF(q)
K2.<x> = PolynomialRing(F)
F2.<u> = F.extension(x^2+1)
E2 = EllipticCurve(F2, [0, 4+4*u])
o = E2.order()

P = E2.random_element()*(o//r)
Q = E2.random_element()*(o//r)
R = E2.random_element()*(o//r)
S = E2.random_element()*(o//r)

def random_gen_fg(P,Q,R,S):
    P,Q,R,S = random.randint(1,r-1)*P,random.randint(1,r-1)*Q,random.randint(1,r-1)*R,random.randint(1,r-1)*S
    f1 = (P._miller_(Q+S,r))
    f2 = (P._miller_(S,r))
    g1 = (Q._miller_(P+R,r))
    g2 = (Q._miller_(R,r))
    return P.weil_pairing(Q,r)+(f1/f2*g2/g1)

look_for_JBNRZ = [random_gen_fg(P,Q,R,S) if i == '1' else random.randint(1,q-1)*u+random.randint(1,q-1) for i in secret]


#pankas用注释符把自己注释掉了，你必须使用一些过滤手段停止他的作弊行为。
secret = bytes_to_long(pankas_part)

p = 567811
F = GF(p)
n, k, r= 16, 10, 6
t = n//4

C = codes.GeneralizedReedSolomonCode([F(_+1) for _ in range(n)],k)
S = matrix(F,r,r,[(155790, 486108, 98452, 364639, 120720, 313488), (100323, 367952, 158314, 537951, 1368, 437409), (24424, 3563, 165622, 226117, 268381, 281060), (306717, 437800, 498491, 454109, 45791, 427166), (440079, 197166, 514113, 24595, 172079, 106605), (529695, 239369, 361569, 565415, 72455, 244407)])
H_ = S*C.parity_check_matrix()*matrix(Permutations(n).random_element())

s = [sorted(random.sample([_ for _ in range(n)],t-1)) for i in range(len(secret))]
look_for_pankas = [H_*vector([random.randint(1,32) if j in s[i] else 0 for j in range(n)]) if secret[i] == '1' else vector([random.randint(1,p-1) for j in range(6)]) for i in range(len(secret))]


#v0id通过某些方法修改了自己的人体结构，看上去需要经历一些反混淆反编译才能重现世间。
secret = bin(bytes_to_long(v0id_part))[2:]

F = GF(2 ** 256, 'z')
z = F.gens()[0]
P = PolynomialRing(F, 'u, v')
u, v = P.gens()
PP.<x> = PolynomialRing(F)
x = PP.gens()[0]

h = u^2 + u
f = u^5 + u^3 + 1
on_curve = v^2 + h*v - f
h,f = h(u=x),f(u=x)

H = HyperellipticCurve(f, h)
J = H.jacobian()

def init():
    while 1:
        try:
            plain = random.randint(1,2^256)
            xx = F.fetch_int(plain)
            y, k = on_curve(u=xx, v=x).roots()[0]
            assert k == 1
            return - xx, y
        except:
            continue

look_for_v0id = [(3*J(H(init())))[0] if i == '1' else random.choice([(7*J(H(init())))[0],x^2+F.fetch_int(random.randint(1,2^256))*x+F.fetch_int(random.randint(1,2^256))]) for i in secret]

print(look_for_JBNRZ)
print(look_for_pankas)
print(look_for_v0id)

重量级的来了，在躲猫猫4里你会接触到：

椭圆曲线的除子理论及双线性配对
编码理论(Niederreiter system以及选作其中纠错码的Generalized Reed-Solomon code)
超椭圆曲线上的Jacobian群

上学期看到这一套躲猫猫题目的时候，在前三个题目虽然说也遇到了不少挫折，但是努努力多思考下还是能够做出来。然而看到躲猫猫4的几个小问的时候，才发自内心的觉得自己了解的知识真的还非常有限，然后就下了决心去啃啃论文，把每个方向都了解一些，哪怕只学到一点皮毛也好。

于是就真的硬着头皮看了好些文献，同源、编码、超椭之类的东西都去学了一点点，前几天看完了yolbby给我的双线性配对书的主要章节，终于可以回头来尝试这个题目了。

然后就发现，虽然现在大概能看明白题意，解题的思路还是很匮乏，并且实际实现自己的想法的时候也会遇到诸多问题。道阻且长，继续努力吧。

4.1

题目：

#JBNRZ开了修改器把自己卡在七教二楼阳台的墙壁中间。你就算知道他在哪，也没法摸到他。
secret = bin(bytes_to_long(JBNRZ_part))[2:]

q = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
r = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001
k = GF(r)(q).multiplicative_order()
F = GF(q)
K2.<x> = PolynomialRing(F)
F2.<u> = F.extension(x^2+1)
E2 = EllipticCurve(F2, [0, 4+4*u])
o = E2.order()

P = E2.random_element()*(o//r)
Q = E2.random_element()*(o//r)
R = E2.random_element()*(o//r)
S = E2.random_element()*(o//r)

def random_gen_fg(P,Q,R,S):
    P,Q,R,S = random.randint(1,r-1)*P,random.randint(1,r-1)*Q,random.randint(1,r-1)*R,random.randint(1,r-1)*S
    f1 = (P._miller_(Q+S,r))
    f2 = (P._miller_(S,r))
    g1 = (Q._miller_(P+R,r))
    g2 = (Q._miller_(R,r))
    return P.weil_pairing(Q,r)+(f1/f2*g2/g1)

look_for_JBNRZ = [random_gen_fg(P,Q,R,S) if i == '1' else random.randint(1,q-1)*u+random.randint(1,q-1) for i in secret]

这一小问目前有点小问题，曲线是BLS12-381，但是由于对于指定的r-torsion曲线嵌入度为12，所以在$GF(q^2)$上的曲线E2是并不能有效作双线性配对，因为r-torsion需要在$GF(q^{12})$下才会展现出完整的结构，所以不lift上去是不行的。

等yolbby把这个题目改一改之后再更新吧。

4.2

题目：

#pankas用注释符把自己注释掉了，你必须使用一些过滤手段停止他的作弊行为。
secret = bytes_to_long(pankas_part)

p = 567811
F = GF(p)
n, k, r= 16, 10, 6
t = n//4

C = codes.GeneralizedReedSolomonCode([F(_+1) for _ in range(n)],k)
S = matrix(F,r,r,[(155790, 486108, 98452, 364639, 120720, 313488), (100323, 367952, 158314, 537951, 1368, 437409), (24424, 3563, 165622, 226117, 268381, 281060), (306717, 437800, 498491, 454109, 45791, 427166), (440079, 197166, 514113, 24595, 172079, 106605), (529695, 239369, 361569, 565415, 72455, 244407)])
H_ = S*C.parity_check_matrix()*matrix(Permutations(n).random_element())

s = [sorted(random.sample([_ for _ in range(n)],t-1)) for i in range(len(secret))]
look_for_pankas = [H_*vector([random.randint(1,32) if j in s[i] else 0 for j in range(n)]) if secret[i] == '1' else vector([random.randint(1,p-1) for j in range(6)]) for i in range(len(secret))]

这个小问基于一个GF(p)下(16,10)-GRS码实现的编码系统，给的数据不少所以要先理一理。

GRS是一种线性分组码，这里要先简单介绍一下广泛意义上的(n,k)-线性分组码的概念(真的是极简版的介绍，有空的话之后会单独开一篇文章来说)。

纠错码主要基于以下理念：在传播消息时，由于各种可能的因素，有时难免会产生部分的传输错误，那么接收方就只能收到带有错误的消息。然而，如果将一些能够反映消息本身部分内容的冗余信息附加在传输消息中，那么就可以辅助解码从而得到准确的原始消息。

线性分组码就是其中的一种，一个(n,k)-线性分组码是一个消息长为k、码字长为n的纠错码。

而GRS码又是线性分组码的一种。拿题目的(16,10)-GRS码来举例，在这种编码中，原始信息位长度是10，码字长度为16，也就是说一个信息和一个码字分别可以看作是GF(p)下的10维向量和16维向量，而多出的r=16-10就是冗余位的长度。

线性分组码本质上是高维空间的一个子空间。因为一个码字本身是n维向量，然而由于消息是k维向量，一个消息对应一个码字，所以码字空间其实是n维线性空间的k维子空间。

那么也就是说，对于一个消息的编码过程，实质上可以看作是k维向量向n维向量的线性映射，这个映射过程就可以用一个矩阵表示，也就是生成矩阵G，与之对应的就有校验矩阵H。

对于这两个矩阵、如何对带有错误的码字进行准确解码、纠错能力等问题在这里就不展开了，有兴趣的师傅可以自己查阅了解，这里只阐述了点基本概念而已。

这里先继续用编码理论的思路来讲预期做法。

思路1

总之，题目先生成了一个(16,10)-GRS码，他的校验矩阵相当于已经给出了，与此同时还给出了一个奇怪6x6的S矩阵，然后计算了一个H’矩阵如下：

$H'_{6,16} = S_{6,6}H_{6,16}P_{16,16}$

其中S可逆，P是一个1-16的随机置换形成的矩阵。

然后，题目对flag的每一bit都生成了一个随机sample，每个sample是在1-16中随机抽取三个数字。我们要做的decision是：

1 : $H’v_i$，vi是仅有3个位置不为0的16维随机向量

0 : 随机的6维向量

对于为1的bit，其实这就是Niederreiter system的实现。Niederreiter system是一种基于编码的密码的后量子密码体制，他的实现步骤为：

选取一个可以纠t个错的线性分组码C当作纠错码，这里选取的是(16,10)-GRS码
计算$H’ = SHP$，然后得到公钥和私钥分别为：

$Pub : (H',t)$ $Pri : (S,H,P)$

加密：待加密消息为至多t个位置非0的n维向量，按如下方式计算密文：

$y^T = H'x^T$

解密：对于密文$y^T$，私钥持有者可以计算：

$S^{-1}y^T = S^{-1}H'x^T$ $\rightarrow S^{-1}H'x^T = S^{-1}(SHP)x^T = H(Px^T) = H(xP^T)^T$

由于P是置换矩阵，所以乘P^T的操作不会改变x中非零项的数量，也就是说$xp^T$依然仅有至多t个位置非0。所以对这个消息调用syndrome decode就可以得到xP^T，然后再求逆就有原始消息x了。

syndrome decode指的是伴随式解码，一个伴随式就是校验矩阵H右乘码字。

在这里，由于$xP^T$显然也是码字，所以左乘S逆矩阵得到的就是伴随式，所以可以调syndrome解码。

而由于这题本身初始化GRS码时就固定了校验矩阵H，并且还给出了私钥里的可逆矩阵S，而我们并不关心置换矩阵P，因为只要解出的码符合3个位置非0——也就是成功解码就代表着flag当前bit为1，反之为0，就可以逐bit判断了。

然而，syndrome decode的基本原理是将伴随式与错误向量做对应，这在消息和错误均为二进制编码很有效，但是我怎么找都找不到GF(p)下的syndrome解码实现原理，调sage本身的api也很慢很慢，最后还是用yolbby的独家板子才得以解决。

exp：

from Crypto.Util.number import *
from sage.modular.overconvergent.hecke_series import ech_form
from sage.coding.decoder import Decoder, DecodingError
from sage.coding.grs_code import GeneralizedReedSolomonCode

class Syndrome_decode(Decoder):
    def __init__(self, code):
        super(Syndrome_decode, self).__init__(code, code.ambient_space(),
                "EvaluationVector")

    def _repr_(self):
        return "Key equation decoder for %s" % self.code()

    def _partial_xgcd(self, a, b, PolRing):
        prev_t = PolRing.zero()
        t = PolRing.one()

        prev_r = a
        r = b

        while(r.degree() >= t.degree()):
            q = prev_r.quo_rem(r)[0]
            prev_r, r = r, prev_r - q * r
            prev_t, t = t, prev_t - q * t

        return (r, t)
    
    def _forney_formula(self, error_evaluator, error_locator):
        C = self.code()
        alphas = C.evaluation_points()
        col_mults = C.parity_column_multipliers()
        ELPp = error_locator.derivative()
        F = C.base_ring()
        zero, one = F.zero(), F.one()
        e = []

        for i in range(C.length()):
            alpha_inv = one/alphas[i]
            if error_locator(alpha_inv) == zero:
                e.append(-alphas[i]/col_mults[i] * error_evaluator(alpha_inv)/ELPp(alpha_inv))
            else:
                e.append(zero)

        return vector(F, e)

    def decode(self,S):
        C = self.code()

        PolRing = C.base_field()['x']
        x = PolRing.gen()
        
        S = PolRing([i for i in S])

        a = x ** (C.minimum_distance() - 1)

        (EEP, ELP) = self._partial_xgcd(a, S, PolRing)

        e = self._forney_formula(EEP, ELP)
        return e

p = 567811
F = GF(p)
n, k, r= 16, 10, 6
t = n//4

C = codes.GeneralizedReedSolomonCode([F(_+1) for _ in range(n)],k)
S = matrix(F,r,r,[(155790, 486108, 98452, 364639, 120720, 313488), (100323, 367952, 158314, 537951, 1368, 437409), (24424, 3563, 165622, 226117, 268381, 281060), (306717, 437800, 498491, 454109, 45791, 427166), (440079, 197166, 514113, 24595, 172079, 106605), (529695, 239369, 361569, 565415, 72455, 244407)])


#part2
H = C.parity_check_matrix()
D = Syndrome_decode(C)
flag = ""
with open(r"/home/tiffany/Desktop/ctf/duomaomao/duomaomao4/here pankas is.txt","r") as f:
    c = eval(f.read())

for i in range(len(c)):
    res = D.decode(S^(-1)*vector(F,c[i]))
    if(not all(j == 0 for j in res)):
        flag += "1"
    else:
        flag += "0"

print(long_to_bytes(int(flag,2)))

#in_study_tr4v3l_4nd_a_bR1ght_fut

思路2

然而，通读完题目内容其实有一个地方非常显眼，那就是flag当前bit为1时，取的vi不仅仅只有3个位置非0这一特点，一个更重要的地方在于每个位置都是1-32的相对于p很小的小量，这就给用格求解提供了机会。

其实一个很有意思的点在于，在了解了纠错码和格密码之后，我发现他们其实有相似的目的，都是消除传输过程中的一些噪声。如果把传输的信息看作GF(p)下的一个向量的话，那么他们的区别在于：

纠错码的错误，是该向量的少数位置发生错误，但是错误值可以很大

格的噪声，噪声值比较小，但是每个位置都可以产生噪声

所以1-32这个范围的不当选取就使得这个码字同时满足了格密码纠错和纠错码纠错的要求。这里就用格密码来尝试纠错，回顾一下当flag当前bit为1时密文为：

$c_i = H'v_i = (SHP)v_i$

P仅仅是个置换，不会影响vi中元素的大小，我们也不需要关心这个置换究竟是什么，只需要知道vi做了置换后依然是个短向量，不妨记作ai，那么就有：

$c_i = SHa_i$

也就是：

$a_i^T (H^TS^T) = c_i^T$

而S、H都是知道的，所以对上面的式子简单进行格规约，就可以发现bit为1的密文ci，规约出的向量会从某一行开始与完全随机的ci有显著的数量级差异，就可以依据这个做出判断了。

exp：

from Crypto.Util.number import *

p = 567811
F = GF(p)
n, k, r= 16, 10, 6
t = n//4

C = codes.GeneralizedReedSolomonCode([F(_+1) for _ in range(n)],k)
S = matrix(F,r,r,[(155790, 486108, 98452, 364639, 120720, 313488), (100323, 367952, 158314, 537951, 1368, 437409), (24424, 3563, 165622, 226117, 268381, 281060), (306717, 437800, 498491, 454109, 45791, 427166), (440079, 197166, 514113, 24595, 172079, 106605), (529695, 239369, 361569, 565415, 72455, 244407)])


#part2
H = C.parity_check_matrix()
flag = ""
with open(r"/home/tiffany/Desktop/ctf/duomaomao/duomaomao4/here pankas is.txt","r") as f:
    c = eval(f.read())

for i in range(len(c)):
    M = Matrix(ZZ,(H.T*S.T).stack(-vector(F,c[i])))
    L = block_matrix([
        [identity_matrix(n+1),M],
        [matrix.zero(r,n+1),identity_matrix(r)*p]])
    L[:,-r:] *= p
    
    res = L.LLL()
    if(all(abs(j) < 32 for j in res[10])):
        flag += "1"
    else:
        flag += "0"


print(long_to_bytes(int(flag,2)))

#in_study_tr4v3l_4nd_a_bR1ght_fut

4.3

题目：

#v0id通过某些方法修改了自己的人体结构，看上去需要经历一些反混淆反编译才能重现世间。
secret = bin(bytes_to_long(v0id_part))[2:]

F = GF(2 ** 256, 'z')
z = F.gens()[0]
P = PolynomialRing(F, 'u, v')
u, v = P.gens()
PP.<x> = PolynomialRing(F)
x = PP.gens()[0]

h = u^2 + u
f = u^5 + u^3 + 1
on_curve = v^2 + h*v - f
h,f = h(u=x),f(u=x)

H = HyperellipticCurve(f, h)
J = H.jacobian()

def init():
    while 1:
        try:
            plain = random.randint(1,2^256)
            xx = F.fetch_int(plain)
            y, k = on_curve(u=xx, v=x).roots()[0]
            assert k == 1
            return - xx, y
        except:
            continue

look_for_v0id = [(3*J(H(init())))[0] if i == '1' else random.choice([(7*J(H(init())))[0],x^2+F.fetch_int(random.randint(1,2^256))*x+F.fetch_int(random.randint(1,2^256))]) for i in secret]

这个小问基于一条亏格为2的GF(2^256)下的的超椭圆曲线。

这里还是简单介绍一下超椭圆曲线的几个基本概念。

1、曲线方程：
$y^2 + h(x)y - f(x) = 0$
其中$h(x),f(x)$都是系数在域K下的多项式。

2、亏格：

这个概念比较复杂，他其实本质上代表着曲线上所有除子对应的度最小的等价有效除子的最大值。但是反映在曲线方程中其实就是：
$deg(h(x)) \leq g$ $deg(f(x)) = 2g + 1$
3、除子群

对于普通的椭圆曲线，他的群结构似乎很显然，因为可以直接用点来定义运算，但实质上，这是ECC上除子群恰好可以和点群作同构导致的，它的本质仍然是除子群(左边是点群的元素，右边是除子群的元素)：
$P \leftrightarrow (P) - (O)$
在超椭中，直观的点群结构不再存在了，因此为了利用曲线上的群结构来构造密码体制，必须使用有理函数和除子来定义除子群，而Jacobian群其实就是解决了除子运算问题的除子群。

4、Jacobian群的元素

Jacobian群的元素是一个多项式二元组$[u(x),v(x)]$，满足以下几点性质：

$u(x)$为首一多项式

$u(x) \; | \; v^2(x) + h(x)v(x) - f(x)$

$deg(v(x)) < deg(u(x)) < g$

了解了基本概念后，再来看看这个题目的decision需要我们做什么。由于J(H(init()))其实是生成该超椭圆曲线上Jacobian群的一个随机元素，不妨记为Di，那么对于flag的每一bit有：

1 : $c_i = 3D_i的u(x)$

0 : $c_i = 7D_i的u(x)$，或度为1的随机多项式

如果之前有做过NKCTF的fly to the hyper一题大概可以想到这个3、7应该是和Jacobian的元素阶判断有关的，这就需要先求出群阶。而题目中又只给了Jacobian群元素的u(x)，所以其实还需要从u(x)恢复v(x)，从而得到完整的群元素才行。所以一共需要做三件事：

求出Jacobian的群阶
对每个元素由u(x)恢复v(x)
判断元素阶从而做出decision

接下来就三个部分分开阐述。

求Jacobian的群阶

这个考点出现过不少次了，最近一点的可以直接看NKCTF fly to the hyper的官方wp，这里直接给出solver。

from Crypto.Util.number import *

#calc order
def Hyper_Jacobian_order(n,q=2):
    F = GF(q)
    PP.<u> = PolynomialRing(F)
    h = u^2 + u
    f = u^5 + u^3 + 1
    H = HyperellipticCurve(f, h)

    #calc M1,M2
    M1,M2 = H.count_points_exhaustive(2)

    #calc a1,a2
    a1 = M1 - 1 - q
    a2 = (M2 - 1 - q^2 + a1^2) // 2
    
    #calc y1,y2
    X = var('X')
    y1,y2 = solve([X^2 + a1*X + (a2 - 2 * 2) == 0], X)
    y1,y2 = y1.rhs(),y2.rhs()
    
    #calc alpha1,alpha2
    alpha1 = solve([X^2 - y1*X + q == 0], X)[0].rhs()
    alpha2 = solve([X^2 - y2*X + q == 0], X)[0].rhs()

    #calc Nn
    Nn = int(abs(1-alpha1^n)^2*abs(1-alpha2^n)^2)
    
    return Nn

n = 256
order = Hyper_Jacobian_order(n)

print(order)

得到的阶为：

1	13407807929942597099574024998205846127384782207827457971403006387925941306569427075743805985793764139096494648696821820448189053384542053304334065342873600

由u(x)恢复v(x)

这一部分其实也有出现过，其具体求解的思路是：

由于有$u(x) \; | \; v^2(x) + h(x)v(x) - f(x)$，所以对ux的根xi，会有：

$v^2(x_i) + h(x_i)v(x_i) - f(x_i) = 0$

由于hx、fx已知，所以代入xi后，上述方程其实是关于v(xi)这个数值的二次方程，所以可以求这个二次方程的根得到v(xi)的值
此时，又因为有$deg(v(x)) < deg(u(x)) < g$，所以ux的根的数量会大于vx的度，所以有足够的点对进行拉格朗日插值，从而恢复完整的vx

需要注意的问题是，求根的过程并不是在GF(2^256)上进行的，而应该在GF(2)的代数闭包去求根，才能得到所有根

一个简单的求解示例如下：

import random

deg = 256
F = GF(2 ** deg)
z = F.gens()[0]
P = PolynomialRing(F, 'u, v')
u, v = P.gens()
PP.<x> = PolynomialRing(F)
x = PP.gens()[0]

h = u^2 + u
f = u^5 + u^3 + 1
on_curve = v^2 + h*v - f
h,f = h(u=x),f(u=x)

H = HyperellipticCurve(f, h)
J = H.jacobian()

def init():
    while 1:
        try:
            plain = random.randint(1,2^deg)
            xx = F.from_integer(plain)
            y, k = on_curve(u=xx, v=x).roots()[0]
            assert k == 1
            return - xx, y
        except:
            continue


L = GF(2).algebraic_closure()
u = (3*J(H(init())))[0]
x1,x2 = [r for r in u.change_ring(L).roots(multiplicities=False)]

a = f(x1)
b = h(x1)
F = a - x*b - x^2
v11,v12 = F.roots(multiplicities=False)

a = f(x2)
b = h(x2)
F = a - x*b - x^2
v21,v22 = F.roots(multiplicities=False)

PR.<x> = PolynomialRing(L)
v = [
    PR.lagrange_polynomial([(x1,v11),(x2,v21)]),
    PR.lagrange_polynomial([(x1,v12),(x2,v21)]),
    PR.lagrange_polynomial([(x1,v11),(x2,v22)]),
    PR.lagrange_polynomial([(x1,v12),(x2,v22)])
]
for i in v:
    print(J(u,i))

这里就会出现问题，由于GF(2^256)扩张次数有点大，所以有时候求根会很慢很慢，有的求根可能就几秒钟，有的十分钟也求不完，我的求解过程也就卡在这一步了，先继续往下。

不过，特征为2的扩域应该有快速求根的方式，只是我实在没找到sage的实现，也没有找到对于快速求根原理的介绍，更别说自己想出来怎么求根了

判断元素阶

factor一下第一步计算得到的阶：

1	2^18 * 3^2 * 5^2 * 17^4 * 113^2 * 137^2 * 769^2 * 9601^2 * 138113^2 * 5649473^2 * 170045569^2 * 2147442977^2 * 1601948502115309903982784222721^2

可以发现阶中有3这个因子而没有7这个因子，所以可以通过检查阶的方式作decision，具体实现如下：

from Crypto.Util.number import *
import random

F = GF(2 ** 256, 'z')
z = F.gens()[0]
P = PolynomialRing(F, 'u, v')
u, v = P.gens()
PP.<x> = PolynomialRing(F)
x = PP.gens()[0]

h = u^2 + u
f = u^5 + u^3 + 1
on_curve = v^2 + h*v - f
h,f = h(u=x),f(u=x)

H = HyperellipticCurve(f, h)
J = H.jacobian()

def init():
    while 1:
        try:
            plain = random.randint(1,2^256)
            xx = F.from_integer(plain)
            y, k = on_curve(u=xx, v=x).roots()[0]
            assert k == 1
            return - xx, y
        except:
            continue

order = 13407807929942597099574024998205846127384782207827457971403006387925941306569427075743805985793764139096494648696821820448189053384542053304334065342873600

A = 3*J(H(init()))
B = 7*J(H(init()))

print(order // 3^2 * A)
print(order // 3^2 * B)

结果为：

1
2

(1)
(x^2 + x + 1, y + (z^128 + z^64 + z^32 + z^16 + z^8 + z^5 + z^4 + z^2 + 1)*x + z^255 + z^254 + z^253 + z^252 + z^248 + z^245 + z^242 + z^239 + z^238 + z^236 + z^234 + z^233 + z^230 + z^227 + z^225 + z^224 + z^222 + z^221 + z^220 + z^217 + z^215 + z^214 + z^210 + z^209 + z^204 + z^203 + z^202 + z^200 + z^199 + z^197 + z^196 + z^194 + z^193 + z^192 + z^191 + z^190 + z^189 + z^188 + z^183 + z^182 + z^180 + z^179 + z^177 + z^170 + z^169 + z^168 + z^167 + z^160 + z^158 + z^157 + z^156 + z^155 + z^153 + z^152 + z^149 + z^148 + z^147 + z^143 + z^141 + z^137 + z^136 + z^135 + z^133 + z^132 + z^131 + z^129 + z^127 + z^126 + z^125 + z^122 + z^120 + z^116 + z^115 + z^114 + z^113 + z^110 + z^109 + z^108 + z^107 + z^104 + z^103 + z^102 + z^98 + z^89 + z^88 + z^87 + z^85 + z^84 + z^83 + z^78 + z^74 + z^69 + z^68 + z^65 + z^64 + z^63 + z^61 + z^60 + z^59 + z^58 + z^55 + z^54 + z^53 + z^52 + z^50 + z^47 + z^46 + z^45 + z^43 + z^42 + z^35 + z^31 + z^26 + z^23 + z^22 + z^21 + z^20 + z^19 + z^18 + z^15 + z^13 + z^12 + z^11 + z^10 + z^9 + z^8 + z^5 + z^4 + z^2 + z + 1)

完整总结

然而由于第二步中快速求根我不太会实现，所以还没完全解出来，解出来之后再更新吧。

总结

总的来说这一系列题目真的丰富又有趣，听yolbby说他在招新赛上早早就放了这四个题目出来，直到比赛结束也只有躲猫猫1有一个解，在我完整浏览完所有题目所有小问过后，我觉得这不是没有原因(坏人(๑¯ω¯๑))。

但是呢，做完这些题目也是真的接触到了很多很多新奇的东西，这样一想又很符合招新赛的初衷了。

也欢迎大家看他的官方题解，部分题目的思路和我并不一样：

https://yolbby.github.io/